C++之unordered_map和unordered_set以及哈希详解

转x33g5p2x  于2022-03-31 转载在 其他  
字(18.5k)|赞(0)|评价(0)|浏览(492)

unordered_map和unordered_set的使用

map和set底层是红黑树实现的，map是KV模型，set是K模型，而unordered_map和unordered_set底层是哈希表实现的，unordered_set是K模型，unordered_map是KV模型

unordered_map和unordered_set的命名体现特点，在功能和map/set是一样的，区别在于，它遍历出来是无序的，另外，它们的迭代器是单向迭代器

unordered_map的文档

  1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的
    value。
  2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键
    和映射值的类型可能不同。
  3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所
    对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
  4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率
    较低。
  5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
  6. 它的迭代器至少是前向迭代器。

下面我们来看一下unordered_map和unordered_set的使用：

  1. #include<iostream>
  2. #include<unordered_set>
  3. #include<unordered_map>
  4. using namespace std;
  6. void test_unordered_set()
  7. {
  8.     unordered_set<int> s;
  9.     s.insert(3);
  10.     s.insert(4);
  11.     s.insert(5);
  12.     s.insert(3);
  13.     s.insert(1);
  14.     s.insert(2);
  15.     s.insert(6);
  16.     unordered_set<int>::iterator it = s.begin();
  17.     while (it != s.end())
  18.     {
  19.         cout << *it << " ";
  20.         ++it;
  21.     }
  22.     cout << endl;
  23. }
  25. int main()
  26. {
  27.     test_unordered_set();
  28.     return 0;
  29. }

可以看到它遍历出来是无序的，并且相同的数只会插入一次

  1. #include<iostream>
  2. #include<unordered_map>
  3. using namespace std;
  4. void test_unordered_map()
  5. {
  6.     unordered_map<string, string> dict;
  7.     dict.insert(make_pair("string", "字符串"));
  8.     dict.insert(make_pair("sort", "排序"));
  9.     dict.insert(make_pair("string", "字符串"));
  10.     dict.insert(make_pair("string", "字符串"));
  11.     auto it = dict.begin();
  12.     while (it != dict.end())
  13.     {
  14.         cout << it->first << ":" << it->second << endl;
  15.         it++;
  16.     }
  17. }
  18. int main()
  19. {
  20.     test_unordered_map();
  21.     return 0;
  22. }

它遍历出来也是无序的，并且相同的数只会插入一次

unordered_set和unordered_map的两个OJ题

两个数组的交集

题目思路：
用unordered_set对nums1中的元素去重，然后用unordered_set对nums2中的元素去重，最后遍历s1，如果s1中某个元素在s2中出现过，即为交集

  1. class Solution {
  2. public:
  3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
  4.         // 用unordered_set对nums1中的元素去重
  5.         unordered_set<int> s1;
  6.         for (auto e : nums1)
  7.         s1.insert(e);
  8.         // 用unordered_set对nums2中的元素去重
  9.         unordered_set<int> s2;
  10.         for (auto e : nums2)
  11.         s2.insert(e);
  12.         // 遍历s1，如果s1中某个元素在s2中出现过，即为交集
  13.         vector<int> vRet;
  14.         for (auto e : s1)
  15.         {
  16.         if (s2.find(e) != s2.end())
  17.         vRet.push_back(e);
  18.         }
  19.         return vRet;
  20.     }
  21. };

两个数组的交集二

题目思路：
1、两个位置的值相等，则是交集，同时++

2、两个位置的值不相等，则不是交集值，小的++

set和undered_set的性能比较

  1. void test_op()
  2. {
  3.     set<int> s;
  4.     unorder_set<int> us;
  5.     const int n = 100000;
  6.     vector<int> v;
  7.     srand(time(0));
  8.     for(size_t i = 0;i<n;++i)
  9.     {
  10.         v.push_back(rand());
  11.     }
  12.     //插入性能比较
  13.     size_t begin1 = clock();
  14.     for(auto e:v)
  15.     {
  16.         us.insert(e);
  17.     }
  18.     size_t end1 = clock();
  19.     cout<<end1-begin1<<endl;
  20.     
  21.     size_t begin2 = clock();
  22.     for(auto e:v)
  23.     {
  24.         s.insert(e);
  25.     }
  26.     size_t end2 = clock();
  27.     cout<<end2-begin2<<endl;
  28.     
  29.     //查找性能比较
  30.     size_t begin3 = clock();
  31.     for(auto e:v)
  32.     {
  33.         us.find(e);
  34.     }
  35.     size_t end3 = clock();
  36.     cout<<end1-begin1<<endl;
  37.     
  38.     size_t begin4 = clock();
  39.     for(auto e:v)
  40.     {
  41.         s.find(e);
  42.     }
  43.     size_t end4 = clock();
  44.     cout<<end2-begin2<<endl;
  45.     
  46.     //删除效率比较
  47.     size_t begin5 = clock();
  48.     for(auto e:v)
  49.     {
  50.         us.erase(e);
  51.     }
  52.     size_t end5 = clock();
  53.     cout<<end5-begin5<<endl;
  54.     
  55.     size_t begin6 = clock();
  56.     for(auto e:v)
  57.     {
  58.         s.erase(e);
  59.     }
  60.     size_t end6 = clock();
  61.     cout<<end6-begin6<<endl;
  62. }

发现不管运行多少次，都是哈希表比较优，unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

哈希

哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经
过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2N)，搜索的效率取决
于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过
某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函
数可以很快找到该元素。

当向该哈希结构中：

  • 插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

  • 搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比
较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表
(Hash Table)(或者称散列表)

例如：我们有数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快 问题：按照上述哈希方式，向集合中
插入元素44，会出现什么问题？发现4这个位置已经被占用了

哈希冲突

对于两个数据元素的关键字 和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同关键字通过
相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
发生哈希冲突该如何处理呢？

常见哈希函数

  1. 直接定址法

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

  1. 除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函
数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

哈希冲突的解决

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那
么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

  • 线性探测：index+i (i = 1,2,3,4…)
    从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

  • 二次探测：index+i^2(i = 1,2,3,4…)
    线性探测的缺陷是产生冲突的数据堆积在一块，相比线性探测的好处，如果一个位置有很多值映射，冲突剧烈，那么它们存储时相对会比较分散，不会引发一片一片的冲突

开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码
归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结
点存储在哈希表中。

闭散列的实现

我们实现哈希表，那么数据怎么存储呢？数据的结构又是什么呢？数据的存储很好想到，可以用一个vector存就好了，那么数据的结构出来存储数据还需要什么呢？比如我们有以下数据：

我们查找一个值时，按照哈希函数求得位置，如果当前位置不是，则可能遇到了冲突，所以一直往后找，当遇到空位置时说明这个值肯定不存在了，因为如果存在，肯定存储在了第一个空位置，那么当我们删除一个值，直接删除的话这个位置变成了空，但是这样有问题：使得查找一个值提早遇到空，那么就找不到这个值

比如删除333，直接删除后变成了空位置，我们再查找14会怎么样？我们先求得14的位置是4，发现4这个位置是空，所以直接就返回不存在，导致14存在，但是查找不到14

解决方案：每个位置存储值得同时再存储一个状态标记：空、满、删除

如果一个值删除了，将该位置标记为删除，查找一个值如果遇到了删除，那么不停止继续查找，插入一个值时遇到了空和删除都可以插入

所以还需要该存储位置的当前状态：

  1. EMPTY(空数据的位置)
  2. EXIST(已存储数据)
  3. DELETE(以前有数据，但是删除了)
  1. enum Status
  2. {
  3.     EMPTY,//空
  4.     EXIST,//存在
  5.     DELETE//删除
  6. };

数据的存储结构

我们实现KV模型，所以数据弄成pair，另外还需要状态：

  1. template<class K,class V>
  2. struct HashData
  3. {
  4.     pair<K,V> _kv;
  5.     Status _status = EMPTY; //状态
  6. }

哈希表的结构

vector来存储HashData，_n用来存储有效数据的个数

  1. template<class K,class V>
  2. class HashTable
  3. {
  4. public:
  5. private:
  6.     vector<HashData<K,V>> _tables;//vector来存储HashData
  7.     size_t _n = 0;//存储有效数据的个数
  8. };

哈希表的插入

我们为了避免哈希冲突变多，我们引入一个负载因子，当负载因子过大时需要对哈希表进行增容

  1. 如果哈希表中已经存在该键值对，则插入失败返回false
  2. 判断该哈希表的大小以及负载因子，确定是否需要增容
  3. 将键值对插入哈希表
  4. ++_n

首先我们解决增容的问题，首先我们确定的是_table.size() == 0时需要增容，其次我们设置负载因子=有效数据/表的大小，如果负载因子大于0.7时就增容。

那么怎么增容呢？

有一种方法是创建一个新vector，resize新空间大小，然后将旧表中的数据复制到新表当中

  1. //方法一
  2. size_t newSize = _table.size()==0? 10:_table.size()*2;
  3. vector<HashData<K,V>> newTable;
  4. newTable.resize(newSize);
  5. for(size_t i =0;i<_tables.size();++i)
  6. {
  7.     if(_table[i]._status == EXIST)
  8.     {
  9.         //将存在的数据复制到新表中
  10.         size_t index = _table[i]._kv.first % newTable.size();
  11.         //...
  12.     }
  13. }

比较好的方法是建立一个临时新表，给新表开扩容后的空间，然后遍历旧表将旧表的数据插入新表，最后将新表和旧表交换：

  1. //方法二：
  2. size_t newSize = _table.size()==0? 10 : _table.size()*2;
  3. HashTable<K,V> newHT;//建立一个临时新表
  4. newHT._tables.resize(newSize);//给新表开扩容后的空间
  5. for(auto& e:_tables)
  6. {
  7.     if(e._status == EXIST)
  8.     {
  9.         newHT.Insert(e._kv);//将旧表的数据插入新表
  10.     }
  11. }
  12. _table.swap(newHT._tables);//将新表和旧表交换

插入哈希表的代码(首先计算出插入的位置，如果该位置存在的话就遍历后面的位置，遍历的过程中如果等于的表的末尾，则返回起始位置继续遍历，直到遇到空或者删除)：

  1. size_t start = kv.first % _tables.size();
  2. size_t i = 0;
  3. size_t index = start + i;
  4. while(_table[index]._status == EXIST)
  5. {
  6.     ++i;
  7.     //index = start+i;//线性探测
  8.     index = start+i*i;//二次探测
  10.     if(index == _tables.size())
  11.     {
  12.         //当index到达最后的时候,让它回到起始
  13.         index = 0;
  14.     }
  15. }
  16. //走到这里要么是空要么是删除
  17. _tables[index]._kv = kv;
  18. _tables[index]._status = EXIST;
  19. ++_n;

插入的完整代码：

  1. //插入
  2. bool Insert(const pair<K,V>& kv)
  3. {
  4.     if(Find(kv.first))
  5.     {
  6.         return false;
  7.     }
  8.     if(_table.size() == 0 || (double)(_n / _table.size()) > 0.7)
  9.     {
  10.         //扩容
  11.         size_t newSize = _table.size()==0? 10 : _table.size()*2;
  12.         HashTable<K,V> newHT;//建立一个临时新表
  13.         newHT._tables.resize(newSize);//给新表开扩容后的空间
  14.         for(auto& e:_tables)
  15.         {
  16.             if(e._status == EXIST)
  17.             {
  18.                 newHT.Insert(e._kv);//将旧表的数据插入新表
  19.             }
  20.         }
  21.         _table.swap(newHT._tables);//将新表和旧表交换
  22.     }
  24.     size_t start = kv.first % _tables.size();
  25.     size_t i = 0;
  26.     size_t index = start + i;
  27.     while(_table[index]._status == EXIST)
  28.     {
  29.         ++i;
  30.         //index = start+i;//线性探测
  31.         index = start+i*i;//二次探测
  33.         if(index == _tables.size())
  34.         {
  35.             //当index到达最后的时候,让它回到起始
  36.             index = 0;
  37.         }
  38.     }
  39.     //走到这里要么是空要么是删除
  40.     _tables[index]._kv = kv;
  41.     _tables[index]._status = EXIST;
  42.     ++_n;
  44.     return true;
  45. }

哈希表的查找

哈希表的查找逻辑很简单：先计算出查找的key的位置，当这个位置不等于空时，判断key值是不是相等并且状态位存在，如果是的话返回，不是的话进行线性探测或者二次探测，直到遇到位置为空状态

  1. HashData<K,V>* Find(const K& key)
  2. {
  3.     if(_table.size() == 0)
  4.     {
  5.         //防止除0错误
  6.         return nullptr;
  7.     }
  8.     size_t start = key % _table.size();
  9.     size_t i = 0;
  10.     size_t index = start + i;
  11.     while(_tables[index]._status != EMPTY)
  12.     {
  13.         if(_tabled[index]._kv.first == key && _table[index]._status == EXIST)
  14.         {
  15.             return &_tabled[index];
  16.         }
  17.         else
  18.         {
  19.             ++i;
  20.             //index = start +i;
  21.             index = start + i*i;//二次探测
  22.             index %= _tables.size();
  23.         }
  24.     }
  25.     return nullptr;
  26. }

哈希表的删除

首先找到这个节点，进行伪删除，将该节点的状态设置成删除然后–_n即可

  1. bool Erase(const K& key)
  2.  {
  3.      HashData<K,V>* ret = Find(key);
  4.      if(ret == nullptr)
  5.      {
  6.          //没有这个值
  7.          return false;
  8.      }
  9.      else
  10.      {
  11.          //伪删除
  12.          ret->_status = DELETE;
  13.          _n--;
  14.          return true;
  15.      }
  16.  }

哈希表闭散列的代码

  1. #pargma once
  2. namespace close_hash
  3. {
  4.     enum Status
  5.     {
  6.         EMPTY,//空
  7.         EXIST,//存在
  8.         DELETE//删除
  9.     };
  10.     template<class K,class V>
  11.     struct HashData
  12.     {
  13.         pair<K,V> _kv;
  14.       	Status _status = EMPTY; //状态
  15.     }
  16.     template<class K,class V>
  17.    	class HashTable
  18.     {
  19.     public:
  20.         bool Erase(const K& key)
  21.         {
  22.             HashData<K,V>* ret = Find(key);
  23.             if(ret == nullptr)
  24.             {
  25.                 //没有这个值
  26.                 return false;
  27.             }
  28.             else
  29.             {
  30.                 //伪删除
  31.                 ret->_status = DELETE;
  32.                 _n--;
  33.                 return true;
  34.             }
  35.         }
  36.         HashData<K,V>* Find(const K& key)
  37.         {
  38.             if(_table.size() == 0)
  39.             {
  40.                 //防止除0错误
  41.                 return nullptr;
  42.             }
  43.             size_t start = key % _table.size();
  44.             size_t i = 0;
  45.             size_t index = start + i;
  46.             while(_tables[index]._status != EMPTY)
  47.             {
  48.                 if(_tabled[index]._kv.first == key && _table[index]._status == EXIST)
  49.                 {
  50.                     return &_tabled[index];
  51.                 }
  52.                 else
  53.                 {
  54.                     ++i;
  55.                     //index = start +i;
  56.                    	index = start + i*i;//二次探测
  57.                     index %= _tables.size();
  58.                 }
  59.             }
  60.             return nullptr;
  61.         }
  62.         //插入
  63.         bool Insert(const pair<K,V>& kv)
  64.         {
  65.             if(Find(kv.first))
  66.             {
  67.                 return false;
  68.             }
  69.             if(_table.size() == 0 || (double)(_n / _table.size()) > 0.7)
  70.             {
  71.                 //扩容
  72.                 //方法一
  73.                 size_t newSize = _table.size()==0? 10:_table.size()*2;
  74.                 vector<HashData<K,V>> newTable;
  75.                 newTable.resize(newSize);
  76.                 for(size_t i =0;i<_tables.size();++i)
  77.                 {
  78.                     if(_table[i]._status == EXIST)
  79.                     {
  80.                         //将存在的数据复制到新表中
  81.                         size_t index = _table[i]._kv.first % newTable.size();
  82.                         //...
  83.                     }
  84.                 }
  85.                 //方法二：
  86.                 size_t newSize = _table.size()==0? 10 : _table.size()*2;
  87.                 HashTable<K,V> newHT;//建立一个临时新表
  88.                 newHT._tables.resize(newSize);//给新表开扩容后的空间
  89.                 for(auto& e:_tables)
  90.                 {
  91.                     if(e._status == EXIST)
  92.                     {
  93.                         newHT.Insert(e._kv);//将旧表的数据插入新表
  94.                     }
  95.                 }
  96.                 _table.swap(newHT._tables);//将新表和旧表交换
  97.             }
  98.             
  99.             size_t start = kv.first % _tables.size();
  100.             size_t i = 0;
  101.             size_t index = start + i;
  102.             while(_table[index]._status == EXIST)
  103.             {
  104.                 ++i;
  105.                 //index = start+i;//线性探测
  106.                 index = start+i*i;//二次探测
  107.                 
  108.                 if(index == _tables.size())
  109.                 {
  110.                     //当index到达最后的时候,让它回到起始
  111.                     index = 0;
  112.                 }
  113.                 //插满的时候会死循环
  114.             }
  115.             //走到这里要么是空要么是删除
  116.             _tables[index]._kv = kv;
  117.             _tables[index]._status = EXIST;
  118.             ++_n;
  119.             
  120.             return true;
  121.         }
  122.     private:
  123.         vector<HashData<K,V>> _tables;//vector来存储HashData
  124.         size_t _n = 0;//存储有效数据的个数
  125.     }
  126. }

我们上面的代码有些问题：

如果是key是string，上面的代码是编不过去的，因为key是string，无法计算位置，所以此时就用到了仿函数，仿函数通过重载方法将string转化为整形用来做key，这里运用了BKDR Hash思想来完成string到key的转换，发生冲突的概率很小

  1. template<class K>
  2. struct HashFunc
  3. {
  4.     size_t operator()(const K&key)
  5.     {
  6.         return key;
  7.     }
  8. };    
  9. struct HashFuncString
  10. {
  11.     size_t operator()(const string& key)
  12.     {
  13.         //BKDR Hash思想
  14.         size_t hash = 0;
  15.         for(size_t i = 0;i<key.size();++i)
  16.         {
  17.             hash*=131;
  18.             hash += key[i];//转成整形
  19.         }
  20.         return hash;
  21.     }
  22. };

如果我们写成这样我们创建string为key的哈希表的时候就需要这样写，将HashFuncString仿函数传进去：

  1. HashTable<string, string, HashFuncString> dict;

而我们使用unordered_map时是不需要传这个仿函数进去的，这里用到了模板的特化：

  1. template<class K>
  2. struct HashFunc
  3. {
  4.     size_t operator()(const K&key)
  5.     {
  6.         return key;
  7.     }
  8. }; 
  9. template<>
  10. struct HashFunc<string>
  11. {
  12.     size_t operator()(const string& key)
  13.     {
  14.         //BKDR Hash思想
  15.         size_t hash = 0;
  16.         for(size_t i = 0;i<key.size();++i)
  17.         {
  18.             hash*=131;
  19.             hash += key[i];//转成整形
  20.         }
  21.         return hash;
  22.     }
  23. };

此时哈希表的模板参数也就要发生变化：

  1. template<class K, class V, class Hash = HashFunc<K>>

不传仿函数过去，它会自己推演，是K是int类型就调用HashFunc<int>，是string就调用更匹配的HashFunc<string>

哈希表闭散列的完整代码

  1. #pargma once
  2. namespace close_hash
  3. {
  4.     enum Status
  5.     {
  6.         EMPTY,//空
  7.         EXIST,//存在
  8.         DELETE//删除
  9.     };
  10.     template<class K,class V>
  11.     struct HashData
  12.     {
  13.         pair<K,V> _kv;
  14.       	Status _status = EMPTY; //状态
  15.     };
  16.     template<class K>
  17.     struct HashFunc
  18.     {
  19.         size_t operator()(const K&key)
  20.         {
  21.             return key;
  22.         }
  23.     };    
  24.     //特化
  25.     template<>
  26.     struct HashFunc<string>
  27.     {
  28.         size_t operator()(const string& key)
  29.         {
  30.             //BKDR Hash思想
  31.             size_t hash = 0;
  32.             for(size_t i = 0;i<key.size();++i)
  33.             {
  34.                 hash*=131;
  35.                 hash += key[i];//转成整形
  36.             }
  37.             return hash;
  38.         }
  39.     };  
  40.     template<class K,class V,class Hash = HashFunc<K>>
  41.    	class HashTable
  42.     {
  43.     public:
  44.         bool Erase(const K& key)
  45.         {
  46.             HashData<K,V>* ret = Find(key);
  47.             if(ret == nullptr)
  48.             {
  49.                 //没有这个值
  50.                 return false;
  51.             }
  52.             else
  53.             {
  54.                 //伪删除
  55.                 ret->_status = DELETE;
  56.                 _n--;
  57.                 return true;
  58.             }
  59.         }
  60.         HashData<K,V>* Find(const K& key)
  61.         {
  62.             if(_table.size() == 0)
  63.             {
  64.                 //防止除0错误
  65.                 return nullptr;
  66.             }
  67.             Hash hf;
  68.             size_t index = hf(key) % _table.size();
  69.             size_t i = 0;
  70.             size_t index = start + i;
  71.             while(_tables[index]._status != EMPTY)
  72.             {
  73.                 if(_tabled[index]._kv.first == key && _table[index]._status == EXIST)
  74.                 {
  75.                     return &_tabled[index];
  76.                 }
  77.                 else
  78.                 {
  79.                     ++i;
  80.                     //index = start+i;//线性探测
  81.                     index = start+i*i;//二次探测
  82.                     index %= _tables.size();
  83.                 }
  84.             }
  85.             return nullptr;
  86.         }
  87.         //插入
  88.         bool Insert(const pair<K,V>& kv)
  89.         {
  90.             if(Find(kv.first))
  91.             {
  92.                 return false;
  93.             }
  94.             if(_table.size() == 0 || (double)(_n / _table.size()) > 0.7)
  95.             {
  96.                 //扩容
  97.                 //方法二：
  98.                 size_t newSize = _table.size()==0? 10 : _table.size()*2;
  99.                 HashTable<K,V> newHT;//建立一个临时新表
  100.                 newHT._tables.resize(newSize);//给新表开扩容后的空间
  101.                 for(auto& e:_tables)
  102.                 {
  103.                     if(e._status == EXIST)
  104.                     {
  105.                         newHT.Insert(e._kv);//将旧表的数据插入新表
  106.                     }
  107.                 }
  108.                 _table.swap(newHT._tables);//将新表和旧表交换
  109.             }
  110.             Hash hf;
  111.             size_t start = hf(kv.first) % _tables.size();
  112.             //线性探测
  113.             size_t i = 0;
  114.             size_t index = start + i;
  115.             while(_table[index]._status == EXIST)
  116.             {
  117.                 ++index;
  118.                 if(index == _tables.size())
  119.                 {
  120.                     //当index到达最后的时候,让它回到起始
  121.                     index = 0;
  122.                 }
  123.                 //插满的时候会死循环
  124.             }
  125.             //走到这里要么是空要么是删除
  126.             _tables[index]._kv = kv;
  127.             _tables[index]._status = EXIST;
  128.             ++_n;
  129.             
  130.             return true;
  131.         }
  132.     private:
  133.         vector<HashData<K,V>> _tables;//vector来存储HashData
  134.         size_t _n = 0;//存储有效数据的个数
  135.     }
  136. }

开散列的实现

开散列概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

数据的存储结构

因为桶里面是单链表结构，所以需要有一个指向下一个节点的指针_next，还有一个pair来存储数据

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

哈希表的结构

vector里面需要存储Node而不是Node，如果是Node会出现二义性：存节点了还是没有存，因为定义对象出现时节点都申请出来了，都进行了初始化。所以这里需要存储Node，指向第一个节点

  1. class HashTable
  2.  {
  3.      typedef HashBucketNode<K,V> Node;
  4.      private:
  5.      size_t _n = 0;//哈希表中的有效数据
  6.      vector<Node*> _tables;//会出现二义性：存节点了还是没有存,因为定义对象出现节点都申请出来了，都进行了初始化
  7.  };

开散列是通过单链表链接分方式处理哈希冲突的，所以并不需要给每个节点设置状态，只需要将哈希地址相同的元素都放到同一个哈希桶里以单链表链接，开散列可以无限的插入，如果表的大小太小，那么每个桶中的单链表就会链接的节点越多，这样找一个节点时效率就会变低，所以开散列我们也要通过负载因子来判断是否增容，通过增容，每个哈希桶的链接的元素相对变少，效率也就好了些，所以我们需要一个_n变量来记录哈希表中的有效数据，来计算负载因子

注意：

负载因子 = 数据个数/表的大小，负载因子越低，冲突的概率越低，空间浪费越高，负载因子越高，冲突的概率越高，空间浪费越低

哈希表的插入

哈希表的插入步骤：

  1. 如果哈希表中已经存在该键值对，则插入失败返回false
  2. 判断该哈希表的大小以及负载因子，确定是否需要增容
  3. 将键值对插入哈希表
  4. ++_n

首先我们解决增容的问题，首先我们确定的是_table.size() == 0时需要增容，其次我们设置负载因子=有效数据/表的大小，如果负载因子大于1时就增容。

那么怎么增容呢？

可以这样扩容吗？直接扩2倍：

此时表的大小发生变化，所以需要重新计算位置，会导致处理十分混乱

需要这样扩容：创建一个新表，该哈希表是原来表的2倍，之后遍历旧哈希表，将旧哈希表的数据插入到新哈希表中，最后将新表和旧表交换即可：

将旧哈希表的数据插入到新哈希表中，如果像闭散列那样的方式写时，即通过复用Insert来插入数据时会有一个问题，闭散列表中就是存储数据的，而开散列表中不存储数据，存储的是节点的指针，通过复用Insert来插入数据时，相当于又创建了重复的节点，把已经存在的节点再创建一遍，到最后又要将旧表中和新表中重复的节点释放一次，是不是多此一举了

所以我们只需要通过遍历旧哈希表的哈希桶，将旧表哈希桶的数据头插到新表的哈希桶中，然后将旧表的头节点的next置为空，最后新表和旧表交换即可

  1. bool Insert(const pair<K,V>& kv)
  2. {
  3.     //当负载因子到1时，进行扩容
  4.     if(_n == _table.size())
  5.     {
  6.         size_t newSize = _tables.size() == 0?10:_tables.size()*2;
  7.         vector<Node*> newtables;
  8.         newtables.resize(newSize,nullptr);
  9.         for(size_t i =0;i<_tables.size();i++)
  10.         {
  11.             //遍历旧表
  12.             Node* cur = _tables[i];
  13.             while(cur)
  14.             {
  15.                 //桶里有数据
  16.                 Node* next = cur->_next;
  17.                 size_t index = cur->kv.first % newSize;//当前节点在新表中的位置
  18.                 //头插
  19.                 cur->_next = newtable[index];//插入节点的next指向新表的第一个节点
  20.                 newtable[index] = cur;//第一个节点变为cur
  22.                 cur = next;
  23.             }
  24.             _tables[i] = nullptr;
  25.         }
  26.         newtables.swap(_tables);
  27.     }
  29.     size_t index = kv.first % _tables.size();//要存的位置
  30.     Node* cur = _table[index];
  31.     while(cur)
  32.     {
  33.         if(cur->_kv.first == kv.first)
  34.         {
  35.             return false;
  36.         }
  37.         else
  38.         {
  39.             cur = cur->_next;
  40.         }
  41.     }
  42.     Node* newnode = new Node(kv);
  43.     //插入节点->头插
  44.     newnode->_next = _table[index];
  45.     _table[index] = newnode;
  46.     ++_n;
  47. }

哈希表插入效率很高，但是扩容影响了插入接口的效率，扩容的代价比较大

哈希表的查找

  1. 如果表的大小等于0，返回nullptr
  2. 找到桶的位置，然后进行遍历桶，比较值是否相等，相等则返回，不相等继续下一个节点
  3. 遍历完没找到返回nullptr
  1. Node* Find(const K& key)
  2. {
  3.     if(_table.size() == 0)
  4.     {
  5.         return nullptr;
  6.     }
  7.     size_t index = key % _table.size();
  8.     Node* cur = _table[index];//第一个节点的指针
  9.     while(cur)
  10.     {
  11.         if(cur->_kv.first == key)
  12.         {
  13.             return cur;
  14.         }
  15.         else
  16.         {
  17.             cur = cur->_next;
  18.         }
  19.     }
  20.     return nullptr;
  21. }

哈希表的删除

  1. 如果表的大小等于0，返回false
  2. 找到桶的位置，需要注意删除节点需要保存节点的前一个节点，遍历桶找要删除的节点进行删除，需要注意头删和非头删，头删时prev为空，非头删prev不为空
  3. 删除完成–_n，返回true，否则返回false
  1. bool Erase(const K& key)
  2.  {
  3.      if(_table.size() == 0)
  4.      {
  5.          return false;
  6.      }
  7.      size_t index = key % _table.size();
  8.      Node* prev = nullptr;
  9.      Node* cur = _tables[index];
  10.      while(cur)
  11.      {
  12.          if(cur->_kv.first == key)
  13.          {
  14.              //找到这个节点
  15.              if(prev == nullptr)
  16.              {
  17.                  //cur是第一个节点
  18.                  _table[index] = cur->_next;
  19.                  delete cur;
  20.              }
  21.              else
  22.              {
  23.                  //不是头节点
  24.                  prev->next = cur->_next;
  25.                  delete cur;
  26.              }
  27.              --_n;
  28.              return true;
  29.          }
  30.          else
  31.          {
  32.              prev = cur;
  33.              cur = cur->_next;
  34.          }
  35.      }
  36.      //没有这个值
  37.      return false;
  38.  }

开散列和闭散列一样，都得通过仿函数处理string的情况：

  1. template<class K>
  2. struct HashFunc
  3. {
  4. 	size_t operator()(const K& key)
  5. 	{
  6. 		return key;
  7. 	}
  8. };
  9. // 特化
  10. template<>
  11. struct HashFunc < string >
  12. {
  13. 	size_t operator()(const string& key)
  14. 	{
  15. 		// BKDR Hash思想
  16. 		size_t hash = 0;
  17. 		for (size_t i = 0; i < key.size(); ++i)
  18. 		{
  19. 			hash *= 131;
  20. 			hash += key[i];
  21. 		}
  23. 		return hash;
  24. 	}
  25. };

哈希表的大小尽可能是一个素数，这样效率会有提高，源码里面增加了一个素数表，还有一个GetNextPrime函数，获取下一个素数，我们可以用这个函数来获得newSize：

  1. size_t GetNextPrime(size_t prime)
  2. {
  3.     const int PRIMECOUNT = 28;
  4.     const size_t primeList[PRIMECOUNT] =
  5.     {
  6.         53ul, 97ul, 193ul, 389ul, 769ul,
  7.         1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
  8.         49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
  9.         1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
  10.         50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
  11.         1610612741ul, 3221225473ul, 4294967291ul
  12.     };
  13.     size_t i = 0;
  14.     for(; i < PRIMECOUNT; ++i)
  15.     {
  16.         if(primeList[i] > prime)
  17.             return primeList[i];
  18.     }
  19.     return primeList[i];
  20. }

所以我们的扩容的newSize这样获取，这样可以获取比表大小大的素数，所以insert接口扩容大小这样写效率更高：

  1. size_t newSize = GetNextPrime(_table.size());//获取比表大小大的素数

STL当中有桶的个数和最大桶的个数的接口：

哈希桶的析构函数

  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.     _n = 0;
  15. }

哈希表开散列的完整代码

  1. namespace bucket_hash
  2. {
  3. 	template<class K, class V>
  4. 	struct HashNode
  5. 	{
  6. 		pair<K, V> _kv;
  7. 		HashNode<K, V>* _next;
  9. 		HashNode(const pair<K, V>& kv)
  10. 			:_kv(kv)
  11. 			, _next(nullptr)
  12. 		{}
  13. 	};
  15. 	size_t GetNextPrime(size_t prime)
  16. 	{
  17. 		const int PRIMECOUNT = 28;
  18. 		static const size_t primeList[PRIMECOUNT] =
  19. 		{
  20. 			53ul, 97ul, 193ul, 389ul, 769ul,
  21. 			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
  22. 			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
  23. 			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
  24. 			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
  25. 			1610612741ul, 3221225473ul, 4294967291ul
  26. 		};
  28. 		size_t i = 0;
  29. 		for (; i < PRIMECOUNT; ++i)
  30. 		{
  31. 			if (primeList[i] > prime)
  32. 				return primeList[i];
  33. 		}
  35. 		return primeList[i];
  36. 	}
  38. 	template<class K, class V, class Hash = HashFunc<K>>
  39. 	class HashTable
  40. 	{
  41. 		typedef HashNode<K, V> Node;
  42. 	public:
  44. 		// 拷贝 和 赋值 需要自己实现桶的拷贝
  46. 		~HashTable()
  47. 		{
  48. 			for (size_t i = 0; i < _tables.size(); i++)
  49. 			{
  50. 				Node* cur = _tables[i];
  51. 				while (cur)
  52. 				{
  53. 					Node* next = cur->_next;
  54. 					delete cur;
  55. 					cur = next;
  56. 				}
  58. 				_tables[i] = nullptr;
  59. 			}
  60. 			_n = 0;
  61. 		}
  63. 		bool Erase(const K& key)
  64. 		{
  65. 			if (_tables.size() == 0)
  66. 			{
  67. 				return false;
  68. 			}
  70. 			Hash hf;
  71. 			// 素数
  72. 			size_t index = hf(key) % _tables.size();
  73. 			Node* prev = nullptr;
  74. 			Node* cur = _tables[index];
  75. 			while (cur)
  76. 			{
  77. 				if (cur->_kv.first == key)
  78. 				{
  79. 					// 1、cur是头结点
  80. 					// 2、非头节点
  81. 					if (prev == nullptr)
  82. 					{
  83. 						_tables[index] = cur->_next;
  84. 					}
  85. 					else
  86. 					{
  87. 						prev->_next = cur->_next;
  88. 					}
  90. 					delete cur;
  91. 					--_n;
  93. 					return true;
  94. 				}
  95. 				else
  96. 				{
  97. 					prev = cur;
  98. 					cur = cur->_next;
  99. 				}
  100. 			}
  102. 			return false;
  103. 		}
  105. 		Node* Find(const K& key)
  106. 		{
  107. 			if (_tables.size() == 0)
  108. 			{
  109. 				return nullptr;
  110. 			}
  112. 			Hash hf;
  113. 			size_t index = hf(key) % _tables.size();
  114. 			Node* cur = _tables[index];
  115. 			while (cur)
  116. 			{
  117. 				if (cur->_kv.first == key)
  118. 				{
  119. 					return cur;
  120. 				}
  121. 				else
  122. 				{
  123. 					cur = cur->_next;
  124. 				}
  125. 			}
  127. 			return nullptr;
  128. 		}
  130. 		bool Insert(const pair<K, V>& kv)
  131. 		{
  132. 			Hash hf;
  134. 			//当负载因子到1时，进行扩容
  135. 			if (_n == _tables.size())
  136. 			{
  137. 				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
  138. 				size_t newSize = GetNextPrime(_tables.size());
  140. 				//HashTable<K, V> newHT;
  141. 				vector<Node*> newtables;
  142. 				newtables.resize(newSize, nullptr);
  143. 				for (size_t i = 0; i < _tables.size(); ++i)
  144. 				{
  145. 					Node* cur = _tables[i];
  146. 					while (cur)
  147. 					{
  148. 						Node* next = cur->_next;
  150. 						size_t index = hf(cur->_kv.first) % newSize;
  151. 						cur->_next = newtables[index];
  152. 						newtables[index] = cur;
  154. 						cur = next;
  155. 					}
  156. 					_tables[i] = nullptr;
  157. 				}
  159. 				newtables.swap(_tables);
  160. 			}
  162. 			size_t index = hf(kv.first) % _tables.size();
  163. 			Node* cur = _tables[index];
  164. 			while (cur)
  165. 			{
  166. 				if (cur->_kv.first == kv.first)
  167. 				{
  168. 					return false;
  169. 				}
  170. 				else
  171. 				{
  172. 					cur = cur->_next;
  173. 				}
  174. 			}
  176. 			Node* newnode = new Node(kv);
  177. 			newnode->_next = _tables[index];
  178. 			_tables[index] = newnode;
  180. 			++_n;
  182. 			return true;
  183. 		}
  185. 	private:
  186. 		vector<Node*> _tables;
  187. 		size_t _n = 0; // 存储多少有效数据
  188. 	};

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/attemptendeavor/article/details/123859811

内容来源于网络，如有侵权，请联系作者删除！

c++算法哈希

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com