Hacker News Reader

Recently I was reading about hash tables on wikipedia and I was surprised to learn about how much the birthday problem influenced their design.

"A real world example of a hash table that uses a self-balancing binary search tree for buckets is the HashMap class in Java version 8."

https://en.wikipedia.org/wiki/Hash_table#Separate_chaining_w...

View on HN

This is only to counter worst-case attack scenarios which do not happen in a realistic scenario. Like >100 collisions.

Robin Hood or its better cousin Hopscotch hashing, which was forgotten here, counter that scenario much better, with only ~1-3% performance loss on average in the best case, and much better perf. numbers in the average write-heavy case, where their "move to front" strategy pays off. And they have the worst case scenario also covered, unlike all others.

The birthday problem directly relates to Bloom and Cuckoo filters as well. The false positive rate is how often two hashes collide.

Reply on news.ycombinator.com