Do not grow the raw table when lots of deletion and insertion is performed

[YjyJeff]

In some cases, we know the capacity of the hash table, for example, we want to store the fixed number of elements in the cache. Therefore, we allocate the hash table with with_capacity(CAP) method. When the cache is full, we need to delete the entry and insert the new entry into it. In ideal, the hash table should never grow.

However, the hash table grows... We can try the following code to verify it, the code will panic at try_insert_no_grow

use std::hash::BuildHasher;

use hashbrown::hash_map::DefaultHashBuilder;
use hashbrown::raw::RawTable;
use rand::Rng;

const CAP: usize = 10;

fn main() {
    let mut table = RawTable::<u64>::with_capacity(CAP);
    let hash_builder = DefaultHashBuilder::default();
    let mut prev = 0;
    let mut rng = rand::thread_rng();
    loop {
        let val = rng.gen::<u64>();
        let hash = hash_builder.hash_one(val);
        if table.find(hash, |&probe| probe == val).is_none() {
            if table.len() == CAP {
                table.remove_entry(hash, |&probe| probe == prev);
            }
            table.try_insert_no_grow(hash, val).unwrap();
        }
        prev = val;
    }
}

The reason why it happens is that: the erase function does not increase the growth_left. Can we accomplish the above case without growing?

Thanks in advance

[Amanieu]

Note that due to the logic here, this growth will only happen once. After that it will always perform an in-place rehash which will not allocate.

[YjyJeff]

Note that due to the logic here, this growth will only happen once. After that it will always perform an in-place rehash which will not allocate.

I got the same conclusion after reading the code. So, the design of the hashbrown caused that we can not avoid the in-place rehashing, right?

[Amanieu]

If you reserve space for CAP * 2 then it should never grow.