新论文 · v1arXiv:2611.17688
Exact Failure Probabilities for d-Choice Cuckoo Hashing
Chenyang Zhang, Ling Ren
原文摘要
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.
cs.DS