闲聊哈希表（中）

richiefang

闲聊哈希表（中） [复制链接]

上期链接：
https://bbs.eeworld.com.cn/thread-97607-1-1.html

上期，我们说到了散列函数(Hash Function)。它又名哈希函数，是计算机科学中一个重要的课题。什么是散列函数呢？其实，这个概念并没有一个严格的定义。一般说来，散列函数满足以下的条件：
1、对输入值运算，得到一个固定长度的摘要(Hash value)；
2、不同的输入值可能对应同样的输出值；
以下的函数都可以认为是一个散列函数：
f(x) = x mod 16;                                       (1)
f(x) = (x2 + 10) * x;                                         (2)
f(x) = (x | 0×0000FFFF) XOR (x >> 16);    (3)
不过，仅仅满足上面这两条的函数，作为散列函数，还有不足的地方。我们还希望散列函数满足下面几点：
1、散列函数的输出值尽量接近均匀分布；
2、x的微小变化可以使f(x)发生非常大的变化，即所谓“雪崩效应”(Avalanche effect)；
上面两点用数学语言表示，就是：
1，  输出值y的分布函数F(y)=y/m, m为散列函数的最大值。或记为y~U[0, m]
2，|df(x)/dx| >> 1；
从上面两点，大家看看，前面举例的三个散列函数，哪个更好呢？对了，是第三个：
f(x) = (x | 0×0000FFFF) XOR (x >> 16);
它很完美地满足“好的散列函数”的两个附加条件。
那么，为什么散列函数要带有这两个附加条件呢？原来，这是为了减少“哈希冲突”（Hashcollision），也就是两个不同输入产生了相同输出值的情况。根据抽屉原理，Hash算法不可能没有冲突(collision)，但是，由于冲突会造成一些问题，可能会影响到应用Hash函数的某些算法的效率，所以，我们需要尽量避免之。这样，对Hash算法的选择，就是很重要的了。密码学中的著名摘要算法的MD5和SHA1，以及另一种用于字符串摘要计算的Jenkins Hash算法，都是很经典的Hash算法，有兴趣的同学可以阅读参考。
顺便延伸阅读一下，对计算机信息安全感兴趣的同学，一定听说过密码学家王小云教授。王教授成名的贡献，就是发现了大大加速找出MD5和SHA1等Hash算法冲突的方法。譬如，根据“生日攻击”理论，对于Hash value为160bit的SHA1算法，找出一个Hash冲突需要280次运算，而王小云找出了一个269次运算就能找出冲突的算法，也就是提高了211=2048倍的效率！所以说，王教授的成果大大动摇了现代密码学的基础。
今天的最后，给大家留下了一个问题：上次说到，Hash表中，数据存储的位置，是通过Hash函数计算得到的。那么，如果两条数据记录的Hash值发生冲突，应该怎么办呢？

lixiaohai8211

受教于hash表 中