哈希

一、哈希表底层结构剖析

1.unordered系列底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

2.哈希概念

在顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。图示如下：

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快问题：按照上述哈希方式，向集合中插入元素11，会出现什么问题？这就涉及到了哈希冲突，见下文：

3.哈希冲突

对于两个数据元素的关键字 $k_{i}$ 和 $k_j{}$ (i != j)，有 $k_{i}$ != $k_j{}$ ，但有：Hash( $k_{i}$ ) == Hash( $k_j{}$ )，即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

当我们按照上述操作直接建立映射关系，还会出现如下几个问题：

数据范围很广，不集中，导致空间消耗太多怎么办？

key的数据不是整数

发生哈希冲突该如何处理呢？这里我们首先使用哈希函数解决数据范围广，不集中，key的数据不是整数的问题，再来解决哈希冲突。

4.哈希函数（直接定址 + 除留余数）

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

常见哈希函数

1、直接定址法--(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

面试题：字符串中第一个只出现一次字符

2、除留余数法--(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

比如我给出的数据集合为{3，6，999，70，-10}，如此不集中分布广的数据，就不能用直接定址法，因为分布太广，会导致空间浪费过多。这就需要用到除留余数法来解决：

除留余数法就是先统一将数字转换为无符号，解决了负数的问题，再用key%表的大小，随后映射到哈希表中，图示：

此时，哈希冲突就会出现了，当插入数字200的时候，根据除留余数法的规则，200理应映射到下标70的位置，可是该位置已经有数值了，这就需要通过后文的开散列和闭散列的相关知识点来帮助我们解决哈希冲突。

3、平方取中法--(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4、折叠法--(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5、随机数法--(了解)

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法

6、数学分析法--(了解)

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

5.哈希冲突解决

解决哈希冲突的两种方法是：闭散列和开散列

5.1.闭散列（线性探测 + 二次探测）

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？有以下两种方法：
1、线性探测
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。找下一个空位置的方法为：hash(key)%N + i。拿上图继续演示：

比如我在此基础上继续插入20，200，50。首先，20%10=0，下标0的位置有了70，继续往后找，下标1是空的，把20放进去；200%10=0，下标0为70，往后找，下标1是20，往后找，下标2是空的，放进去……。

线性探测优点：实现非常简单

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

当再插入数值11时，11%10=1，可是下标1位置被下标0位置的冲突而被10占了，于是继续往后找空位，恶行循环，导致拥堵。

为了解决此麻烦，又推出了二次探测。
2、二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：hash(key) + i^2^（i = 0 1 2 3……）。以下图示例：

同样是插入20，200，50。20%10+0^2^=0，下标0有值就加1^2^=1，下标1为空放进去，20%10+2^2^=4，下标4为空放进去，50%10+3^2^=9，不为空，换成+4^2^=16，超过数组的长度，绕回来，数到16，为下标7为空放进去。

二次探测就是对上述线性探测的优化，不那么拥堵。简而言之，线性探测是依次寻找空位置，必然拥堵，而二次探测跳跃着寻找空位置，就没那么拥堵。不过这俩方法没有本质的冲突，本质都是在占空的的位置，只是一个按顺序占位，一个分散着占位。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：闭散列最大的缺陷就是空间利用率比较低，这也是闭散列的缺陷，但是往后又推出一种开散列来解决哈希冲突的问题，此法还是比较优的。

5.2.开散列

开散列法又叫链地址法(开链法、哈希桶)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

简而言之就是我的数据不存在表中，表里面存储一个链表指针，就是把冲突的数据通过链表的形式挂起来，示例：

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素，大大减少了闭散列法冲突的弊端性。后文将会详细讲解闭散列哈希表以及开散列哈希桶的具体模拟实现。

二、闭散列哈希表的模拟实现

1.哈希表的基本框架

在模拟实现之前，要清楚实现哈希表所需的必要成分：

哈希节点状态的类

哈希表的类
//哈希表
template<class K, class V>
class HashTable
{
    
    
public:
    //...
private:
    vector<Data> _table; //哈希表
    size_t _n = 0; //哈希表中的有效元素个数
};
接下来依次展开说明。

2.哈希节点状态的类

在闭散列的哈希表中，哈希表每个位置除了存储数据之外，还存储该位置当前的状态，哈希表中每个位置的可能状态如下：

EMPTY（没有数据的空位置）。

EXIST（存在存储数据）。

DELETE（原有数据存在，但现在被删除）。

我们可以用枚举定义这三个状态。

而这三种状态我们可以借助enum枚举来帮助我们表示数组里每个位置的状态。这里我们专门封装一个类来记录每个位置的状态，以此汇报给后续的哈希表。
enum State
{
    
    
    EMPTY,
    EXIST,
    DELETE
};
//哈希节点状态的类
template<class K, class V>
struct HashData
{
    
    
    pair<K, V> _kv;
    State _state = EMPTY;//记录每个位置的状态，默认给空
};
//哈希表的类
template<class K, class V, class HashFunc = DefaultHash<K>>//添加仿函数便于把其他类型的数据转换为整型数据
class HashTable
{
    
    
    typedef HashData<K, V> Data;
public:
    //相关功能的实现……
private:
    vector<Data> _tables;
    size_t _n = 0;//记录存放的有效数据的个数
};
实现好了哈希节点的类，就能够很好的帮助我们后续的查找，示例：

为什么需要标识哈希表中每个位置的状态？

若是不设置哈希表中每个位置的状态，那么在哈希表中查找数据的时候可能是这样的。以除留余数法的线性探测为例，我们若是要判断下面这个哈希表是否存在元素50，步骤如下：

通过除留余数法求得元素50在该哈希表中的哈希地址是0。

从0下标开始向后进行查找，若找到了50则说明存在。

但是我们在寻找元素50时，不可能从0下标开始将整个哈希表全部遍历一次，这样就失去了哈希的意义。我们只需要从0下标开始往后查找，直到找到元素50判定为存在，或是找到一个空位置判定为不存在即可。

因为线性探测在为冲突元素寻找下一个位置时是依次往后寻找的，既然我们已经找到了一个空位置，那就说明这个空位置的后面不会再有从下标0位置开始冲突的元素了。比如我们要判断该哈希表中是否存在元素30，步骤如下：

通过除留余数法求得元素30在该哈希表中的哈希地址是0。

从0下标开始向后进行查找，直到找到下标为5的空位置，停止查找，判定元素30不存在。

但这种方式是不可行的，原因如下：

如何标识一个空位置？用数字0吗？那如果我们要存储的元素就是0怎么办？因此我们必须要单独给每个位置设置一个状态字段。

如果只给哈希表中的每个位置设置存在和不存在两种状态，那么当遇到下面这种情况时就会出现错误。

我们先将上述哈希表当中的元素200找到，并将其删除，此时我们要判断当前哈希表当中是否存在元素50，当我们从0下标开始往后找到2下标（空位置）时，我们就应该停下来，此时并没有找到元素50，但是元素40却在哈希表中存在。

因此我们必须为哈希表中的每一个位置设置一个状态，并且每个位置的状态应该有三种可能，当哈希表中的一个元素被删除后，我们不应该简单的将该位置的状态设置为EMPTY，而是应该将该位置的状态设置为DELETE。
这样一来，当我们在哈希表中查找元素的过程中，若当前位置的元素与待查找的元素不匹配，但是当前位置的状态是EXIST或是DELETE，那么我们都应该继续往后进行查找，而当我们插入元素的时候，可以将元素插入到状态为EMPTY或是DELETE的位置。

3.哈希表的扩容

散列表的载荷因子定义为：α = 填入表中的元素个数 / 散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以α越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α越小，表明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。

对于开放定址法（闭散列），载荷因子是特别重要因素，应严格限制在0.7 ~ 0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照质数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了载荷因子为0.75，超过此值将resize散列表。

综上，我们在后续的插入操作中，必然要考虑到扩容的情况，我们直接把负载因子控制在0.7，超过了就扩容。具体操作见下文哈希表的插入操作。

4.构建仿函数把所有数据类型转换为整型并特化

在我们后续的插入操作中，插入的数据类型如果是整数，那么可以直接建立映射关系，可若是字符串，就没那么容易了，因此，我们需要套一层仿函数，来帮助我们把字符串类型转换成整型的数据再建立映射关系。主要分为以下三类需要写仿函数的情况：

1、key为整型，为默认仿函数的情况

此时的数据类型为整型，直接强转size_t随后返回

2、key为字符串，单独写个字符串转整型的仿函数

针对于字符串转整型，我们推出下面两种方法，不过都是会存在问题的：

只用首字母的ascii码来映射，此法不合理，因为"abc"和"axy"本是俩不用字符串，经过转换，会引发冲突。

字符串内所有字符ASCII码值之和，此法也会产生冲突，因为"abcd"和"bcad"在此情况就会冲突。

为了避免冲突，几位大佬推出多种算法思想，下面取其中一种算法思想来讲解：
//BKDR哈希算法：
hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..
大佬博客链接：各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

为了能够让我们的哈希表能够自动识别传入数据的类型，不用手动声明，这里我们可以借助特化来解决，仿函数+特化总代码如下：
//利用仿函数将数据类型转换为整型
template<class K>
struct HashFunc
{
    
    
    size_t operator()(const K& key)
    {
    
    
        return (size_t)key;
    }
};
//模板的特化
template<>
struct HashFunc<string>
{
    
    
    size_t operator()(const string& key)
    {
    
    
        //BKDR哈希算法
        size_t hash = 0;
        for (auto ch : key)
        {
    
    
            hash = hash * 131 + ch;//把所有字符的ascii码值累计加起来
        }
        return hash;
    }
};

5.哈希表的插入

哈希表的插入主要是三大步骤：

一、去除冗余

二、扩容操作

三、插入操作

下面分开来演示。

一、去除冗余：

复用Find查找函数，查看哈希表中是否存在该数据的键值对

若存在，则插入失败

不存在，再进行后续的插入操作

二、扩容操作：

如果哈希表一开始就为空，那么就需要扩容，一般设置哈希表初始大小为10

如果哈希表的负载因子大于0.7，就需要扩容到原表大小的二倍

扩容以后要重新建立映射关系

创建一个新的哈希对象，扩容到先前旧表扩容的大小

遍历旧表，把旧表每个存在的元素插入到新表，此步骤让新表自动完成映射关系，无序手动构建

利用swap函数把新表与旧表交换，此时的旧表就是已经扩好容且建立好映射关系的哈希表

三、插入操作：

借助仿函数把插入的数据类型转为整型并定义变量保存插入键值对的key

通过哈希函数计算出对应的哈希地址

若产生哈希冲突，则从哈希地址处进行线性探测 / 二次探测，如果位置的状态为EXIST，说明还要往后遍历查找

遍历结束，说明此位置的状态为空EMPTY或删除DELETE，可以插入数据

把要插入的数据放进该位置，更新状态为EXIST，有效数据个数++
//插入
bool Insert(const pair<K, V>& kv)
{
    
    
    //1、去除冗余
    if (Find(kv.first))
    {
    
    
        //说明此值存在，直接返回false
        return false;
    }
    //2、扩容
        //负载因子超过0.7，就扩容
    if (_n * 10 / _tables.size() >= 7)
    {
    
    
        HashTable<K, V, Hash> newHT;
        newHT._tables.resize(_tables.size() * 2);
        //遍历旧表，把旧表每个存在的元素插入newHT
        for (auto& e : _tables)
        {
    
    
            if (e._state == EXIST)
            {
    
    
                newHT.Insert(e._kv);
            }
        }
        _tables.swap(newHT._tables);//建立映射关系后交换
    }
    //3、插入
    Hash hf;
    size_t hashi = hf(kv.first) % _tables.size();
    while(_tables[hashi]._status == EXIST)
    {
    
    
        // 线性探测
        hashi++;
        hashi %= _tables.size(); // 防止hashi超出哈希表范围
    }
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    _n++;

    return true;
}
注意：

用变量%=哈希表的size()，不能是capacity()，因为[ ]运算符会判断下标是否小于size，且对于哈希表，应该尽量控制size和capacity一样大。

产生哈希冲突向后进行探测时，一定会找到一个合适位置进行插入，因为哈希表的负载因子是控制在0.7以下的，也就是说哈希表永远都不会被装满。

6.哈希表的查找

查找的核心逻辑就是找到key相同，就返回此对象的地址，找到空就返回nullptr，具体规则如下：

先去判断哈希表的大小是否为0，为0则查找失败

通过哈希函数计算出对应的哈希地址

按照线性探测 / 二次探测的方式去查找，如果遍历到某哈希表的值等于要查找的值（前提是此位置的状态不为DELETE删除），返回此对象的地址，说明查找成功；如果遍历找到一个状态为EMPTY的位置则判定查找失败
//查找
Data* Find(const K& key)
{
    
    
    //判断表的size是否为0
    if (_tables.size() == 0)
    {
    
    
        return nullptr;
    }
    HashFunc hf;
    size_t starti = hf(key);//通过仿函数把其它类型数据转为整型数据
    starti %= _tables.size();
    size_t hashi = starti;
    size_t i = 1;
    //线性探测/二次探测
    while (_tables[hashi]._state != EMPTY)//不为空就继续
    {
    
    
        if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
        {
    
    
            return &_tables[hashi];//找到了就返回此对象的地址
        }
        hashi = starti + i;//二次探测改为 +i^2
        ++i;
        hashi %= _tables.size();//防止hashi超出数组
    }
    return nullptr;
}
注意：

在查找过程中，必须找到位置状态为EXIST，并且key值匹配的元素，才算查找成功。若仅仅是key值匹配，但该位置当前状态为DELETE，则还需继续进行查找，因为该位置的元素已经被删除了。

7.哈希表的删除

删除的逻辑很简单，遵循下面的规则：

复用Find函数去帮我们查找删除的位置是否存在

若存在，把此位置的状态置为DELETE即可，此时表中的有效数据个数_n--，最后返回true

若不存在，直接返回false
//删除函数
bool Erase(const K& key)
{
    
    
    //1、查看哈希表中是否存在该键值的键值对
    HashData<K, V>* ret = Find(key);
    if (ret)
    {
    
    
        //2、若存在，则将该键值对所在位置的状态改为DELETE即可
        ret->_state = DELETE;
        //3、哈希表中的有效元素个数减一
        _n--;
        return true;
    }
    return false;
}
注意：

虽然删除元素时没有将该位置的数据清0，只是将该元素所在状态设为了DELETE，但是并不会造成空间的浪费，因为我们在插入数据时是可以将数据插入到状态为DELETE的位置的，此时插入的数据就会把该数据覆盖。

三、开散列哈希桶的模拟实现

1.哈希桶的基本框架

根据我们先前对开散列哈希桶的了解，得知其根本就是一个指针数组，数组里每一个位置都是一个链表指针，因此我们要单独封装一个链表结构的类，以此来告知我们哈希表类的每个位置为链表指针结构。
在开散列的哈希表中，哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是一个结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点。
//每个哈希桶中存储数据的结构
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, class V>
class HashBucket
{
    
    
public:
    //...
private:
    vector<Node*> _table; //哈希表
    size_t _n = 0; //哈希表中的有效元素个数
};

2.构建仿函数把数据类型转为整型并特化

此步操作的方法和闭散列哈希表所实现的步骤一致，目的都是为了能够让后续操作中传入的所有数据类型转换为整型数据，以此方便后续建立映射关系，直接看代码：

//利用仿函数将数据类型转换为整型
template<class K>
struct HashFunc
{
    
    
    size_t operator()(const K& key)
    {
    
    
        return (size_t)key;
    }
};
//模板的特化
template<>
struct HashFunc<string>
{
    
    
    size_t operator()(const string& key)
    {
    
    
        //BKDR哈希算法
        size_t hash = 0;
        for (auto ch : key)
        {
    
    
            hash = hash * 131 + ch;//把所有字符的ascii码值累计加起来
        }
        return hash;
    }
};

3.哈希桶的插入

哈希桶的插入主要分为这几大步骤

一、去除冗余

二、扩容操作

三、头插操作

下面开始具体展开说明：

1、去除冗余：

复用Find查找函数，查看哈希表中是否存在该键值的键值对

若存在，则插入失败

不存在，再进行后续的插入操作

2、扩容操作：

针对哈希桶的扩容，我们有两种方法进行扩容，法一和哈希表扩容的方法一致

法一：

当负载因子==1时扩容

扩容后重新建立映射关系

创建一个新的哈希桶对象，扩容到原哈希表大小的两倍

遍历旧表，把旧表每个存在的元素插入到新表，此步骤让新表自动完成映射关系，无序手动构建

利用swap函数把新表交换到旧表那，此时的旧表就是已经扩好容且建立号映射关系的哈希表

此扩容的方法会存在一个问题：释放旧表会出错！！！

当我们把旧表的元素映射插入到新表的时候，最后都要释放旧表，按照先前哈希表的释放，我们无需做任何处理，但是现在定义的结构是vector，是自定义类型，会自动调用析构函数进行释放，vector存储的数据是Node ，Node 是内置类型，不会自动释放，最后会出现表我们释放了，但是链表结构的数据还没释放，因此，我们还需借助手写析构函数来帮助我们释放。
//析构函数
~HashTable()
{
    
    
    for (size_t i = 0; i < _tables.size(); i++)
    {
    
    
        Node* cur = _tables[i];
        while (cur)
        {
    
    
            Node* next = cur->_next;
            delete cur;
            cur = next;
        }
        _tables[i] = nullptr;//释放后置空
    }
}
重点： 在将原哈希表的数据插入到新哈希表的过程中，不要通过复用插入函数将原哈希表中的数据插入到新哈希表，因为在这个过程中我们需要创建相同数据的结点插入到新哈希表，在插入完毕后还需要将原哈希表中的结点进行释放，多此一举。

法二：

实际上，这里我们没必要再创建新的节点，我们只需要遍历原哈希表的每个哈希桶，通过哈希函数将每个哈希桶中的结点重新找到对应位置插入到新哈希表即可，这里不需要再创建新节点，直接利用原链表里的节点，不用进行结点的创建与释放。
为了降低时间复杂度，在增容时取结点都是从单链表的表头开始向后依次取的，在插入结点时也是直接将结点头插到对应单链表。
3、头插操作：

借助仿函数找到映射的位置（头插的位置）

进行头插的操作

更新有效数据个数
//插入
bool Insert(const pair<K, V>& kv)
{
    
    
    //1、去除冗余
    if (Find(kv.first))
    {
    
    
        return false;
    }
    //构建仿函数，把数据类型转为整型，便于后续建立映射关系
    HashFunc hf;
    //2、负载因子 == 1就扩容
    if (_tables.size() == _n)
    {
    
    
        /*法一
        HashTable<K, V> newHT;//
        newHB._tables.resize(_table.size(), nullptr);
        //遍历旧表，把旧表的数据重新映射到新表
        for (auto cur : _tables)
        {
            while (cur)//如果cur不为空，就插入
            {
                newHB.Insert(cur->_kv);
                cur = cur->_next;
            }
        }
        _tables.swap(newHB_tables);*/

        //法二：
        vector<Node*> newTables;
        // newTables.resize(2 * _tables.size(), nullptr);
        newTables.resize(__stl_next_prime(_tables.size()), nullptr);
        for (size_t i = 0; i < _tables.size(); i++)//遍历旧表
        {
    
    
            Node* cur = _tables[i];
            while (cur)
            {
    
    
                Node* next = cur->_next;
                size_t hashi = hf(cur->_kv.first) % newSize;//确认映射到新表的位置
                //头插到新表
                cur->_next = newTable[hashi];
                newTable[hashi] = cur;
                cur = next;
            }
            _tables[i] = nullptr; //
        }
        _tables.swap(newTables);
    }
    //3、头插
    //找到对应的映射位置
    size_t hashi = Hash()(kv.first) % _tables.size();
    //头插到对应的桶即可
    Node* newNode = new Node(kv); //需要写构造函数，不然无法构造newNode
    newNode->_next = _tables[hashi];
    _tables[hashi] = newNode;
    ++_n;
    return true;
}

4.哈希桶的查找

遵循下列规则：

先去判断表的大小是否为0，为0则查找失败
通过哈希函数计算出对应的哈希地址
找到对应的哈希桶中的单链表，在其中进行遍历查找，找到了，返回节点指针；遍历结束，说明没找到，返回nullptr

//查找
Node* Find(const K& key)
{
    
    
    //防止后续除0错误
    if (_tables.size() == 0)
    {
    
    
        return nullptr;
    }
    //找到对应的映射下标位置
    //Hash hs;
    //size_t hashi = hs(key) % _tables.size();
    size_t hashi = Hash()(key) % _tables.size();
    Node* cur = _tables[hashi];
    //在此位置的链表中进行遍历查找
    while (cur)
    {
    
    
        if (cur->_kv.first == key)
        {
    
    
            //找到了
            return cur;
        }
        else
        {
    
    
            cur = cur->_next;            
        }
    }
    //遍历结束，没有找到，返回nullptr
    return nullptr;
}

5.哈希桶的删除

在哈希表中删除数据的步骤如下：

通过哈希函数计算出对应的哈希桶下标。

遍历对应的哈希桶，寻找待删除结点。

若找到了待删除结点，则将该结点从单链表中移除并释放。

删除结点后，将哈希表中的有效元素个数减一。
//删除函数
bool Erase(const K& key)
{
    
    
        //防止后续除0错误
    if (_tables.size() == 0)
    {
    
    
        return false;
    }
    //1、通过哈希函数计算出对应的哈希桶编号下标（除数不能是capacity）
    size_t hashi = Hash(key) % _tables.size();
    //2、在下标为hashi的哈希桶中寻找待删除结点
    Node* prev = nullptr;
    Node* cur = _tables[hashi];
    while (cur) //直到将该桶遍历完为止
    {
    
    
        if (cur->_kv.first == key) //key值匹配，则查找成功
        {
    
    
            //3、若找到了待删除结点，则删除该结点
            if (cur == _tables[hashi]) //待删除结点是哈希桶中的第一个结点
            {
    
    
                _tables[hashi] = cur->_next; //将第一个结点从该哈希桶中移除
            }
            else //待删除结点不是哈希桶的第一个结点
            {
    
    
                prev->_next = cur->_next; //将该结点从哈希桶中移除
            }
            delete cur; //释放该结点
            //4、删除结点后，将哈希表中的有效元素个数减一
            _n--;
            return true; //删除成功
        }
        else
        {
    
    
             prev = cur;
            cur = cur->_next;   
        }
    }
    return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败
}
注意：

不要先调用查找函数判断待删除结点是否存在，这样做如果待删除不在哈希表中那还好，但如果待删除结点在哈希表，那我们还需要重新在哈希表中找到该结点并删除，还不如一开始就直接在哈希表中找，找到了就删除。

法二：替换法删除

上述的删除是按部就班的删除，建立prev作为cur的前指针，以此利用prev和cur->next来建立关系从而删除cur节点，但是我们可以不用借助prev指针，就利用先前二叉搜索树的替换法删除的思想来解决。图示：

当我要删除24时，把节点24的下一个节点的值54替换掉24，随后删除原来节点24，再建立链表的关系即可。

当删除的是尾节点14时，直接和头节点进行交换，删除头节点，并建立链表关系。

这里就不代码演示了，因为整体的成本看还是法一更方便理解些。

6.哈希表的大小为什么建议是素数

都说使用除留余数法时，哈希表的大小最好是素数，这样能够减少哈希冲突产生的次数。

下面用合数（非素数）10和素数11来进行说明。

合数10的因子有：1，2，5，10。

素数11的因子有：1，11。

我们选取下面这五个序列：

间隔为1的序列：s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

间隔为2的序列：s2 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

间隔为5的序列：s3 = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}

间隔为10的序列：s4 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}

间隔为11的序列：s5 = {11, 22, 33, 44, 55, 66, 77, 88, 99, 110}

实验一：将s1插入表长为10的哈希表，即模10：

哈希表 0 1 2 3 4 5 6 7 8 9

10 1 2 3 4 5 6 7 8 9

实验二：将s1插入表长为11的哈希表，即模11：

哈希表 0 1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

实验三：将s2插入表长为10的哈希表，即模10：

哈希表 0 1 2 3 4 5 6 7 8 9

10 2 4 6 8

20 12 14 16 18

实验四：将s2插入表长为11的哈希表，即模11：

哈希表 0 1 2 3 4 5 6 7 8 9 10

12 2 14 4 16 6 18 8 20 10

实验五：将s3插入表长为10的哈希表，即模10：

哈希表 0 1 2 3 4 5 6 7 8 9

10 5

20 15

30 25

40 35

50 45

实验六：将s3插入表长为11的哈希表，即模11：

哈希表 0 1 2 3 4 5 6 7 8 9 10

45 35 25 15 5 50 40 30 20 10

实验七：将s4插入表长为10的哈希表，即模10：

哈希表 0 1 2 3 4 5 6 7 8 9

10

20

30

40

50

60

70

80

90

100

实验八：将s4插入表长为11的哈希表，即模11：

哈希表 0 1 2 3 4 5 6 7 8 9 10

100 90 80 70 60 50 40 30 20 10

实验九：将s5插入表长为10的哈希表，即模10：

哈希表 0 1 2 3 4 5 6 7 8 9

110 11 22 33 44 55 66 77 88 99

实验十：将s5插入表长为11的哈希表，即模11：

哈希表 0 1 2 3 4 5 6 7 8 9 10

11

22

33

44

55

66

77

88

99

110

根据上述实验，我们可以得出以下结论：

如果一个序列中，每个元素之间的间隔为1，那么不管哈希表的大小为几，该序列插入哈希表后都是均匀分布的（实验一、实验二）。

如果一个序列中，每个元素之间的间隔刚好是哈希表大小或哈希表的倍数，那么该序列插入哈希表时，将全部产生冲突（实验七、实验十）。

哈希表中的分布按照序列的间隔进行分隔，如果序列的间隔恰好是哈希表大小的因子，那么哈希表的分布就会产生间隔（实验三、实验五、），反之则不会（实验三、实验四、实验五、实验六、实验八、实验九）。

某个随机序列当中，每个元素之间的间隔是不定的。因此，为了尽量减少冲突，我们就需要让哈希表的大小的因子最少，这样才能最大可能避免让某两个元素之间的间隔是哈希表的因子，所以哈希表的大小最好是素数。

如何实现？

我们如果每次增容时让哈希表的大小增大两倍，那么增容后哈希表的大小就不是素数了。因此我们可以将需要用到的素数序列提前用一个数组存储起来，当我们需要增容时就从该数组当中进行获取就行了。

我们看一下STL库中的处理方式，库中有一个素数序列，都是素数，且它们近似以2倍的形式进行增长，我们就可以将它们用一个数组存储起来。当我们需要增容时，就在该素数数组中找到下一个素数作为哈希表增容后的大小即可。
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] =
    {
    
    
        53ul, 97ul, 193ul, 389ul, 769ul,
        1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
        49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
        1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
        50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
        1610612741ul, 3221225473ul, 4294967291ul
    };

    for (int i = 0; i < __stl_num_primes; ++i)
    {
    
    
        if (__stl_prime_list[i] > n)
        {
    
    
            return __stl_prime_list[i];
        }
    }

    return __stl_prime_list[__stl_num_primes - 1];
}

哈希表	0	1	2	3	4	5	6	7	8	9
	10	1	2	3	4	5	6	7	8	9

哈希表	0	1	2	3	4	5	6	7	8	9	10
		1	2	3	4	5	6	7	8	9	10

哈希表	0	1	2	3	4	5	6	7	8	9	10
		12	2	14	4	16	6	18	8	20	10

哈希表	0	1	2	3	4	5	6	7	8	9	10
		45	35	25	15	5	50	40	30	20	10

哈希表	0	1	2	3	4	5	6	7	8	9	10
		100	90	80	70	60	50	40	30	20	10

哈希表	0	1	2	3	4	5	6	7	8	9
	110	11	22	33	44	55	66	77	88	99

参考博文：

1、哈希表、哈希桶的模拟实现

哈希

哈希

一、哈希表底层结构剖析

1.unordered系列底层结构

2.哈希概念

3.哈希冲突

4.哈希函数（直接定址 + 除留余数）

5.哈希冲突解决

5.1.闭散列（线性探测 + 二次探测）

5.2.开散列

二、闭散列哈希表的模拟实现

1.哈希表的基本框架

2.哈希节点状态的类

3.哈希表的扩容

4.构建仿函数把所有数据类型转换为整型并特化

5.哈希表的插入

6.哈希表的查找

7.哈希表的删除

三、开散列哈希桶的模拟实现

1.哈希桶的基本框架

2.构建仿函数把数据类型转为整型并特化

3.哈希桶的插入

4.哈希桶的查找

5.哈希桶的删除

6.哈希表的大小为什么建议是素数

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

哈希

哈希

一、哈希表底层结构剖析

1.unordered系列底层结构

2.哈希概念

3.哈希冲突

4.哈希函数（直接定址 + 除留余数）

5.哈希冲突解决

5.1.闭散列（线性探测 + 二次探测）

5.2.开散列

二、闭散列哈希表的模拟实现

1.哈希表的基本框架

2.哈希节点状态的类

3.哈希表的扩容

4.构建仿函数把所有数据类型转换为整型并特化

5.哈希表的插入

6.哈希表的查找

7.哈希表的删除

三、开散列哈希桶的模拟实现

1.哈希桶的基本框架

2.构建仿函数把数据类型转为整型并特化

3.哈希桶的插入

4.哈希桶的查找

5.哈希桶的删除

6.哈希表的大小为什么建议是素数

热门文章

最新文章

相关电子书