关于散列表的一些思考
lan
12 Mar 2019
散列表（也叫Hash表）是一种应用较为广泛的数据结构，几乎所有的高级编程语言都内置了散列表这种数据结构。然而散列表在不同的编程语言中称呼不一样，在JavaScript中被称为对象，在Ruby中被称为哈希，而在Python中被称为字典。即便称呼不同，语法不同，它们的原理基本相通。
原理解析
在现代的编程语言中，几乎都会有散列表的身影，故而难以忽视它为程序员所带来的种种便利性。散列跟数组是很相似的，较大的区别在于，数组直接通过特定的索引来访问特定位置的数据，而散列表则是先通过散列函数来获取对应的索引，然后再定位到对应的存储位置。这是比较底层的知识了，一般的散列表，在底层都是通过数组来进行存储，利用数组作为底层存储的数据结构最大的好处在于它的随机访问特性，不管数组有多长，访问该数组的时间复杂度都是O(1)。
当然要设计一个能用的散列表，在底层仅仅用普通的数组是不够的，毕竟我们需要存储的不仅仅是数值类型，还可能会存储字符串为键，字符串为值，或者以字符串为键，某个函数的指针为值 (JavaScript就很多这种情况)的键值对。在这类情况中，我们需要对底层的结点进行精心设计，才能够让散列表存储更多元化的数据。
无论以何种数据类型为键，我们始终都需要有把键转换成底层数组任意位置索引的能力，通过散列函数可以做到这一点。散列函数是个很考究的东西，设计得不好可能会导致频繁出现多个不同的键映射到同一个索引值的现象，这种现象称之为冲突，文章的后半部分会看到常用的一些解决冲突的方式。除此之外，每次为散列表所分配的空间是有限的，随着元素的插入，散列表会越来越满，这时，冲突的几率就越高。故而，我们需要定期对散列表进行扩张，并把已有的键值对重新映射到新的空间中去，让散列表中的键值对更加分散，降低冲突的几率。这个过程被称为Resize。这个过程能够在一定程度上降低散列表的冲突几率，提高查找效率。
接下来会从散列函数，冲突解决，散列查找以及散列表Resize这几个方面来详细谈谈散列表的基本概念。
为何不用链表来存储键值对？
散列表本质上就是用来存储键值对的，其实完全可以用一个链表来实现键值对存储的功能，这样就不会产生冲突了。举个简单的例子
typedef struct Node {
char * key;
char * value;
struct Node * next;
} Node;
以上的结点能够存储以字符串为键，字符串为值的键值对。假设完全用链表来实现键值对存储机制，那么每次插入元素，我们都得遍历整个链表，对比每个结点中的键。如果键已经存在的话则替换掉原来的值，如果遍历到最后都不能找到相关的结点则创建新的结点并插入到散列的末端。查找的方式其实也类似，同样是遍历整个链表，查找到对应键值对则返回相关的值，当遍历到散列最后都不能找到相关值的话则提示找不到对应结点。删除操作跟插入操作类似，都需要遍历链表，寻找待删除的键值对。
这种实现方式虽然操作起来较为简便，也不会有冲突产生，不过最大的问题在于效率。无论是插入，查找还是删除都需要遍历整个链表，最坏情况下时间复杂度都是O(n)。假设我们有一个相当庞大的键值对集合，这样的时间成本是难以让人接受的。为此在存储键值对的时候都会采用数组来作为底层的数据结构，得益于它随机访问的特征，无论最终的键值对集合多有庞大，访问任意位置的时间复杂度始终为O(1)。即便这种方式会有产生冲突的可能，但只要散列函数设计得当，Resize的时机合适，散列表访问的时间复杂度都会保持在O(1)左右。
散列函数
散列函数在维基百科上的解释是
散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。
在散列表中所谓的“指纹”其实就是我们所分配的数组空间的索引值，不同类型的键需要设计不同的散列函数，它将会得到一个数值不是太大的索引值。假设我们用C语言来设计一个以字符串为键，字符串为值的散列表，那么这个散列表的结点可以被设计成
typedef struct Hash {
char * key; // 指向散列的键
char * value; // 指向散列的值
char isNull; // 标识这个散列是否为空
} Hash;
以这个结点为基础可以简单地创建一个长度为7的散列表
Hash hash[7]
接下来就要设计对应的散列函数了，这个函数的目的是把字符串转换成整型数值。字符串和整型最直接的关联无非就是字符串的长度了，那么我们可以设计一个最简单的字符串散列函数
#include <string.h>
unsigned long simpleHashString(char * str) {
return strlen(str);
}
不过这个散列函数有两个比较大的问题
- 对同样长度的字符串，它的散列值都是相同的。放在数组的角度上来看就是，它们所对应的数组索引值是一样的，这种情况会引发冲突。
- 以字符串为键，当它的长度大于7的时候，它所对应的索引值会造成数组越界。
针对第一种情况，可以简单描述为，这个散列函数还不够“散”。可以进一步优化，把字符串中的每个字节所对应的编码值进行累加如何？
#include <string.h>
unsigned long sum(char * str) {
unsigned long sum = 0;
for (unsigned long i = 0; i < strlen(str); i++) {
sum += str[i];
}
return sum;
}
unsigned long simpleHashString(char * str) {
return strlen(str) + sum(str);
}
这样似乎就可以得到一个更“散”的地址了。接下来还需要考虑第二种情况，索引值太大所造成的越界的问题。要解决越界的问题，最粗暴的方式就是对数组进行扩展。不过依照我前面写的这个不太合格的散列函数，散列函数的值几乎是随着字符串的增长而线性增长。举个例子
int main() {
printf("%lu", simpleHashString("Hello World"));
}
打印结果是1063，这是一个相当大的值了。如果要按这个数值来分配内存的话那么所需要的内存空间是sizeof(Hash) * 1063 => 25512个字节，大概是25KB，这显然不太符合情理。故而需要换个思路去解决问题。为了让散列函数的值坐落在某个范围内，采用模运算就可以很容易做到这一点
unsigned long simpleHashStringWithMod(char * str) {
return (strlen(str) + sum(str)) % 7;
}
这里除数是7，故而散列函数simpleHashStringWithMod所生成索引值的取值范围是0 <= hvalue < 7，恰好落在长度为7的数组索引范围内。如果要借助这个散列函数来存储键值对{'Ruby' => 'Matz', 'Java' => 'James'}，那么示意图为
这里只是做个简单的示范，长度为7的散列表会显得有点短，很容易就会产生冲突，接下来会谈谈解决冲突的一些方式。
冲突
前面我们所设计的散列函数十分简单，然而所分配的空间却最多只能够存储7个键值对，这种情况下很快就会产生冲突。所谓冲突就是不同的键，经过散列函数处理之后得到相同的散列值。也就是说这个时候，它们都指向了数组的同一个位置。我们需要寻求一些手段来处理这种冲突，如今用途比较广泛的就有开放地址法以及链地址法，且容我一一道来。
1. 开放地址法
开放地址法实现起来还算比较简单，只不过是当冲突产生的时候通过某种探测手段来在原有的数组上寻找下一个存放键值对位置。如果下个位置也存有东西了则再用相同的探测算法去寻找下下个位置，直到能够找到合适的存储位置为止。目前常用的探测方法有
- 线性探测法
- 平方探测法
- 伪随机探测法
无论哪种探测方法，其实都需要能够保证对于同一个地址输入，第n次探测到的位置总是相同的。
线性探测法很容易理解，简单来讲就是下一个索引位置，计算公式为hashNext = (hash(key) + i) mod size。举个直观点的例子，目前散列表中索引为5的位置已经有数据了。当下一个键值对也想在这个位置存放数据的时候，冲突产生了。我们可以通过线性探测算法来计算下一个存储的位置，也就是(5 + 1) % 7 = 6。如果这个地方也已经有数据了，则再次运用公式(5 + 2) % 7 = 0，如果还有冲突，则继续(5 + 3) % 7 = 1以此类推，直到找到对应的存储位置为止。很明显的一个问题就是当数组越满的时候，冲突的几率越高，越难找到合适的位置。用C语言来实现线性探测函数linearProbing结果如下
int linearProbing(Hash * hash, int address, int size) {
int orgAddress = address;
for (int i = 1; !hash[address].isNull; i++) {
address = (orgAddress + i) % size; // 线性探测
}
return address;
}
只要散列表还没全满，它总会找到合适的位置的。平方探测法与线性探测法其实是类似的，区别在于它每次所探测的位置不再是原有的位置加上i，而是i的平方。平方探测函数quadraticProbing大概如下
int quadraticProbing(Hash * hash, int address, int size) {
for (int i = 1; !hash[address].isNull; i++) {
address = (address + i * i) % size; // 平方探测
}
return address;
}
上面两个算法最大的特点在于，对于相同的地址输入，总会按照一个固定的路线去寻找合适的位置，这样以后要再从散列表中查找对应的键值对就有迹可循了。其实伪随机数也有这种特性，只要随机的种子数据是相同的，那么每次得到的随机序列都是一定的。可以利用下面的程序观察伪随机数的行为
#include <stdio.h>
#include <stdlib.h>
int main()
{
int seed = 100;
srand(seed);
int value = 0;
int i=0;
for (i=0; i< 5; i++)
{
value =rand();
printf("value is %d\n", value);
}
}
伪随机种子是seed = 100，这个程序无论运行多少次打印的结果总是一致的，在我的计算机上会打印以下数值
value is 1680700
value is 330237489
value is 1203733775
value is 1857601685
value is 594259709
利用这个特性，我们就能够以伪随机的机制来实现伪随机探测函数randomProbing
int randomProbing(Hash *hash, int address, int size) {
srand(address);
while (!hash[address].isNull) {
address = rand() % size;
}
return address;
}
无论采用哪种方式，只要有相同的address输入，都会得到相同的查找路线。总体而言，用开放地址法来解决地址冲突问题，在不考虑哈希表Resize的情况下，实现起来还是比较简单的。不过不难想到，它较大问题在于当散列表满到一定程度的时候，冲突的几率会比较大，这种情况下为了找到合适的位置必须要进行多次计算。另外还有个问题，就是删除键值对的时候，我们不能把键值对的数据简单地“删除”掉，并把当前位置设置成空。因为如果直接删除并设置为空的话会出现查找链中断的情况，任何依赖于当前位置所做的搜索都会作废，可以考虑另外维护一个状态来标识当前位置是“空闲”的，表明它曾经有过数据，现在也接受新数据的插入。
PS: 在这个例子中，我们可以只利用isNull字段来标识不同状态。用数值0来标识当前结点已经有数据了，用1来标识当前结点是空的，采用2来标识当前结点曾经有过数据，目前处于空闲状态，并且接受新数据的插入。这样就不会出现查找链中断的情况了。不过需要对上面的探测函数稍微做一些调整，这里不展开说。
2. 链地址法
链地址法跟开放地址法的线性探测十分相似，最大的不同在于线性探测法中的下一个节点是在当前的数组上去寻找，而链地址法则是通过链表的方式去追加结点。实际上所分配数组的每一个位置都可以称之为桶，总的来说，开放地址法产生冲突的时候，会去寻找一个新的桶来存放键值对，而链地址法则是依然使用当前的桶，但是会追加新结点增加桶的深度。示意图大概如下
可见它的结点结构是
typedef struct Hash {
char * key; // 指向散列的键
char * value; // 指向散列的值
char isNull; // 标识这个散列是否为空
struct Hash * next; // 指向下一个结点
} Hash;
除了原来的数据字段之外，还需要维护一个指向下一个冲突结点的指针，实际上就是最开始谈到的链表的方式。这种处理方式有个好处就是，产生冲突的时候，不再需要为了寻找合适的位置而进行大量的探测，只要通过散列函数找到对应桶的位置，然后遍历桶中的链表即可。此外，利用这种方式删除节点也是比较容易的。即便是采用了链地址法，到了一定时候还是要对散列表进行Resize的，不然等桶太深的时候，依旧不利于查找。
3. 汇总
总体而言，采用开放地址法所需要的内存空间比较少，实现起来也相对简单一些，当冲突产生的时候它是通过探测函数来查找下一个存放的位置。但是删除结点的时候需要另外维护一个状态，才不至于查找链的中断。链地址法则是通过链表来存储冲突数据，这为数据操作带来不少便利性。然而，无论采用哪种方式，都需要在恰当的时候进行Resize，才能够让时间复杂度保持在O(1)左右。
查找
了解如何插入，那么查找也就不成问题了。对开放地址法而言，插入算法大概如下
- 通过散列函数计算出键所对应的散列值。
- 根据散列值从数组中找到相对应的索引位置。
- 如果这个位置是“空闲”的，则插入数据。如果该键值对已经存在了，则替换掉原来的数据。
- 如果这个位置已经有别的数据了，表明冲突已经产生。
- 通过特定的探测法，计算下一个可以存放的位置。
- 返回第三步。
而查找算法是类似的
- 通过散列函数计算出键所对应的散列值。
- 根据散列值从数组中找到相对应的索引位置。
- 如果这个位置为空的话则直接返回说找不到数据。
- 如果这个位置能够匹配当前查找的键，则返回需要查找的数据。
- 如果这个位置已经有别的数据，或者状态显示曾经有过别的数据，表明有冲突产生。
- 通过特定的探测法，计算下一个位置。
- 返回第三步。
链地址法其实也类似，区别在于插入键值对的时候如果识别到冲突，链地址法并不会通过一定的探测法来查找下一个存放数据的位置，而是顺着链表往下搜索，增添新的结点，或者更新已有的结点。查找的时候则是沿着链表往下查找，找到目标数据则直接把结果返回。假设穷尽链表都无法找到对应的数据，表明数据不存在。
重组（Resize）
Resize是专业术语，直接翻译过来是重新设置大小，不过有些书籍会把它翻译成重组，我觉得这个翻译更为贴切。当原有的散列表快满的时候，其实我们不仅需要对原有的空间进行扩张，还需要用新的散列函数来重新映射键值对，让键值对可以更加分散地存储。
不过不同的实现方式进行重组的时机不太一样，对于开放地址法而言，每个桶都只能存放一个键值对，需要通过特定的探测法把冲突数据存放到相关的位置中。当散列表越满的时候冲突的几率就越大，要找到可以存放数据的地方将会越艰难，这将不利于后续的插入和查找。为此需要找到一个恰当的时机对散列表进行Resize。业界通过载荷因子来评估散列表的负载，载荷因子越大，冲突的可能性就越高。
载荷因子 = 填入表中的元素个数 / 散列表的长度
采用开放地址法来实现的散列表，当载荷因子超过某个阀值的时候就应当对散列表进行Resize了，不过阀值的大小则由设计者自行把控了。据维基百科上的描述，Java的系统库把载荷因子的阀值设置为0.75左右，超过这个值则Resize散列表。
而采用链地址法实现散列的时候，利用链表的特性，每个桶都能够存放多个结点，因此在链地址法中通过桶的深度来评估一个散列是否需要Resize更有意义。你可以当桶的最大深度超过某个值的时候对原有的散列进行Resize。
无论采用哪种实现方式，Resize的时机还需要设计者自行把控，不同的应用场景Resize的时机也可能会有所不同。Resize操作可以让我们原有的键值对数据更加分散，让散列表插入和查找的时间复杂度保持在O(1)左右。然而Resize毕竟是耗时操作，时间复杂度随着键值对数据的增长而增长，因此不宜操作得过于频繁。
总结
这篇文章主要从原理层面阐述了一个散列表的实现方式，总结了实现一个散列表需要注意的一些事项。需要设计一个较好的散列函数，让键值对更加分散以减少冲突的可能。然而很多时候冲突难以避免，我们需要一些手段来解决冲突，还要在恰当的时候进行Resize。一般而言，散列表的底层是采用了能够随机访问的数据结构，只要散列表中的键值对足够分散，就能够把时间复杂度控制在O(1)左右。