解决冲突
链接法，开放寻址
全域散列
如果从H中随机选择一个散列函数，当关键字k不等于l时，两者的冲突是多少？
1.关键字k，选一个散列函数，然后散列进入T的一个槽中
2.两个键碰撞的概率
关键字l（不确定），选一个散列函数，然后对于l也散列到和k同一个槽中，此时散列函数确定，而且要散列到同一个槽中（也就是结果和一样）
这样如果在U中有一个值可以根据这个散列函数并散列到指定的槽中，要么在U中有这个值（<= 1/m 查完最后一个的话是1/m）与其他键冲突的期望？
C_x 表示除了x外 其他键和它碰撞次数的总数
c_xy表示 两个键碰撞 （当碰撞的时候c_xy的值加1，不碰撞保持）
结论：E(c_xy) = 1/m （概率都相等，期望也就和概率一样了） 和
E(C_x) = (n-1)/m
为什么选双向链表？（不考虑首尾是空指针的情况）
.png
