Efficient Hashing with Lookups in two Memory Accesses 2018 (0407023v1) 计算机科学

ar Xiv :cs/ 0407 023v 1[ cs.D S] 9J ul2 004Efficient Hashing with Lookups in two Memory AccessesRina Panigrahy ∗August 22, 2018AbstractThe study of hashing is closely related to the analysis of balls and bins. Azar et. al. [1] showed that instead of using a single hash function if we randomly hash a ball into two bins and place it in the smaller of the two, then this dramatically lowers the maximum load on bins. This leads to the concept of two-way hashing where the largest bucket contains O(l