devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++：哈希表

作者：繁依Fanyi0 | 2024-07-14 06:26:07

赞

踩

C++：哈希表

哈希表概念

哈希表可以简单理解为：把数据转化为数组的下标，然后用数组的下标对应的值来表示这个数据。如果我们想要搜索这个数据，直接计算出这个数据的下标，然后就可以直接访问数组对应的位置，所以可以用O(1)的复杂度直接找到数据。

其中，这个数据对应的数字叫做关键码(Key)，这个把关键码转化为下标的规则，叫做哈希函数(Hash)。

要注意的是，有一些数据并不是整型，比如字符串，对象等等。对于这种数据，我们要先用一套规则把它们转化为整数（关键码），然后再通过哈希函数映射为数组下标。

哈希函数

哈希函数原则：

  1. 哈希函数转换后，生成的地址（下标）必须小于哈希表的最大地址（下标）
  2. 哈希函数计算出来的地址（下标）必须均匀地分布
  3. 哈希函数尽可能简单
直接定址法

取关键字的某个线性函数为哈希表的地址：

除留余数法

假设哈希表的地址数目为m，取Key对m取模后得到的值作为下标

闭散列 - 开放定址法

闭散列，也叫做开放定址法，当发生哈希冲突时，如果哈希表没有被装满，说明哈希表中还有空位置，那么我们可以把发生冲突的数据放到下一个空位置去。

基本结构

首先我们需要一个枚举，来标识哈希表的不同状态：

  1. enum State
  2. {
  3.     EMPTY,
  4.     EXIST,
  5.     DELETE
  6. };

EMPTY：空节点
EXIST：数值存在
DELETE：数值被删除 

哈希表的基本结构：

  1. enum State
  2. {
  3.     EMPTY,
  4.     EXIST,
  5.     DELETE
  6. };
  7.  
  8. template<class K, class V>
  9. struct HashData
  10. {
  11.     pair<K, V> _kv;
  12.     State _state = EMPTY;//标记状态
  13. };
  14.  
  15. template<class K, class V>
  16. class HashTable
  17. {
  18. public:
  19.     HashTable(size_t size = 10)
  20.     {
  21.         _tables.resize(size);
  22.     }
  23.  
  24. private:
  25.     vector<HashData<K, V>> _tables;//哈希表
  26.     size_t _n = 0;//元素个数
  27. };

HashTable构造函数：

  1. HashTable(size_t size = 10)
  2. {
  3.     _tables.resize(size);
  4. }
查找

想要在哈希表中查找数据，无非就遵顼以下规则：

通过哈希函数计算出数据对应的地址
去地址处查找，如果地址处不是目标值，往后继续查找
遇到EMPTY还没有找到，说明数据不存在哈希表中
遇到DELETE和EXIST，继续往后查找

代码如下：

  1. HashData<K, V>* Find(const K& key)
  2. {
  3.     size_t hashi = key % _tables.size();
  4.  
  5.     while (_tables[hashi]._state != EMPTY)
  6.     {
  7.         if (_tables[hashi]._kv.first == key
  8.             && _tables[hashi]._state == EXIST)
  9.             return &_tables[hashi];
  10.  
  11.         hashi++;
  12.         hashi %= _tables.size();
  13.     }
  14.  
  15.     return nullptr;
  16. }

但是当前的代码存在一个问题：哈希表作用于泛型，key % _tables.size()有可能是违法的行为，因为key可能不是一个数字。

对此我们可以在模板中多加一个仿函数的参数，用户可以在仿函数中自定义数据 -> 整型的转换规则，然后我们在对这个整型使用除留余数法获取地址。

在那之前，我们可以先写一个仿函数，用于处理整型 -> 整型的转化：

  1. struct HashFunc
  2. {
  3.     size_t operator()(const K& key)
  4.     {
  5.         return (size_t)key;
  6.     }
  7. };

在STL中，整型-> 整型转化的函数，被写为了一个模板，而这个string -> 整型被写为了一个模板特化：

  1. template<class K>
  2. struct HashFunc
  3. {
  4.     size_t operator()(const K& key)
  5.     {
  6.         return (size_t)key;
  7.     }
  8. };
  9.  
  10. template<>
  11. struct HashFunc<string>
  12. {
  13.     size_t operator()(const string& s)
  14.     {
  15.         size_t hash = 0;
  16.  
  17.         for (auto& e : s)//把字符串的每一个字符ASCII码值加起来
  18.         {
  19.             hash += e;
  20.             hash *= 131; // 31, 131313(任意由1，3间断排列的数字)
  21.         }
  22.  
  23.         return hash;
  24.     }
  25. };

我们将这个HashFunc<K>仿函数作为哈希表的第三个模板参数的默认值：

  1. template<class K, class V, class Hash = HashFunc<K>>
  2. class HashTable
  3. {};

通过仿函数来统一获得整型，再进行除留余数操作：

  1. Hash hs;
  2. size_t hashi = hs(key) % _tables.size();
插入

插入的基本逻辑如下：

  1. 先通过Find接口，查找目标值在不在哈希表中，如果目标值已经存在，返回flse，表示插入失败
  2. 通过哈希函数计算出目标值对应的下标
  3. 向下标中插入数据：如果下标对应的位置已经有数据，往后查找，直到某一个位置为EMPTY或者DELETE.如果下标对应的位置没有数据，直接插入
  4. 插入后，把对应位置的状态转化为EXIST

代码如下：

  1. bool Insert(const pair<K, V>& kv)
  2. {
  3.     if (Find(kv.first))
  4.         return false;
  5.  
  6.     Hash hs;//仿函数实例化出的对象
  7.     size_t hashi = hs(kv.first) % _tables.size();//获得目标值对应的下标
  8.  
  9.     while (_tables[hashi]._state == EXIST)//往后查找合适的位置插入
  10.     {
  11.         hashi++;
  12.         hashi %= _tables.size();
  13.     }
  14.  
  15.     _tables[hashi]._kv = kv;//插入
  16.     _tables[hashi]._state = EXIST;//改变状态
  17.     _n++;//哈希表中的元素个数+1
  18.  
  19.     return true;
  20. }

当这个哈希表越满，我们查找数据的效率就越低，甚至说：如果查找一个不存在的数据，我们可能要用O(N)的复杂度遍历整个哈希表.因此我们因该把哈希表的负载率控制在一定值，当超过一定值，我们就要进行扩容操作。

  1. if ((double)_n / _tables.size() >= 0.7)
  2. {
  3.     size_t newSize = _tables.size() * 2;
  4.  
  5.     HashTable<K, V, Hash> newHT(newSize);
  6.  
  7.     for (auto& e : _tables)
  8.     {
  9.         if (e._state == EXIST)
  10.             newHT.Insert(e._kv);
  11.     }
  12.  
  13.     _tables.swap(newHT._tables);
  14. }

插入总代码：

  1. bool Insert(const pair<K, V>& kv)
  2. {
  3.     if (Find(kv.first))
  4.         return false;
  5.  
  6.     if ((double)_n / _tables.size() >= 0.7)
  7.     {
  8.         size_t newSize = _tables.size() * 2;
  9.  
  10.         HashTable<K, V, Hash> newHT(newSize);
  11.  
  12.         for (auto& e : _tables)
  13.         {
  14.             if (e._state == EXIST)
  15.                 newHT.Insert(e._kv);
  16.         }
  17.  
  18.         _tables.swap(newHT._tables);
  19.     }
  20.  
  21.     Hash hs;
  22.     size_t hashi = hs(kv.first) % _tables.size();
  23.  
  24.     while (_tables[hashi]._state == EXIST)
  25.     {
  26.         hashi++;
  27.         hashi %= _tables.size();
  28.     }
  29.  
  30.     _tables[hashi]._kv = kv;
  31.     _tables[hashi]._state = EXIST;
  32.     _n++;
  33.  
  34.     return true;
  35. }
删除

先通过Find接口找到要删除的值

  • 如果没找到，返回false，表示删除失败
  • 如果找到，把对应节点的状态改为DELETE

最后再把哈希表的_n - 1，表示存在的节点数少了一个。

代码如下：

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

总代码展示

  1. template<class K>
  2. struct HashFunc
  3. {
  4.     size_t operator()(const K& key)
  5.     {
  6.         return (size_t)key;
  7.     }
  8. };
  9.  
  10. template<>
  11. struct HashFunc<string>
  12. {
  13.     size_t operator()(const string& s)
  14.     {
  15.         size_t hash = 0;
  16.  
  17.         for (auto& e : s)//把字符串的每一个字符ASCII码值加起来
  18.         {
  19.             hash += e;
  20.             hash *= 131; // 31, 131313(任意由1，3间断排列的数字)
  21.         }
  22.  
  23.         return hash;
  24.     }
  25. };
  26.  
  27. enum State
  28. {
  29.     EMPTY,
  30.     EXIST,
  31.     DELETE
  32. };
  33.  
  34. template<class K, class V>
  35. struct HashData
  36. {
  37.     pair<K, V> _kv;
  38.     State _state = EMPTY;//标记状态
  39. };
  40.  
  41. template<class K, class V, class Hash = HashFunc<K>>
  42. class HashTable
  43. {
  44. public:
  45.     HashTable(size_t size = 10)
  46.     {
  47.         _tables.resize(size);
  48.     }
  49.  
  50.     HashData<K, V>* Find(const K& key)
  51.     {
  52.         Hash hs;
  53.         size_t hashi = hs(key) % _tables.size();
  54.  
  55.         while (_tables[hashi]._state != EMPTY)
  56.         {
  57.             if (_tables[hashi]._kv.first == key
  58.                 && _tables[hashi]._state == EXIST)
  59.                 return &_tables[hashi];
  60.  
  61.             hashi++;
  62.             hashi %= _tables.size();
  63.         }
  64.  
  65.         return nullptr;
  66.     }
  67.  
  68.     bool Insert(const pair<K, V>& kv)
  69.     {
  70.         if (Find(kv.first))
  71.             return false;
  72.  
  73.         if ((double)_n / _tables.size() >= 0.7)
  74.         {
  75.             size_t newSize = _tables.size() * 2;
  76.  
  77.             HashTable<K, V, Hash> newHT(newSize);
  78.  
  79.             for (auto& e : _tables)
  80.             {
  81.                 if (e._state == EXIST)
  82.                     newHT.Insert(e._kv);
  83.             }
  84.  
  85.             _tables.swap(newHT._tables);
  86.         }
  87.  
  88.         Hash hs;
  89.         size_t hashi = hs(kv.first) % _tables.size();
  90.  
  91.         while (_tables[hashi]._state == EXIST)
  92.         {
  93.             hashi++;
  94.             hashi %= _tables.size();
  95.         }
  96.  
  97.         _tables[hashi]._kv = kv;
  98.         _tables[hashi]._state = EXIST;
  99.         _n++;
  100.  
  101.         return true;
  102.     }
  103.  
  104.     bool Erase(const K& key)
  105.     {
  106.         HashData<K, V>* ret = Find(key);
  107.         if (ret)
  108.         {
  109.             ret->_state = DELETE;
  110.             _n--;
  111.             return true;
  112.         }
  113.  
  114.         return false;
  115.     }
  116.  
  117. private:
  118.     vector<HashData<K, V>> _tables;
  119.     size_t _n = 0;//元素个数
  120. };
开散列 - 哈希桶

在STL库中，采用的是更加优秀的开散列方案。

哈希表的数组vector中，不再直接存储数据，而是存储一个链表的指针。当一个数值映射到对应的下标后，就插入到这个链表中。其中每一个链表称为一个哈希桶，每个哈希桶中，存放着哈希冲突的元素.

基本结构

对于每一个节点，其要存储当前节点的值，也要存储下一个节点的指针，基本结构如下：

  1. template<class K, class V>
  2. struct HashNode
  3. {
  4.     HashNode<K, V>* _next;
  5.     pair<K, V> _kv;
  6.  
  7.     HashNode(const pair<K, V>& kv)
  8.         :_kv(kv)
  9.         ,_next(nullptr)
  10.     {}
  11. };

哈希表：

  1. template<class K, class V, class Hash = HashFunc<K>>
  2. class HashTable
  3. {
  4.     typedef HashNode<K, V> Node;
  5. public:
  6.     HashTable(size_t size = 10)
  7.     {
  8.         _tables.resize(size);
  9.     }
  10.     
  11. private:
  12.     vector<Node*> _tables; //链表指针数组
  13.     size_t _n = 0;//元素个数
  14. };

析构函数，防止内存泄漏：

  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. }
查找

查找的基本逻辑如下：

  1. 先通过哈希函数计算出数据对应的下标
  2. 通过下标找到对应的链表
  3. 遍历链表，找数据:如果某个节点的数据匹配上了，返回该节点指针,如果遍历到了nullptr，返回空指针表示没找到

代码如下：

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

插入的基本逻辑如下：

  1. 先通过Find接口，查找目标值在不在哈希表中，如果目标值已经存在，返回flse，表示插入失败
  2. 通过哈希函数计算出目标值对应的下标
  3. 向下标中插入数据

代码如下：

  1. bool Insert(const pair<K, V>& kv)
  2. {
  3.     if (Find(kv.first))
  4.         return false;
  5.  
  6.     Hash hs;
  7.     size_t hashi = hs(kv.first) % _tables.size();//计算下标
  8.     Node* newNode = new Node(kv);//创建节点
  9.  
  10.     newNode->_next = _tables[hashi];//头插
  11.     _tables[hashi] = newNode;
  12.  
  13.     ++_n;//更新元素个数
  14.     return true;
  15. }

关于扩容:如果我们单纯的进行插入，就要把原先的所有节点释放掉，再创建新的节点。这样会浪费很多时间。我们最好把原先创建的节点利用起来，因此我们要重写一个逻辑，把原先的节点进行迁移。 

  1. if (_n == _tables.size())
  2. {
  3.     vector<Node*> newTables(_tables.size() * 2, nullptr);
  4.     for (size_t i = 0; i < _tables.size(); i++)
  5.     {
  6.         Node* cur = _tables[i];
  7.         while (cur)
  8.         {
  9.             Node* next = cur->_next;
  10.  
  11.             size_t hashi = hs(cur->_kv.first) % newTables.size();
  12.             cur->_next = newTables[hashi];
  13.             newTables[hashi] = cur;
  14.  
  15.             cur = next;
  16.         }
  17.  
  18.         _tables[i] = nullptr; //防止移交的节点被析构
  19.     }
  20.  
  21.     _tables.swap(newTables);
  22. }
删除

删除逻辑：

  1. 通过哈希函数计算出对应的下标
  2. 到对应的哈希桶中查找目标值
  • 如果找到，删除对应的节点
  • 如果没找到，返回false表示删除失败
  • _n - 1表示删除了一个元素

代码如下：

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

代码展示

  1. template<class K>
  2. struct HashFunc
  3. {
  4.     size_t operator()(const K& key)
  5.     {
  6.         return (size_t)key;
  7.     }
  8. };
  9.  
  10. template<>
  11. struct HashFunc<string>
  12. {
  13.     size_t operator()(const string& s)
  14.     {
  15.         size_t hash = 0;
  16.  
  17.         for (auto& e : s)//把字符串的每一个字符ASCII码值加起来
  18.         {
  19.             hash += e;
  20.             hash *= 131; // 31, 131313(任意由1，3间断排列的数字)
  21.         }
  22.  
  23.         return hash;
  24.     }
  25. };
  26.  
  27. template<class K, class V>
  28. struct HashNode
  29. {
  30.     HashNode<K, V>* _next;
  31.     pair<K, V> _kv;
  32.  
  33.     HashNode(const pair<K, V>& kv)
  34.         :_kv(kv)
  35.         ,_next(nullptr)
  36.     {}
  37. };
  38.  
  39. template<class K, class V, class Hash = HashFunc<K>>
  40. class HashTable
  41. {
  42.     typedef HashNode<K, V> Node;
  43. public:
  44.     HashTable(size_t size = 10)
  45.     {
  46.         _tables.resize(size);
  47.     }
  48.  
  49.     ~HashTable()
  50.     {
  51.         for (size_t i = 0; i < _tables.size(); i++)
  52.         {
  53.             Node* cur = _tables[i];
  54.             while (cur)
  55.             {
  56.                 Node* next = cur->_next;
  57.                 delete cur;
  58.                 cur = next;
  59.             }
  60.             _tables[i] = nullptr;
  61.         }
  62.     }
  63.  
  64.     Node* Find(const K& key)
  65.     {
  66.         Hash hs;
  67.         size_t hashi = hs(key) % _tables.size();
  68.  
  69.         Node* cur = _tables[hashi];
  70.         while (cur)
  71.         {
  72.             if (cur->_kv.first == key)
  73.                 return cur;
  74.  
  75.             cur = cur->_next;
  76.         }
  77.  
  78.         return nullptr;
  79.     }
  80.  
  81.     bool Insert(const pair<K, V>& kv)
  82.     {
  83.         if (Find(kv.first))
  84.             return false;
  85.  
  86.         Hash hs;
  87.  
  88.         //哈希桶情况下，负载因子到1才扩容
  89.         if (_n == _tables.size())
  90.         {
  91.             vector<Node*> newTables(_tables.size() * 2, nullptr);
  92.             for (size_t i = 0; i < _tables.size(); i++)
  93.             {
  94.                 Node* cur = _tables[i];
  95.                 while (cur)
  96.                 {
  97.                     Node* next = cur->_next;
  98.  
  99.                     size_t hashi = hs(cur->_kv.first) % newTables.size();
  100.                     cur->_next = newTables[hashi];
  101.                     newTables[hashi] = cur;
  102.  
  103.                     cur = next;
  104.                 }
  105.  
  106.                 _tables[i] = nullptr; //防止移交的节点被析构
  107.             }
  108.  
  109.             _tables.swap(newTables);
  110.         }
  111.  
  112.         size_t hashi = hs(kv.first) % _tables.size();
  113.         Node* newNode = new Node(kv);
  114.  
  115.         newNode->_next = _tables[hashi];
  116.         _tables[hashi] = newNode;
  117.  
  118.         ++_n;
  119.         return true;
  120.     }
  121.  
  122.     bool Erase(const K& key)
  123.     {
  124.         Hash hs;
  125.         size_t hashi = hs(key) % _tables.size();
  126.  
  127.         Node* prev = nullptr;
  128.         Node* cur = _tables[hashi];
  129.         while (cur)
  130.         {
  131.             if (cur->_kv.first == key)
  132.             {
  133.                 if (prev)
  134.                     prev->_next = cur->_next;
  135.                 else
  136.                     _tables[hashi] = cur->_next;
  137.  
  138.                 delete cur;
  139.                 --_n;
  140.                 return true;
  141.             }
  142.  
  143.             prev = cur;
  144.             cur = cur->_next;
  145.         }
  146.  
  147.         return false;
  148.     }
  149.  
  150. private:
  151.     vector<Node*> _tables; //链表指针数组
  152.     size_t _n = 0;//元素个数
  153. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/823541
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号