哈希函数（二）-基数转换法、哈希冲突、开放地址法

基数转换法：将关键字看成另一种进制的数再转换成原来进制的数，然后选其中几位作为哈希地址。

比如，将关键字看作是13进制的数，再将其转变为10进制的数，然后将其作为哈希地址。

以343246为例，计算方式如下：

$(343246)_{13} = 3 * 13^{5} + 4 * 13^{4} + 3 * 13^{3} + 2 * 13^{2} + 4 * 13^{1} + 6 * 13^{0} = (1235110)_{10}$

哈希冲突：不同的关键字通过同一个哈希函数可能得到同一哈希地址，即 key1 ≠ key2，而 Hash(key1) = Hash(key2)，这种现象称为哈希冲突。

理想状态下，我们的哈希函数是完美的一对一映射，即一个关键字（key）对应一个值（value），不需要处理冲突。但是一般情况下，不同的关键字 key 可能对应了同一个值 value，这就发生了哈希冲突。

设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题。常用的哈希冲突解决方法主要是两类：「开放地址法」和「链地址法」。

开放地址法：指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时，处理冲突时需要尝试另外的单元，直到找到空的单元为止。

当发生冲突时，开放地址法按照下面的方法求得后继哈希地址： $H (i) = (H a s h (k e y) + F (i)) % m ， i = 1, 2, 3, . . ., n (n \leq m - 1)$ 。

H(i) 是在处理冲突中得到的地址序列。即在第 1 次冲突（i = 1）时经过处理得到一个新地址 H(1)，如果在 H(1) 处仍然发生冲突（i = 2）时经过处理时得到另一个新地址 H(2) …… 如此下去，直到求得的 H(n) 不再发生冲突
Hash(key) 是哈希函数，m 是哈希表表长，取余目的是为了使得到的下一个地址一定落在哈希表中
F(i) 是冲突解决方法，取法可以有以下几种：
- 线性探测法： $F (i) = 1, 2, 3, . . ., m - 1$
- 二次探测法： $F (i) = 1^{2}, - 1^{2}, 2^{2}, - 2^{2}, . . ., n^{2} (n \leq m / 2)$
- 伪随机数序列：F(i) = 伪随机数序列

开放地址法举例

举例说明一下如何用以上三种冲突解决方法处理冲突，并得到新地址 H(i)。例如，在长度为 11 的哈希表中已经填有关键字分别为 28、49、18 的记录（哈希函数为 Hash(key) = key % 11）。

现在将插入关键字为 38 的新纪录，根据哈希函数得到的哈希地址为 5，产生冲突。接下来分别使用这三种冲突解决方法处理冲突。

使用线性探测法：得到下一个地址 $H (1) = (5 + 1) % 11 = 6$ ，仍然冲突；继续求出 $H (2) = (5 + 2) % 11 = 7$ ，仍然冲突；继续求出 $H (3) = (5 + 3) % 11 = 8$ ，8 对应的地址为空，处理冲突过程结束，记录填入哈希表中序号为 8 的位置。