← 研踪 PaperTrailarXiv:2611.17688 · v1
Exact Failure Probabilities for d-Choice Cuckoo Hashing
首次提交 2026-11-13 11:13
版本更新 2026-11-13 11:13
雷达观测 2026-11-17 04:57
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-13 11:13 · 最新观测版本
Exact Failure Probabilities for d-Choice Cuckoo Hashing
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.
查看此版本解读 →查看此版本原文 ↗