【C++】——精细化哈希表架构：理论与实践的综合分析 ...

先找出你的能力在那里，然后再决定你是谁。
—— 塔拉·韦斯特弗 《你当像鸟飞往你的山》

---

目录
1. C++ 与哈希表：核心概念与引入
2. 哈希表的底层机制：原理与挑战
2.1 核心功能剖析：效率与灵活性的均衡
2.2 哈希辩论的本质：问题与应对计谋
2.3 开散列与闭散列：两大办理方案的比力
3. 闭散列的精确实现：从设计到优化
3.1 整体框架设计：面向扩展的架构
3.2 仿函数的灵活性：高效哈希的关键
3.3 插入操作：辩论检测与位置分配
3.4 查找操作：速度与准确的双重保障
3.5 删除操作：标记与重构的细节优化
4. 开散列的灵活实现：从底子到高效
4.1 节点设计：指针与数据的均衡艺术
4.2 整体框架搭建：链表与逻辑的融合
4.3 插入函数：链表拓展与哈希分布
4.4 删除函数：节点清算与空间复用
4.5 查找操作：定位效率的优化实践
4.6 功能测试：多场景验证与性能分析

---

1、C++ 与哈希表：核心概念与引入

哈希表（Hash Table）是一种紧张的数据结构，它通过哈希函数将键映射到表中的特定位置，从而实现对纪录的快速访问，支持高效的插入和查找操作。
哈希表的概念最早由H. P. Luhn于1953年提出，他首次描述了使用哈希函数加速数据检索的过程。自此，这一头脑渐渐演化并广泛应用于数据库管理系统和编程语言中，成为盘算机科学范畴的紧张底子之一。
随着盘算机硬件性能的提拔和数据量的爆炸性增长，哈希表的作用愈发凸显。作为一种高效的数据结构，哈希表在软件工程、数据库系统、网络搜刮引擎等范畴饰演着不可或缺的角色，尤其在处理大规模数据和高频率查询时展现出卓越的性能优势。
在C++中，哈希表的功能重要通过unordered系列关联式容器实现。在C++98标准中，STL提供了一组底层基于红黑树的关联式容器，如map和set。这些容器在最坏情况下的查询复杂度为O(log N)，即需要进行与红黑树高度成比例的比力操作。当树的节点数目巨大时，查询效率大概会受到显著影响。
为了进一步提拔查询性能，C++11引入了四种unordered系列的关联式容器，包括unordered_map、unordered_set、unordered_multimap和unordered_multiset。这些容器在使用方式上与传统的红黑树关联式容器相似，但其底层实现基于哈希表。通过哈希函数的高效映射，unordered容器在平均情况下可以或许实现O(1)的常数级查询复杂度，极大地进步了数据访问速度，尤其适用于对查询性能要求较高的场景。
总之，哈希表及其在C++中的实现，不但优化了数据存储与检索效率，还推动了现代软件开辟在处理大规模数据时的能力边界，成为盘算机科学范畴中不可或缺的核心技术之一。
2、哈希表的底层机制：原理与挑战

2.1 核心功能剖析：效率与灵活性的均衡

在序次结构和均衡树中，元素的关键码与其存储位置之间并没有直接的对应关系。因此，在查找一个元素时，必须通过多次比力其关键码。在序次查找中，时间复杂度为 O(N），而在均衡树中，查找时间复杂度为树的高度 O(log2N))，搜刮效率取决于查找过程中元素比力的次数。
理想的搜刮方法：可以不经过任何比力，一次直接从表中得到要搜刮的元素。为此，我们可以构造一种特殊的存储结构，通过一个哈希函数（hashFunc）将元素的存储位置与其关键码（key）创建逐一映射关系。在这种结构中：

• 插入元素：通过哈希函数盘算待插入元素的存储位置，并将元素存储在该位置。
  
• 搜刮元素：盘算元素的关键码对应的存储位置，直接访问该位置。如果该位置的元素关键码与待查找的元素类似，则搜刮成功。
  

2.2 哈希辩论的本质：问题与应对计谋

对于两个数据元素的关键字 ，如果其下标不同，对应的元素值也不同。但哈希函数盘算效果却是类似，即 Hash（ki）==Hash（kj），简单说两个不同的key大概会映射到同个位置去
这种现象称为哈希辩论或哈希碰撞。
哈希辩论的发生大概是由于哈希函数的设计问题。一个好的哈希函数应该满足以下原则：

• 界说域覆盖所有关键字：哈希函数的界说域必须包含所有需要存储的关键字；如果散列表允许有 m个地址，则哈希函数的值域应当在 0到 m-1 之间。
  
• 匀称分布：哈希函数应能将关键字匀称地映射到整个地址空间中，减少辩论的概率。
  
• 盘算简单：哈希函数应设计得尽大概简单，以进步盘算效率。
  

然而，由于存储空间有限，哈希函数难以完全制止哈希辩论的发生。因此，发生哈希辩论时，系统需要采取得当的处理方法。通常，哈希辩论的办理方案有两种常见方法：闭散列（Open Addressing）和开散列（Chaining）。
在闭散列中，当发生辩论时，探求一个空位将元素存储在散列表中。这通常通过线性探测、二次探测或双重散列等技术实现。
在开散列中，当发生辩论时，多个元素被存储在同一个地址位置的链表中，通常采用链表或其他数据结构来存储这些“同义词”。
在讨论哈希辩论的处理方法时，另一个紧张的概念是负载因子（Load Factor）。负载因子是哈希表中元素个数与表的总容量之间的比值，通常表现为：

负载因子反映了哈希表的“密集程度”。当负载因子较高时，意味着哈希表中存储的元素靠近其总容量，发生哈希辩论的概率增大；相反，负载因子较低时，哈希表中的元素较少，辩论的概率较小。
负载因子的应用与影响：

• 影响哈希辩论的概率：负载因子越大，哈希表中的元素越密集，碰撞的概率也越高。为了降低辩论发生的概率，通常在负载因子达到肯定阈值时，会进行哈希表的扩容，将哈希表的容量增大，从而降低负载因子并减少辩论。
  
• 闭散列中的负载因子：在闭散列法中，当负载因子增大时，查找、插入等操作的时间复杂度会增加。因为哈希表的空闲位置减少，辩论发生后需要进行探测，大概导致操作变得低效。为制止这种情况，当负载因子凌驾肯定值（通常为 0.7 或 0.75）时，会触发扩容操作，将哈希表的巨细翻倍，并重新盘算每个元素的哈希地址。
  
• 开散列中的负载因子：在开散列法中，负载因子的增大会导致链表的长度增加，进而影响查找效率。当负载因子过高时，链表变长，查找、插入和删除操作的时间复杂度会退化为线性时间 O(n)。因此，在开散列中，通常也会采取相似的计谋，监控负载因子的变革，当负载因子凌驾某个阈值时，进行扩容或重新哈希。
  

2.3 开散列与闭散列：两大办理方案的比力

哈希（散列）方法是一种高效的数据存储和检索方式，其核心在于哈希函数和哈希表的构建。通过哈希函数将数据映射到数组索引上，可以快速定位元素。然而，当多个数据被映射到类似的索引（即哈希辩论）时，需要采取有效的计谋进行处理。根据办理辩论的方式，哈希表分为两种范例：闭散列和开散列。
闭散列（开放定址法）
闭散列的核心头脑是将辩论的元素存放到哈希表中的其他空位置。其重要实现方式是线性探测：

• 插入：通过哈希函数盘算得到目标位置。如果该位置为空，则直接插入；若发生辩论，则从辩论位置开始，依次向后探测，直到找到空位置为止，再插入元素。例如，若元素44盘算出的哈希地址为4，但位置4已存有元素4，则继承向后探测，找到下一个空位置存放44。
  
• 删除：采用伪删除标记着代物理删除，以免影响其他元素的搜刮路径。例如，若直接删除元素4，则会导致后续查找44时路径断裂，因此采用标记伪删除的方法。
  

优点：

• 实现简单，无需额外数据结构支持。
  

缺点：

• 容易产生数据堆积（又称“聚集”），即多个辩论元素连续占据空位置，导致后续插入和查找的效率显著下降。
  
• 空间使用率较低，特别是在装载因子较高时，辩论频率增加，性能退化明显。
  

为缓解上述问题，可以使用二次探测法或其他改进方法优化辩论处理。
开散列（链地址法）
开散列通过为每个哈希地址维护一个链表来办理辩论：

• 插入：盘算哈希地址后，将辩论元素添加到对应链表的末尾。
  
• 删除：直接从链表中删除目标元素，链表结构确保不会影响其他元素的查找。
  

优点：

• 空间使用率高，能更好地适应高装载因子。
  
• 辩论处理灵活，不会产生数据堆积，查找效率相对稳定。
  

缺点：

• 需要额外的链表存储空间。
  
• 链表操作增加了肯定的复杂性。
  

演示两种方法 {19,30,5,36,13,20,21,12,24,96} 这组值映射到M=11的表中，采用的哈希函数：
除法散列法也叫做除留余数法，顾名思义，假设哈希表的巨细为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

3、闭散列的精确实现：从设计到优化

3.1 整体框架设计：面向扩展的架构

首先我们需要进行一个简单的框架搭建：
   

• 我们需要一个HashData类，来储存数据
  
• HashTable类底层是vector容器
  
• 因为会有不同范例的key，所以我们需要一个仿函数来将不同范例转换为size_t，这样才支持哈希函数映射
  
• 因为闭散列的删除不能直接删除节点，否则会导致线性探测失效，所以HashData类里需要纪录状态
  

1. //版本一 --- 开放地址法（闭散列）
2. #include<utility>
3. #include<iostream>
4. #include<vector>
5. using namespace std;
7. //节点状态
8. enum status
9. {
10.         EXIST,
11.         EMPTY,
12.         DELETE
13. };
14. //设计节点
15. template<class K, class V>
16. struct HashData
17. {
18.         //键值对
19.         pair<K, V> _kv;
20.         //状态
21.         status _status;
22. };
23. // kv键值，仿函数解决不同类型key转换为size_t类型的下标
24. template<class K,class V,class Hash=HashFunc<K>>
25. class HashTable
26. {
27. public:
28.         HashTable()
29.         {
30.                 _table.resize(10);
31.         }
32. private:
33.         //底层是vector容器
34.         vector<HashData K, V>> _table;
35.         size_t _n;//有效数据个数
36.     Hash hs；//仿函数
37. };

复制代码

3.2 仿函数的灵活性：高效哈希的关键

仿函数的作用是将不同数据范例的key转换为可以使用的size_t范例，这样可以才气一 一映射已往
对于可以直接表现范例转换的范例直接转换即可。而对于不能直接转换的范例（好比string）就要进行特殊处理了！

1. template<class K>
2. struct HashFunc
3. {
4.         size_t operator()(const K& key)
5.         {
6.                 return (size_t)key;
7.         }
8. };
10. template<>
11. struct HashFunc<string>
12. {
13.         size_t operator()(const string& s)
14.         {
15.                 // BKDR
16.                 size_t hash = 0;
17.                 for (auto ch : s)
18.                 {
19.                         hash += ch;
20.                         hash *= 131;
21.                 }
23.                 return hash;
24.         }
25. };

复制代码

3.3 插入操作：辩论检测与位置分配

• 首先插入之前要先检查是否在哈希表中已经有数据了
  
• 然后检查该次是否需要进行扩容
  
• 通过key值选取合适位置进行插入，有效个数++
  
  1. bool insert(const pair<K, V>&kv)
  2. {
  3.         //插入前先进行一个检查
  4.         if (Find(kv.first)) return false;
  5.         //是否需要扩容
  6.         if (_n >= _table.size() * 0.7)
  7.         {
  8.                 //进行替换
  9.                 HashTable<K, V> newHT;
  10.                 newHT._table.resize(_table.size() * 2);
  11.                 //进行赋值
  12.                 for (auto &s : _table)
  13.                 {
  14.                         if (s._status == EXIST)
  15.                                 newHT.insert(s._kv);
  16.                 }
  17.                 //进行替换！！！
  18.                 _table.swap(newHT._table);
  19.         }
  20.         //进行插入
  21.         //hash地址
  22.         size_t hash0 = kv.first % _table.size();
  23.         size_t hashi = hash0;
  24.         size_t i = 1;
  25.         //寻找合适位置进行插入
  26.         // 线性探测
  27.         while (_table[hashi].status == EXIST)
  28.         {
  29.                 hashi = (hash0 + i) % _table.size(); //取模解决回绕问题
  30.                 ++i;
  31.         }
  32.         //找到合适位置了进行插入
  33.         _table[hashi]._kv = kv;
  34.         _table[hashi].status = EXIST;
  35.         _n++;
  36.         return true;
  37. }

  复制代码

3.4 查找操作：速度与准确的双重保障

查找逻辑很简单对Key进行线性探测即可

1. HashData<K, V>* Find(const K& key)
2. {
3.         size_t hash0 = hs(key) % _table.size();
4.         size_t hashi = hash0;
5.         size_t i = 1;
6.         while (_table[hashi]._state != EMPTY)
7.         {
8.                 if (_table[hashi]._state == EXIST
9.                         && _table[hashi]._kv.first == key) //这里需要加判断状态语句 我们删除只是该状态
10.                 {
11.                         return &_table[hashi];
12.                 }
14.                 // 线性探测
15.                 hashi = (hash0 + i) % _table.size();
16.                 ++i;
17.         }
18.         return nullptr;
19. }

复制代码

3.5 删除操作：标记与重构的细节优化

删除先通过key找到需要删除的数据
然后将状态设置为DELETE, 有效个数- -

1. //删除
2. bool Erase(const K& key)
3. {
4.         //size_t hash0 = hs(key) % _tables.size();
5.         //size_t hashi = hash0;
6.         //size_t i = 1;
7.         //while (_table[hashi]._state != EMPTY)
8.         //{
9.         //        if (_table[hashi]._state == EXIST
10.         //                && _table[hashi]._kv.first == key)
11.         //        {
12.         //                _table[hashi].status = DELETE;
13.         //                --_n;
14.         //                return true;
15.         //        }
16.         //        // 线性探测
17.         //        hashi = (hash0 + i) % _tables.size();
18.         //        ++i;
19.         //}
20.         //return  false;
22.         //复用 Find
23.         HashData<K, V>* ret = Find(key);
24.         if (ret == nullptr)
25.         {
26.                 return false;
27.         }
28.         else
29.         {
30.                 ret->_status = DELETE;
31.                 --_n;
32.                 return true;
33.         }
34. }

复制代码

这里一开始的空间机制可以优化，我们使用的哈希函数是除法散列法也叫做除留余数法，当使用除法散列法时，建议M取不太靠近2的整数次冥的个质数(素数)。这样可以有效制止哈希辩论
优化一下：采用靠近2倍扩容的素数表进行开辟空间扩容

1. class HashTable
2. {
3. public:
4.         HashTable()
5.                 :_tables(__stl_next_prime(0))
6.                 , _n(0)
7.         {}
9.         inline unsigned long __stl_next_prime(unsigned long n)
10.         {
11.                 // Note: assumes long is at least 32 bits.
12.                 static const int __stl_num_primes = 28;
13.                 static const unsigned long __stl_prime_list[__stl_num_primes] = {
14.                         53, 97, 193, 389, 769,
15.                         1543, 3079, 6151, 12289, 24593,
16.                         49157, 98317, 196613, 393241, 786433,
17.                         1572869, 3145739, 6291469, 12582917, 25165843,
18.                         50331653, 100663319, 201326611, 402653189, 805306457,
19.                         1610612741, 3221225473, 4294967291
20.                 };
21.                 const unsigned long* first = __stl_prime_list;
22.                 const unsigned long* last = __stl_prime_list + __stl_num_primes;
23.                 const unsigned long* pos = lower_bound(first, last, n);
24.                 return pos == last ? *(last - 1) : *pos;
25.         }
27.         bool Insert(const pair<K, V>& kv)
28.         {
29.                 if (Find(kv.first))
30.                         return 0;
32.                 //负载因子>=0.7 扩容
33.                 if (_n*10 / _tables.size() >= 7)
34.                 {
35.                         HashTable<K, V>newht;
36.                         newht._tables.resize(__stl_next_prime(_tables.size() + 1));
37.                         for (auto& data : _tables)
38.                         {
39.                                 // 旧表的数据映射到新表
40.                                 if (data._state == EXIST)
41.                                 {
42.                                         newht.Insert(data._kv);
43.                                 }
44.                         }
45.                         _tables.swap(newht._tables);
47.                 }
48.                 size_t hash0 = kv.first % _tables.size();
49.                 size_t hashi = hash0;
50.                 size_t i = 1;
51.                 int flag = 1;
53.                 while (_tables[hashi]._state == EXIST)
54.                 {
55.                         // 线性探测
56.                         hashi = (hash0 + i) % _tables.size();
57.                         ++i;
59.                         /*hashi = (hash0 + (i*i*flag)) % _tables.size();
60.                         if (hashi < _tables.size())
61.                                 hashi += _tables.size();
63.                         if (flag == 1)
64.                         {
65.                                 flag = -1;
66.                         }
67.                         else
68.                         {
69.                                 ++i;
70.                                 flag = 1;
71.                         }*/
72.                 }
74.                 _tables[hashi]._kv = kv;
75.                 _tables[hashi]._state = EXIST;
76.                 ++_n;
78.                 return 1;
79.         }
81.         HashData<K, V>* Find(const K& key)
82.         {
83.                 size_t hash0 = key % _tables.size();
84.                 size_t hashi = hash0;
85.                 size_t i = 1;
86.                 while (_tables[hashi]._state != EMPTY)
87.                 {
88.                         if (_tables[hashi]._state == EXIST
89.                                 && _tables[hashi]._kv.first == key)
90.                         {
91.                                 return &_tables[hashi];
92.                         }
94.                         // 线性探测
95.                         hashi = (hash0 + i) % _tables.size();
96.                         ++i;
97.                 }
99.                 return nullptr;
100.         }
102.         bool Erase(const K& key)
103.         {
104.                 HashData<K, V>* ret = Find(key);
105.                 if (ret == nullptr)
106.                         return 0;
107.                 ret->_state = DELETE;
108.                 return 1;
109.                
110.         }
111. private:
112.         vector<HashData<K, V>> _tables;
113.         size_t _n; //标识数据个数
114. };

复制代码

这样我们就实现了开辟地址法（闭散列）的哈希表！！！
4. 开散列的灵活实现：从底子到高效

我们已经实现了闭散列版本的哈希表，本日计划实现另一种哈希表的实现方式——开散列版本（也称哈希桶）。在深入实现之前，让我们先分析所需的工作。
开散列的核心头脑是将哈希表设计为一个数组，每个数组元素对应一个映射地址。为了办理哈希辩论，开散列采用链表的情势将辩论的元素链接起来，从而确保高效的查找和插入操作。

由于涉及到链表的使用，我们可以直接使用 STL库的 list 数据结构。然而，list 本质上是一个双向循环链表，对我们这样简单的场景来说，大概显得有些复杂且不敷高效。为了简化实现并节流内存空间，我们可以自行构造一个简单的单向非循环链表，完全可以满足需求，同时节流约一半的空间。
通过这一设计，我们既可以制止闭散列中大概出现的过多探测问题，又能以较低的实现成本构建一个功能完备且高效的哈希表。
4.1 节点设计：指针与数据的均衡艺术

因为我们要实现单链表结构，肯定要来先设计一下节点框架：

1. //节点设计
2. template<class K, class V, class Hash = HashFunc<K>>
3. struct HashNode
4. {
5.         //储存的数据
6.         pair<K, V> _kv;
7.         //下一个节点的指针
8.         HashNode<K, V>* _next;
9.         HashNode(const pair<K, V>& kv)
10.                 :_kv(kv)
11.                 , _next(nullptr)
12.         {}
13. };

复制代码

4.2 整体框架搭建：链表与逻辑的融合

设计完成节点后，就可以动手构建整体框架了。哈希桶的底层结构通常由一个指针数组构成，同时需要引入一个变量用于纪录当前有效元素的个数，以便在负载因子过高时实时触发扩容操作。
实现的核心功能包括插入、删除和查找三个基本操作。需要注意的是，不同范例的数据在插入时需要通过哈希函数转换为 size_t 范例，这样才气将数据正确映射到数组中的对应位置。
在实现这些功能时，需要重点关注以下几点：

• 插入操作：根据哈希函数确定目标位置，处理大概的辩论，将新元素插入到对应链表中。
  
• 删除操作：查找到目标位置的链表节点并删除，同时需要妥善处理链表毗连。
  
• 查找操作：根据哈希函数定位到目标链表，然后序次查找目标节点。
  

通过上述基本功能的实现，我们可以构建一个高效的哈希桶结构，为后续功能扩展和优化打下结实底子。

1. namespace hash_bucket
2. {
3.     //仿函数 转整形
4.         template<class K>
5.         struct HashFunc
6.         {
7.                 size_t operator()(const K& key)
8.                 {
9.                         return (size_t)key;
10.                 }
11.         };
13.         template<>
14.         struct HashFunc<string>
15.         {
16.                 size_t operator()(const string& s)
17.                 {
18.                         // BKDR
19.                         size_t hash = 0;
20.                         for (auto ch : s)
21.                         {
22.                                 hash += ch;
23.                                 hash *= 131;
24.                         }
26.                         return hash;
27.                 }
28.         };
30.         //节点设计
31.         template<class K, class V, class Hash = HashFunc<K>>
32.         struct HashNode
33.         {
34.                 //储存的数据
35.                 pair<K, V> _kv;
36.                 //下一个节点的指针
37.                 HashNode<K, V>* _next;
38.                 HashNode(const pair<K, V>& kv)
39.                         :_kv(kv)
40.                         , _next(nullptr)
41.                 {}
42.         };
44.                 //开散列的哈希表
45.         //       key           value      仿函数（转换为size_t）
46.         template<class K, class V, class Hash = HashFunc<K>>
47.         class HashTable
48.         {
49.                 typedef HashNode<K, V> Node;
51.                 inline unsigned long __stl_next_prime(unsigned long n)
52.                 {
53.                         static const int __stl_num_primes = 28;
54.                         static const unsigned long __stl_prime_list[__stl_num_primes] =
55.                         {
56.                         53, 97, 193, 389, 769,
57.                         1543, 3079, 6151, 12289, 24593,
58.                         49157, 98317, 196613, 393241, 786433,
59.                         1572869, 3145739, 6291469, 12582917, 25165843,
60.                         50331653, 100663319, 201326611, 402653189, 805306457,
61.                         1610612741, 3221225473, 4294967291
62.                         };
63.                         const unsigned long* first = __stl_prime_list;
64.                         const unsigned long* last = __stl_prime_list +
65.                                 __stl_num_primes;
66.                         const unsigned long* pos = lower_bound(first, last, n);
67.                         return pos == last ? *(last - 1) : *pos;
68.                 }
69.         public:
70.                 HashTable()
71.                         :_tables(__stl_next_prime(0))
72.                         ,_n(0)
73.                 {}
74.         private:
75.                 vector<Node*> _tables; // 指针数组
76.                 //vector<list<pair<K, V>>> _tables;
77.                 size_t _n = 0; // 表中存储数据个数
79.                 //struct Date
80.                 //{
81.                 //        list<pair<K, V>>_list;
82.                 //        map<pair<K, V>>_map;
83.                 //        size_t len; // len <=8 _list >8 存_map 红黑树
84.                 //};
85.                 //vector<Date>_tables;
86.                 //size_t  n = 0;
87.         };
90. }

复制代码

4.3 插入函数：链表拓展与哈希分布

实现插入函数时，可以按照以下步调进行：

• 检查键是否存在：在插入新元素之前，首先检查当前键是否已经存在于哈希表中，只有在键不存在时才进行插入操作。
  
• 检查是否需要扩容：根据当前的负载因子（有效元素数与桶容量的比值），判定是否需要扩容以包管操作的效率。
  
• 盘算哈希值并定位映射位置：使用仿函数盘算键的哈希值 hashi，从而确定其在哈希表中的映射位置。
  
• 创建并插入新节点：构造一个新节点，并采用头插法将其插入到对应位置的链表中。
  

关于扩容逻辑，需要特别注意优化实现。最直观的方法是遍历原哈希表，将数据重新插入到新的哈希表中，并释放旧节点。然而，这种方式多做了无意义的节点释放与重建操作。实际上，我们可以直接将原有的节点从旧哈希表中迁移到新哈希表中，无需释放和重新分配，既节流了时间也优化了内存使用。

1. bool Insert(const pair<K, V>& kv)
2. {
3.         //先查找，已经有了相同数据插入失败
4.         if (Find(kv.first))
5.                 return 0;
7.         Hash hash;
9.         // 负载因子等于1时候 进行扩容
10.         if (_n==_tables.size())
11.         {
12.                 //HashTable<K, V>newht;
13.                 //newht._tables.resize(__stl_next_prime(_tables.size() + 1));
14.                 //for (size_t i = 0; i < _tables.size(); i++)
15.                 //{
16.                 //        Node* cur = _tables[i];
17.                 //        while (cur)
18.                 //        {
19.                 //                newht.Insert(cur->_kv);
20.                 //                cur = cur->_next;
21.                 //        }
22.                 //}
23.                 //_tables.swap(newht._tables);
24.                 // // 多次插入 繁琐
26.                 // 这?如果使?上?的?法，扩容时创建新的结点，后?还要使?旧结
27.                 //点，浪费了
28.                         // 下?的?法，直接移动旧表的结点到新表，效率更好
29.                 vector<Node*> newtable(__stl_next_prime(_tables.size() + 1));
30.                 for (size_t i = 0; i < _tables.size(); i++)
31.                 {
32.                        
33.                         Node* cur = _tables[i];
34.                         while (cur)
35.                         {
36.                                 Node* next = cur->_next;
37.                                 // 头插到新链表
39.                                 size_t hashi = hash(cur->_kv.first) % newtable.size();
40.                                 cur->_next = newtable[hashi];
41.                                 newtable[hashi] = cur;
42.                                 cur = next;
44.                         }
45.                         _tables[i] = nullptr;
46.                 }
47.                 _tables.swap(newtable);
48.         }
50.         size_t hashi = hash(kv.first) % _tables.size();
51.         // 头插
52.         Node* newnode = new Node(kv);
53.         newnode->_next = _tables[hashi];
54.         _tables[hashi] = newnode;
55.         ++_n;
56.         return 1;
57. }

复制代码

4.4 删除函数：节点清算与空间复用

删除的逻辑是根据key值找到对应的位置，在该位置的链表中检索是否有相称的数值。如果有就进行删除，否则返回false

1. bool Erase(const K& key)
2. {
3.        
4.         if (Find(key) == nullptr)
5.                 return 0;
7.         Hash hash;
8.         size_t hashi = hash(key) % _tables.size();
9.         Node* cur = _tables[hashi];
10.         Node* prev = nullptr;
11.         while (cur)
12.         {
13.                 if (cur->_kv.first == key)
14.                 {
15.                         if (prev == nullptr) //只有一个节点
16.                         {
17.                                 _tables[hashi] = cur->_next;
18.                         }
19.                         else //中间节点
20.                         {
21.                                 prev->_next = cur->_next;
22.                         }
23.                         delete cur;
24.                         --_n;
25.                         return 1;
26.                 }
27.                 else
28.                 {
29.             // 在链表里遍历到删除的数据
30.                         prev = cur;
31.                         cur = cur->_next;
32.                 }
33.         }
34.         return 0;
35. }

复制代码

4.5 查找操作：定位效率的优化实践

查找的逻辑和删除类似，根据key值找到映射位置，再在该链表中进行检索，找到返回节点指针，反之返回空指针。

1. Node* Find(const K& key)
2. {
3.         Hash hash;
4.         size_t hashi = hash(key) % _tables.size();
5.         Node* cur = _tables[hashi];
6.         while (cur)
7.         {
8.                 if (cur->_kv.first == key)
9.                 {
10.                         return cur;
11.                 }
12.                 cur = cur->_next;
13.         }
14.         return __nullptr;
15. }

复制代码

4.6 功能测试：多场景验证与性能分析

这里我们分别测试插入删除，插入探求，字符串的处理：

1. int main()
2. {
3.         int a[] = { 19,30,5,36,13,20,21,12,24,96 };
5.         hash_bucket::HashTable<int, int> ht2;
6.         for (auto e : a)
7.         {
8.                 ht2.Insert({ e,e });
9.         }
11.         cout << ht2.Find(96) << endl;
12.         cout << ht2.Find(30) << endl;
13.         cout << ht2.Find(19) << endl << endl;
15.         ht2.Erase(96);
16.         ht2.Erase(19);
17.         ht2.Erase(30);
19.         cout << ht2.Find(96) << endl;
20.         cout << ht2.Find(30) << endl;
21.         cout << ht2.Find(19) << endl << endl;
23.         hash_bucket::HashTable<string, string> ht3;
24.         const char* a2[] = { "abcd","sort","insert" };
25.         for (auto& e : a2)
26.         {
27.                 ht3.Insert({ e,e });
28.         }
29.         cout << ht3.Find("abcd") << endl;
31.         cout << ht3.Erase("abcd") << endl;
33.         return 0;
34. }

复制代码

看起来没有问题，调试看看分布：

通过对监督窗口的查看，我们可以验证我们的代码正常运行的！
Thanks谢谢阅读！！！


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。