python - 如何预先确定为 N 个项目创建哈希表的理想大小？

Question

如果我使用以下方法计算碰撞概率:

def collision(hash_t, items):
    prob = 1.0
    for i in range(1, items):
        prob *= (hash_t - i) / float(hash_t)
    return 1 - prob

有没有一种简单的方法来创建一个模型，根据冲突的概率计算哈希表中查找和插入的成本，这样我就可以根据速度与内存分配来决定最佳大小？

Answer 1

虽然这取决于您的散列函数 + 数据类型(以确定散列如何发生)、散列条目的大小(对于 Python，32 位系统与 64 位系统可能有所不同)、您的冲突处理策略以及您的时间/内存要求，以下是一个很好的经验法则:

使用 2/3 的负载系数。

也就是说，哈希表的大小是元素数量的 3/2。因此，如果有 1,000 个元素，则有 1,500 个条目。如果每个哈希元素都是 32 位(假设基于 32 位 Python 安装，如果这是错误的，请有人纠正我)，那么您就浪费了近 2 kB，这确实是一个很小的内存量。如果您有 2,000,000 个条目，您将浪费近 4 MB，这也是很小的。

简而言之，哈希表中常见的考虑因素很少是空间，而是时间。 Python 自己的 dict 实现在扩展哈希表大小之前使用最大负载因子 2/3。这是基于性能下降，许多碰撞策略在 70% 或 80% 负载系数左右表现不佳。