Is it possible to build a lazy ScopedHashMap on top of this crate? about hashbrown HOT 4 CLOSED

The API of this crate is identical to the one for the libstd HashMap. So no, it probably isn't possible to implement your idea on top of hashbrown.

I'm not even sure if lazy deletion would even be a performance improvement: it means that you have to scan all elements on insert, which is incompatible with SwissTable's SIMD lookup algorithm.

from hashbrown.

Gotcha'. I'm not sure what you mean by "scan all elements" though... You can only scan the ones which are possible candidates for insertion. If the first slot you inspect (for insertion) is empty, then you just insert the pair in there, no deletions involved, even though you might have outdated key-value pairs lying around.

from hashbrown.

What I mean is that hashbrown doesn't even look at the elements when searching for a slot for insertion, it only looks at the hashes until it finds a matching hash or an empty slot. SIMD allows scanning 16 hashes in a single instruction, which is the main reason why hashbrown is faster than the standard library. Changing this scan to additionally check scopes and outdated generations would greatly increase complexity and slow insertions down significantly.

from hashbrown.

Oh, I see. Thanks for the explanation and (super) speedy response. Also, thanks for writing this crate 😄.

from hashbrown.