哈希表 HashTable | 彩潭有鲤的札记

type

status

date

slug

summary

哈希函数

哈希函数是哈希表中最重要的部分。一般来说，哈希函数会满足以下几个条件：

哈希函数应该易于计算，并且尽量使计算出来的索引值均匀分布。

哈希函数计算得到的哈希值是一个固定长度的输出值

如果 Hash(key1) 不等于 Hash(key2)，那么 key1、key2 一定不相等

如果 Hash(key1) 等于 Hash(key2)，那么 key1、key2 可能相等，也可能不相等（会发生哈希碰撞）

在哈希表的实际应用中，关键字的类型除了数字类，还有可能是字符串类型、浮点数类型、大整数类型，甚至还有可能是几种类型的组合。一般我们会将各种类型的关键字先转换为整数类型，再通过哈希函数，将其映射到哈希表中。

而关于整数类型的关键字，通常用到的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。

直接定址法

直接定址法：取关键字本身 / 关键字的某个线性函数值作为哈希地址。即：Hash(key) = key 或者 Hash(key) = a * key + b，其中 a 和 b 为常数。

这种方法计算最简单，且不会产生冲突。适合于关键字分布基本连续的情况，如果关键字分布不连续，空位较多，则会造成存储空间的浪费。

举一个例子，假设有一个记录了从 1 岁到 100 岁的人口数字统计表。其中年龄为关键字，哈希函数取关键字自身：

年龄	1	2	3	…	25	26	27	…	100
人数	3000	2000	5000	…	1050	…	…	…	…

比如想要查询25岁的人有多少，则只要查询表中第 25 项即可。

除留余数法

除留余数法：假设哈希表的表长为 m，取一个不大于 m 但接近或等于 m 的质数 p，利用取模运算，将关键字转换为哈希地址。即：Hash(key) = key % p，其中 p 为不大于 m 的质数。

这也是一种简单且常用的哈希函数方法。其关键点在于 p 的选择。根据经验而言，一般 p 取素数或者 m，这样可以尽可能的减少冲突。

比如需要将 7 个数 [432, 5, 128, 193, 92, 111, 88] 存储在 11 个区块中（长度为 11 的数组），通过除留余数法将这 7 个数应分别位于如下地址：

索引	00	01	02	03	04	05	06	07	08	09	10
数据	88	111	ㅤ	432	92	5	193	ㅤ	128	ㅤ	ㅤ

平方取中法

平方取中法：先通过求关键字平方值的方式扩大相近数之间的差别，然后根据表长度取关键字平方值的中间几位数为哈希地址。比如：Hash(key) = (key * key) // 100 % 1000，先计算平方，去除末尾的 2 位数，再取中间 3 位数作为哈希地址。

这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关，所以产生的哈希地址也比较均匀，有利于减少冲突的发生。

基数转换法

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

以343246为例，哈希地址计算：

哈希冲突

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

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

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

开放地址法（闭散列）

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

当发生冲突时，开放地址法按照下面的方法求得后继哈希地址：H(i) = (Hash(key) + F(i)) % m，i = 1, 2, 3, ..., n (n ≤ m - 1)。

H(i) 是在处理冲突中得到的地址序列。即在第 1 次冲突（i = 1）时经过处理得到一个新地址 H(1)，如果在 H(1) 处仍然发生冲突（i = 2）时经过处理时得到另一个新地址 H(2) …… 如此下去，直到求得的 H(n) 不再发生冲突。

Hash(key) 是哈希函数，m 是哈希表表长，对哈希表长取余的目的是为了使得到的下一个地址一定落在哈希表中。

F(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 的位置。

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

使用伪随机数序列：假设伪随机数为 9，则得到下一个地址 H(1) = (9 + 5) % 11 = 3，3 对应的地址为空，处理冲突过程结束，记录填入哈希表中序号为 3 的位置。

使用这三种方法处理冲突的结果如下图所示：

线性探测哈希表的代码实现：

线性探测哈希表的缺陷如下：

发生哈希冲突时，需要接近的时间复杂度来解决冲突

在多线程环境中，线性探测所用到的基于数组实现的哈希表，只能给全局的表用互斥锁来保证哈希表的原子操作，以确保线程安全

链地址法（开散列）

链地址法（Chaining）：将具有相同哈希地址的元素（或记录）存储在同一个线性链表中。

链地址法是一种更加常用的哈希冲突解决方法。相比于开放地址法，链地址法更加简单。

假设哈希函数产生的哈希地址区间为 [0, m - 1]，哈希表的表长为 m。则可以将哈希表定义为一个有 m 个头节点组成的链表指针数组 T。

这样在插入关键字的时候，只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i，然后将其以链表节点的形式插入到以 T[i] 为头节点的单链表中。在链表中插入位置可以在表头或表尾，也可以在中间。如果每次插入位置为表头，则插入操作的时间复杂度为。

而在在查询关键字的时候，只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i，然后将对应位置上的链表整个扫描一遍，比较链表中每个链节点的键值与查询的键值是否一致。查询操作的时间复杂度跟链表的长度 k 成正比，也就是。对于哈希地址比较均匀的哈希函数来说，理论上讲，k = n // m，其中 n 为关键字的个数，m 为哈希表的表长。

假设现在要存入的关键字集合 keys = [88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32]。再假定哈希函数为 Hash(key) = key % 13，哈希表的表长 m = 13，哈希地址范围为 [0, m - 1]。将这些关键字使用链地址法处理冲突，并按顺序加入哈希表中（图示为插入链表表尾位置），最终得到的哈希表如下图所示。

相对于开放地址法，采用链地址法处理冲突要多占用一些存储空间（主要是链节点占用空间）。但它可以减少在进行插入和查找具有相同哈希地址的关键字的操作过程中的平均查找长度。这是因为在链地址法中，待比较的关键字都是具有相同哈希地址的元素，而在开放地址法中，待比较的关键字不仅包含具有相同哈希地址的元素，而且还包含哈希地址不相同的元素。

在链地址法哈希表中，当发生哈希冲突时，将发生哈希冲突的元素采用链表数据结构连接起来。但是如果发生哈希冲突的元素过多，则会导致链表过长，那么其搜索的时间复杂度就会增加。其常见的优化手段：

当链表长度过长时，可以将链表转化为红黑树数据结构的形式；

链式哈希表每个桶都可以创建自己的互斥锁，不同的桶之间可以进行并发操作；

链地址法哈希表的实现：

STL实现

SG 的hashtable实现了哈希表的数据结构，其采用除留余数法来构造散列函数，同时通过开链法来解决哈希冲突的问题。它称hashtable表格内的元素为【桶(bucket)】。

hashtable的节点定义：

bucket所维护的linked list，并不采用STL的list或slist，而是自行维护上述的hashtable node。至于buckets结构体，则以vector完成，以便有动态扩充能力。

对于hashtable的迭代器来说，其前进操作是首先尝试从目前所指的节点出发，前进一个节点，由于节点被安置在list内，所以利用节点的 next 指针即可轻易达成前进操作。如果目前节点正巧是list的尾端，就跳至下一个 bucket 身上，那正是指向下一个list的头部节点。

注：hashtable的迭代器没有后退操作，也没有定义所谓的逆向迭代器。

虽然开链法并不要求表格大小必须为质数，但 SGI STL 仍然以质数来设计表格大小，并且先将 28 个质数（逐渐呈现大约 2 倍关系）计算好，以备随时访问，同时提供一个函数__stl_next_prime()，用来查询在这 28 个质数之中，最接近某数并大于某数的质数。

注意，是否重建表格的依据是拿元素个数和bucket vector的大小来比，如果前者大于后者，就重建表格。因此，每个bucket(list)的最大容量和 bucktes vector 的大小相同。

对于哈希函数来说，由于某些元素型别无法对其进行取模运算，因此 SGI 对内建的所有 hash functions 包装了一层，通过函数 bkt_num() 来获取元素落脚的位置。

在 <stl_hash_fun.h> 中定义有数个现成的 hash functions，全部都是仿函数。通过【模板特化】机制来计算相应的哈希函数。其中，针对 char、int、long 等整数型别，大部分的 hash functions 什么都不做。但是对于字符串 const char*，则设计有相应的转换函数：

而对于其他的型别，例如 string、double、float 等，用户都必须自行为它们定义 hash function。

一致性哈希算法

一个良好的分布式哈希方案，应该具有良好的单调性，即服务节点的增减不会造成大量哈希的重新定位。

首先，一致性哈希算法会将整个哈希值空间理解成一个环，其取值范围是共 4G 的整数空间：

然后，将所有的服务器进行哈希，最终落在这个一致性哈希环上。现在假设有 A、B、C 三台服务器，它们经过哈希后，相应的位置如下：

对客户端进行负载时，先通过哈希输入值得到一致性哈希环上的一个哈希值，然后顺着顺时针方向，所遇到的第一台服务器，就是最终所需要负载到的服务器。如下图，现在有 1、2、3、4 四个客户端分别被哈希到该环上的不同位置，可见，最终 Client1 会被分配给 Server C，Client 2 和 Client3 会被分配给 ServerB，Client4 会被分配给 ServerA：

对于在简单哈希算法中所存在的“重新定位”的问题，在一致性哈希算法中会得到相应的解决。

假如此时 ServerC 挂掉了，那么原来在 ServerB 上的 Clinet2 和 Client3 依然会在 ServerB 上，Client4 也是一样，仅仅只有 Client1 改变到了 ServerB 上：

而假如此时新增加了一台服务器 ServerD，如下图所示，那么 Client1、Client2、Client3 都不会收到影响，仅仅只有 Client4 受到了影响：

综上所述，一致性哈希算法的容错性和可扩展性的分析如下：

容错性：当某个服务器挂掉时，仅仅只有分发在所挂掉的服务器上的客户端会受到影响；

可扩展性：当增加一台服务器时，受影响的客户端仅仅只有在新增加的服务器沿着逆时针方向所碰到的上一台服务器之间的客户端；

可见，对于一致性哈希算法而言，服务节点的增减并不会造成大量哈希的重新定位。

但是，如果服务器在哈希到哈希环上时如果过于紧凑，那么服务器的压力就不能做到尽量平均分配，如下图所示，可见，四个客户端都会被分配给 ServerB，而 ServerA 上却并未分配客户端：

为了使得在哈希环上的服务器节点分配更加分散，可以使用【虚拟节点】的方法来进行处理。虚拟节点即将同一个主机在哈希环上设置多个虚拟主机，如下图所示中的服务器 A 和服务器 B，在每个虚拟节点中存储的是真实的物理主机地址：

虚拟节点的引入就是为了防止物理节点过少，导致哈希处理后，在一致性哈希环上挤在一起，导致某一台服务器负载太多，其它的服务器一直很空闲。