4 ms·
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,
by cmrx64 11y 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-works-in-java.html http://netjs.blogspot.com.au/2015/05/how-hashmap-internally-...
[2] - http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ http://codecapsule.com/2013/11/17/robin-hood-hashing-backwar...
- ot 11y agoThat'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.