Probabilistic behavior of hash tables

Dawei Hong, Jean-Camille Birget, Shushuang Man

We extend a result of Goldreich and Ron about estimating the collision probability of a hash function. Their estimate has a polynomial tail. We prove that when the load factor is g…