现在我们来解决第二个问题：如何构造一个好的散列函数。

一个好的散列函数应（近似地）满足简单均匀散列：每个关键字都等可能的被散列到各个槽位，并与其他关键字散列到哪一个槽位无关（但很遗憾，我们一般无法检验这一条件是否成立）。

在实际应用中，常常可以可以运用启发式方法来构造性能好的散列函数。设计过程中，可以利用关键字分布的有用信息。一个好的方法导出的散列值，在某种程度上应独立于数据可能存在的任何模式。

下面给出两种基本的构造散列函数的方法：

(1) 除法散列法

除法散列法的做法很简单，就是让关键字k去除以一个数m，取余数，这样就将k映射到m个槽位中的某一个，即散列函数是：

h(k) = k mod m ，

由于只做一次除法运算，该方法的速度是非常快的。但应当注意的是，我们在选取m的值时，应当避免一些选取一些值。例如，m不应是2的整数幂，因为如果m = 2 ^ p，则h(k)就是k的p个最低位数字。除非我们已经知道各种最低p位的排列是等可能的，否则我们最好慎重的选择m。而一个不太接近2的整数幂的素数，往往是较好的选择。

(2) 乘法散列法

该方法包含两个步骤。第一步：用关键字k乘以A（0 < A < 1），并提取kA的小数部分；第二步：用m乘以这个值，在向下取整，即散列函数是：

h(k) = [m (kA mod 1)]，

这里“kA mod 1”的是取kA小数部分的意思，即kA –[kA]。

乘法散列法的一个优点是，一般我们对m的选择不是特别的关键，一般选择它为2的整数幂即可。虽然这个方法对任意的A都适用，但Knuth认为，A ≈ （√5 - 1）/ 2 = 0.618033988…是一个比较理想的值

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。