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.