详解STL之 hash table — 超绝“常数平均时间”效率

1.hash table 概述

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

hash table 可提供对任何有名项的存取操作和删除操作。由与操作对象是有名项。所以hash table也可被视为一种字典结构。这种结构的用意在于提供常数时间之基本操作，就像stack和queue那样。乍听之下这就是不可能完成的任务，因为制约条件如此少，而元素个数增加，搜寻操作必定耗费更多时间。

2. 直接定址法

(1) 方法解释

当关键词的范围比较集中时，直接定地址发就是非常简单高效的方法，比如一组关键词都在[0,99]之间，那么我们开一个100个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组管几字值都在[a,z]的小写字母，那么我们开一个26个数的数组A，每个关键字ASCII码就是存储位置的下标。如果插入元素i，我们就执行A[i]++，如果删除元素i，就执行A[i]--，如果搜寻元素i，就检查A[I]是否为0。以上的每一个元素操作都是常数时间，但这个解法的额外负担是 array 的空间和初始化时间。也就是说直接定址法本质就是用关键词计算出一个绝对位置或相对位置。这个方法我们在计数排序部分已经用过了，其次在string章节的OJ也用过。

387. 字符串中的第一个唯一字符

(2) 缺点

这个解法有两个现实问题

第一，如果元素是32-bits，而非16-bits，我们所准备的array A的大小就是，有点太大了。第二，如果元素形态是字符串（或其他）而非整数，将无法拿来做array的索引。

第二个问题不难解决，字符串 “jjhou” 是由 ‘j’，‘j’，‘h’，‘o’，‘u’，构成。那么既然数字1234是由，我们也可以吧字符编码，每个字符以一个7- bits数值来表示(assic码)，而从字符串 “jjhou”变现为：

太不切实际了，更长的字符串会导致更大的索引值，又回到第一个问题了！

3. 哈希冲突

为了避免使用一个大的荒谬的array，办法之一就是使用某种映射函数，将大数映射成小数。负责将某一元素映射成“大小可接受之索引”，这样的函数为hash function（散列函数）。例如：假设x是任意整数 TableSize 是array大小，则x%TableSize 会得到一个整数，范围在 0~TableSize之间，恰可作为array的索引。（这里只是用来引出哈希冲突概念，详细内容下面会讲）

使用 hash function 会带来一个问题：可能有不同元素被映射到同一个位置。这无法避免，因为元素个数大于array容量。这便是所谓的“哈希冲突”或“哈希碰撞”。理想情况是找出一个好的哈希函数避免碰撞，单数实际场景中，冲突是不可避免的，所以要经肯呢个设计出优秀的哈希函数减少冲突，同时也要设计出解决冲突的方案。

4. 负载因子

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

5. 将关键字转为整数

我们将关键词映射到数组中位置，一般是整数做好映射计算，如果不是整数，我们要想办法转化成整数，这个细节我们后面代码实现中再进行细节展示。下面哈希函数我们讨论的是，如果关键词不是整数时，那么key就是关键词转换成的整数。

6. 哈希函数

一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计。

(1) 除法散列法/除留余数法

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

①  当使用除法散列法时，要尽量避免M为某些值，比如2的幂，10的幂等，而应该取素数（质数）。

<1> 如果是2的幂，那么  %  本质相当于保留key的后x位，那么后x位相同的值，计算出的哈希值是一样的，会发生冲突！例如：{63,31}看起来没有关联，但如果M是16，也就是2的4次方，那么计算出的哈希值是二进制后的4位，都是15，因为63的二进制值的后八位是00111111,而31的二进制后8位是00011111。

<2> 如果是10的幂，就更明显了，保留的都是10进制的后x位，如：{112,12312}，如果M是100，也就是10的2次方，那么计算出来的哈希值都是12。

② Java的HashMap采用除法散列法时就是2的整数次幂做哈希表的大小M，这样玩的话，就不用取模了，而可以直接用位运算，相对而言位运算比模更高效。但是他不是单纯的取模，比如M是2^16次方，本质是取后16位，那么key' = key >> 16，然后把key和key'异或的结果作为哈希值h(key) = key ^ key'。也就是说我们映射出的值还是在 [0，M) 范围内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀一些即可。

假设x是将要被映射的元素，y是整数次幂（y最好是从16开始取或取较小数进行多次异或），pow函数是幂函数，pow(x,y)表示x的y次方，哈希函数为：( x & ( pow(2,y) -1 ) ) ^ ( x >> ( 32 - y ) )

( pow(2,y) -1 ) ：得到的二进制是y个1

( x & ( pow(2,y) -1 ) ) : 取x二进制的后y位

( x >> ( 32 - y )）：取x的前（32-y）位二进制

( x & ( pow(2,y) -1 ) ) ^ ( x >> ( 32 - y ) ) ：^后得到的数就是我们要的哈希值，

(2) 乘法散列法

(3) 全域散列法

● 如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，比 如，让所有关键字全部落入同一个位置中。这种情况是可以存在的，只要散列函数是公开且确定 的，就可以实现此攻击。解决方法自然是见招拆招， 给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。 ●  h (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, 则 h (8) = ( ( 3 × 8 + 4 ) % 17 ) % 6  = 5 ● 需要注意的是 每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续增删查改都固定使用这个散列函数 ，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数， 查找又是另一个散列函数，就会导致找不到插入的key了。

(4) 其他方法

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

7.处理哈希冲突

实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了冲突，那么插入数据时，如何解决冲突呢？主要有两种方法，开放地址法和链地址法。

(1) 开放地址法

在开放地址法中所有的元素都放到哈希表里，当一个关键字key用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储（开放定址法中负载因子一定是小于1的）。这里的规则有三种：线性探测、二次探测、双重探测。

① 线性探测（linear probing）

● 从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。

● h (key) = hash0 = key % M，hash0位置冲突了，则线性探测公式为：                                          hc (key,i) - hashi = ( hash0 + i ) % M，i = {1,2,3,...,M-1}，负载因子小于1，则多探测M-1次，一定呢呢个找到一个存储key的位置。

● 线性探测的问题假设，hash0，hash1，hash2，hash3位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，凸显出的一个问题：平均插入成本的增长幅度，远高于负载因子的成长幅度。这样的现象在hashing过程中称为群集/堆积/主集团。此时的我们手上有的是一团一被用过的方格，插入过程很有可能在主集团所形成的堆积中爬行，不断解决碰撞问题，最后才插入成功，但是却也增长了主机团的堆积面积。

● 下面演示 {89,18,49,58,9} 这一组值映射到M等于10的表中：

② 二次探测（quadratic probing）

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

下面是二次探测的一个实例：

 二次探测带来的疑问：

● 二次探测能否保证每次探测的位置都必然是一个不同的位置？能否保证如果表格中没有X，那么我们插入的X一定能成功？

   当我们假设表格的大小是质数，而且永远保持负载系数在0.5以下，那么就可以确定每插入一个新元素所需要的线性探测不多于2。

● 线性探测的运算过程比较简单，二次探测法则明显复杂得多，这样是否会在执行效率上带来负面影响？

   众所周知，乘法和除法的底层其实就是+和-，二次探测直接用 i^2其实是很很耗时的，但是我们可以用一个很有意思的小设计可以去除耗时的乘法和除法：

hash (i) = ( hash0 + i^2 ) % M

hash (i-1) = ( hash0 + ( i -1 )^2 ) % M

-> hash(i) - hash (i-1) = ( i^2 - (i-1)^2 ) % M

-> hash(i) = hash (i-1) + ( 2i -1) % M  

这样我们就可以用前一个hash值来计算下一个hash值，就不需要执行二次方所需要的乘法。虽然还是要用乘法，但那是 *2，可以用左移操作符（<<1相当于*2）快速完成。

● 不论线性探测还是二次探测，当负载系数过高时，表格能否动态增长？

   欲扩充表格首先必须找出下一个新的而且够大的（大约两倍）的质数，然后必须考虑表格重建的成本，不可能是原封不动的拷贝，我们必须检验旧表格的每一个元素，计算其在新表格的位置，然后再插入新表。

③ 双重探测

第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。h1(key) = hash0 = key % M，hash0位置冲突了，则双重探测公式为： hc(key,i) = hashi = (hash0 + i * h2(key)) % M，i = {1, 2, 3, ..., M}要求 h2(key) 且 h2(key) 和 M 互为质数，有两种简单的取值方法：1、当 M 为 2 的整数幂时，从 [0，M-1] 任选一个奇数；2、当 M 为质数时，h2(key) < M。h2(key) = key % (M − 1) + 1保证 h2(key) 与 M 互质是因为根据固定的偏移量所寻址的所有位置将形成一个群，若最大公约数 p = gcd(M, h2(key)) > 1，则所能寻址的位置的个数为 M/p < M，使得对于一个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，则所能寻址的位置为{1, 4, 7, 10}，寻址个数为 12/gcd(12, 3) = 4。

(2) 开放地址法模拟实现

开放定址法解决冲突不管使用哪种方法，占用的都是哈希表中的空间，始终存在互相影响的问题。所以开放定址法，我们简单选择线性探测实现即可。

① 开放定址法的哈希表结构

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 HashTable{private:vector<HashData<K, V>> _tables;size_t _n = 0; // 表中存储数据个数};

② 扩容

我们将哈希表负载因子控制在0.7，当负载因子到0.7以后我们就扩容，我们想要保持哈希表的大小是一个质数，所以不能用2被扩了。方案一，使用除留余数法中我们讲过过的Java 的HashMap的方法；方案二，就是SGI实现哈希表的方法，给一个近似2倍的质数表，每次到质数表中获取扩容后的大小。

// 扩容inline unsigned long __stl_next_prime(unsigned long n){// 注意：假设long至少是32位(long 的大小可能因编译器和平台而异)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;// lower_bound()是泛型算法，使用前序列必须是有序的const unsigned long* pos = lower_bound(first, last, n); // lower_bound()取 >= // 找出上述28个素数中最接近并大于或等于n的那个质数return pos == last ? *(last - 1) : *pos;}

③ key不能取模的问题

当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加一个仿函数，这个仿函数支持把key转换成一个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数就用默认参数即可，如果key不能转换成整形，就需要自主实现一个仿函数。实现这个仿函数的要求就是尽量key的每个值都参与到计算中，让不同的key转换出的整型值不同，string做哈希表的key非常常见，所以把string特化一下。

对于自定义类型（如Date）不仅要特化实现仿函数，还要内部实现元素比较相等。

● 字符串转换成整形，可以把字符ascii码相加即可

● 但是直接相加的话，类似"ab"和"ba"这样的字符串计算出是相同的
● 这里我们使用BKDR哈希的思路，用上次的计算结果去乘以一个质数，这个质数一般用31, 131等效果会比较好

            // ab : ( ( 97*131 ) + 98 ) * 131 = 1677455
            // ba : ( ( 98*131 ) + 97 ) * 131 = 1694485

● string的组合数26^16远大于size_t的组合数2^32，有风险性，冲突不可避免！

★★★ hashtable对key的要求是什么 ？

1、支持比较相等 2、支持转成整形(可用仿函数)

注：RBTree对key的要求是支持比较大小。

// 仿函数模版：返回一个可以执行取模运算(%)的数值template<class K>struct HashFunc{size_t operator()(const K& key){ // 这里的模版针对char,int,long等整数类别的值,只是单纯的返回原值return (size_t)key;}};// 对于string等容器或自定义类型,无法强转成size_t,就需要自己实现一个特化版本// 对于自定义类型如struct Date内除了要自主实习仿函数还要支持比较相等！template<>struct HashFunc<string>{size_t operator()(const string& s){size_t hash = 0;for (auto str : s){hash *= 131;hash += str;}// 这里如果hash整形溢出，对于无符号整数会发生值环绕// 类似于取模运算，但并不是显示的(从0重新开始)return hash;}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:private:    vector<HashData<K, V>> _tables;    size_t _n = 0; // 表中存储数据个数};

④ 完整代码

enum State{EMPTY, // 空EXIST, // 有值DELETE // 销毁};template<class K, class V>struct HashData{pair<K,V> _kv;State _state = EMPTY; //给每个存储位置一个状态值};// 仿函数模版：返回一个可以执行取模运算(%)的数值template<class K>struct HashFunc{size_t operator()(const K& key){ // 这里的模版针对char,int,long等整数类别的值,只是单纯的返回原值return (size_t)key;}};// 对于string等容器或自定义类型,无法强转成size_t,就需要自己实现一个特化版本// 对于自定义类型如struct Date内除了要自主实习仿函数还要支持比较相等！template<>struct HashFunc<string>{// 字符串转换成整形，可以把字符ascii码相加即可// 但是直接相加的话，类似"ab"和"ba"这样的字符串计算出是相同的// 这里我们使用BKDR哈希的思路，用上次的计算结果去乘以一个质数，这个质数一般用31, 131等效果会比较好size_t operator()(const string& s){size_t hash = 0;for (auto str : s){hash *= 131;hash += str;// ab : ((97*131)+98)*131 = 1677455// ba : ((98*131)+97)*131 = 1694485}// 这里如果hash整形溢出，对于无符号整数会发生值环绕// 类似于取模运算，但并不是显示的(从0重新开始)// 注:string的组合数26^16远大于size_t的组合数2^32，有风险性，冲突不可避免！return hash;}};// 扩容inline unsigned long __stl_next_prime(unsigned long n){// 注意：假设long至少是32位(long 的大小可能因编译器和平台而异)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;// lower_bound()是泛型算法，使用前序列必须是有序的const unsigned long* pos = lower_bound(first, last, n); // lower_bound()取 >= // 找出上述28个素数中最接近并大于或等于n的那个质数return pos == last ? *(last - 1) : *pos;}namespace zyt{template<class K,class V,class Hash = HashFunc<K>>struct Hashtable{public:Hashtable():_tables(__stl_next_prime(0)),_n(0){}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 负载因子 >= 0.7扩容if (_n * 10 / _tables.size() >= 7){Hashtable<K, V, Hash> newht;//newht._tables.resize(_tables.size()*2); // 尽量避免为2的幂// 一定要强转，不然你想象不到会报什么奇怪的错，气死我了！！！！unsigned long len = (unsigned long)_tables.size() + 1;size_t newsize = __stl_next_prime(len);newht._tables.resize(newsize);for (auto& data : _tables){// 旧表的数据映射到新表if (data._state == EXIST){newht.Insert(data._kv);}}// 交换资源_tables.swap(newht._tables);}Hash hash; //仿函数size_t hashi = hash(kv.first) % _tables.size(); //算出要插入的下标while (_tables[hashi]._state == EXIST){// 线性探测++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;} // 查找，返回找到的数据HashData<K,V>* Find(const K& key){Hash hs; //仿函数size_t hash0 = hs(key) % _tables.size(); // 除留余数法，算出key映射的下标位置size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}// 线性探测hashi = (hash0 + i) % _tables.size();++i;}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr)return false;else{ret->_state = DELETE;return true;}}private:vector<HashData<K, V>> _tables;size_t _n; // 哈希表储存元素的个数};}

④ 测试用例

#include"hashtable.h"void test1(){zyt::Hashtable<int,int> hash;hash.Insert({ 1,1 });hash.Insert({ 2,2 });hash.Insert({ 3,3 });hash.Insert({ 4,4 });cout << hash.Find(1)->_kv.first << endl;cout << hash.Erase(1) << endl;cout << hash.Erase(3) << endl;cout << hash.Erase(7) << endl;}void test2(){int a[] = { 19,30,5,36,13,20,21,12 };zyt::Hashtable<int, int> ht;for (auto e : a){ht.Insert({ e, e });}//ht.Insert({ 15, 15 });ht.Erase(30);if (ht.Find(20)){cout << "找到了" << endl;}if (ht.Find(30)){cout << "找到了" << endl;}else{cout << "没有找到" << endl;}}void test3(){const char* a1[] = { "abcd", "sort", "insert" };zyt::Hashtable<string, string> ht1;for (auto& e : a1){ht1.Insert({ e, e });}cout << HashFunc<string>()("abcd") << endl;cout << HashFunc<string>()("bcad") << endl;cout << HashFunc<string>()("aadd") << endl;}struct Date{int _year;int _month;int _day;Date(int year = 1, int month = 1, int day = 1):_year(year), _month(month), _day(day){}// 内部支持比较相等bool operator==(const Date& d){return _year == d._year&& _month == d._month&& _day == d._day;}};struct DateHashFunc{ // 仿函数返回可以被%的整数size_t operator()(const Date& d){size_t hash = 0;hash += d._year;hash *= 131;hash += d._month;hash *= 131;hash += d._day;hash *= 131;return hash;}};void test4(){int a2[] = { -19,-30,5,36,13,20,21,12 };zyt::Hashtable<int, int> ht2;for (auto e : a2){ht2.Insert({ e, e });}// 哈希冲突zyt::Hashtable<Date, int, DateHashFunc> ht;ht.Insert({ { 2024, 10, 12 }, 1});ht.Insert({ { 2024, 12, 10 }, 1 });}

(3) 链地址法

开方地址法中所有元素都放在哈希表中，链地址法中所有数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射到这个位置，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突数据连接成一个链表，挂在哈希表映射位置的下面，链地址法也叫做哈希桶或拉链法

① 扩容

链地址法的负载因子没有限制，可以大于1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；STL中unordered_xxx的最大复杂因子基本都控制在1，大于1就扩容，我们实现也用这个方法。

② 极端情况

Java中一要求链表长度 > 8时，用 rbtree 代替存储。=> 表格链的节点中存储的就不是Node*了，而是一个一个的对象(head/root/len...)，从原来的指针数组变成对象数组。

③ 链地址法完整代码

// 仿函数模版：返回一个可以执行取模运算(%)的数值template<class K>struct HashFunc{size_t operator()(const K& key){ // 这里的模版针对char,int,long等整数类别的值,只是单纯的返回原值return (size_t)key;}};// 对于string等容器或自定义类型,无法强转成size_t,就需要自己实现一个特化版本// 对于自定义类型如struct Date内除了要自主实习仿函数还要支持比较相等！template<>struct HashFunc<string>{// 字符串转换成整形，可以把字符ascii码相加即可// 但是直接相加的话，类似"ab"和"ba"这样的字符串计算出是相同的// 这里我们使用BKDR哈希的思路，用上次的计算结果去乘以一个质数，这个质数一般用31, 131等效果会比较好size_t operator()(const string& s){size_t hash = 0;for (auto str : s){hash *= 131;hash += str;// ab : ((97*131)+98)*131 = 1677455// ba : ((98*131)+97)*131 = 1694485}// 这里如果hash整形溢出，对于无符号整数会发生值环绕// 类似于取模运算，但并不是显示的(从0重新开始)// 注:string的组合数26^16远大于size_t的组合数2^32，有风险性，冲突不可避免！return hash;}};namespace hash_bucket{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 Hash = HashFunc<K>>struct Hashtable{typedef HashNode<K, V> Node;public:Hashtable():_tables(11) // 0到10,_n(0){}                ~Hashtable()        {        // 依次把每个桶析构        for (size_t bucket = 0; bucket < _tables.size(); bucket++)        {        Node* cur = _tables[bucket];        // 删除bucket的每个节点        while (cur)        {        Node* last = cur->_next;        delete cur;        cur = last;        }        _tables[bucket] = nullptr;        }            _n = 0;        // 注意：_tables vector没有释放掉空间，仍保持原来大小        }// 允许键值重复bool Insert(const pair<K, V>& kv){Hash hs;// 负载系数等于1扩容if (_n = _tables.size()){vector<Node*> newTables(_tables.size() * 2);// 处理每一个旧bucketfor (size_t bucket = 0; bucket < _tables.size(); bucket++){Node* first = _tables[bucket]; //指向原桶节点所对应串行的起始节点// 处理每一个旧bucket所含的每一个节点while (first){// 找到节点在新标的位置size_t newhashi = hs(first->_kv.first) % newTables.size();// 1.让旧bucket指向其所对应串行的下一个节点(以便迭代处理)_tables[bucket] = first->_next;// 2.将当前节点直接转插入到新表内first->_next = newTables[newhashi];// 3.成为其对应串行的第一个节点(头插)newTables[newhashi] = first;// 4.指针回到旧bucket所指的待处理串行，准备处理下一个节点first = _tables[bucket];}_tables[bucket] = nullptr; // 一串行的节点已经被转移到新表了}// 新旧表交换资源,出函数时局部变量newTables释放的内存是原来旧表的空表格_tables.swap(newTables); }// 插入新节点(头插)size_t hashi = hs(kv.first) % _tables.size(); // 映射的哈希值Node* newnode = new Node(kv);newnode->_next = _tables[hashi];// _tables[hashi]表示原链表的第一个节点_tables[hashi] = newnode; // 令新节点成为链表的第一个结点++_n;return true;}Node* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size(); // 定位Node* first = _tables[hashi];while (first){if (first->_kv.first == key)return first;elsefirst = first->_next;}return nullptr;}bool Erase(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* node = _tables[hashi]; while (node){if (node->_kv.first == key){if (prev == nullptr) // 删除的是第一个节点{_tables[hashi] = node->_next;}else{prev->_next = node->_next;}delete node;--_n;return true;}prev = node;node = node->_next; // 向下找}return false;}private:vector<Node*> _tables; // 指针数组size_t _n;};}

④ 测试代码

#include"hashbuckets.h"void test5(){int a2[] = { 19,30,5,36,13,20,21,12,24,96 };hash_bucket::Hashtable<int, int> ht2;for (auto e : a2){ht2.Insert({ e, e });}ht2.Insert({ 100, 100 });ht2.Insert({ 101, 101 });cout << ht2.Find(100)->_kv.first << endl;ht2.Erase(19);ht2.Erase(30);cout << ht2.Find(19) << endl;cout << ht2.Find(30) << endl;}