Robin Hood哈希的预期最大探测序列长度是多少？实验结果为何与理论不符？

首先你混淆了两个核心概念：理论最坏情况探测长度和随机键分布下的预期最大探测序列长度——这两者完全不是一回事。

• 你提到的log2(n)（比如n=65536时的16）是最坏情况的探测长度，这个结论针对的是刻意构造的极端键分布（比如让所有键哈希值完全冲突、或者形成特定的探测链），属于理论上的边界场景，实际随机数据中几乎不会出现。
• 而你实验中得到的315，是随机键分布下的预期最大探测序列长度，这个结果完全合理。当哈希表负载因子趋近于1（你这里是满表，n个键填进大小为n的表），Robin Hood哈希的预期最大探测序列长度是Θ(√n)量级：对于n=65536，√n=256，你的实验结果315和这个理论量级吻合，属于正常波动范围。

补充一点：负载因子对这个值影响极大。如果哈希表负载因子降低（比如0.7左右），预期最大探测序列长度会大幅缩短；但当负载因子接近1时，不管是线性探测还是Robin Hood哈希，最大探测序列的预期值都会飙升到平方根级别——Robin Hood的优势是平均探测长度远低于线性探测，而非最大探测序列长度在高负载下的量级。

内容的提问来源于stack exchange，提问作者kolbe