A Simple Hash Class With Strong Randomness Properties In Graphs And Hypergraphs

Aumüller Martin, Dietzfelbinger Martin, Woelfel Philipp. Arxiv 2016

[Paper]    
ARXIV Graph Independent

We study randomness properties of graphs and hypergraphs generated by simple hash functions. Several hashing applications can be analyzed by studying the structure of $d$-uniform random ($d$-partite) hypergraphs obtained from a set $S$ of $n$ keys and $d$ randomly chosen hash functions $h_1,\dots ,h_d$ by associating each key $x\in S$ with a hyperedge $\{h_1(x),\dots ,h_d(x)\}$. Often it is assumed that $h_1,\dots ,h_d$ exhibit a high degree of independence. We present a simple construction of a hash class whose hash functions have small constant evaluation time and can be stored in sublinear space. We devise general techniques to analyze the randomness properties of the graphs and hypergraphs generated by these hash functions, and we show that they can replace other, less efficient constructions in cuckoo hashing (with and without stash), the simulation of a uniform hash function, the construction of a perfect hash function, generalized cuckoo hashing and different load balancing scenarios.

Similar Work

• Codes From Incidence Matrices Of Hypergraphs
• Explicit And Efficient Hash Families Suffice For Cuckoo Hashing With A Stash
• Sichash -- Small Irregular Cuckoo Tables For Perfect Hashing
• Cuckoo Hashing In Cryptography Optimal Parameters Robustness And Applications