c++进阶——哈希表的实现

哈希表的实现

本篇文章，我们来学习一下哈希表的一些内容。学习本节课是非常具有意义的，因为c++STL库中的两个系列的容器unordered_set和unordered_map都是基于哈希表的思想来实现的。所以我们需要深入了解哈希。

对于这两个系列的容器的使用，其实看名字可以大概知道，这是和map和set相互对应的。只不过有一些区别。基本上就是会使用map和set就会使用unordered_set和unordered_map。所以对于这两个容器的使用就不再花开文章进行专门的介绍了。

下面我们来探究一下二者不同的地方。

unordered_map和unordered_set

这两个系列的容器是基于哈希表来实现的。而map和set是基于红黑树这个比较特殊的二叉搜索树来实现的。二者有如下的区别：

1. 中序遍历的序列不同：
   map和set是二叉搜索树，其天生的性质就决定了其中序遍历得到的序列是一个升序序列(默认比较规则下)。当然也可以是控制降序。但是对于unordered_map和unordered_set来说，这是没有顺序的。在这里不进行演示。后续讲完哈希表的实现后自然能明白。
2. 哈希表在搜索和插入的效率上会比红黑树的效率高一些。
3. 哈希表也是和红黑树一样，根据关键字Key来存储。但是哈希表不是直接根据Key来存储的，需要将关键字转化为整型后再操作：
   但是这就导致了一个问题，实现哈希表的时候就得加入一个仿函数。因为有些数据类型不支持直接转化为整形的。如string，如自己实现的一些日期类等。所以需要自行编写仿函数进行转整形操作。在哈希表中通过仿函数调用。
4. 哈希表的key需要支持相等比较：
   这点其实比较不好理解，因为当前还没有学习哈希表的概念是什么。但是在这里稍微提及一下。因为哈希表是通过关键字转整形后进行操作的。但是最终存储在表中的是什么？还是关键字和映射的数据(如果有)。搜索的时候也是通过这个关键字进行相同的操作，然后找到对应的位置。在不支持冗余数据的情况下，是需要比较一下插入的关键字是否存在。势必要比较两个关键字是否相等。对于内置类型和STL库中的数据类型，其实已经在标准库中重载好了它们对应的operator==函数。但是有一些数据类型，很可能是没有实现的。比如我们自己写的日期类。又或者有时候比较方式不是我们想要的效果(如pair类的比较)。

所以有些情况下我们需要自行实现相等比较。但是对于个别类型来讲已经实现好了，直接使用库里面的重载过的就行。

有两种方法解决：
1.自行编写仿函数，在哈希表的实现中再多加一个模板参数，专门用来判断关键字相等问题。
2.自行重载operator==函数，这样子就不用写仿函数。

标准库里面使用的是第一种。其实这是很合理的。因为有时候传来的数据类型的源码我们不能进行修改的，但是又没有实现重载。所以自然需要自行调用仿函数了。

这两个系列的容器就先讲到这，没看懂不要紧，后续我们再回过头来看。

还需要多说一句的是：在本篇文章中，为了方便实现，默认所有的传入的数据都已支持相等的重载。其实加上也不难，但重点还是在于理解。为了方便所以选择第二种方式。

哈希的引入

哈希(hash)又称散列，是一种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进行快速查找。

这大概是什么意思呢？

就是现在有一些数据要进行存储。如果用序列式容器(如list、vector等)存储就会有一个问题，就是查找的效率特别特别低。查找效率是O(N)。当N特别大的时候，效率特别低下。

对此有人发明了各种各样的搜索树，成功地将搜索效率和插入效率都整到了O(LogN)级别，这是质的飞跃。但是能不能更快呢？达到O(1)级别。

所以就有人发明了哈希的概念。对于红黑树或者是AVL树，还是要满足太多规则。特别是搜索树的规则，导致了插入和搜索的时候必须走树高度的对数次才能找到插入。

但是我们更希望的是，直接通过一个映射关系，就像函数那样，传入一个关键字，就能知道对应的位置。这样子不就是O(1)吗？哈希就是这个意思。就是将所有的关键字以一种特殊的映射方式，能够找到对应的位置存储。其实就是将这些数据分散到一个表上。每个关键字都对应表上的一个位置。这就是散列的思想。

散列的一些基本概念

前面我们引入了哈希这个思想。但是在实现哈希表之前，我们还是得知道一些基本概念。

哈希表的本质是一个表。为了实现快速的搜索和插入，对于底层容器的选择就极为重要。必须能够通过某个操作快速定位。需要支持随机访问。有这个思想的容器就是vector或者deque了。因为它们的迭代器都是随机迭代器，支持随机访问。且重载了operator[]。

在SGI-STL30版本下选的是vector，其实用vector是最方便的。因为我们更熟悉这个容器，且deque虽然支持随机访问，但是在访问中间数据的时候是远远不如vector的效率的。使用哈希的思想本质上就是为了快速查找和插入。所以这里选择使用vector的适配器模式。

将Key转成整形和哈希函数

现在来解决第一个问题，为什么要将关键字Key转成整形？

哈希表本质上也是一个类模板。里面存储的数据是什么是不知道的。对于关键字的类型更是如此。类模板最重要的就是泛型编程。就是要将所有的不同形式转化为相同形式。

我们再回顾一下哈希的思想：将关键字通过一定的映射方式，在哈希表中找到位置进行存储。其实就是在一个vector中通过下标来找位置。

假设关键字Key通过映射方式F得到下标，下标必然是个整形。所以很自然而然的想到了应该将关键字已某种形式转入为整形后再来通过映射F，这样子不就构成了Key到下标的映射了吗？至于本身就是整形的数据就不需要再转化了。直接映射。这点很简单，通过一个仿函数控制一下就好了。就跟我们在封装map和set的时候一样，为了能够让不同数据比较，通过仿函数KeyOfT来取出数据的关键字。

但是这里需要说明的是，转成整形的方法有很多种。可以自由选择。但是需要尽量选择比较散的映射关系？什么意思呢？比如对于string类，我们可以选择将所有的字符的ACSII码加起来，代表一个string转化的整形。但是对于“abcd”，“acbd”这两个来说，使用这个方法会导致它们算出来的整形一样。那通过同一个映射方法必然是会导致二者在同一个位置上的。这一点就是我们后面要讲的哈希冲突概念。这会极大影响效率。这样算出来的整形必然是比较集中的。所以我们尽量需要选择一些算出来比较散的转整形函数。

在此还提一下，一般转整形的函数我们称之为Hash。

第二点：何为哈希函数？
哈希函数其实就是我们上面讲的映射方式F。学过高数的都知道，函数抽象化后其实就是映射关系。通过关键字转化为整形后，我们就是通过哈希函数来将整形转化为一个下标。

大致关系可以如下图所示：

对于某个数据，我们不知道是什么类型，所以要先取出它的关键字。然后通过Hash转化为整形后，最后通过哈希函数将这些关键字转化后的整形下标尽可能地散开分布在哈希表上。然后通过下标插入数据。这就构成了从数据到位置地映射关系。

只不过这里的映射关系是比较复杂的。可能会有多次映射。

哈希冲突

这个是怎么一回事呢？

哈希冲突的本质就是有一些数据会堆积在同一个位置。这是无法避免的。因为映射方式有很多种。但是数据量比较大或者比较巧合的情况下，肯定会有数据挤到同一个位置去。这个时候应该怎么办呢？

首先我们得明白一个道理，就是虽然哈希冲突是不可避免的。但是还是需要尽可能的选取一些比较优秀的哈希函数，使得数据分布在哈希表中是比较分散的。这样子效率较高。但是冲突毕竟是不可避免。所以还是得解决这个问题。

解决方案主要有两种f方法，开放定址法和链地址法。

当然在这里一时半会儿也讲不清楚，这些内容将放在后面部分来讲解。

负载因子

假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么 ，负载因子有些地方也翻译为载荷因子/装载因子等，他的英文为load factor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；

注意这里的哈希表大小M其实就是内部vector的size()函数。就是当前表有多少个可用空间。

开放定址法和链地址法

先前我们说过，哈希表的实现有两种方式，一种是开放定址法，另一种是链地址法。

我们先来讲讲什么是开放定址法：
Leetcode 387 找出字符串第一个唯一字符

就以这个题为例，这题的思想其实很简单。字符串里面也就是一些ascii码值。总共是256个，那我们就可以开辟一个256大小的char数组，将ascii值从头到尾遍历一遍，出现一次，就在数组对应的位置记录一次出现。全部记录完后，就再遍历一次字符串，第一个遍历到的字符在数组中对应数字是1的就是字符串的第一个唯一字符。

这其实和我们之前实现的计数排序的很像。其实这种就是开放定址法。就是每个关键字对应着的数组中一个确定的位置。

但是开放定址法会出现哈希冲突的问题。

再来说说何为链地址法。链地址法的哈希表也被称为哈希桶：

就是一个数组，但是每个数组指向的其实是一个链表。就很像数组中每个位置下面挂着一个桶，然后这个桶里面装的都是链表节点。这样子就不会起到哈希冲突了。算出来如果是一个位置就下面挂着。

但是很多人会说，如果一个链表过长怎么办？这点不需要担心。

在java中是这样解决的：就是当一个链表数据超过8个的时候，会将链表一个个的插入到红黑树中。此时对应的位置放的就不是链表节点的指针了，而是指向红黑树的指针。但是这个方法比较复杂，那是否还有别的解决方式呢？

有的，我们可以手动控制一下。像c++中是这么解决的：即控制负载因子。一个链表比较长的时候必然会导致负载因子过大。对于哈希桶发来说，负载因子是可以大于1的。c++中就是将负载因子控制在1。一旦负载因子到1了就需要对表进行扩容。这个时候就需要对所有的节点进行重新映射。由于表的空位变多，自然会导致数据被分散。所以就解决了这个问题。

本文中就采取第二种方式进行实现。

哈希函数的选取

无论是开放定址法还是链地址法，都面临着哈希函数如何选取的问题。假设已经获取到数据的关键字Key了，应该采用何种映射方式映射到表的不同位置呢？

就算哈希桶能解决哈希冲突的问题，但是我们还是更希望能够设计出将数据较均匀的分布在表中的M个空间当中。虽然这是很困难的，但是我们需要尽可能往这个方面考量。

除法散列法/除留余数法

先来将第一种方法，即除法散列法。其实也叫除留余数法。什么意思呢？

除法散列法也叫做除留余数法，顾名思义，假设哈希表的大小为M，那么通过Key转化的整形除以M(表的空间)的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

这种还是能够较为分散的把数据分散到哈希表中的。这也是实践中用的比较多的方式。本文也是采取这种方式对哈希表和哈希桶进行实现。

但是还是有一些问题需要注意的：

1. 当使用除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是 ，那么key%2^x的本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如：{63 , 31}看起来没有关联的值，如果M是16，也就是 ，那么计算出的哈希值都是15，因为63的⼆进制后8位是 00111111，31的⼆进制后8位是 00011111。如果是 ，就更明显了，保留的都是10进值的后x位，如：{112, 12312}，如果M是100，也就是 ，那么计算出的哈希值都是12。这种现象是很容易发生的。

我们可以这么理解，因为这样选取的M，会导致Key参与运算的位减少了。比如63和31取模16，真正参与运算的只有后面五个比特位，这样子很容器导致哈希函数映射出来的值会有很大概率会冲突。所以尽量不要选这些数。

2. 经过研究者的不断探究，发现当使用除法散列法时，建议M取不太接近2的整数次幂的一个质数(素数)。至于这个质数怎么取等一下来说。这个证明需要比较高的数学水准。就和希尔排序一样。证明过程可能会涉及一些当前我们不知道的数学知识。感兴趣的可以了解一下。

3. 需要说明的是，并不是说不能让M的大小为2的幂或者10的幂。各个语言的实践中也是八仙过海，各显神通，Java的HashMap采用除法散列法时就是2的整数次幂做哈希表的大小M，这样玩的话，就不用取模，而可以直接位运算，相对而言位运算比模更高效一些(在计算机底层种除法和取模效率是比较低的)。

但是java的实现不是单纯的去取模，比如M是2^16次方，本质是取后16位，那么用
key’ = key >> 16 ，然后把 key 和 key’ 异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀⼀些即可。所以我们上面建议M取不太接近2的整数次幂的一个质数的理论是大多数数据结构书籍中写的理论而已。但是实践中可能会不同的实现，我们需要灵活运用，抓住本质去理解，而不能死读书和死记硬背。

本质上哈希函数的选取就是选取让key的更多位参与运算的那一个。

乘法散列法

乘法散列法对哈希表大小M没有要求，他的大思路第一步：用关键字 Key转化的整形 乘上常数 A (0<A<1)，抽取出 k*A 的小数部分。第二步：后再用M乘以k *A 的小数部分，再向下取整。

比如M = 53， Key = 15，A = 0.63：得到的下标就是：
(0.6 * 15) = 9.45，取出小数部分0.45再乘以M = 0.45 * M = 23.85。向下取整得到23。
一定是向下取整。向上取整会面临着越界的风险。

所以在此基础上15映射的位置是23。

其实这么做也是有道理的。就是想通过key的乘法操作得到一个值，这个值又必须在[0, M)之间。那得到的值必然是大于0，小于1的数字。因为这样才能保证在表中选的位置是在范围之内的。所以就通过如上的操作，用某种方式对Key操作，得到小数。再用这个小数乘M在表中选取位置，由此构成了从Key到存储位置的映射。

这个A是选取(0, 1)区间的数字。但是我们还是秉承着分散的概念，需要选取一个合适的A。使得从key * A得到的小数再乘M是尽可能分散的。

h(key) = floor(M × ((A × key)%1.0))，floor为向下取整函数。
还是经过研究者的一系列研究，发现A取黄金比例数的时候是最合适的：
即A = ( sqrt(5) − 1)/2 = 0.6180339887，一般来说取个0.618就足够了。

全域散列法(了解)

如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，比如，让所有关键字全部落入同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。

这种方法了解一下即可：
h(key) = ((a × key + b)%P )%M，假设哈希函数是这一个。我们将这个函数公布出去。我们对于P的选取必定是一个大于M的质数。为什么？

因为任何数字对M取余，得到的答案只可能是[0, M - 1]，如果P小于M，(a × key + b)%P 得到的答案一定 <= P - 1 < M。

但是对M取余的数字P如果一定是小于M的，那就会导致算出来的结果就是P。那么这就出现问题了。上面的那个哈希函数算出来的下标值 = P，小于M，那就会导致表中大于P的位置的下标是永远无法被映射到的。这是很浪费的。所以P的选取需要是大于M的质数，又因为希望能够更加的散，所以M还是得选取一个质数。

这个时候，P需要选⼀个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。假设P=17，M=6，a = 3， b = 4, 则 h34 (8) = ((3 × 8 + 4)%17)%6 = 5。

但是这样子怎么样做到防止别人攻击呢？难道是每次对Key转化的整形选取不同的哈希函数来映射吗？当然不是。同一个表里面哈希函数必须相同，要不然映射关系就全乱了，就没有什么所谓的哈希的概念了。

这里的随机是指系统的启动的时候。数据可能是存储再磁盘或者数据库中。假设系统启动后要把数据全部导入到哈希表上，那就要确定好这一次系统启动后的哈希函数。
比如第一次启动选取P = 17， M = 6， a = 3, b = 4
但是关了之后下一次选取的时候就可能是P = 25， M = 15， a = 5, b = 2

这里的随机是指每次系统启动的时候对于这个哈希函数有随机选取的操作，只不过在确定选好后，只要系统不关闭，就不会再改变哈希函数了。因为每次运行的时候必须遵循同一个哈希函数。这样子就很难再被外界进行攻击了。因为这四个项可以任意取，想要针对每一种情况进行设计攻击数据集基本上是没什么可能。

其他方法（了解）

上面的几种方法是《算法导论》书籍中讲解的方法。
《殷人昆 数据结构：用面向对象方法与C++语言描述 （第二版）》和 《[数据结构(C语言版)].严蔚敏_吴伟民》等教材型书籍上面还给出了平方取中法、折叠法、随机数法、数学分析法等，这些方法相对更适用于一些局限的特定场景，有兴趣可以去看看这些书籍。

针对于开放定址法的哈希冲突解决方案

前文提到，对于开放定址法必然会存在哈希冲突的问题。因为哈希函数不可能完全做到能够把关键字非常均匀的映射到表中的每一个位置。必然是会有映射到同一个地方的。但是链地址法不存在这个问题。我们这个部分就是需要来重点讲一下，针对于开放定址法如何解决。

线性探测

针对于开放定址法，哈希冲突的时候肯定是没办法在表中一个位置存储多个值的。这个时候可以采用第一种方法——线性探测：

线性探测就是，从发生冲突的第一个位置开始，依次向后探测位置，直到找到空的位置再来存入。如果走到哈希表的尾部了还没有找到空的位置，就需要绕到表头找。

h(key) = hash0 = key % M，hash0位置冲突了，则线性探测公式为：
hc(key,i) = hashi = (hash0 + i) % M。i = {1, 2, 3, …, M − 1}

一般来说，对于开放定址法的哈希表的负载因子，我们是不会让它等于1的时候才扩容的。一般是在0.7左右就需要进行扩容了。插入数据的时候一定是保证有空位的。所以最多探测M - 1次就能找到空位进行插入。只不过这种情况不太好。所以在负载因子达到一定程度的时候就进行扩容，这样就能减少线性探测的次数。

下面演示 {19,30,5,36,13,20,21,12} 等这一组值映射到M=11的表中：

注：哈希函数选择除法散列法

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，
h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1

由图得：
插入19的时候直接放在下标8的位置。
插入30的时候算出来是也是8，但是由于已经被19占位，所以向后探测了一次就发现有空位，所以30放在的是下标为9的位置。
以此类推…

但是有人会疑问，这样子好像不方便通过关键字Key来查找了。这是不需要担心的。查找的时候其实也是一样的，先算出正常应该放在的位置。如果那个位置与搜索的Key不同，也是进行线性探测就可以。直到遇到空的位置都没找到，那就是没有这个关键字。

探测的注意事项

现在我们已经大致掌握线性探测的方法了，但是还是有一些细节我们需要注意一下：

哈希表自然会有插入、删除等接口。但是学过顺序表的删除的都知道，其实顺序表的删除不是真的说把那个空间释放掉。

在栈里面直接让栈顶位置向栈底移动一个位置就可以，如果是vector，就是让表示数据结尾的位置向前移动一个位置。可以理解为间接删除。

但是在这个哈希表里，存储的顺序可不是线性的，这是一个关联式容器。这怎么处理呢？删除也没办法真的释放掉那个空间。所以我们需要对每个位置设定状态。

enum Status{EMPTY，EXIST,DELETE
}

所以我们需要确定一下当前位置是什么状态。如果是空的就可以插入。

这点是必须要做的。我们举一个例子就知道：

假设不设立状态，我们现在将30删掉。如果不设立状态，这个30必然还是在这个表里面的。如果现在插入一个41，经过哈希函数映射后得到：h(41) = 8，那就需要进行线性探测。如果不设立状态，按照正常的逻辑去比较是否为空，必然是探测到下标为4的位置。但问题是在我们认知的状态下，30是已经被删除的。这个位置是可以被插入的。所以应该插入到下标为9的位置才对。所以从这里来看，设立状态是非常有必要的。

又或者是查找的时候，如果不设立状态，那也是会被误导。因为数据不是真的被删除了，只是设立状态而已。如果判断一下key是否等于对应位置二段关键字，这当然会错。所以需要设立状态。在查找的时候，如果碰到空就停下，其他情况下还得继续往后找。因为没办法保证所要找的数据是不是给挤到后面的位置去了。

所以最后哈希表每个位置存储的就不只是数据了，应该是一个类，类里面有对应得数据，和当前位置在哈希表中的状态：

template<class T>
struct HashData{//数据T _data;//状态Status _state;
}

由于线性探测实现比较简单，本篇文章的开放定址法的代码将采用这个方式解决哈希冲突。

二次探测

但是线性探测会有这么一个问题：
线性探测的比较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1，hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。下⾯的⼆次探测可以一定程度改善这个问题。

因为线性探测得本身就是一个一个向后找位置插入，如果连续几个Key映射的位置都是一样的。这会堆积在一起。然后需要不断地线性探测。一旦聚集在一起，那么哈希表的各种操作效率就低得多了。最理想的状况就是不经过线性探测或者比较少的线性探测就能找到位置。

对此提出了二次探测的方法：
线性探测其实也叫一次探测，这是步长i的幂。一个一个找这太集中了。哈希表最大的特点就是散列，所以探测方式可以再散一点。所以有人提出了二次探测的方法：

从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下⼀个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。

h(key) = hash0 = key % M , hash0位置冲突了，则二次探测公式为：
hc(key,i) = hashi = (hash0 ± i² ) % M， i = {1, 2, 3, …, }。

但是这里和线性探测有点点区别。线性探测是单向查找，超过表尾就要回到表头。
但是二次探测是双向查找，对于超出表头的情况，需要回到表尾。

那怎么样回到表头/表尾呢？

假设当前hashi = hash0 + i² > M，这个时候回到表头就很简单了，取模就可以，直接让hashi = hashi % M。但是可以不用特殊判断。因为即使没超出表尾来取余，那次是的hashi一定小于M，对M取模一定是hashi。所以无论如何都直接取余就可以了。

但是针对于超出表头的情况怎么办呢？直接让当前位置 + M作为下一个坐标。其实这里就是和循环队列的时候是一样的。特殊判断一下就可以。

当然不太清楚的话可以举个例子：
假设某个表M = 11，现在hash0 = 2，向左边探测第二次的时候，hashi = hash0 - 4 = -2。
表头的坐标为0，也就是说，现在超出表头两个位置。所以hashi = -2的时候应该是表尾的倒数第二个数据才对。这个时候让 -2 + M = 9，这正好是倒数第二个位置的坐标。

这里我们就通过举一个实例来进行验证，感兴趣的可以多举几个例子。

二次探测的思想其实和线性探测差不多。只不过探测空位置更加分散而已。只需要注意上面说的探测的时候表尾和表头之间的位置转换即可。

双重散列(了解)

前面学的探测都是给定具体的步长的。双重散列就不一样了，在发生冲突的时候探测方式就不是通过i的幂次方来探测了。而是通过另一个哈希函数进行探测。

第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。
h1 (key) = hash0 = key % M , hash0位置冲突了，则双重探测公式为：
hc(key,i) = hashi = (hash0 + i ∗ h2 (key)) % M， i = {1, 2, 3, …, M}。

但是这个是有要求的：
要求h2 (key) < M且 和M互为质数，有两种简单的取值方法：

1. 当M为2整数幂时，从[0，M-1]任选⼀个奇数；
2. 当M为质数时，h2 (key) = key % (M − 1) + 1

保证h2 (key)与M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群，若最大公约数p = gcd(M, h1 (key)) > 1，那么所能寻址的位置的个数为M/P < M，使得对于⼀个关键字来
说无法充分利用整个散列表。

举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的位置为{1, 4, 7, 10}，寻址个数为12/gcd(12, 3) = 4。

这背后蕴含着非常多的数学证明知识。可以只做了解。因为实际应用中很少这么用。

代码实现部分

上面都是哈希表的理论知识，我们还是应该着手实现一下。也方便后续实现STL库中的那两个容器。在这里先声明一些细节：

1. 本篇文章重点是掌握哈希表的思想和简单的实现，了解原理。所以对于存储的数据直接就让它为pair类型。对类型的泛化和红黑树一样，放在封装容器来实现。
2. 哈希函数选取的是除法散列法，当然可以选择其他。这个由实现者自行决定。
3. 对于开放定址法的实现部分，解决哈希冲突直接采用线性探测，方便实现。
4. 实现的哈希表不支持数据的冗余。
5. 对于哈希表的实现要多加一个仿函数，用来将Key转化为整形。这个我们下面来说。

开放定址法的代码实现

现在我们开始开放定址法的实现。

基本结构和前置准备

我们来直接看结构：

enum Status {EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData {pair<K, V> _kv;//这个状态是必须存在的 重点放在博客上去讲解Status _state = EMPTY;
};template<class K>
struct HashFunc {size_t operator()(const K& key) {return (size_t)key;}
};template<>
struct HashFunc<string> {//由于字符串在hash内用的是很多的 直接特化一个版本//BKDR哈希算法size_t operator()(const string& str) {size_t hash = 0;for (auto ch : str) {hash += ch;hash *= 131;}return hash;}
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:private:vector<HashData<K, V>> _table;size_t _DataNum = 0;//存储数据个数
};

这是和适配器模式，底层存一个vector。这个vector就来存放数据和状态。

这里我们面临着第一个问题：就是传入的Key很可能不是整形，有可能是string，也有可能是自己实现的日期类等。这些类型是没有办法直接转为整形的。所以我们需要一个仿函数对传入的Key进行转整形操作。也就是模板参数里面的Hash。

对于这个转整形函数，如果编译器是支持直接走隐式类型转换变整形的，那就直接强转整形的数据。但是有一些自定义类型是没办法直接强制转换的。

一般来说，可以让一个类里面自己实现好转整形操作，然后传入调用就好了。但是不能完全指望类里面有完成这些事情。所以还是需要自行写仿函数。针对于string这种用的比较多的数据类型，我们可以考虑对他的转整形仿函数进行一个特化。

对于string我们使用的是BKDR算法，就是认为字符串是一个很长的整形。每一位上都有权重。我们常见的二进制的权重是2的幂，十进制是10的幂。对于string来讲，把它认为是131是比较合理的。当然这也是通过数学证明的。感兴趣的可以去看一下。

对于其它的类的转整形函数，可以自行实现一下。尽量能够让数据较为分散就可以了。

我们采用的是除法散列法，前面提到过，尽可能地将表的空间M设置为一个比较原理2地整数次幂地一个质数。这个应该怎么操作呢？

打开SGI_STL30版本地源码，发现库中是提供一个质数表的。我们只需要传入一个数，就能返回表中第一个大于等于这个数的质数。

也就是说，刚开始传一个0进去，返回的就是53。
当需要扩容的时候，就传当前空间个数 + 1进去，就能返回下一个质数。

这样子就很好的解决了这个问题，在本文的实现中也会以这个为标准实现：

public://为了保证表的容量数尽量为一个整数，且每次扩容尽可能的达到二倍扩容//这里采用和c++STL库中一样的方式，列一个质数表inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list +__stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}//当然也可以写其它的构造HashTable():_table(__stl_next_prime(0)),_DataNum(0){}

对于此类型的哈希表来讲，底层只有以恶搞vector和一个表示数据个数的变量。其实是不需要写析构等函数的。因为内置类型没有指向资源，自定义类型vector是已经实现了析构等操作，编译器会自己调用。所以写一个哈希表的默认构造就可以了。

const size_t Size() const{return _DataNum;
}const size_t Capacity() const {return _table.size();  
}

当然可以把当前数据个数和表的空间个数的接口给出来。

最后实现哈希表最重要的操作：增、删、查。修改其实不是在哈希表这一层来使用的，这点我们在后面封装unordered_set和unordered_map的时候再来细说。

插入接口

插入操作十分简单：

//实现insert
bool Insert(const pair<K, V>& kv) {//查找逻辑的使用if (Find(kv.first)) return false;Hash hash;size_t hashNum = hash(kv.first);//如果负载因子(存储数据量/空间数)比较大的时候，是需要进行扩容的。//Capacity()接口就是表的当前空间个数if (_DataNum * 10 / Capacity() >= 7) {//扩容HashTable<K, V, Hash> newTable;  newTable._table.resize(__stl_next_prime(Capacity() + 1)); for (size_t i = 0; i < Capacity(); ++i) {newTable.Insert(_table[i]._kv);}_table.swap(newTable._table);}//取模散列size_t hash0 = (hashNum % Capacity());//可能会有hash冲突的问题 ——》线性探测size_t i = 1; size_t hashi = hash0;while (_table[hashi]._state == EXIST) {hashi = (hash0 + i) % Capacity();++i;}_table[hashi]._kv = kv;_table[hashi]._state = EXIST; ++_DataNum;return true;
}

插入的实现非常简单。首先查找一下这个Key是否存在，如果存在时没办法进行插入操作的。虽然当前没有实现查找接口Find，但是逻辑不会变。先认为已经实现好了。后面再补就好。

将关键字Key通过仿函数Hash转化为一个整形变量HashNum。这个时候再来对HashNum进行取模操作得到hash0的位置。如果这个位置是EXIST状态，就需要进行线性探测。否则直接插入就好。然后让数据个数_DataNum自增就可以了。

但是也不是能够直接一上来就插入。还需要判断是否需要扩容。我们这里规定负载因子大于等于0.7就进行扩容操作。扩容后就会导致表的空间个数M改变，那么除法散列法的哈希函数也会跟着改变。也就是所有旧表中的数据都需要进行重新映射到新表中。

当然可以一个一个遍历原来的表，然后进行新的映射。走的逻辑就会下面部分的插入逻辑代码一样了。但是这样写代码太冗余了。既然逻辑一样就进行复用。所以开一个新的哈希表newTable，遍历旧表，将数据传给新表的Insert接口。最后交换两个表的vector就好了。数据个数大小不用交换。因为扩容的过程不会改变存储数据个数。

很多人会认为这是递归。注意这里不是。递归是自己调用自己。这里是自己的Insert接口调用自己的吗？很明显不是。这里是this->Insert()内调用newTable->Insert()。这是两个不同的类在调用Insert()接口。当然不是递归。这样子我们就完成了代码的复用，也完成了插入逻辑。

查找接口

直接来看代码：

HashData<K, V>* Find(const K& key) {Hash hash;size_t hashNum = hash(key);size_t hash0 = hashNum % Capacity();//线性探测size_t hashi = hash0;size_t i = 0;while (_table[hashi]._state != EMPTY) {//但是注意 这个时候key不知道传入的是什么，所以得自己支持重载 =//或者加一个仿函数(不方便改别人代码的情况下)//但是这里我的所有测试都是自己支持 重载的= if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key){//找到了return &(_table[hashi]);}++i;hashi = (hash0 + i) % Capacity();}return nullptr;
}

查找是根据关键字Key来找，也是按照哈希的思想查找。
先对Key转整形，再通过哈希函数获取位置。最后线性探测。

查找的时候，如果碰到空的，就说明找不到了。但是如果是碰到存在或者删除状态，那就不好说，因为不确定要找的数据是不是因为这些值给顶到后面部分去了。

查找的时候涉及一个问题，就是Key是否支持相等比较。我们在这里默认是支持的(也就是需要依靠类本身去重载operator==函数)。但是库里面是多一个模板参数的。也就是Equal，这是用来自行写支持Key的相等比较的仿函数。但是这里以了解原理为主，所以就不写这个仿函数了。需要自行对数据类型进行相等比较的重载。

还有一个就是我们前面说到的，这里的删除并不是真正意义上的删除。只不过是把哈希表那个位置的状态设定为DELETE。但是数据还是在表中的。所以不能单单认为Key和表中的关键字一样就认为是找到了，得判断一下状态。

删除接口

bool Erase(const K& key) {HashData<K, V>* ptr = Find(key);if (ptr == nullptr) {cout << "不存在可删除项" << endl;return false;}ptr->_state = DELETE;--_DataNum;return true;
}

删除操作就简单太多了。先判断一下是否能删除。如果有这个数据就将状态设置为DELETE就可以了，同时再让表中数据个数自减。这样子就完成了删除操作。

HashTable完整代码

enum Status {EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData {pair<K, V> _kv;//这个状态是必须存在的 重点放在博客上去讲解Status _state = EMPTY;
};template<class K>
struct HashFunc {size_t operator()(const K& key) {return (size_t)key;}
};template<>
struct HashFunc<string> {//由于字符串在hash内用的是很多的 直接特化一个版本//BKDR哈希算法size_t operator()(const string& str) {size_t hash = 0;for (auto ch : str) {hash += ch;hash *= 131;}return hash;}
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public://为了保证表的容量数尽量为一个整数，且每次扩容尽可能的达到二倍扩容//这里采用和c++STL库中一样的方式，列一个质数表inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list +__stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}HashTable():_table(__stl_next_prime(0)),_DataNum(0){}//其它的构造template<class K, class V>HashTable(const initializer_list<pair<K, V>>& itl) {auto Iit = itl.begin();while (Iit != itl.end()) {Insert(*Iit);++Iit;}}//实现insertbool Insert(const pair<K, V>& kv) {//理解hash表插入的本质是什么——博客上写if (Find(kv.first)) return false;Hash hash;size_t hashNum = hash(kv.first);//如果负载因子(存储数据量/空间数)比较大的时候，是需要进行扩容的。if (_DataNum * 10 / Capacity() >= 7) {//扩容HashTable<K, V, Hash> newTable;  newTable._table.resize(__stl_next_prime(Capacity() + 1)); for (size_t i = 0; i < Capacity(); ++i) {newTable.Insert(_table[i]._kv);}_table.swap(newTable._table);}//取模散列size_t hash0 = (hashNum % Capacity());//可能会有hash冲突的问题 ——》线性探测size_t i = 1; size_t hashi = hash0;while (_table[hashi]._state == EXIST) {hashi = (hash0 + i) % Capacity();++i;}_table[hashi]._kv = kv;_table[hashi]._state = EXIST; ++_DataNum;return true;}HashData<K, V>* Find(const K& key) {Hash hash;size_t hashNum = hash(key);size_t hash0 = hashNum % Capacity();//线性探测size_t hashi = hash0;size_t i = 0;while (_table[hashi]._state != EMPTY) {//但是注意 这个时候key不知道传入的是什么，所以得自己支持重载 =//或者加一个仿函数(不方便改别人代码的情况下)//但是这里我的所有测试都是自己支持 重载的= if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {//找到了return &(_table[hashi]);}++i;hashi = (hash0 + i) % Capacity();}return nullptr;}bool Erase(const K& key) {HashData<K, V>* ptr = Find(key);if (ptr == nullptr) {cout << "不存在可删除项" << endl;return false;}ptr->_state = DELETE;--_DataNum;return true;}const size_t Size() const{return _DataNum;}const size_t Capacity() const {return _table.size();  }private:vector<HashData<K, V>> _table;size_t _DataNum = 0;
};

哈希桶的代码实现

上面是通过开放定址法来实现的。但是开放定址法无论怎么解决哈希冲突的问题，本质都是内卷的。因为总是会有映射到同一个位置的多个数据。一旦出现这个情况，必然要进行探测位置。这就是你挤我我挤我的感觉。实际应用中，更常用的是链地址法：

template<class K, class V>
struct HashNode {pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}
};template<class K>
struct HashFunc{size_t operator()(const K& key) {return (size_t)key;}
};template<>
struct HashFunc<string> {size_t operator()(const string& str) {size_t hash = 0;for (auto ch : str) {hash += ch;hash *= 131;}return hash;}
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:using Node = HashNode<K, V>;inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list +__stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}HashTable() :_table(__stl_next_prime(0)), _NodeNum(0) {}  bool Insert(const pair<K, V>& kv) {if (Find(kv.first))return false;Hash hash;size_t hashNum = hash(kv.first);//负载因子为1的时候就进行扩容if (_NodeNum == Capacity()) {//扩容逻辑vector<Node*> newtables(__stl_next_prime(Capacity() + 1), nullptr);for (size_t i = 0; i < Capacity(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;// 旧表中节点，挪动新表重新映射的位置size_t New_hashi = hash(cur->_kv.first) % newtables.size();// 头插到新表cur->_next = newtables[New_hashi];newtables[New_hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtables);}size_t hashi = hashNum % Capacity();//头插Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_NodeNum;return true;}Node* Find(const K& key) {Hash hash;size_t hashi = hash(key) % Capacity();Node* cur = _table[hashi];while (cur) {if (cur->_kv.first == key) return cur;cur = cur->_next;}return nullptr;}bool Erase(const K& key) {if (Find(key) == nullptr)return false;Hash hash;size_t hashi = hash(key) % Capacity();Node* prev = nullptr;Node* cur = _table[hashi];while (cur) {if (cur->_kv.first == key) {//删除操作if (prev == nullptr) //头删_table[hashi] = cur->_next;else prev->_next = cur->_next;delete cur;--_NodeNum;return true;}prev = cur;cur = cur->_next;}return false;}size_t Capacity() const {return _table.size();}size_t Size() const {return _NodeNum;}private:vector<Node*> _table;size_t _NodeNum = 0;
};

哈希桶的实现是非常简单的。只需要把vector中每个链表存储的数据改成节点的指针就可。
和前面的开放定址法的区别也就是在于增删查的操作不太一样而已。

我们稍微讲解一下就可以：

1. 对于插入接口：
   使用了哈希桶的方法后，就不怕哈希冲突的问题了。直接插入到对应位置指向的链表就可以了。这里涉及一个问题：头插还是尾插？

为了实现插入到效率为O(1)，必然是头插。头插是十分方便的。对于插入的时候的扩容逻辑，这个是需要讲一下：会发现代码实现中并没有复用插入的逻辑。而是遍历旧表一个个的映射到新表去。为什么？

因为如果是复用逻辑，那就又要开新节点。在堆上开辟空间，特别是在数据量比较大的情况下，是很影响效率的。开放定址法敢这么用是因为它们的数据存储在栈区中，栈区对这些操作是高效多得多。但是当前我们所有的节点都是在堆区上存储的。所以最好的办法就是将旧表中的节点一个个的根据新的映射方式，挂到新的表上。也就是上面写的逻辑。

2. 对于查找接口：
   查找接口就很轻松了。找到对应映射的位置，对链表进行搜索就好了。也不用担心状态什么东西。直接比较Key是否相等就好。这也能看得出来哈希桶的效率是十分高的。

3. 对于删除接口：
   删除也简单，先判断是否存在。不存在删除失败。
   若是存在，就找到那个位置，但是删除链表的节点的时候需要注意，头删和其他位置的删除是不一样的，所以需要进行特殊的判断处理。

最后再来返回看unordered_set和unordered_map的使用：
会发现每一点涉及到的都进行讲解过了。如为什么Key要自行支持转整形，为什么Key要支持相等比较。这些下面都讲过。然后只需要根据这些基础的支持和适当查阅文档就可以学会使用了。但是这两个容器和set和map的差别不是很大，特别是在用法这一块。所以会使用map和set就会使用这两个容器。