In-memory hash tree implementation

Re:In-memory hash tree implementation by cmrx64 on Sunday March 27, 2016 @09:03PM (#11372179)

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...

[ Parent | on HN ]

Re:In-memory hash tree implementation by ot on Sunday March 27, 2016 @09:29PM (#11372250)

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.

[ Parent | on HN ]