Hash表的碰撞概率

有一个经典的概率问题：N个人在一起开party，问这N个人中，至少有2个人生日相同的概率是多少？（N>=2，不考虑2月29的情况，不考虑润年，不考虑双胞胎。）

至少有2个人生日相同的概率，与完全没有人生日相同的概率，形成互补，而后者更容易计算。

# N=2，生日相同的概率：
>>> 1 - 364/365
0.002739726027397249
# N=3，至少2人生日相同的概率：
>>> 1 - (364/365)*(363/365)
0.008204165884781345
# N=4，至少2人生日相同的概率：
>>> 1 - (364/365)*(363/365)*(362/365)
0.016355912466550215

Hash表的碰撞概率（至少2个key经过hash计算，得到的positon一样），与此问题类似。N个完全随机的key，通过hash计算position，共有M个position，碰撞的概率如何计算。就如N个人，每个人都有个随机的生日，共365种可能，碰撞的概率一样。

def hash_collision_p(N, M):
    q = 1
    for i in range(1,N):
        q *= (M-i)/M
    return 1-q

>>> hash_collision_p(2,365)
0.002739726027397249
>>> hash_collision_p(4,365)
0.016355912466550215

>>> hash_collision_p(20,365)
0.41143838358058027
>>> hash_collision_p(24,365)
0.538344257914529
>>> hash_collision_p(28,365)
0.6544614723423995
>>> hash_collsion_p(32,365)
0.7533475278503208

>>> hash_collsion_p(120,10000)
0.5117175336118225
>>> hash_collsion_p(160,10000)
0.7216336576276512
>>> hash_collsion_p(200,10000)
0.8651196385197777

所以，不要以为自己的Hash表容量很大，key数量少，就可以不考虑碰撞，或者认为碰撞的概率很低。这是错误的观点！从上述数据来分析，如果要将碰撞概率控制在很小的水平上，position的数量需要比key的数量至少大20倍以上！

Rehasing是一个动作。比如，当碰撞的概率超过设定的阈值，或者说，当Load Factor超过阈值，扩大位置数，但要对所有元素进行Rehasing。就是新创建一个容量更大的Hash Table，然后将所有元素全部重新添加进去，此过程会重新计算每个元素的hash值，因此称为Rehashing。

Bucket就是对本文Position的另一个称呼，编程语言中似乎更喜欢用Bucket这个词。

在Hash表的实现中，一般都会采用linked-list方式来处理冲突，这个list被称为collision chain。这个链表越长，性能越差。理论上Hash表（采用linked-list处理冲突）的查询Big-Oh是\(O(N)\)，就是极端情况下，Collision Chain造成的。

当然也可以不用linked-list来处理Hash Table的冲突，可选项还有AVLTree等。