大家好,我是多选参数的程序锅,一个正在”捣鼓“操作系统、学数据结构和算法以及 Java 的硬核菜鸡。
今天这篇主要是想讲一下 hash table,hash table 的应用很广泛,随处可见,因此掌握 hash table 是很重要的。本篇将先从 hash table 的基本概念开始介绍。介绍完之后再讲解一下散列表的设计,也就是散列表函数应该如何设计,冲突方法的选择等。最后,讲解一下散列表和链表的结合使用(不是链表法那种),这跟 LeetCode 上一道题很相似。
本篇相关的代码都可以从 https://github.com/DawnGuoDev/algorithm 获取,另外,该仓库除了包含了基础的数据结构和算法实现之外,还会有数据结构和算法的笔记、LeetCode 刷题记录(多种解法、Java 实现) 、一些优质书籍整理。
★本文的图很多都是从极客时间王争老师专栏那边拷贝过来或者晚上直接截图过来的,因为这些图太好看了,而且本文内容的主要参考也是该专栏。 ”
散列表即哈希表(Hash Table),我们常见的散列映射、映射、字典和关联数组都是散列表。散列表是一种结合了散列函数和数组的数据结构,相当于借助散列函数对数组这种数据结构进行扩展,同时保持和利用了数组支持按照下标随机访问元素的特性。因此,可以说散列表是一种包含额外逻辑的数据结构。
★Python 中的 dict 其实也就是散列表、Java 中的 Map 也是散列表。 ”
散列表经常用于存储键值对,比如我们要在散列表中存储(商品名,商品价格)这么一对内容,其中商品名相当于键、商品价格相当于值。这个键先经过散列函数的计算得到散列值(数组下标),然后根据散列值在数组相应的位置存储(商品名,商品价格)这一对内容。当我们按照键查询这一对内容时,只要使用同样的散列函数,将键转换为下标,从数组下标的位置取这一对内容就完成了查找。因此,散列表用于查找时,时间复杂度是 O(1)。
在整个散列表设计过程中核心的问题是散列函数设计、散列冲突解决以及装载因子的确定。下面先对散列函数、散列冲突解决的方法以及装载因子进行理论级别的介绍,之后我们再讲解散列表的设计。
散列函数是这样的函数,无论它的输入是什么,它的输出都是一个数字。用专业术语来表示的话,散列函数将输入映射为数字。这个数字可以作为数组的索引,用来确定元素的存储位置。因此,一个散列函数 hash() 设计的基本要求是:
对于前文提到的基本要求中的第三点,其实在现实中很难找到一个 hash 函数使得任何不同的 key 对应的 hash 值都不一样。即便是业界著名的 MD5、SHA、CRC 等 hash 算法,也无法避免这种问题,即不同的 key 对应的 hash 值可能是一样,那么也就是说分配的存储位置是一样的,这个问题就叫做散列冲突。而且数组的存储空间有限,当存储的元素越来越多,也会加大散列冲突的概率。因此下面来说一下散列冲突的解决方法:开放寻址法和链表法。
开放寻址法的核心思想是,如果出现了散列冲突,那么就重新探测下一个空闲位置,将其插入。有以下这么几种常见的探测方法:线性探测(Linear Probing)、二次探测(Quadratic Probing)和双重散列。
线程探测其实存在很大问题,当散列表中插入的数据越来越多时,散列表冲突的可能性越来越大,空闲位置越来越少,线程探测时间会越来越长。极端情况下,可能会探测整个散列表,所以最坏时间复杂度是 O(n)。删除和查找同理。
链表法中,散列值相同的元素都会插入到相同的链表中。如图所示,每个 slot 对应一个链表,这个链表中的元素的散列值都是一样的。
插入的时候,通过散列函数计算出对应的 slot 位置,然后将元素插入到对应链表中即可。假如采用头插法,整个时间复杂度为 O(1)。
查找、删除的时候,同样先计算出对应的 slot 位置,然后遍历链表查找或者删除。由于查找和删除这两个操作的时间复杂度跟链表的长度 k 成正比,因此时间复杂度为 O(k)。在比较平均情况下,k=n/m,n 表示散列中数据的个数,m 是散列表中 slot 的个数。
不管使用哪种冲突解决的方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率。一般会尽可能保证散列表中有一定比例的空闲槽位。在散列表中用装载因为这一概念来表示空位的多少,计算公式为 散列表的装载因子=填入表中的元素个数/散列表的长度
。装载因子越大说明空闲位置越少,冲突越多,散列表的性能会下降。
★装载因子的值不一定要小于 1,可以大于 1,比如采用链表法之后填入表中的元素个数可以大于散列表的长度。 ”
总的来说,散列表一般情况下的时间复杂度为 O(1)。但是散列表的查找时间复杂度受到散列函数、冲突解决方法、装载因子等影响。如果散列函数设计的不好,或者装载因子过高又或者冲突解决方法不合适都可以导致散列冲突发生的概率升高,散列表查询效率下降。因此散列表的设计主要是考虑到三方面,一是散列函数的选择,二是装载因子如何确保不会过大,三是冲突解决方法的选择。下面就来探讨一下散列表的设计准则。
如果散列表设计的不好,可能导致拒绝服务攻击(DoS)的目的。比如有些恶意攻击者,通过精心构造的数据结构,使得所有的数据经过散列函数之后,得到的散列值都是一样。假如使用基于链表的冲突解决方法,那这个时候,散列表就会退化为链表,查询的时间就从 O(1) 退化为了 O(n)。如果散列表中有 10w 个数据,退化后散列表的查询效率就下降了 10w 倍。假如之前运行 100 次查询需要 0.1 秒,那么现在则需要 1w 秒。进一步导致因为查询而消耗大量 CPU,使得系统无法响应其他请求,也就达到了 DoS 攻击。这也就是散列撞击攻击的原理。 ”
散列函数的好坏直接决定了冲突发生的概率。如果一个散列函数不好,导致无论生成的散列值都是一样的,那么冲突会很明显。
常用的简单的散列函数设计方法有:
hash("nice") = (('n'-'a')*26^3 + ('i'-'a')*26^2 + ('c'-'a')*26 + ('e'-'a'))/78978
装载因子越大,也就是散列表中的元素占比越来越大,空闲位置越来越小,那么散列冲突的概率也就越来越大。假如采用开放寻址法,则寻址次数将会很多;采用链表法,则链表将会很长。
解决这类问题的一个直观的方法就是对散列表进行扩容。当装载因子大于某个值时,散列表可以申请一个更大的散列表,然后将数据都搬移到这个新的散列表中。相比数组扩容来说,散列表的扩容会比较麻烦。因为散列表的大小变了,数组的存储位置也变了(存储位置是跟散列表大小取模之后的),所以我们需要通过散列函数重新计算每个数据的存储位置。比如下面这个例子中,散列函数为:key%n,n 为散列表的大小。那么,21 这个元素的位置原本存储在下标为 0 的位置,在扩容之后存储位置变成了 7。
★这种情况下的时间复杂度是多少呢?类似与数组的扩容,可以采用均摊分析方法。在插入 n 个数据之后,要想在插入一个数据的时候,时间复杂度为 O(n),得最终时间复杂度为 O(1)。同样,均摊情况下,时间复杂度接近最好情况,即 O(1)。 当然,当散列表中的数据越来越少的时候,原本扩容的空间中空闲位置会越来越多。那么可以在装载因子小于某个值之后,动态缩容。但是一般不缩容。 ”
上面这种方法有个弊端,那就是在装载因子到达阈值进行扩容时需要将所有数据都进行迁移。这种方法相对来说比较低效,比如当前散列表的大小是 1GB,要想扩容为原来的两倍,那么这个时候的插入操作是很耗时的。
为了解决这个问题,我们可以将扩容的操作穿插到插入操作的过程中,即将扩容的操作分批完成而不是一次性完成。具体的做法是:在申请新空间之后,并不将老的数据搬移到新的散列表中。当有新数据插入的时候,我们将新数据插入到新的散列表中,然后从老的散列表中取出一个数据插入到新的散列表中。之后,每次插入一个数据时,都重复上述的过程。经过多次插入操作之后,老的散列表中的数据就都一点一点移到了新的散列表中了。这样,统一的扩容操作相当于被均摊到多次插入操作中了,那么每次插入数据的时间复杂度都是 O(1)。
那么这个期间的查询操作该怎么样呢?可以首先去新的散列表中查找,如果没有查找到再去老的散列表中查找。
前面讲到装载因子大于某个值时就需要进行扩容,那么装载因子的阈值需要选择得当。如果阈值太大,那么会导致冲突过多;如果太小,那么会导致内存浪费严重。
阈值的选择需要考虑到时间、空间复杂度等。如果内存空间不紧张,对效率要求很高,那么可以降低阈值;如果内存空间紧张,效率要求不高,那么阈值可以增大,甚至可以大于 1。
前面讲了一下散列冲突的两种解决方法:开放寻址法和链表法。这两种方法在实际的软件开发中都经常用到。比如 Java 的 LinkedHashMap 采用的是链表法。ThreadLocalMap 是采用线性探测的开放寻址法来解决的。那么这两种方法有什么优缺点吗?适合于哪些场景?
开放寻址法的优点就是所有的数据都存储在数组中,所以可以有效地利用 CPU 缓存加速查询速度。而且,这种方式实现的散列表,序列化比较简单。链表法包含指针,序列化起来就没那么容易。
开发寻址法的缺点就是在删除数据的时候比较麻烦。需要先对已删除数据所在的位置进行标记。另外,开发寻址法中所有的数据都放在一个数组中,比起链表法来说冲突的代价更大。因此,使用开放寻址法的话,装载因子的阈值得比较小,也就导致了这种方法比链表法浪费更多的内存空间。
综上,数据量比较少、装载因子比较小的时候可以使用开放寻址法。这也是 Java 中 ThreadLocalMap 采用开放寻址法解决冲突的原因。
链表法的缺点是相对来说比较耗内存,主要是因为链表是需要存储指针的,尤其对于存储小的对象来说(说不定指针所占的内存空间比对象所需的内存空间还要大)。当然,对于存储的是大对象来说就没什么太大问题了。另外链表法对 CPU cache 不太友好,这也是因为链表法中的结点是分散在内存中的,而非连续。
链表法的优点是内存的利用率比开放寻址法要高。因为链表节点可以在需要的时候再创建,并不需要像开放寻址法那样事先申请好的(PS:我的理解是这样的,开放寻址法中我需要先创建存储数据的结构,但是链表法中,只需要先创建一个存放节点地址的数组即可,真正存放数据的节点在需要的时候再创建)。
另外,链表法的装载因子阈值可以更高,可以大于 1,而开放寻址法的装载因子阈值只能小于 1。当链表法和开放寻址法的阈值同时接近 1 时,开放寻址法会有更大的散列冲突,甚至会遍历整个散列表,性能下降很多。但是,对于链表法来说,即便装载因子为 10,只要散列函数的值随机均匀,那么只是链表的变长了而已。查找效率虽然有所下降、虽然也有冲突,但是相比开发寻址法的顺序遍历来说,链表法好多了。
链表法的另一个优点,我觉得是更具灵活性。为什么呢?因为我们可以对链表法进行改造。比如将链表中使用的单链表替换成双向链表、双向循环链表,甚至可以将其替换为更加高效的动态数据结构,比如红黑树、跳表等。这样,即便在极端情况下(所有数据都散列到一块去了),那么最终的散列表查找时间也只不过是 O(logn)。
综上,数据量比较大、并且存储的对象所占内存比较大时,可以使用链表法。因为链表法更灵活,支持更多策略,比如红黑树替代链表。
要想设计一个具有如下特性的散列表(比如工业级散列表):
那么需要从上面所提到的三个点出发,即:
当然还需要结合具体的业务场景、业务数据来具体分析。
前段时间在看 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 缓存淘汰算法的缓存系统模型。
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 是通过散列表和双向链表这两种数据结构组合实现的。