数据结构——哈希表的实现
目录
1 哈希概念
1.1 直接定址法
1.2 哈希冲突
1.3 负载因子
1.4 将关键字转成整数
1.5 哈希函数
1.5.1 除法散列法 / 除留余数法
1.5.2 乘法散列法
1.5.3 全域散列法
1.5.4 其他方法
1.6 处理哈希冲突
1.6.1 开放地址法
1.6.1.1 线性探测
编辑 1.6.1.2 二次探测
1.6.2 代码实现开放地址法
1.6.2.1 扩容操作
1.6.2.2 Key不能取模的问题
1.6.2.3 插入一个数据
1.6.2.4 查找一个数据
1.6.2.5 删除一个元素
1.6.3 链地址法
1.6.3.1 解决冲突的思路
1.6.3.2 扩容
1.6.3.3 极端场景
1.6.3.4 插入一个元素
1.6.3.5 查找一个元素
1.6.3.6 删除一个元素
1.6.4 质数表
1 哈希概念
哈希（hash）又称散列，是一种组织数据的方法。从译名上来看的话，有散乱排列的意思。本质就是通过一个哈希函数把关键字Key跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进而能够快速查找。
1.1 直接定址法
当关键字的范围比较集中时，直接定址法就是一个非常简单且高效的方法，比如一组关键字都在 [0，99] 的这个范围之间，我们开一个100个数的数组，每个关键字的值直接就可以是存储位置的下标。再比如说一组关键字都在[a，z]的小写字母这个范围中，那么我们开一个26个数的数组，每个关键字的acsii码就可以是存储位置的下标，也就是直接定址法的本质就是用关键字计算出一个绝对位置或者相对位置。这个方法我们在计数排序部分就已经用过了。
直接定址法我们感觉它使用起来确实很方便，但是，直接定址法的缺点同样也是非常明显的，可以说是内存不够用，假设我们只有数据范围是[0，9999]的N个值，此时，我们要映射到一个M个空间的数组中（一般情况下M>=N），那么此时我们还需要借助哈希函数hf，关键字Key被放到数组中下标为hf(Key)这个位置上去，这里我们需要注意的是hf(Key)所计算出来的值必须是在[0，M)这个范围之内。
1.2 哈希冲突
直接定址法在将关键字映射到数组中不同位置的时候，其实还存在一个问题，就是两个不同的Key可能会映射到同一个位置中去，而这种问题我们将其称之为是哈希冲突，或者哈希碰撞。理想情况下是找出一个好的哈希函数以避免发生哈希冲突，但是在实际的场景中，冲突是绝对不可避免的，所以我们要在这里尽可能地去设计出优秀的哈希函数，减少冲突地次数，同时也要去设计出解决冲突地方法。
1.3 负载因子
假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子=N/M，负载因子有些地方也被翻译成载荷因子/装载因子等，它的英文为load factor。负载因子越大，哈希冲突地概率就越高，高间利用率就会越高；负载因子越小，哈希冲突的概率就越低，空间利用率就会越低。
1.4 将关键字转成整数
我们将关键字映射到数组中的某一个位置上，一般是整数好做映射计算，如果不是整数，我们就要想办法将这个关键字转化成整数，这个小细节我们后面在代码实现中再展示（其实都不用我们刻意的去实现一个关键字转化为整数的函数，因为大佬们已经都将关键字所有可能的存在形式转化成整数的这一所有的函数都实现了出来）。下面哈希函数我们在讨论时，如果关键字不是整数，那么我们讨论关于Key转化成整数的这个函数。
1.5 哈希函数
一个好的哈希函数应该让N个关键字被等概率的均匀的散布到哈希表的M个空间中，但是实际中却是很难做到的，但是我们也要尽可能地往这个方向上考量设计。（我们在下面写博客的时候就将各个哈希函数与其所产生的哈希冲突的解决方法结合在一起来写，这样写更有效）
1.5.1 除法散列法 / 除留余数法
1>.除法散列法又名除留余数法，顾名思义，假如哈希表的大小为，那么通过Key除以M的余数作为余数来作为映射位置的下标，也就可得哈希函数：h(Key)=Key%M。
2>.当我们使用除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等（如果我们大家在这里认真地去发现的话，不难会发现Key%2^x，本质上就相当于保留Key地后x位（2进制），如果后x位一样的值，由此计算出来的哈希值就是一模一样的了），这样会造成冲突。比如：63和31这两个值，假如M是16（2^4，保留二进制的后4位），那么这样的话，计算出来的哈希值均为15，63的二进制后8位是00111111（二进制1111的十进制是15），31的二进制后8位是00011111。如果是10^x的话，结果那就会更明显了，保留的都是十进制的后x位，如：112和12312这两个值，假如M为10^2，那么计算出来的哈希值均为12。
3>.当使用除法散列法时，建议M取不太接近2的整数次幂的一个质数。
4>.需要说明的是，除留余数法在实践中也是八仙过海，各显神通，Java的HashMap采用除法散列法时就是用2的整数次幂去做的哈希表的大小M的，这样玩的话，它并没有像我们上述所讲的那样，采用取模运算，而是直接采用位运算的方法，位运算相当于取模运算来说效率会显得更高一些。但它不是单纯地去取哪几位，比如M是2^16，本质上最终得到的是数字二进制的后16位，但是通过我们前面所讲解过的知识可知，这样是不行的，Java自然也知道这一点，因此为了避免这种情况，它没有将二进制的后16位作为哈希表，而是又求了Key的前16位，然后将这两个值进行异或操作，最后将这个异或的结果作为了哈希值，例：
也就是说这里打破了那个最后几位相同的不足，我们映射出来的值还是在[0，2^16]范围之内，但是这里尽量要让Key所有的位都参与运算，这样映射出来的哈希值就会显得更均匀一些，我们上面建议M取不太接近2的整数次幂的一个质数的理论是大多数的数据结构的书籍中写的理论，但在实践中，灵活运用，抓住本质。
OK，回到我们这里的C++中来，我们上面是采用这个除法散列法去作为哈希函数的，通过前面方法的实现步骤我们可以得知，不同的值是极有可能映射到表中的同一个位置的，但是，我们一个位置上只能存储一个数据，这就引发了哈希冲突，目前为止，有2种解决方法，这个我们稍后再讲，这里先将哈希函数这一部分讲完。（后面的三种方法以及刚刚讲解的这种方法我们只需简单了解一下即可，不要求大家重点掌握）
1.5.2 乘法散列法
1>.乘法散列法对哈希表⼤⼩M没有要求，他的⼤思路第⼀步：⽤关键字Key乘上常数A(0<A<1)，并抽取出Key*A 的⼩数部分。第⼆步：后再⽤M乘以Key*A 的⼩数部分，再向下取整。
2>.h(Key)=floor(M*((A*Key)%1.0))，其中floor表⽰对表达式进⾏下取整，A∈(0,1)，这⾥
最重要的是A的值应该如何设定，Knuth认为A = ( 5 − 1)/2 = 0.6180339887....(⻩⾦分割点])⽐较好。
3>.乘法散列法对哈希表⼤⼩M是没有要求的，假设M为1024，Key为1234，A = 0.6180339887, A*Key=762.6539420558，取⼩数部分为0.6539420558, M×((A×Key)%1.0) = 0.6539420558*1024 =669.6366651392，那么h(1234) = 669。
1.5.3 全域散列法
1>.如果存在⼀个恶意的对⼿，他针对我们提供的散列函数，特意构造出⼀个发⽣严重冲突的数据集，⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决⽅法⾃然是⻅招拆招，给散列函数增加随机性，攻击者就⽆法找出确定可以导致最坏情况的数据。这种⽅法叫做全域散列。
2>.hab (key) = ((a × key + b)%P )%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。
3>.需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。
1.5.4 其他方法
1>.上⾯的⼏种⽅法是《算法导论》书籍中讲解的⽅法。
2>.《殷⼈昆 数据结构：⽤⾯向对象⽅法与C++语⾔描述 （第⼆版）》和 《[数据结构(C语⾔版)].严蔚敏_吴伟⺠》等教材型书籍上⾯还给出了平⽅取中法、折叠法、随机数法、数学分析方法等，这些⽅法相对更适⽤于⼀些局限的特定场景，有兴趣可以去看看这些书籍。
1.6 处理哈希冲突
1.6.1 开放地址法
在开放地址法种=中所有的元素都放到哈希表里，当一个关键字Key用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储，开放地址法中负载因子（表中存储值得个数 / 哈希表的大小）一定是小于1的，这里的规则有3种：线性探测，二次探测，双重探测（这里我们不讲这个规则，既不常用又不好动，因此我们这里只讲解前两种规则）。
1.6.1.1 线性探测
1>.从发生冲突得位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾的话，则回绕到哈希表头的位置继续往后找。
2>.h(Key)=hash0=Key%M，若hash0这个位置冲突了（也就是已经有数据存在了），则线性探测公式为：hc(Key，i)=hashi=(hash0+i)%M，i={1,2,3...,M-1}，因为负载因子始终要保持<1，则最多探测M-1次，一定能找到一个存储Key的位置。
3>.线性探测的比较是简单且容易实现的，线性探测的问题假设，hash0这个位置连续冲突，hash0，hash1，hash2位置均已经存储数据了，后续映射到hash0，hash1，hash2，hash3位置的值都会去争夺hash3这个位置，这种现象叫做群积（1.6.1.2中的二次探测可以一定程度上解决这个问题）。
4>.下面我们来演示{19，30，5，36，13，20，21，12}这一组值映射到M=11的表中。
1.6.1.2 二次探测
1>.从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾的话，则会回绕到哈希表头的位置上；如果往左走到哈希表头，则回绕到哈希表尾的位置。
2>.h(Key)=hash0=Key%M，hash0的位置冲突了，则第二次探测的公式为：hc(Key，i)=hashi=(hash+-i^2)%M，i={1,2,3...,M/2}。
3>.二次探测当hashi=(hash-i^2)%M时，当hashi<0时，需要hashi+=M。
4>.下面就来浅浅地演示一下{19，30，52，63，11，22}这组值映射到M=11地表中。
OK，上述的两种开放地址法是应对哈希冲突的一种比较简单的一种方法，相当来说是比较好理解的。
1.6.2 代码实现开放地址法
我们这里讲的开放地址法在实践中使用的并不多，我们后面会讲的链地址法，实践中使用的次数更多的是链地址法更多的是链地址法，开放地址法解决冲突不管是用线性还是二次，它最终都是去占用别的元素的空间，也就是说占用的均为哈希表中的空间，始终都会存在互相影响的问题，效率提升不上去。
我们在正式开始写哈希表的一系列操作时，我们先来看一下哈希表的结构，我们的这个代码是选择使用开放地址法中的线性探测这个方法做了一个简要的分析，它难免会发生位置冲突，进而去占领别的元素的原本地盘，根据这个方法，我们来捋一下思路，如果当前的这个元素元素的位置存在且没有元素，那么这个位置就归这个元素了，反之，要从这个被映射的位置开始，不断地往后去找一个存在且为空的位置去插入这个元素，既然这样的话，那么我们的查找思路就是从当前这个被映射的位置开始不断地往后找，直到遇上了一个没有存放数据地位置（要查找地那个元素绝对在被映射地位置和第一个遇到的空位置之间），删除元素的操作在这里和查找元素的操作如出一辙了，OK，以上思路就是我们实现的主要思路，其实说到这里还有一个小问题，我们来通过前面所讲解的线性探测的那个例子来说明一下这个问题，这里我先提前来为大家说一下，我们除了要写一些基本的结构以外，还要另外再写一个枚举来标明一下当前这个位置的状态：
OK，好，如上图所示，我们这里将30这个元素直接给删除了的话，此时我们若再通过find函数去找20这个元素的话，就会找不到了（我们这里要知道的是，20这个元素原本的位置其实并不是在下标为10的这个位置，而是在下标为9的这个位置），我们这里用我们前一页中所说的查找的思路来顺一下，先通过20这个元素来找到它原本被映射的位置，这里是下标为9的位置，然后我们再从下标为9的这个位置往后找，直到遇到最后一个空位置，按照我们上面那个哈希表来看的话，下标为9的那个位置就是一个空位置（这里其实用空位置的这个说法并不准确，因为我们是无法将某一个空间中所存放的数据给彻底地删除掉的，只能说是用另一个毫不相关地数据去替换掉我们这里的这个原有的数据），编译器在这里就不会再去后面继续找了，直接返回，因此查找就失败了，但其实20这个元素是存在的，基于这个原因和我们无法判断这个位置是否是我们上面思路中的空位置，因此，我们在这里决定去定义一个枚举类型用来标记各个空间中存储值的状态。
enum State//写一个枚举来标记空间中存储值的状态。
{
EXIST,//这个位置有值，也就是这个位置已经有数据了。
EMPTY,//这个位置没有元素。
DELETE//这个位置原来是有元素存在的，被删除了，因此，这个位置就没有元素了。
};哈希表中每个元素中除了有存放数据的空间，还要有一个枚举的空间，由于是多个数据变量，因此这里将哈希表的元素用一个类封装起来。
template<class K,class V>//这里用模板，因为我们前面讲过unordered_set和unordered_map的使用，它们两个的底层用的就是哈希表，因此存放数据的那个变量我们这里暂时使用成pair类类型的变量。
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;//建立好一块空间后，它的内部是没有存储我们想要的那个数据的，因此默认为空(EMPTY)
HashData(const pair<K, V>& kv)
:_kv(kv)
{ }
};如上述代码所述，当我们给每个位置加上一个状态标识{EXIST，EMPTY，DELETE}，这样我们在删除30的时候就不用再删除值了，而是把状态改成DELETE就可以了，那么我们在查找20的时候就是以遇到EMPTY为结束的条件，就可以找到20这个元素了。
1.6.2.1 扩容操作
我们这里用的是除留余数法的那个哈希函数，这个哈希函数要求我们每次扩容的空间个数取不小于2的整数次幂的一个质数。而且我们这里将哈希表负载因子控制在0.7，当负载因子到0.7以后我们这里就需要继续扩容操作了，我们这里还是按照2倍扩容，但是同时我们要保持哈希表的大小是一个质数，第一次开的空间个数是一个质数，那2倍之后就不是质数了。那么如何解决这个问题呢？一种发案就是上面除法散列法中我们讲的Java的HashMap中使用的2的整数幂，另一种发案就是sgi版本的哈希表使用的方法，给了一个近似2倍的质数表，每次去质数表中去获取扩容后的大小。（我们这里暂时就先不将这个质数表的代码给大家展示出来了，给大家简单说一下质数表这个函数的函数名：__stl_next_prime(unsigned long n);这个函数的功能就是根据当前哈希表的大小来找到下一次扩容后的哈希表的空间大小，并返回该大小的值，后续会说，这里我们暂时只需知晓它的作用即可）
1.6.2.2 Key不能取模的问题
当Key是string / Date等类型的数据时，Key无法进行取模（取模操作仅限于整数），那么我们需要给HashTable增加一个仿函数，这个仿函数支持把Key转换成一个可以取模的整形数据，如果Key可以转换成整形并且不易冲突，那么这个仿函数就用默认的参数（缺省值）即可，如果这个Key不能转换成整形，我们就需要自己实现一个仿函数去传给这个参数，实现这个仿函数的要求就是尽量Key的每个值均要参与到计算中去，让不同的Key转换出整形值不同。string做哈希表的Key非常常见，所以我们在这里可以考虑把string特化一下。我们下面用代码来实现出这个将Key转换成整形数据的仿函数：
template<class K>//我们这个仿函数的作用是将Key转化成整数类型，而通过我们前面的学习，我们得知这个Key有很多种类型的可能，因此这里使用模板。
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;//直接将其转化成整数类型，这里我们只是进行模拟实现的操作，不需要实现的就和库中的一模一样，因此这里我们就简单点，一笔带过就好了。
}
};//string做Key的场景我们是比较常见的，因此，我们在这里考虑把string给特化一下。
template<>
struct HashFunc<string>//当我们将HashFunc当作第三个模板参数给哈希表，若string作为Key传过来并且调用这个仿函数进行整形转换操作时，调用的不是上面的那个operator()，而是接下来的这个operator()。
{
size_t operator()(const string& key)
{
//字符串转换成整形操作，我们这里有多种方法可以选择，如：可以将这个字符串的各个字符的ascii码相加起来，但是直接相加的话，类似"abcd"和"bcda"这样的字符串计算出的整数值是相同的，这里我们可以使用BKDR(计算机领域的一位大佬)哈希的思路，用上一次计算所得的结果去乘以一个质数，这个质数一般取31，131等效果会比较更好(这里我们取131作为那个质数)。
size_t amount = 0;
for (auto ch : key)
{
amount *= 131;
amount += ch;
}
return amount;
}
};OK，好的，有了上面的基础常识后，我们接下来用线性探测的方法来实现一下哈希表的一些基本操作先来实现一下哈希表的一个整体框架：
template<class K,class V,class Hash=HashFunc<K>,class KeyOfT,class Pred=equal_to<K>,class Alloc=allocator<K>>
class HashTable
{
public:
HashTable()
{
//通过我们前面所讲述过的知识可以得知，在使用哈希表时，我们是要将一个个数据全部存放到哈希表中，既然是存放，那么就得有空间，因此我们在刚刚建好一个哈希表的对象后，就要立马创建好相应的空间出来，因此我们在构造函数中要写一个开创空间的步骤。
_tables.resize(__stl_next_prime(_tables.size() + 1));//开创一个质数大小的空间，从质数表中去取要开创空间的大小，用resize函数去开创，至于为什么要传"size()+1"而不是"size()"我们后面会讲到。
}
private:
vector<HashData<K, V>> _tables;//哈希表的各个操作都是基于底层封装的那个顺序表实现的。
size_t _n = 0;//记录存储的数据个数。
};1.6.2.3 插入一个数据
bool Insert(const pair<K, V>& kv)//这里我们要插入一个HashData类型的元素，按照道理来说，Insert这个函数的参数应该是一个HashData类型的引用才对，但是我们这里的参数却是一个pair类型的变量，有些同学在这里会有一些疑惑，这时为什么呢？这个问题其实和我们的空间开创有关，通过我们上述的代码实现可以得知，在哈希表的实现中，我们无论是空间的开创还是对原有空间的扩容操作，我们这里都是使用resize这个函数在这里进行操作的，而resize函数的功能是将数据的个数扩大到n个(n是传过去的一个整数类型的数据，如果忘了的话可以参考前面的在章节中对resize这个函数的讲解)，也就是说，我们开创了一个哈希表类型的对象后，编译器不仅仅是开创了相应大小的空间，每个空间中均是存放了一个HashData类类型的对象作为元素，既然如此的话我们也就完全没有必要再创建一个HashData类类型的对象了，而是创建一个pair类类型的对象，将原有空间中所存储的那个HashData对象中的那个pair类类型的变量替换成我们传过来的这个pair类类型的对象即可。
{
if (Find(kv.first))//我们这里实现的这个哈希表是作为unordered_set和unordered_map这两个容器的底层的，通过我们前面的学习可知，unordered_set和unordered_map这两个容器是不支持重复的，因此，我们再这里要先检查一下关键字是否再该关键字，若存在的话，则说明接下来要插入的这个元素是存放的，已经存在了，不能插入到哈希表中，若不存在，则可以插入到哈希表中去。
{
return false;//插入失败。
}
//按照我们前面的思路来说，接下来的操作就该开始插入操作了，实际上在找映射的位置之前我们还需要干一件事，就是判断一下负载因子是否大于0.7，如果分析负载因子大于0.7的话，就需要进行扩容操作。
if (_n * 10 / _tables.size() >= 7)//计算一下该哈希表的负载因子是否小于0.7，_n是哈希表中存储的数据的个数。注：这里我们的_n不可以除以哈希表的空间大小，只能除以size()，借助下面第一幅图来解释一下：我们哈希表的底层结构是封装了一个vector类类型的对象，因此哈希表在访问元素时也是用operator[]去访问的，而我们前面在讲vector中的operator[]这个函数接口时，讲过说这个函数接口会判断要访问的元素下标是否是在size()之内，如果在的话，才会进行访问，反之，则会报错，也就是说，我们插入一个元素的范围是<size()，元素不可以插在size()和capacity()之间的空间中去，否则在调用operator[]成员函数时会报错(这里我们可以不用怎么在意这个，因为我们前面在哈希表中开空间时用的是resize()函数去开创的，每次开创过后的size()和capacity()基本都是相同的)。
{
//开创空间，到质数表中去找比当前的空间大的下一个质数。
//我们这里是对底层的那个顺序表进行扩容，我们这里的扩容和我们前面实现的传统扩容操作并不相同，不能在原来的那个顺序表中实现扩容操作，我们前面所讲过的哈希表的元素插入时是这个元素的整数形式最终映射到顺序表中的相应位置(下标位置)，也就是说，在元素相同的情况下，哈希表的大小不同，相应的，映射到的位置不同，基于此原因，如果我们在原顺序表中进行扩容的话，后续在调整各个元素位置时，就容易出现数据丢失的情况，因此，我们这里选择再开创一个顺序表，该顺序表的大小就是扩容后的大小。
vector<HashData<K, V>> newtables(__stl_next_prime(_tables.size() + 1));//接下来要进行的操作就是讲原顺序表中的元素全部都重新映射到刚刚新开创的这个顺序表中。
for (auto& data : _tables)
{
//通过我们前面对哈希表存储的元素方式的了解及其使用，我们可以了解到哈希表中的元素存储时并不是以一个接一个的方式去存储的，也就是说我们再获取空间中的元素时还需要去判断一下该空间中是否含有元素。
if (data._state == EXIST)
{
size_t hash0 = data._kv.first % newtables.size();//找到新空间中映射的位置。
//通过我们前面的讲解可知，我们这里是用线性探测的方法去实现插入元素的，而我们这里所写的这个"移动"元素的操作不就相当于是往扩容后的新空间中去插入元素吗？因此，我们这里也使用线性探测的方法。
while (_table[hash0]._state == EXIST)//通过我们前面对线性探测的分析可知，既有可能会出现哈希冲突的这一情况，解决办法是依次往后去寻找空位置，而发生传统的原因就是因为这个元素映射的位置倍别的元素给占据了，依次，我们这里选择借助循环来找到当前元素应该存储的位置，如果这个位置的_state是EXIST的话，则说明当前这个位置已经倍其它的元素给占据了，就需要我们继续往后去找合适的位置了。
{
hash0++;
hash0 %= _tables.size();//为了防止当hash0>=_tables.size()这种情况，hash0就是我们查找空间的下标，当hash0到哈希表的最后一个空间的位置时，那么它下一个要到的空间的位置就一个是该哈希表的第一个空间的位置，也就是从下标为0的位置依次往后走，"%"一下，就足可保证hash0绝对是在[0,_tables.size()-1];这个范围之间活动的。
}//除了循环的话，就说明找到空位置了，找到了合适的位置之后，下一步就是将数据放到里面了。
newtables[hash0] = data;
newtables[hash0]._state = EXIST;//更新该空间的_state为EXIST，说明该空间已经有元素了。
}//除了这个if语句后，就说明"移动"好一个元素了，继续进行范围for的遍历操作，直到将原数组中的所有元素全部都"移动"到新的数组中。
}//当编译器执行语句出了这个范围for之后，就说明我们这里已经将原数组中的所有元素全部"移动"到新的数组中去了，程序到这里其实还没完，我们这里进行的这个扩容操作的目的是将原哈希表中的那个数组空间(顺序表)给扩大；但是我们前面的一系列操作是额外开创了一块扩容后的空间大小的顺序表，也就是说，"移动"完所有的元素后，哈希表中的那个数组还是没有变化，因此我们接下来要将哈希表中的那个顺序表换成我们前面开创的那个大小为扩容后的大小的顺序表，只需交换一下两个顺序表的指针即可。
_tables.swap(newtables);//直接调用vector库中的那个swap所有函数即可，可以大幅度地提高运行效率。
}//以上所有操作均是与扩容操作相关地，作用就是判断是否需要扩容......;我们的这个成员函数的目的其实是往哈希表中要插入一个元素，也就是说，上述的所有操作并不是我们实现的插入的核心代码，接下来的才是：
size_t hahs0= kv.first % _tables.size();//求出当前这个元素在哈希表中被映射的位置。
while (_tables[hash0]._state == EXIST)//解释和前面相同。
{
hash0++;
hash0 %= _tables.size();
}//说明已经找到了要存储的位置了。
_tables[hash0]._kv = kv;
_tables[hash0]._state = EXIST;
++_n;//插入一个元素后，数据个数就会增加1。
return true;//插入成功。
}OK，上述代码就是我们这里写的插入元素的操作，我们在写插入的代码时，其中有扩容的操作，我们这里在写这个扩容操作时，是我们自己在开创空间，我们之前有讲过像这种我们自己去扩容的空间这个方法是传统的扩容，那么，接下来，我们就来写一下上述代码中有关扩容操作的现代写法。
if (_n * 10 / _tables.size() >= 7)//扩容(现代写法)
{
HashTable<K, V> newht;//再开创一个新的哈希表。
newht._tables.resize(__stl_next_prime(_tables.size() + 1));//将新开创的这个哈希表类型的对象的空间个数用resize()函数扩容，扩容后该哈希表的大小就是我们想要的大小。
//接下来，就是将原哈希表中所有的元素全部"移动"到刚刚开创的newht这个哈希表中去，这里我们仍然将其看成是插入到newht这个哈希表中。
for (auto& data : _tables)
{
if (data._state == EXIST)
{
newht.Insert(data._kv);
}
}
_tables.swap(newht._tables);
}以上就是我们所实现的扩容操作的现代写法，有的小伙伴在这里写这个现代写法时，产生了一些问题，就是在现代写法的代码中，我们是将原哈希表中的所有元素均插入到了新开创的哈希表中去，既然如此的话，有人就会问，在newht中难道就不会发生扩容操作吗（在实现插入操作时）？说实话，在将原哈希表中的所有元素 " 移动 " 到newht的过程中，确实不会再发生扩容了，因为newht的大小就是我们扩容之后的大小，这里是元素 " 移动 " 也就是说元素的个数是固定的，只是空间扩大为原来的近2倍的空间，那么这样的话，就算最后将所有的元素都 " 移动 " 结束之后，newht中的负载因子的值最终也不会超过0.6，因此newht是不会再进行扩容操作的；我们前面已经讲过了哈希表的结构了，一个哈希表的内部只有一个vector类类型的对象和一个size_t类型的变量，因此最后将原哈希表和newht中的顺序表交换一下即可。
1.6.2.4 查找一个数据
HashData<K, V>* Find(constK& key)
{
//我们这里在实现哈希表的这些操作时，我们是使用线性探测提供的那个哈希函数的，在前面我们讲过，整个哈希函数的实现中只能使用同一个哈希函数去实现，因此我们这里在查找某一个元素的时候，也使用线性探测的方法去查找。
size_t hasi = key % _tables.size();//首先找到关键字为key的这个元素映射在哈希表中的位置hashi，通过我们前面的讲解可以得知线性探测难免会发生哈希冲突，这样的话，就会占据别人的位置，也就是说，我们此时所求出来的那个映射的位置有可能并不是关键字为key的这个元素真正的存储位置，因此，我们这里从映射的这个位置开始依次往后去找，根据我们前面所讲过的知识可知，当两个不同的元素若映射到同一个位置时，那么它们实际的存储位置之间必然是没有空位置的(不包括_state为DELETE的位置)，因此可以根据这个条件去写循环。
while (_tables[hashi]._state !=EMPTY)
{
if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)//若满足if语句中的条件，则说明找到了，返回这块空间的地址即可。
{
return &_tables[hashi];
}//没进入if语句里面的话，则说明没找到，则要继续线性往后去找。
hashi++;
hashi %= _tables.size();//我们在查找的过程中必须始终要保证查找的那个位置(hashi)不能越过哈希表的大小，同时，若hashi查找到了哈希表的最后一个位置的话，那么下一个查找的位置就要是下标为0的这个位置。
}//若出了while循环的话，则说明整个哈希表中没有关键字为key的这个元素，查找失败。
return nullptr;
}1.6.2.5 删除一个元素
bool Erease(const K& key)
{
//我们这里实现的是删除元素的操作，既然是要删除，那么首先我们得要找到这个元素才行。
HashData<K, V>* ret = Find(key);
if (ret == nullptr)//ret若为空，则说明要删除的这个元素不存在。
{
return false;
}
else
{
ret->_state = DELETE;//将这块空间的状态改为DELETE，就说明这块空间中的元素被删除掉了，已经没有值了，可以存储其它元素。
return true;
}
}1.6.3 链地址法
1.6.3.1 解决冲突的思路
开放给地址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置上时，我们把这些冲突的数据连接成一个链表，挂在哈希表的这个位置的下面，链地址法也叫做拉链法或者哈希桶。我们下面演示一下将{24，13，5，96，30，17}这组值映射到M=11的哈希表中：
1.6.3.2 扩容
开放定址法中负载因子必须小于1，链地址法的负载因子就没有限制了，可以大于1.负载因子越大，哈希冲突的概率越高，空间利用率就越高；负载因子越小，哈希冲突的概率就越低，空间利用率就越低；STL中将unordered_xxx的最大负载因子基本控制在1，大于1的话就扩容，我们后面再代码中也使用这个方式。
1.6.3.3 极端场景
如果极端场景下，某个桶特别长的话怎么办呢？其实我们这里可以考虑使用全域散列法，这样就不容易被针对了。但是假设不是被针对了，用了全域散列法，但是偶然情况下，某个桶很长，查找效率很低怎么办？这里在Java8的HashMap中当桶的长度超过⼀定阀值(8)时就把链表转换成红黑树。⼀般情况下，不断扩容，单个桶很长的场景还是比较少的，下面我们代码实现就不搞这么复杂了，这个解决极端场景的思路，大家了解⼀下。
通过我们上述对链地址法的讲解以及对哈希表的了解可知，我们这里的链地址法它是将所有的映射位置相同的元素都放在了同一个位置上，这样的话，我们在查找元素的时候，直接找到这个元素的映射位置就可以了，既然这样的话，那么我们这里的链地址法中的元素就和我们前面开放地址法中的元素时不同的，开放地址法中的HashData类中有一个枚举类型的变量，目的主要是去用于查找元素的，而对于这里的链地址法来说，HashData类中是不需要那个枚举类型的变量，通过我们前面对链地址法的讲解可以得知，我们在HashData类中还需要有一个哈希元素的指针，因此，我们这里来重新写一下链地址法中的哈希表的元素节点（链地址法中的元素是单独作为一个节点由指针连接起来的）。
template<class K,class V>
class HashNode
{
public:
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K, V>& kv)
:_kv(kv)
,_next(nullptr)
{ }
};OK，有了上面的基础后，我们接下来用链地址法的方法来实现一下哈希表的一些基本操作，这个链地址法相对来说还是比较重要的，因为在实际的实现过程中，就是通过链地址法去实现的，因此这里需要我们重点掌握一下，在实现具体操作之前，我们这里先来实现一下哈希表的一个整体框架：
template<class K, class V, class Hash = HashFunc<K>, class KeyOfT, class Pred = equal_to<K>, class Alloc = allocator<K>>
class HashTable
{
public:
typedef HashNode<K, V> Node;
HashTable()
{
_tables.resize(__stl_next_prime(_table.size() + 1), nullptr);
}
private:
vector<HashNode<K, V>*> _tables;//指针数组。
size_t _n = 0;//哈希表中存储的数据个数。
};1.6.3.4 插入一个元素
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))//解析与前面的相同。
{
return flase;
}
size_t hashi = kv.first % _tables.szie();//通过我们前面的讲解可知，我们链地址法是将元素元素到某一个位置上，哪怕要映射的位置是相同的，因此，我们首先要求出该元素被映射的位置。
//我们这个链地址法这里也需要考虑扩容的问题，对于链地址这个方法，库中是当负载因子大于1时，才进行扩容操作，我们这里为保持一致，就选择当负载因子为1时，我们就开始进行扩容操作。
if (_n / _tables.size() == 1)//开始扩容
{
//对于我们这里接下来要进行的这个扩容操作，相信大多数的小伙伴第一时间想到的是传统的扩容方法，毕竟它比较容易想到，既然这个传统方法大家都能想得到的话，我们就不在这里浪费时间再去写了，我们这里直接就用现代写法去写了，如果这里大家要用传统的写法去试一试的话，有一个东西大家在这里注意一下，就是销毁掉旧单链表时的那个销毁的过程是需要我们自己单独去首先的，因为_tables里面存放的指针类型，按照我们之前所学的知识来说，编译器去销毁vector类类型的对象时，先自动调用vector的析构函数，vector的构造函数会自动去调用vector中所存储的元素的析构函数，在我们这里，_tables中存储的是指针，指针没有析构，因此这里编译在自动销毁旧单链表时，只会调用vector的构造函数，不会调用各个元素节点的析构函数，这样显然时不行的，久而久之，会出现一些风险，我们这里在最后需要利用for循环一步步将各个元素节点给释放掉如果用传统方法去实现的话。
HashTables<K, V> newht;
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++)//利用for循环来找到每一个元素，找到这个元素之后，将其新插入到刚刚开创的新哈希表newht中去。
{
Node* cur = _tables[i];
while (cur)//如果cur为空，则说明哈希表中下标为i的这个位置上所有的元素全部都遍历完了。
{
newht.Insert(cur->_kv);//将遍历到的这个元素给重新插入到newht中去。
cur = cur->_next;//cur进行往下走。
}
}//当我们出了for循环之后，就说明我们这里将原单链表中所有的元素全部都遍历完了。
_tables.swap(newht._tables);
}//上述操作知识扩容操作，并不是我们这里插入元素的操作，接下来，才真正是实现插入元素的操作。
//通过我们前面对链地址法的一个演示可知，我们映射到某一个位置上时，是头插到前面，就像前面的演示中，30这个元素插入到哈希表中，30所映射到的位置下面原来已经链接上了一个节点(96)了，我们是将30这个元素插入到96这个元素的前面，并不是插入到96这个元素的下面，我们这里之所以选择头插，因为头插的效率是最高的，如果我们选择插入到96后面的话，还需要借助循环去找到相应的位置，如果某个桶特别长的话，那么循环也是需要耗费大量的时间的。
Node* newnode = new Node(kv);//创建一个新节点，这个新节点存放要插入的这个元素。
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}OK，上述代码就是我们这里所实现的插入元素的代码，我们在其中写了一段扩容的代码，我们的扩容操作是开创了新的代码，就是我们在从旧单链表中找到元素，将找到的这个元素重新插入到newht这个哈希表中的这个操作，这里编译器是重新开创了一个与找到的那个元素一样大的空间，将这个新空间链接到newht哈希表中去。这样做的话，可以是可以，但是这样做的话，会导致空间的浪费，基于此，我们这里直接移动旧表的节点到新表，岂不更好，我们就上述方法来重新实现一下扩容操作：
if (_n / _tables.size() == 1)
{
vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;//通过我们上述的讲解可知，我们这里是要将旧表中所有的元素全部重新链接到新表中，我们这里采用的方法是直接移动旧表中的节点到新表中去，我们都知道，旧表中在同一个映射位置的所有元素在新表中的映射位置可能有所不同，也就是说，当我们链接好一个旧表中的一个元素之后，我们接下来要去链接这个位置的下一个元素，因此，我们这里需要重新定义一个指针去指向下一个要映射到新表中的元素。
size_t hashi = cur->_kv.first % _tables.size();//找到这个元素在新表中被映射的位置。
cur->_next = newtable[hashi];
newtables[hashi] = cur;
cur = next;//cur指针指向的是要移动到新表中的节点。
}//出了循环之后，就说明旧表中下标为i的这个位置中的所有映射全部都移动完了，由于旧表中存放的都是指针，因此最后将其置空，保持一个好习惯。
_tables[i] = nullptr;
}
_tables.swap(newtable);
}1.6.3.5 查找一个元素
Node* Find(const K& key)
{
size_t hashi = key % _tables.size();//找到关键字为key的这个元素在表中映射的位置。
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)///找到了那个关键字为key的元素。
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;//没找到。
}1.6.3.6 删除一个元素
bool Erase(const K& key)
{
//我们这里的操作是删除一个元素，既然是要删除元素，那么首先我们要找到这个元素，按照我们前面的惯例，我们这里完全可以通过Find函数去找到这个元素的位置，但是基于我们这里的链地址法的特点，我们这里是不可以用Find函数去找到关键字为key的元素，我们的链地址法中的每一个节点之间均是通过指针链家起来的，如果要删除某一个节点，就要该元素后面的所有节点全部都要重新接到该元素前面的那个接到后面，因此，我们还需要有一个指针去指向要删除的这个节点，而Find函数去找相应的节点。
size_t hashi = key % _tables.size();
Node* prev = nullptr;
node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
//_tables这个数组是一个指针数组，也就是说，_tables的每一个节点位置上存放的都是节点的地址。这里我们就要分情况考虑了。
if (prev == nullptr)
{
//如果满足这个条件的话，就说明下标为hashi的这个位置上的第一个就是我们要找的元素，按照我们前面所讲的规则以及指针数组的性质来看的话，我们这里可以让下标为hashi这个位置的第二个元素成为第一个元素即可。
_tables[hashi] = cur->_next;
}
else//说明cur指向的这个当前这个节点是中间的某个节点，让该节点后面的所有节点全部都接到prev节点的后面。
{
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}1.6.4 质数表
我们前面的讲解中讲过质数表这个东西，前面只是浅浅地讲了一下，这里我来写一下质数表地这个代码吧，相信看过这个代码过后就明白了：
inline unsigned long __stl_next_prime(unsigned long n)
{
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;
}相信凭借大家现在地实力，要想看懂上述的一段代码其实并不难，甚至可以说丝毫没有压力，通过我们前面的讲解可知，我们每次进行扩容操作时，都是从质数表中，也就是上述代码中的28个质数中挑选出扩容的空间的个数，通过上述的代码我们可知，这里是通过lower_bound这个函数去找相应的扩容的值的，我们前面在 " map和set的使用，相信我，超简单的！" （链接我放在下面了）这篇博客中讲过，它是返回大于等于val的迭代器的，这里与其类似，上述代码中的lower_bound函数返回的是[first,last]这个区间中大于等于n的值，因为是大于等于，因此在传参时才需要我们多加1，否则的话会达不到我们想要的效果。
OK，今天我们就先讲到这里了，那么，我们下一篇再见，谢谢大家的支持！
