Hacker News new | ask | show | jobs
by cmrx64 3740 days ago
Depends on the implementation. Some algorithms[1] have a load factor no more than 0.80 before insert/lookup performance starts to degrade significantly. Others, like the algorithm used in Rust[2], can achieve load factors in excess of 0.98 without breaking a sweat.

[1] http://netjs.blogspot.com.au/2015/05/how-hashmap-internally-...

[2] - http://codecapsule.com/2013/11/17/robin-hood-hashing-backwar...

1 comments

That's why I said "good hash table". Even a simple open-addressing hash table with quadratic probing can easily go to load factor 0.8 with reasonable performance. With cuckoo-hashing you can get much higher and still guarantee worst-case constant-time lookups and amortized constant-time insertions.