哈希函数
哈希函数
所有哈希函数都有如下一个基本特性：根据同一哈希函数计算出的哈希值如果不同，那么输入值肯定也不同。但是，根据同一哈希函数计算出的哈希值如果相同，输入值不一定相同。
常见的哈希函数有以下几个：
-
直接定址法：直接以关键字 k 或者 k 加上某个常数
(k+c)作为哈希地址。 -
数字分析法：提取关键字中取值比较均匀的数字作为哈希地址。
-
除留余数法：用关键字 k 除以某个不大于哈希表长度 m 的数 p，将所得余数作为哈希表地址。
-
分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
-
平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。
-
伪随机数法：采用一个伪随机数当作哈希函数。
直接定址法
如果我们现在要对 0-100 岁的人口数字统计表，那么我们对年龄这个关键字就可以直接用年龄的数字作为地址。此时 f(key) = key。
f(key) = a × key + b
除留余数法
除留余数法此方法为最常用的构造哈希函数方法。对于哈希表长为 m 的哈希函数公式为：
f(key) = key mod p (p ≤ m)
mod 是取模(求余数)的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。有一个关键字，它有 12 个记录，现在我们要针对它设计一个哈希表。如果采用除留余数法，那么可以先尝试将哈希函数设计为 f(key) = key mod 12 的方法。比如 29 mod 12 = 5，所以它存储在下标为 5 的位置。
不过这也是存在冲突的可能的，因为 12 = 2×6 = 3×4。如果关键字中有像 18(3×6)、30(5×6)、42(7×6)等数字，它们的余数都为 6，这就和 78 所对应的下标位置冲突了。
但是我们如果不选用 p=12 来做除留余数法，而选用 p=ll，则结果如下:
使用除留余数法的一个经验是，若哈希表表长为 m，通常 p 为小于或等于表长(最好接近 m)的最小质数或不包含小于 20 质因子的合数。