如何为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

这段话主要讲的是在使用哈希表时的一些基本原则。哈希表是一种用来存储数据的结构，它通过一个叫做哈希函数的东西来决定数据存放的位置。这里提到的几个因素，比如哈希函数、数据类型、哈希表的大小、如何处理碰撞（也就是当两个数据要放在同一个位置时的处理方式），以及你对时间和内存的需求，都会影响哈希表的表现。

简单来说，建议你使用一个负载因子为2/3的哈希表。负载因子就是指哈希表中实际存储的数据量和哈希表总大小的比例。比如，如果你有1000个数据，那么你的哈希表应该有1500个位置来存放这些数据。如果每个哈希元素占32位（这是基于32位的Python安装的假设，如果不对请纠正我），那么你大约会“浪费”将近2千字节的内存，这其实是非常少的。如果你有200万个数据，那你大约会浪费4兆字节的内存，这同样也是很少的。

总的来说，在使用哈希表时，大家通常更关注的是时间而不是空间。Python在实现字典时，使用的最大负载因子是2/3，超过这个比例就会扩大哈希表的大小。这是因为当负载因子达到70%或80%时，很多处理碰撞的策略表现就会变得很差。