A Seven Dimensional Analysis of Hashing Methods [pdf]

Re:A Seven Dimensional Analysis of Hashing Methods [pdf] by nosefouratyou on Tuesday April 25, 2017 @03:24PM (#14197114)

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

[ Parent | on HN ]

Re:A Seven Dimensional Analysis of Hashing Methods [pdf] by rurban on Wednesday April 26, 2017 @05:32AM (#14201684)

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.

[ Parent | on HN ]

Re:A Seven Dimensional Analysis of Hashing Methods [pdf] by shouldbworking on Tuesday April 25, 2017 @07:09PM (#14199046)

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

[ Parent | on HN ]