Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It's not discussed in the article but there is also coalesced hashing [1] which is a hybrid of separate chaining and open addressing. Coalesced hashing makes the best use of space as you can fill a table to capacity before resizing. Speed wise, it provides consistent performance for all operations (insert, search, delete) rather than being optimized for only one or some of them.

Another topic the article doesn't touch on is the difference between dense and sparse hashmaps. The former stores values and keys together but the latter stores values in separate array(s) which is more cache friendly when probing keys.

[1] https://en.wikipedia.org/wiki/Coalesced_hashing



Coalesced hashing is just worse than robin hood tables.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: