【C++进阶】hash表的封装

hash表

哈希表是一种数据结构，它通过将键映射到存储桶或槽来快速查找数据。它的核心思想是通过一个哈希函数（Hash Function）将输入数据（键）转换为数组中的索引，以便在常数时间内进行查找、插入和删除操作。
哈希表的关键组成部门

• 哈希函数 (Hash Function)：将输入的键（key）映射为哈希表的索引。抱负的哈希函数应该均匀分布键，避免过多冲突。
  
• 存储桶 (Bucket)：每个哈希表的槽位。假如两个不同的键通过哈希函数得到了相同的索引（称为哈希冲突），多个键可以通过链表或其他方式存储在同一个槽中。
  
• 哈希冲突 (Hash Collision)：当不同的键映射到同一个存储桶时，发生冲突。常见的办理方法有：
  
  
  
  • 链地址法 (Separate Chaining)：在每个槽中存储一个链表，冲突的键会被添加到链表中。
    
  • 开放地址法 (Open Addressing)：通过重新计算索引（如线性探测、二次探测等），将冲突的键存储在下一个可用的槽位中。
    
  
  

哈希表的优缺点

优点：

• 平均环境下，哈希表的查找、插入和删除操作都能在 O(1) 时间复杂度内完成。
  

缺点：

• 当发生大量冲突时，查找和插入的性能可能退化到 O(n)。
  
• 哈希表的空间使用率不如树结构等其他数据结构高。
  

常见应用场景

哈希表常用于需要快速查找的场景，如数据库索引、缓存、字典等。
接下来我们将分别用开放定址法和哈希桶的方法来实现hash表
开放定址法实现hash表

起首我们在封装hash表之前要了解什么是负载因子。
负载因子 (Load Factor)

负载因子是指哈希表中已存储元素的数量与哈希表大小（存储桶数量）的比值，公式为：
                                         α                            =                                       n                               m                                            \alpha = \frac{n}{m}                     α=mn​

• n：哈希表中已存储的元素数量。
  
• m：哈希表的总存储桶（bucket）数量。
  

比方，假如哈希表有 100 个存储桶，已存储了 60 个元素，那么负载因子为：
                                         α                            =                                       60                               100                                      =                            0.6                                  \alpha = \frac{60}{100} = 0.6                     α=10060​=0.6
负载因子的意义

• 负载因子越小：意味着哈希表中空槽越多，冲突（collisions）的概率越低，查找和插入操作的性能更好。
  
• 负载因子越大：意味着哈希表中存储的元素越来越多，冲突的概率增长，查找和插入操作的效率下降。
  

负载因子的影响

• 假如负载因子过高（接近 1 或大于 1），冲突会变得频繁，导致性能下降。这时通常会进行再散列 (rehashing)，即扩展哈希表的大小，并重新计算全部元素的哈希值。
  
• 在一些常见的哈希表实现中，通常当负载因子超过肯定的阈值（如 0.75）时，会触发再散列操作，以保证哈希表的操作性能。
  

再散列 (Rehashing)

当负载因子达到阈值时，哈希表会增大存储桶的数量（通常是倍增），并重新计算全部已存储元素的哈希值，将它们放入新的存储桶中。这一操作固然代价较高，但可以避免长期的性能退化。
示例

假设一个哈希表的存储桶数量为 10：

• 当插入 5 个元素时，负载因子为：
  

                                         α                            =                                       5                               10                                      =                            0.5                                  \alpha = \frac{5}{10} = 0.5                     α=105​=0.5

• 当插入 9 个元素时，负载因子为：
  

                                         α                            =                                       9                               10                                      =                            0.9                                  \alpha = \frac{9}{10} = 0.9                     α=109​=0.9 此时可能需要进行再散列操作来扩展哈希表的大小。
团体框架

1.         //三种状态
2.         enum State
3.         {
4.                 EXIST,//存在
5.                 EMPTY,//空
6.                 DELETE//删除
7.         };
8.         template<class K, class V>
9.         struct HashData
10.         {
11.                 pair<K, V> _kv;
12.                 //初始状态是空
13.                 State _state = EMPTY;
14.         };
15.         template<class K, class V>
16.         class HashTable
17.         {
18.         public:
19.         private:
20.                 //用一个Hash表来存储
21.                 vector<HashData<K, V>> _tables;
22.                 //表中插入的数据个数
23.                 size_t _n = 0;
24.         };

复制代码

在开放定址法中，我们需要用一个状态来表示hash表中每个位置的状态，由于每个位置的状态不止两种，以是我们不能使用布尔值来表示每个位置的状态，应该使用enum来定义多种状态，我们定义三种状态（EMPTY，EXIST，DELETE）分别表示空，存在，删除。
在HashTables中_n表示hash表中插入了多少个数。
接下来我们来封装insert
insert

1. bool Insert(const pair<K, V>& kv)
2. {
3.         //去冗余
4.         if (Find(kv.first))
5.         {
6.                 return false;
7.         }
8.         //扩容，通过负载因子来进行扩容
9.         if (_n * 10 / _tables.size() == 7)//负载因子为0.7的时候进行扩容
10.         {
11.                 //不能直接进行resize，因为扩容之后空间变化了，映射也要跟着变化
12.                 //创建一个新表是以前表的二倍
13.                 HashTable<K, V>  newHT;
14.                 newHT._tables.resize(_tables.size() * 2);
15.                 for (size_t i = 0;i < _tables.size();i++)
16.                 {
17.                         if (_tables[i]._state == EXIST)
18.                         {
19.                                 //直接复用insert
20.                                 //这里不是自己调用自己，因为这里是两个对象
21.                                 newHT.Insert(_tables[i]._kv);
22.                         }
23.                 }
24.                 _tables.swap(newHT._tables);
25.         }
26.         Hash hs;
27.         //算起始位置
28.         size_t hashi = hs(kv.first) % _tables.size();
29.         //状态存在则继续
30.         while (_tables[hashi]._state == EXIST)
31.         {
32.                 hashi++;
33.                 //防止hashi越界
34.                 hashi %= _tables.size();
35.         }
36.         //添加值并且状态改为存在
37.         _tables[hashi]._kv = kv;
38.         _tables[hashi]._state = EXIST;
39.         _n++;
40.         return true;
41. }

复制代码

要进行插入我们起首需要找到插入位置，假如当我们找到位置的时候，当前位置已经被占据了，以是我们只能向后移动。

插入的及根本逻辑经济就是如此，既然有插入那肯定有插入位置满的时候，以是插入逻辑中应该涉及到扩容，但是我们不能直接进行扩容，因为当我们扩容的时候，每个data的映射的位置也会随之而变化，这就涉及到我们应该找到新的映射位置，但是对于开放定址法来说，我们不是在插入位置满的时候扩容，而是在负载因子到达0.7的时候进行扩容。

在扩容的时候，我们可以直接创建一个新表，然后在新表中重新映射数据，这里我们可以直接复用insert。（注意：这里调用的不是同一个insert，因为是两个不同的对象）
Find

1. HashData<K, V>* Find(const K& key)
2. {
3.         Hash hs;
4.         //算起始位置
5.         size_t hashi = hs(key) % _tables.size();
6.         //状态存在则继续
7.         while (_tables[hashi]._state != EMPTY)
8.         {
9.                 //这个状态不是DELETE才能进行查找
10.                 if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
11.                 {
12.                         return &_tables[hashi];
13.                 }
14.                 hashi++;
15.                 //防止hashi越界
16.                 hashi %= _tables.size();
17.         }
18.         return nullptr;
19. }

复制代码

对于查找来说我们只需要找到当前需要查找的数据的所在的位置，然后从查找的位置对这个表进行遍历，假如遇到和当前值相等的则直接返回当前位置的地址，需要注意的是：我们还要考虑状态，当状态是DELETE的时候，但是当前值又等于查找的值，这个值是不能返回的，因为当前值已经删除了，以是这种环境需要排除，以是前面需要添加一个判定条件。
erase

1. bool Erase(const K& key)
2. {
3.         //找到删除位置
4.         HashData<K, V>* ret = Find(key);
5.         if (ret)
6.         {
7.                 ret->_state = DELETE;
8.                 return true;
9.         }
10.         return false;
11. }

复制代码

对于删除某个值，我们起首需要查找，以是这里我们可以复用查找，用HashData<K,V>吸取一下，假如当前指针是空指针就直接返回false，说明需要删除的值没在表中，假如当前指针不是空指针，则将状态设置为DELETE状态。
hash桶封装

框架

1. template<class K,class V>
2. struct HashNode
3. {
4.         pair<K,V> _kv;
5.         HashNode<T>* _next;
6.         HashNode(const pair<K,V>& kv)
7.                 :_kv(kv)
8.                 ,_next(nullptr)
9.         {}
10. };
11. template<class K, class V>
12. class HashTable
13. {
14. public:
15.         typedef HashNode<K,V> Node;
16. private:
17.         //hash桶
18.         //hash桶当中的Node节点是new出来的，需要写析构函数
19.         vector<Node*> _tables;
20.         //表中存储的数据个数
21.         size_t _n = 0;
22. };

复制代码

用hash桶来封装hash表我们需要一个结构体，结构体中包含指向下一个结构体的指针，另有一个存放数据的kv。
在HashTable中我们需要一个vector，这个vector的类型是Node*，相称于存放的是指针。

上述代码形貌的结构就是上面这种结构。
insert

1. bool Insert(const pair<K,V>& kv)
2. {
3.         if (Find()) {
4.                 return false;
5.         }
6.         //找到插入的位置
8.         size_t hashi = kv.first % _tables.size();
9.         //需要控制负载因子，hash桶的负载因子需要控制在1
10.         if (_n == _tables.size())
11.         {
13.                 vector<Node*> newtables(_tables.size() * 2, nullptr);
14.                 for (size_t i = 0;i < _tables.size();i++)
15.                 {
16.                         //将旧表中的节点进行复用，头插
17.                         Node* cur = _tables[i];
18.                         while (cur)
19.                         {
20.                                 Node* next = cur->_next;
21.                                 //重新计算插入位置
22.                                 size_t hashi = cur->_kv.first % newtables.size();
23.                                 cur->_next = newtables[hashi];//先指向第一个
24.                                 newtables[hashi] = cur;//然后再成为第一个
25.                                 cur = next;
26.                         }
27.                         _tables[i] = nullptr;
28.                 }
29.                 _tables.swap(newtables);
30.         }
31.         //头插,尾插也可以，但是尾插需要找到尾，所以这里我们选择头插不用找尾
32.         Node* newnode = new Node(kv);
33.         newnode->_next = _tables[hashi];
34.         _tables[hashi] = newnode;
35.         _n++;
36.         return true;
37. }

复制代码

对于插入来说，我们可以直接算出插入位置，然后在当前桶中进行头插，为什么进行头插而不进行尾插呢？
因为头插可以直接插，而尾插则需要找到尾之后才气插入，大大影响了我们的插入效率，以是我们进行头插。
插入的逻辑说完之后，，我们也要扩容，对于hash桶实现hash表来说，我们的扩容的前提是当每个_n== 1的时候，意思就是每个桶都有一个节点的时候，_n==1的时候最好的环境是每个桶有一个节点，，这个环境的前提就是保证每个桶都有节点。
假如我们直接扩容的话也不是不行，但是会很浪费我们的空间，以是我们可以不开释当前节点，直接把旧表的节点插入到新表映射的位置上去，就不消浪费空间了。
find

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

复制代码

对于查找来说直接找到映射位置遍历hash桶即可。
erase

1. bool Erase(const K& key)
2. {
3.         size_t hashi = key % _tables.size();
4.         Node* cur = _tables[hashi];
5.         Node* prev = nullptr;
6.         while (cur)
7.         {
8.                 if (cur->_data == key)
9.                 {
10.                         if (prev == nullptr)
11.                         {
12.                                 _tables[hashi] = cur->_next;
13.                         }
14.                         else
15.                         {
16.                                 prev->_next = cur->_next;
17.                         }
18.                         delete cur;
19.                         _n--;
20.                         return true;
21.                 }
22.                 prev = cur;
23.                 cur = cur->_next;
24.         }
25.         return false;
26. }

复制代码

对于删除的逻辑我们先找到映射位置，然后先定义一个prev标志前一个指针，然后遍历当前桶，假如当前位置的值和需要删除的值相同，则可以分出两种环境，第一种环境是头删，头删就说明prev是nullptr，则可以直接令头指针等于下一个节点，假如是删除中间的，则可以令prev指向cur的下一个节点，然后开释当前节点，注意：开释当前节点的时候需要_n—。
~HashTable()

因为每个节点都是我们new出来的，以是需要我们手动开释，以是写一个析构函数，开释每个节点，遍历每个桶逐个开释

1. ~HashTable()
2. {
3.         for (size_t i = 0;i < _tables.size();i++)
4.         {
5.                 Node* cur = _tables[i];
6.                 while(cur)
7.                 {
8.                         Node* next = cur->_next;
9.                         delete cur;
10.                         cur = next;
11.                 }
12.                 _tables[i] = nullptr;
13.         }
14. }

复制代码

总结

通过对哈希表的封装，我们不仅提升了代码的可读性和复用性，还通过合理设计哈希函数和处理冲突机制，优化了哈希表的性能。封装让我们可以将底层的细节潜伏起来，提供一个简洁高效的接口，便于后续在项目中的使用。在实际开辟中，明确负载因子、再散列等概念，并针对详细场景合理调解这些参数，可以或许确保哈希表在性能和内存占用上的平衡。掌握了这些知识后，信赖你可以或许更加自负地在复杂应用中使用哈希表。

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