数据结构和算法 | 这次妥妥地拿下散列表---基础、如何设计以及扩展使用（LRU）【3】

0. 前言

大家好，我是多选参数的程序锅，一个正在”捣鼓“操作系统、学数据结构和算法以及 Java 的硬核菜鸡。

今天这篇主要是想讲一下 hash table，hash table 的应用很广泛，随处可见，因此掌握 hash table 是很重要的。本篇将先从 hash table 的基本概念开始介绍。介绍完之后再讲解一下散列表的设计，也就是散列表函数应该如何设计，冲突方法的选择等。最后，讲解一下散列表和链表的结合使用（不是链表法那种），这跟 LeetCode 上一道题很相似。

本篇相关的代码都可以从 https://github.com/DawnGuoDev/algorithm 获取，另外，该仓库除了包含了基础的数据结构和算法实现之外，还会有数据结构和算法的笔记、LeetCode 刷题记录（多种解法、Java 实现）、一些优质书籍整理。

本文的图很多都是从极客时间王争老师专栏那边拷贝过来或者晚上直接截图过来的，因为这些图太好看了，而且本文内容的主要参考也是该专栏。

1. 散列表的概念

散列表即哈希表（Hash Table），我们常见的散列映射、映射、字典和关联数组都是散列表。散列表是一种结合了散列函数和数组的数据结构，相当于借助散列函数对数组这种数据结构进行扩展，同时保持和利用了数组支持按照下标随机访问元素的特性。因此，可以说散列表是一种包含额外逻辑的数据结构。

Python 中的 dict 其实也就是散列表、Java 中的 Map 也是散列表。

散列表经常用于存储键值对，比如我们要在散列表中存储（商品名，商品价格）这么一对内容，其中商品名相当于键、商品价格相当于值。这个键先经过散列函数的计算得到散列值（数组下标），然后根据散列值在数组相应的位置存储（商品名，商品价格）这一对内容。当我们按照键查询这一对内容时，只要使用同样的散列函数，将键转换为下标，从数组下标的位置取这一对内容就完成了查找。因此，散列表用于查找时，时间复杂度是 O(1)。

在整个散列表设计过程中核心的问题是散列函数设计、散列冲突解决以及装载因子的确定。下面先对散列函数、散列冲突解决的方法以及装载因子进行理论级别的介绍，之后我们再讲解散列表的设计。

1.1. 散列函数

散列函数是这样的函数，无论它的输入是什么，它的输出都是一个数字。用专业术语来表示的话，散列函数将输入映射为数字。这个数字可以作为数组的索引，用来确定元素的存储位置。因此，一个散列函数 hash() 设计的基本要求是：

散列函数计算得到的散列值是一个非负整数。因为我们得到的散列值是用来作为数组下标的，因为散列值需要是一个大于等于 0 的值，即非负整数。并且在知道散列表使用的数组的情况下，这个散列值应该是在数组的大小范围内的，也就是需要是有效的索引。
如果 key1 = key2，那 hash(key1) == hash(key2)。也就说对于相同的输入，散列函数都能得到相同的输出，即相同的散列值。
如果 key1 != key2，那 hash(key1) != hash(key2)。也就说对于不同的输入，散列函数得到的输出应该是不同的，即映射到了数组不同的位置。

1.2. 散列冲突

对于前文提到的基本要求中的第三点，其实在现实中很难找到一个 hash 函数使得任何不同的 key 对应的 hash 值都不一样。即便是业界著名的 MD5、SHA、CRC 等 hash 算法，也无法避免这种问题，即不同的 key 对应的 hash 值可能是一样，那么也就是说分配的存储位置是一样的，这个问题就叫做散列冲突。而且数组的存储空间有限，当存储的元素越来越多，也会加大散列冲突的概率。因此下面来说一下散列冲突的解决方法：开放寻址法和链表法。

1.2.1. 开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，那么就重新探测下一个空闲位置，将其插入。有以下这么几种常见的探测方法：线性探测（Linear Probing）、二次探测（Quadratic Probing）和双重散列。

线性探测。

当往散列表中插入数据的时候，如果这个数据的键经过散列函数散列之后得到的数组位置已被占用了，那么就从得到的数组位置开始，依次往后查找（到达数组尾之后再从头开始），看是否有空闲位置，直到找到为止。假如回到最初得到的数组位置还是没找到，那么表示也没找到空闲的位置。后面会对空闲位置不够的情况进行扩容，所以一般不存在找不到的情况。

**查找元素的过程类似于插入过程。**通过散列函数求出要查找元素的键值的散列值，然后比较数组中下标为散列值的元素的键值和查找的键值是否相等（存储的时候相当于把整个元素都存进去）。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中空闲的位置，或者回到最初得到的散列值处，则说明要查找的元素并没有在散列表中。

**删除元素的过程比较特殊。**首先还是先求出要删除的元素的键值对应的散列值，然后比较数组中下标为散列值的元素的键值和查找的键值是否相等。如果相等的话，需要将删除的元素标记为 deleted，而不能单纯地把删除的元素位置设置为空。如果不相等则继续往下探测，直至遇到空闲位置或者找到元素位置。当探测过程中遇到标记了 deleted 的位置时，并不停下来而是继续往下探测。为什么要标记为 deleted 呢？如图所示 y 已经被插入到散列表中了（插入的过程中经过了线程探测，最开始得到的散列值是 7，但是最终存储的位置是 3），那么如果删除下标为 1 的元素后不进行标记的话。有一次，假设我们要查找 y 这个元素，我们一开始得到的散列值还是 7。然后采用线性探测的方式，当探测到 1 的时候，发现 1 这个位置为空，然后从删除步骤退出，表示没找到要删除的元素。但是，这个时候 y 是存在于散列表中的。因此，这个时候的执行是错误的。当删除下标为 1 的元素后进行标记，并且遇到标记继续往下探测，那么我们最终可以正确的删除 y 元素。

线程探测其实存在很大问题，当散列表中插入的数据越来越多时，散列表冲突的可能性越来越大，空闲位置越来越少，线程探测时间会越来越长。极端情况下，可能会探测整个散列表，所以最坏时间复杂度是 O(n)。删除和查找同理。
二次探测

与线性探测类似，只是线性探测的步长是 1，也就是探测的顺序为 hash(key)+1、hash(key)+2、hash(key)+3 … 这种。而二次探测的步长变成了原来的二次方，探测的顺序为 hash(key) + 1^2、hash(key) + 2^2 …
双重探测

双重探测的意思就是使用多个散列函数 hash1(key)、hash2(key)、hash3(key) …我们首先使用第一个散列函数计算散列值，发现计算得到的存储位置已经被占用了，那么则使用第二个散列函数，依次类推，直到找到空闲的存储位置。

1.2.2. 链表法

链表法中，散列值相同的元素都会插入到相同的链表中。如图所示，每个 slot 对应一个链表，这个链表中的元素的散列值都是一样的。

插入的时候，通过散列函数计算出对应的 slot 位置，然后将元素插入到对应链表中即可。假如采用头插法，整个时间复杂度为 O(1)。

查找、删除的时候，同样先计算出对应的 slot 位置，然后遍历链表查找或者删除。由于查找和删除这两个操作的时间复杂度跟链表的长度 k 成正比，因此时间复杂度为 O(k)。在比较平均情况下，k=n/m，n 表示散列中数据的个数，m 是散列表中 slot 的个数。

1.3. 装载因子

不管使用哪种冲突解决的方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率。一般会尽可能保证散列表中有一定比例的空闲槽位。在散列表中用装载因为这一概念来表示空位的多少，计算公式为 散列表的装载因子=填入表中的元素个数/散列表的长度。装载因子越大说明空闲位置越少，冲突越多，散列表的性能会下降。

装载因子的值不一定要小于 1，可以大于 1，比如采用链表法之后填入表中的元素个数可以大于散列表的长度。

1.4. 总结

总的来说，散列表一般情况下的时间复杂度为 O(1)。但是散列表的查找时间复杂度受到散列函数、冲突解决方法、装载因子等影响。如果散列函数设计的不好，或者装载因子过高又或者冲突解决方法不合适都可以导致散列冲突发生的概率升高，散列表查询效率下降。因此散列表的设计主要是考虑到三方面，一是散列函数的选择，二是装载因子如何确保不会过大，三是冲突解决方法的选择。下面就来探讨一下散列表的设计准则。

这个舍不得删除：如果散列表设计的不好，可能导致拒绝服务攻击（DoS）的目的。比如有些恶意攻击者，通过精心构造的数据结构，使得所有的数据经过散列函数之后，得到的散列值都是一样。假如使用基于链表的冲突解决方法，那这个时候，散列表就会退化为链表，查询的时间就从 O(1) 退化为了 O(n)。如果散列表中有 10w 个数据，退化后散列表的查询效率就下降了 10w 倍。假如之前运行 100 次查询需要 0.1 秒，那么现在则需要 1w 秒。进一步导致因为查询而消耗大量 CPU，使得系统无法响应其他请求，也就达到了 DoS 攻击。这也就是散列撞击攻击的原理。

2. 散列表的设计

2.1. 散列函数的设计

散列函数的好坏直接决定了冲突发生的概率。如果一个散列函数不好，导致无论生成的散列值都是一样的，那么冲突会很明显。

首先散列函数不能设计过于复杂。因为过于复杂的散列函数，会消耗很多 CPU 周期，也就影响了散列表的性能。别忘了，我们将散列表函数的执行当做 O(1) 的时间复杂度，如果过于复杂，时间复杂度也就是可能不再为 O(1) 了。
其次，散列函数生成的散列值尽可能随机并且均匀分布。这样才能从散列函数角度来减少冲突的次数。即便发生了冲突，在采用链表法时，每个 slot 中的数据也会比较平均。

常用的简单的散列函数设计方法有：

比如用散列表处理手机号码的时候，因为手机号码前几位重复的可能性很大，但是后面几位就比较随机。因此我们就可以使用手机号码的后四位作为散列值。这个叫做数据分析法。
当处理的内容是字符串时，那么可以将每个字母的 ASCII 值 “进位”相加，然后再跟散列表的大小求余作为散列值。比如，英文单词 nice 转化出来的就是下面这样：
```
hash("nice") = (('n'-'a')*26^3 + ('i'-'a')*26^2 + ('c'-'a')*26 + ('e'-'a'))/78978
```
还有什么直接寻址法、平方取中法、折叠法、随机数法等等

2.2. 动态扩容策略和装载因子的确定（整理到这）

装载因子越大，也就是散列表中的元素占比越来越大，空闲位置越来越小，那么散列冲突的概率也就越来越大。假如采用开放寻址法，则寻址次数将会很多；采用链表法，则链表将会很长。

2.2.1. 扩容策略

简单扩容

解决这类问题的一个直观的方法就是对散列表进行扩容。当装载因子大于某个值时，散列表可以申请一个更大的散列表，然后将数据都搬移到这个新的散列表中。相比数组扩容来说，散列表的扩容会比较麻烦。因为散列表的大小变了，数组的存储位置也变了（存储位置是跟散列表大小取模之后的），所以我们需要通过散列函数重新计算每个数据的存储位置。比如下面这个例子中，散列函数为：key%n，n 为散列表的大小。那么，21 这个元素的位置原本存储在下标为 0 的位置，在扩容之后存储位置变成了 7。

这种情况下的时间复杂度是多少呢？类似与数组的扩容，可以采用均摊分析方法。在插入 n 个数据之后，要想在插入一个数据的时候，时间复杂度为 O(n)，得最终时间复杂度为 O(1)。同样，均摊情况下，时间复杂度接近最好情况，即 O(1)。

当然，当散列表中的数据越来越少的时候，原本扩容的空间中空闲位置会越来越多。那么可以在装载因子小于某个值之后，动态缩容。但是一般不缩容。

高效扩容

上面这种方法有个弊端，那就是在装载因子到达阈值进行扩容时需要将所有数据都进行迁移。这种方法相对来说比较低效，比如当前散列表的大小是 1GB，要想扩容为原来的两倍，那么这个时候的插入操作是很耗时的。

为了解决这个问题，我们可以将扩容的操作穿插到插入操作的过程中，即将扩容的操作分批完成而不是一次性完成。具体的做法是：在申请新空间之后，并不将老的数据搬移到新的散列表中。当有新数据插入的时候，我们将新数据插入到新的散列表中，然后从老的散列表中取出一个数据插入到新的散列表中。之后，每次插入一个数据时，都重复上述的过程。经过多次插入操作之后，老的散列表中的数据就都一点一点移到了新的散列表中了。这样，统一的扩容操作相当于被均摊到多次插入操作中了，那么每次插入数据的时间复杂度都是 O(1)。

那么这个期间的查询操作该怎么样呢？可以首先去新的散列表中查找，如果没有查找到再去老的散列表中查找。

2.2.2. 装载因子的阈值确定

前面讲到装载因子大于某个值时就需要进行扩容，那么装载因子的阈值需要选择得当。如果阈值太大，那么会导致冲突过多；如果太小，那么会导致内存浪费严重。

阈值的选择需要考虑到时间、空间复杂度等。如果内存空间不紧张，对效率要求很高，那么可以降低阈值；如果内存空间紧张，效率要求不高，那么阈值可以增大，甚至可以大于 1。

2.3. 散列冲突方法的选择

前面讲了一下散列冲突的两种解决方法：开放寻址法和链表法。这两种方法在实际的软件开发中都经常用到。比如 Java 的 LinkedHashMap 采用的是链表法。ThreadLocalMap 是采用线性探测的开放寻址法来解决的。那么这两种方法有什么优缺点吗？适合于哪些场景？

2.3.1. 开放寻址法

开放寻址法的优点就是所有的数据都存储在数组中，所以可以有效地利用 CPU 缓存加速查询速度。而且，这种方式实现的散列表，序列化比较简单。链表法包含指针，序列化起来就没那么容易。

开发寻址法的缺点就是在删除数据的时候比较麻烦。需要先对已删除数据所在的位置进行标记。另外，开发寻址法中所有的数据都放在一个数组中，比起链表法来说冲突的代价更大。因此，使用开放寻址法的话，装载因子的阈值得比较小，也就导致了这种方法比链表法浪费更多的内存空间。

综上，数据量比较少、装载因子比较小的时候可以使用开放寻址法。这也是 Java 中 ThreadLocalMap 采用开放寻址法解决冲突的原因。

2.3.2. 链表法

链表法的缺点是相对来说比较耗内存，主要是因为链表是需要存储指针的，尤其对于存储小的对象来说（说不定指针所占的内存空间比对象所需的内存空间还要大）。当然，对于存储的是大对象来说就没什么太大问题了。另外链表法对 CPU cache 不太友好，这也是因为链表法中的结点是分散在内存中的，而非连续。

链表法的优点是内存的利用率比开放寻址法要高。因为链表节点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好的（PS：我的理解是这样的，开放寻址法中我需要先创建存储数据的结构，但是链表法中，只需要先创建一个存放节点地址的数组即可，真正存放数据的节点在需要的时候再创建）。

另外，链表法的装载因子阈值可以更高，可以大于 1，而开放寻址法的装载因子阈值只能小于 1。当链表法和开放寻址法的阈值同时接近 1 时，开放寻址法会有更大的散列冲突，甚至会遍历整个散列表，性能下降很多。但是，对于链表法来说，即便装载因子为 10，只要散列函数的值随机均匀，那么只是链表的变长了而已。查找效率虽然有所下降、虽然也有冲突，但是相比开发寻址法的顺序遍历来说，链表法好多了。

链表法的另一个优点，我觉得是更具灵活性。为什么呢？因为我们可以对链表法进行改造。比如将链表中使用的单链表替换成双向链表、双向循环链表，甚至可以将其替换为更加高效的动态数据结构，比如红黑树、跳表等。这样，即便在极端情况下（所有数据都散列到一块去了），那么最终的散列表查找时间也只不过是 O(logn)。

综上，数据量比较大、并且存储的对象所占内存比较大时，可以使用链表法。因为链表法更灵活，支持更多策略，比如红黑树替代链表。

2.4. 总结

要想设计一个具有如下特性的散列表（比如工业级散列表）：

支持快速的查找、插入、删除等操作
内存占用合理、不能过多浪费内存空间
性能稳定，极端情况下，散列表的性能也不会退化到无法接受的程度

那么需要从上面所提到的三个点出发，即：

设计一个合适的散列函数：散列函数要让散列后的值随机且均匀分布；散列函数的设计不能过于复杂，太复杂会太耗时间，影响散列表性能。
确定装载因子的阈值，选择扩容策略：可以不选择一次性扩容的方式，而是将扩容均摊到每次插入操作中。
选择合适的散列冲突解决方法：大部分情况下，链表法更加普适。同时还可以将链表法中的链表改造成其他动态查找数据结构，比如红黑树，来避免极端情况下散列表的时间复杂度退化为 O(n)。但是，对于小规模数据、装载因子不高的散列表适合开放寻址法。

当然还需要结合具体的业务场景、业务数据来具体分析。

3. 散列表和链表联用

前段时间在看 Linux 内核源码的时候，有时候会看到散列表和链表的联合使用，散列表用来快速查找，而链表则使用 LRU 算法来维护（比如可查看文件系统缓存这一块的内容）。那么接下来我们来看一下为什么将它们放在一起使用？以及散列表和链表的联用是什么样的？

在单纯使用链表实现 LRU 缓存淘汰算法时，我们是按照时间先后（最新访问的算是后）来维护链表结构。由于缓存是有限的，所以链表的结点数量也是有限。因为当缓存空间不够的时候，需要淘汰一个数据的时候，那么直接将链表头部的节点删去就好。

当需要访问某个数据时，是先去缓存中查找的。如果没有找到所需数据，则先去访问内存然后把数据读到缓存中，即把数据放到链表尾部；如果找到了所需数据，它们则将它们移到链表的尾部。因为查询数据的时候需要遍历链表，所以单纯的使用单链表的方式实现 LRU 缓存淘汰算法的时间复杂度为 O(n)。然而，缓存包含的几种常见的操作都需要查找操作，比如以下几种：

往缓存中添加一个数据（不得先找到插入的位置的才能添加嘛）
从缓存中删除一个数据（不得先找到才能删嘛）
从缓存中查找一个数据

当使用单链表的时候，时间复杂度是 O(n)。但是如果将查找速度很快的散列表和链表组合使用的话，可以将查找的时间复杂度降低到 O(1)。从而使得上述三种常见操作的时间复杂度都降低到 O(1)。

那么散列表和链表联合之后，一般如下所示，这边使用的链表一般都是双向链表（Linux 中的链表常用的是双向循环链表）。

链表的每个节点存储数据（data）、链表使用的前驱指针（prev）、链表使用的后继指针（next），以及用于散列表链表的 hnext 指针。在联合使用的情况中，有两个链表，一个是双向链表，使用的是 prev 和 next 两个指针；另一个是散列表的拉链，使用的是 hnext 指针。每个节点都位于这两个链表上。

对于查找一个数据来说，由于每个数据所在的节点又都是属于散列表，所以查找时间复杂度接近 O(1)。当查找到一个数据之后，还需要将数据所在的节点移到双向链表的尾部。

对于删除一个数据来说，需要先找到要删除的数据所在节点，这个时间复杂度是 O(1)。当找到要删除的数据所在的节点之后，由于使用的是双向链表，可以通过 prev 直接找到要删除的前驱节点，因此删除节点只需要 O(1) 的时间度。那么整个操作的时间复杂度也是 O(1)。

对于添加一个数据来说。需要先判断要删除的数据是否在散列表中。如果已经在其中，那么则将数据所在的节点移到双链表的尾部；如果不在其中，则需要将待添加的数据添加到双链表中，这个时候我们先需要判断缓存的容量是否已满。如果已满，那么则将双向链表头部的节点删除，然后再将数据添加到链表的尾部，并添加到散列表的拉链中；如果未满，则将数据直接添加双向链表的尾部，并添加到散列表的拉链中。

综上，整个过程的查找操作都可以通过散列表来完成，时间复杂度可达到 O(1)。其他的操作，删除头结点，链表尾结点插入数据，其实通过存储头尾结点的指针都可以在 O(1) 的时间复杂度内完成。因此，上述的三个操作的时间复杂度都是 O(1)。因此，将散列表和双向链表结合可以实现一个高效的、支持 LRU 缓存淘汰算法的缓存系统模型。

3.1. 实例研究—Java LinkedHashMap

Java 的 LinkedHashMap 这个容器就结合使用了散列表和链表。HashMap 底层是通过散列表这种数据结构实现的，而 LinkedHashMap 多了个 Linked 之后，不单单散列表的冲突使用链表法解决，而且还使用到了链表，即 LinkedHashMap 是通过散列表和链表这两种数据结构组合实现的。Linked 更多是指结合了链表这种方式。下面我们来看一下 LinkedHashMap 的使用：

假如使用 HashMap 的时候，下面的输出结果 2、3、5。

HashMap<Integer, Integer>  m = new HashMap<>();
m.put(3, 12);
m.put(2, 32);
m.put(5, 35);

for (Map.Entry e : m.entrySet()) {
    System.out.println(e.getKey());
}

但是当我们使用 LinkedHashMap 的时候，输出的结果是 3、2、5，也就是说按照数据插入的顺序依次来打印。散列表中的数据插入之后，应该是会无规律存储的，那么为什么可以实现按照数据插入的顺序来遍历打印的呢？

HashMap<Integer, Integer>  m = new LinkedHashMap<>();
m.put(3, 12);
m.put(2, 32);
m.put(5, 35);

for (Map.Entry e : m.entrySet()) {
    System.out.println(e.getKey());
}

这个主要是因为 LinkedHashMap 也是组合使用了散列表和链表。这个链表除了按照插入顺序进行维护之外，还可以按照访问顺序来进行维护。比如下面在创建的时候，使用 true 则表示按照访问时间顺序进行维护。这段代码最终的输出结果是 2、1、3、5，这是因为执行 put 函数之后，会将数据都添加到链表尾部，那么此时的顺序为 3、2、5、1；之后再 put 一个已存在的数据之后，顺序变为 2、5、1、3；最后使用 get 访问之后，顺序变为 2、1、3、5。

HashMap<Integer, Integer>  m = new LinkedHashMap<>(16, 0.75f, true);
m.put(3, 12);
m.put(2, 32);
m.put(5, 35);
m.put(1, 66);

m.put(3, 32);
m.get(5);

for (Map.Entry e : m.entrySet()) {
    System.out.println(e.getKey());
}

综上，我们可以发现 LinkedHashMap 跟我们上述讲解的使用散列表和双向链表来实现 LRU 缓存淘汰策略是很类似的，因此他们的原理也是很相似的。所以 LinkedHashMap 是通过散列表和双向链表这两种数据结构组合实现的。

4. 总结

散列表中最重要的几个概念是散列函数、散列冲突、装载因子，这几个概念需要理解。
散列表在设计的时候需要考虑一下这几个问题，一是散列函数选定的问题，主要是简单，但是要随机和分布均匀；二是装载因子阈值的确定，这个主要需要考虑实际情况；三是扩容问题，在达到装载因子之后需要进行扩容，扩容可以一次性的，也可以是分次的，就将扩容操作均摊到每次添加操作中，维护两个散列表；四是散列冲突方法的选择，开放寻址法比较适合小数据量，数据量大了还得链表法。
散列表可以和双向链表结合用于 LRU 缓存系统模型，那么这两者的结合还可以用于其他很多途径，想想 LinkedHashMap。那么为什么这两者经常一起使用的？散列表支持非常高效的插入、删除、查找等操作。但是散列表中的数据都是通过散列函数打乱之后无规律存储的，也就是散列表无法支持按照某种顺序快速地遍历。因此假如想要按照顺序（插入顺序或访问顺序）遍历时，需要额外的操作，比如将散列表中的数据先拷贝出来再进行排序，再遍历。然而，散列表是一个动态的数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历时都得这么操作，那么效率势必很低。而链表这种方式，插入、删除操作很快，按照某种顺序进行维护是很方便的。因此为了解决散列表的这个问题，可以将散列表和链表一起使用了，从而在实现快速插入、删除、查找的同时，还可以按照某种顺序进行维护。

巨人的肩膀

极客时间，《数据结构与算法之美》，王争
《算法图解》