A hash table is a data structure that efficiently stores objects in a way that allows for fast access, insertion, and deletion. Cuckoo hashing is a method of creating and maintaining hash tables that has been widely used in both theory and practice. Random walk d-ary cuckoo hashing is a natural generalization of cuckoo hashing with low space overhead, guaranteed fast access, and fast in practice insertion time. In this presentation, I will explain this algorithm and my work proving a bound on its insertion time. More precisely, we show that for four or more hash functions and load factors up to the optimal threshold, the expectation of the random walk insertion time is O(1), that is, a constant depending only on the number of hash functions and the load factor, not the size of the table.

The study of cuckoo hashing is directly connected to the study of Erdős-Rényi random hypergraphs, and I will emphasize these connections during my presentation. This presentation is based on https://arxiv.org/abs/2401.14394, joint work with Alan Frieze.