Space Efficient Hash Tables with Worst Case Constant Access Time

We generalize Cuckoo Hashing to d-ary CuckooHashing and show how this yields a simple hash table data structure thatstores n elements in (1 + )n memory cells, for any constant > 0. Assuming uniform hashing, accessing or deleting table entries takes atmost d=O (ln (1/)) probes and the expected amortized insertiontime is constant. This is the first dictionary that has worst caseconstant access time and expected constant update time, works with(1 + )n space, and supports satellite information. Experimentsindicate that d = 4 probes suffice for 0.03.We also describe variants of the data structurethat allow the use of hash functions that can be evaluated in constant time.