5 ms·
Note that the maximum fill factor of hashtables can be increased well above 90% with comparable or better performance to standard open addressing using Robin Ho
by eutectic 11y ago
Note that the maximum fill factor of hashtables can be increased well above 90% with comparable or better performance to standard open addressing using Robin Hood collision resolution with backwards shift deletion. The hashtable in the Rust standard library works like this and there is an argument to be made that it should become standard.
Of course, this doesn't do away with the need to resize, so it might not be appropriate for low latency or memory constrained systems. I wonder whether a tree-based data structure like a crit-bit tree or a HAMT might be able to do similar things to sparsehash with better performance.
- Kiro 11y agoThis may be a strange and off-topic question but may I ask what you do for a living?
- eutectic 11y agoI'm a student of Physics and Mathematics who takes an amateur interest in programming. :)
- detrino 11y agoMy understanding is that Robin Hood hashing has worse performance than linear probing due to greater cache misses. If you are looking for low memory overhead ordered sets/maps, then B-Trees can provide that.