Checking whether `HashMap::insert` would reallocate

help
#1

For a custom data structure I'm implementing, I'd like to be able to use something like the following interface for a hashbrown::HashMap (equivalently std::collections::HashMap):

// returns the value of `map.insert(key, val)` (wrapped in `Ok`)
//   if this call would not cause `map` to reallocate
// if reallocation would occur, returns `Err(())`
fn try_insert(map: &mut HashMap<K, V, S>, key: K, val: V) -> Result<Option<V>, ()> {
    unimplemented!()
}

I thought of comparing map.len() to map.capacity(), but the documentation says that map.capacity() is "only a lower bound", so this would be inexact; is there a way to achieve it in a precise way? (Also if someone feels like explaining why the capacity is not exact I'd be interested in reading that -- otherwise I can dig into the Swiss Tables documentation I guess.) I'm willing to use the RawTable interface if necessary.

(Why do I want this? Because I want to do some other stuff to my HashMap-containing data structure every time reallocation needs to occur, including removing some elements for storage elsewhere.)

1 Like
#2

AFAIK in hashbrown a "slot" in the map can have 3 different states:

  • FULL, meaning this already contains an item, so replacing it doesn't change length nor capacity
  • EMPTY, meaning this doesn't contain an item and inserting here reduces the growth left (in practice the length increases but capacity remains the same)
  • DELETED, this is the strange one. It doesn't contain an item but inserting a new item here doesn't reduce the growth left (in practice it increases both the length and the capacity)

The case when the map has to reallocate is when the growth left is 0 (i.e. the length and the capacity are the same) and inserting will fill an EMPTY slot. However unfortunately hashbrown doesn't offer a way to check if inserting an item will fill an EMPTY or a DELETED slot.

IMO your best bet would be requesting to add a try_insert_no_grow or something like that to RawTable and maybe also hashbrown::HashMap.

1 Like
#3

From what you say, it also sounds like you could (probably?) trust the capacity as long as you aren't deleting items. So if that's good enough for you, and you want to make that a type-supported guarantee, you could write a wrapper around HashMap that doesn't implement any operations that would remove entries.

#4

Thanks -- I do want to support deletion so this is probably out, but I appreciate the suggestion.

#5

Thanks, makes sense! I'll check the hashbrown repo for prior art and maybe open a feature request.

Edit: Feature request: insertion that bails if reallocation would occur · Issue #224 · rust-lang/hashbrown · GitHub

#6

The RawTable impl didn't seem too difficult so I opened a PR:

Edit: Hey, this got merged!

4 Likes
#7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.