哈希表的数据结构与实现详解

OK，回到我们这里的 C++ 中来，我们上面是采用这个除法散列法去作为哈希函数的，通过前面方法的实现步骤我们可以得知，不同的值是极有可能映射到表中的同一个位置的，但是，我们一个位置上只能存储一个数据，这就引发了哈希冲突，目前为止，有 2 种解决方法，这个我们稍后再讲，这里先将哈希函数这一部分讲完。（后面的三种方法以及刚刚讲解的这种方法我们只需简单了解一下即可，不要求大家重点掌握）

1.5.2 乘法散列法

1. 乘法散列法对哈希表大小 M 没有要求，他的第一步思路：用关键字 Key 乘上常数 A(0<A<1)，并抽取出 KeyA 的小数部分。第二步：再用 M 乘以 KeyA 的小数部分，再向下取整。
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, AKey=762.6539420558，取小数部分为 0.6539420558, M×((A×Key)%1.0) = 0.65394205581024 =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，以上思路就是我们实现的主要思路，其实说到这里还有一个小问题，我们来通过前面所讲解的线性探测的那个例子来说明一下这个问题，这里我先提前来为大家说一下，我们除了要写一些基本的结构以外，还要另外再写一个枚举来标明一下当前这个位置的状态：

enum State//写一个枚举来标记空间中存储值的状态。
{
    EXIST,//这个位置有值，也就是这个位置已经有数据了。
    EMPTY,//这个位置没有元素。
    DELETE//这个位置原来是有元素存在的，被删除了，因此，这个位置就没有元素了。
};

如上图所示，我们这里将 30 这个元素直接给删除了的话，此时我们若再通过 find 函数去找 20 这个元素的话，就会找不到了（我们这里要知道的是，20 这个元素原本的位置其实并不是在下标为 10 的这个位置，而是在下标为 9 的这个位置），我们这里用我们前一页中所说的查找的思路来顺一下，先通过 20 这个元素来找到它原本被映射的位置，这里是下标为 9 的位置，然后我们再从下标为 9 的这个位置往后找，直到遇到最后一个空位置，按照我们上面那个哈希表来看的话，下标为 9 的那个位置就是一个空位置（这里其实用空位置的这个说法并不准确，因为我们是无法将某一个空间中所存放的数据给彻底地删除掉的，只能说是用另一个毫不相关的数据去替换掉我们这里的这个原有的数据），编译器在这里就不会再去后面继续找了，直接返回，因此查找就失败了，但其实 20 这个元素是存在的，基于这个原因和我们无法判断这个位置是否是我们上面思路中的空位置，因此，我们在这里决定去定义一个枚举类型用来标记各个空间中存储值的状态。

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 (_tables[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 hash0 = 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(const K& key) 
{
    //我们这里在实现哈希表的这些操作时，我们是使用线性探测提供的那个哈希函数的，在前面我们讲过，整个哈希函数的实现中只能使用同一个哈希函数去实现，因此我们这里在查找某一个元素的时候，也使用线性探测的方法去查找。
    size_t hashi = 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 Erase(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 false;
    }
    size_t hashi = kv.first % _tables.size();//通过我们前面的讲解可知，我们链地址法是将元素元素到某一个位置上，哪怕要映射的位置是相同的，因此，我们首先要求出该元素被映射的位置。
    //我们这个链地址法这里也需要考虑扩容的问题，对于链地址这个方法，库中是当负载因子大于 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 = newtables[hashi];
            newtables[hashi] = cur;
            cur = next;//cur 指针指向的是要移动到新表中的节点。
        }//出了循环之后，就说明旧表中下标为 i 的这个位置中的所有映射全部都移动完了，由于旧表中存放的都是指针，因此最后将其置空，保持一个好习惯。
        _tables[i] = nullptr;
    }
    _tables.swap(newtables);
}

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 = _tables[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，否则的话会达不到我们想要的效果。