paper

Exact Failure Probabilities for d-Choice Cuckoo Hashing

arXiv:2611.17688

Abstract

In d-choice cuckoo hashing, each of n items must be placed in one of its d candidate slots in a table of M slots, and every slot holds at most one item. We give a polynomial-time dynamic programming algorithm to compute the exact probability that no valid placement exists. Our method also handles the variant with separate tables.