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一样），与此问题类似（假设input是完全随机的）。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倍以上！

Hash表中元素个数与位置数的比值，即\(\alpha=\cfrac{N}{M}\)。如果采用open chaining方式处理collision，它同时也是Expected Length of Chain。

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

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

在Hash表的实现中，一般都会采用Linked-List方式来处理冲突，这个List被称为Collision Chain，或Open Chainning。这个链表越长，性能越差。理论上Hash表（采用Linked-List处理冲突）的查询Big-Oh是\(O(N)\)，这是极端情况下，即Worst Case，由查询Collision Chain造成的。实际上，Hash表的分析更应该使用Expected Time Complexity:

Hash表中有N个元素，Successful查询可能查询这N个元素中的任何一个，假设查询第\(ith\)个元素，此时有\(N-i\)个元素在\(ith\)元素后面加入Hash表，在使用open chaining时，有\(\cfrac{N-i}{M}\)个元素可能出现在\(ith\)元素的前面，因此查询到\(ith\)元素的时间为\(1+\cfrac{N-i}{M}\)，查询N个元素中任意一个的概率相同，所以，Expected时间复杂度为\(\cfrac{1}{N}\cdot\sum\limits_{i=1}^N\left(1+\cfrac{N-i}{M}\right)=1+\cfrac{\alpha}{2}-\cfrac{a}{2N}\)。

当然也可以不用Linked-List来处理Hash Table的冲突，可选项还有Red Black Tree等。

Open Chaining的一个缺点，空间利用率有点低，必须为chain申请额外的空间，同时hash table本身还有大量的空间没有被利用起来（看看前文计算碰撞概率，就知道hash table内部的剩余空间是很多的）。

Closed Chaining方案，就是把一个个chain隐藏在hash table内部，去充分利用hash table已有的空间。Hash函数不再仅仅计算一个position，而是计算出一个位置序列，当前面的position已经被占用时，就尝试后一个position，直到找到一个空位置为止。最简单的位置序列，就是前一个位置+1。Closed Chaining是Python采用的方案。