02、散列函数构造方法

散列函数构造方法

直接定址法

如果我们对盈利为 0-9 的菜品设计哈希表，我们则直接可以根据作为地址，则 f(key) = key;

即下面这种情况。

有没有感觉上面的图很熟悉，没错我们经常用的数组其实就是一张哈希表，key 就是数组的索引下标，我们通过下标直接访问数组中的元素。

另外我们假设每道菜的成本为 50 块，那我们还可以根据盈利+成本来作为地址，那么则 f(key) = key + 50。也就是说我们可以根据线性函数值作为散列地址。

f(key) = a % key + b 其中 a,b 均为常数

优点：简单、均匀、无冲突。

应用场景：需要事先知道关键字的分布情况，适合查找表较小且连续的情况

数字分析法

该方法也是十分简单的方法，就是分析我们的关键字，取其中一段，或对其位移，叠加，用作地址。比如我们的学号，前 6 位都是一样的，但是后面 3 位都不相同，我们则可以用学号作为键，后面的 3 位做为我们的散列地址。

如果我们这样还是容易产生冲突，则可以对抽取数字再进行处理。

我们的目的只有一个，提供一个散列函数将关键字合理的分配到散列表的各位置。这里我们提到了一种新的方式，抽取，这也是在散列函数中经常用到的手段。

优点：简单、均匀、适用于关键字位数较大的情况

应用场景：关键字位数较大，知道关键字分布情况且关键字的若干位较均匀

折叠法

其实这个方法也很简单，也是处理我们的关键字然后用作我们的散列地址，主要思路是将关键字从左到右分割成位数相等的几部分，然后叠加求和，并按散列表表长，取后几位作为散列地址。

比如我们的关键字是 123456789，则我们分为三部分 123 ，456 ，789 然后将其相加得 1368 然后我们再取其后三位 368 作为我们的散列地址。

优点：事先不需要知道关键字情况

应用场景：适合关键字位数较多的情况

除法散列法

在用来设计散列函数的除法散列法中，通过取 key 除以 p 的余数，将关键字映射到 p 个槽中的某一个上，对于散列表长度为 m 的散列函数公式为

f(k) = k mod p (p <= m)

例如，如果散列表长度为 12，即 m = 12 ，我们的参数 p 也设为 12，那 k = 100 时 f(k) = 100 % 12 = 4

由于只需要做一次除法操作，所以除法散列法是非常快的。

由上面的公式可以看出，该方法的重点在于 p 的取值，如果 p 值选的不好，就可能会容易产生同义词。见下面这种情况。我们哈希表长度为 6，我们选择 6 为 p 值，则有可能产生这种情况，所有关键字都得到了 0 这个地址数。

那我们在选用除法散列法时选取 p 值时应该遵循怎样的规则呢？

• m 不应为 2 的幂，因为如果 m = 2^p ，则 f(k) 就是 k 的 p 个最低位数字。例 12 % 8 = 4 ，12 的二进制表示位 1100，后三位为 100。
• 若散列表长为 m ,通常 p 为 小于或等于表长（最好接近 m）的最小质数或不包含小于 20 质因子的合数。

**合数：**合数是指在大于 1 的整数中除了能被 1 和本身整除外，还能被其他数（0 除外）整除的数。

质因子：质因子（或质因数）在数论里是指能整除给定正整数的质数。

这里的 2，3，5 为质因子

还是上面的例子，我们根据规则选择 5 为 p 值，我们再来看。这时我们发现只有 6 和 36 冲突，相对来说就好了很多。

优点：计算效率高，灵活

应用场景：不知道关键字分布情况

乘法散列法

构造散列函数的乘法散列法主要包含两个步骤

• 用关键字 k 乘上常数 A(0 < A < 1)，并提取 k A 的小数部分
• 用 m 乘以这个值，再向下取整

散列函数为

f (k) = ⌊ m(kA mod 1) ⌋

这里的 kA mod 1 的含义是取 keyA 的小数部分，即 kA - ⌊kA⌋ 。

优点：对 m 的选择不是特别关键，一般选择它为 2 的某个幂次（m = 2 ^ p ,p 为某个整数）

应用场景：不知道关键字情况

平方取中法

这个方法就比较简单了，假设关键字是 321，那么他的平方就是 103041，再抽取中间的 3 位就是 030 或 304 用作散列地址。再比如关键字是 1234 那么它的平方就是 1522756 ，抽取中间 3 位就是 227 用作散列地址.

优点：灵活，适用范围广泛

适用场景：不知道关键字分布，而位数又不是很大的情况。

随机数法

顾名思义，取关键字的随机函数值为它的散列地址。也就是 f(key) = random(key)。这里的 random 是 随机函数。

优点：易实现

适用场景：关键字的长度不等时

上面我们的例子都是通过数字进行举例，那么如果是字符串可不可以作为键呢？当然也是可以的，各种各样的符号我们都可以转换成某种数字来对待，比如我们经常接触的 ASCII 码，所以是同样适用的。

以上就是常用的散列函数构造方法，其实他们的中心思想是一致的，将关键字经过加工处理之后变成另外一个数字，而这个数字就是我们的存储位置，是不是有一种间谍传递情报的感觉。

一个好的哈希函数可以帮助我们尽可能少的产生冲突，但是也不能完全避免产生冲突，那么遇到冲突时应该怎么做呢？下面给大家带来几种常用的处理散列冲突的方法。