认识哈希以及哈希表的模拟实现

1.什么是哈希

   概念：哈希（hash）又称散列，是一种构造数据的方式。从译名来看，有散乱分列的意思。本质就是通过哈希函数把关键字key跟存储位置创建一个映射关系，查找时通过这个哈希函数盘算出key存储的位置，举行快速地查找
  举个例子：
哈希最简单的一种方式就是直接定址法，当关键字的范围比较集中时，直接定址法就黑白常简单高效的方法，如一组关键字值都在[a,z]的小写字母，那么我们就可以开一个有26个空间的数组，每个关键字通过一个哈希函数盘算出要存储在数组空间的位置，该哈希函数可以为用每个关键字的ASCII码值减去a的ASCII码值，得到的结果就是它们要存储位置的下标，也就是说直接定址法就是用关键字盘算出一个绝对位置大概相对位置。固然该种方法也是有缺点的，当关键字的范围比较分散时，就很浪费内存甚至不敷用。
所以，哈希的本质就是，通过某一种特定的规则，映射到某个存储空间，将关键字存储到这个空间，那么在查找大概删除时也通过该规则找到这个关键字，如许就进步了查找的服从
2.哈希函数

2.1 除留余数法/除法散列法

假设哈希表的巨细为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。当利用除留余数法时们要只管克制M为某些值，如2的幂，10的幂。假如是2^x，那么key模上2的x次方就相称于生存key后面的后x位，那么后x位雷同的值，盘算出来都是一样的，映射位置就辩说了，比方：63和31这两个数，然后取M为16，也就是2的4次方，那么63和31通过哈希函数盘算出来的结果都为15，由于63和31的二进制位的后4位是雷同的，导致结果一样。假如M取10的幂那么就更明显了。所以利用该方法时，发起取M不太靠近2的整数次幂的一个质数（素数）
2.2 乘法散列法

乘法散列法对哈希的巨细M不做要求，第一步：用关键字key乘上常数A(0<A<1)，并抽取出key*A的小数部分，第二步：再用M乘上得到的小数部分，再向下取整。也就是说哈希函数为：h(key) = floor(M x ((A x key)%0.1))，此中floor表示对表达式向下取整，A的取值最好为0.6180339887…（黄金分割点）
2.3 全域散列法

全域散列法重要用于，防止我们利用的哈希函数遭到粉碎，比如针对我们提供的哈希函数，特意构造一个发生严峻辩说的数据集，导致所有关键字都落到同一个位置。办理这种问题的方法就是给我们的哈希函数增长随机性，也就是全域散列法。哈希函数为：h(key) = ((a x key + b) % P)% M，此中P要选一个充足大的素数，a可以选1~P-1的恣意整数，b可以选0到P-1的恣意整数，这些函数构成了一个P*（P-1）组全域散列组。须要注意的是每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数利用，后续的增删查改也要利用这个散列函数，否则就导致找不到插入的key了
以上是几种常见的订定哈希函数的方法
3.哈希辩说

   概念：当两个差别的key映射到同一个位置时，这种情况就叫作哈希辩说大概哈希碰撞
  我们知道即使操持了良好的哈希函数，但是哈希辩说是不可克制的，选择良好的哈希函数只是尽大概地淘汰辩说。那么有什么办法可以办理辩说呢，来看下面几种方法
4.办理哈希辩说的方法

4.1 开放定址法

在开放定址法中所有元素都放到哈希表里，当一个关键字key用哈希函数盘算出的位置辩说了，则再按照某种规则找到一个没有存储数据的位置举行存储，开放定址法中负载因子肯定是小于的，这里的规则有三种如下：

• 线性探测：从发生辩说的位置开始，依次线性向后探测，直到探求到下一个没有存储数据的位置为止，假如走到哈希表尾，则回绕到哈希表头的位置。用除留余数法盘算出h(key) = hash0 = key % M，若hash0的位置辩说了，则线性探测：h(key,i) = hashi = (key + i) % M，i的取值为0到M-1，由于负载因子小于1，负载因子为存储值的个数比上空间个数，则最多探测M - 1次，肯定能找到一个存储key的位置。如下图举例：
  

• 二次探测：从发生辩说位置开始，依次左右按二次方跳跃式探测，直到探求到下一个没有存储数据的位置为止，假如往右走到哈希为，则回绕到哈希表头的位置；假如往左走到哈希头，则回绕到哈希表尾的位置，用除留余数法盘算出h(key)=hash0=key%M,若hash0辩说了，则二次探测：h(key,i)=hashi=(hash0 ± i^2)%M，i的取值为0到M/2，当hashi小于0时须要hashi+=M，如下图举例：
  

• 双重探测(相识)：第一个哈希函数盘算出的值发生辩说，使第二个哈希函数盘算出一个跟key干系的偏移量值，不断以后探测，直到探求到下一个没有存储数据的位置为止。h(key)=hash0=key%M，发生辩说时，双重探测公式为：hc(key,i)=hashi=(hash0+i*h2(key))%M，i的取值为1到M，要h2(key)<M，且它们互为质数。
  

4.1.1 用除留余数法和线性探测模拟实现简单的哈希表

代码如下：

1. #pragma once
2. #include <iostream>
3. #incldue <vector>
4. using namespace std;
6. //用于表示存储空间的状态
7. enum State
8. {
9.         EXIST,
10.         DELETE,
11.         EMPTY
12. };
13. template<class K,class V>
14. struct HashData
15. {
16.         pair<K, V> _kv;
17.         State _state = EMPTY; //存储哈希表中存储空间的状态
18. };
20. //由于哈希表对关键字的要求是支持关键字能取模、且还能支持比较关键字相等
21. //所以我们需要通过用仿函数取去控制关键字
22. template<class K>
23. class HashFunc
24. {
25. public:
26.         const size_t operator()(const K& key)
27.         {
28.                 return (size_t)key;
29.         }
30. };
32. //由于string作为关键字经常被用到，所以可以对string转整型的仿函数作特化
33. template<>
34. class HashFunc<string>
35. {
36. public:
37.         const size_t operator()(const string& key)
38.         {
39.                 size_t ret = 0;
40.                 for (auto& s : key)
41.                 {
42.                         //使string的每个ASCII码值都参与运算，得到不同的关键字
43.                         ret += s;
44.                         ret *= 131;
45.                 }
46.                 return ret;
47.         }
48. };
50. template<class K,class V,class Hash = HashFunc<K>> //由于int类型的关键字经常用，所以用来作缺省值
51. class HashTable
52. {
53. public:
55.         //sgi版本的哈希表
56.         inline unsigned long _stl_next_prime(unsigned long n)
57.         {
58.                 static const int _stl_num_primes = 28;
59.                 static const unsigned long _stl_primes_list[_stl_num_primes] =
60.                 {
61.                         53,        97,        193,        389,        769,
62.                         1543,      3079,      6151,       12289,      24593,
63.                         49157,     98317,     196613,     393241,     786433,
64.                         1572869,   3145739,   6291469,    12582917,   25165843,
65.                         50331653,  100663319, 201326611,  402653189,  805306457,
66.                         1610612741,           3221225473,             4294967291
67.                 };
68.                 const unsigned long* first = _stl_primes_list;
69.                 const unsigned long* last = _stl_primes_list + _stl_num_primes;
70.                 const unsigned long* pos = lower_bound(first, last, n);
71.                 //lower_bound()在迭代器的范围内取>=n的最小值
72.                 return pos == last ? *(pos - 1) : *(pos);
73.         }
74.         HashTable()
75.         {
76.                 //提前开好第一个质数大小的空间
77.                 _tables.resize(_stl_next_prime(1));
78.         }
79.         bool insert(const pair<K, V>& kv)
80.         {
81.                 if (find(kv.first))
82.                         return false; //次模拟实现不允许冗余
84.                 //当负载因子过大时，就会扩容，负载因子一般到0.7就扩容了
85.                 //扩容这里还是按照扩2倍的方式扩容，但是要保持哈希的大小是一个质数，当第一个是质数，
86.                 //扩2倍就不是质数了，如何解决这样的问题呢，使用sgi版本的哈希表，它提供了一个近似2倍的质数表
87.                 //我们可以每次去质数表中获取扩容后的大小即可
88.                
89.                 if ((double)_n / (double)_tables.size() >= 0.7)
90.                 {
91.                         //获取质数表中比当前质数还要大的下一个质数
92.                         size_t newsize = _stl_next_prime(_tables.size() + 1);
93.                        
94.                         //由于扩容了之后，哈希表的大小发生了变化，所以哈希表里面的值需要重新映射
95.                         //创建一个哈希表对象，开一个newsize大小的空间，调用insert函数
96.                         HashTable<K, V, Hash> newhs;
97.                         newhs._tables.resize(newsize);
98.                        
99.                         //遍历旧表，将值全部映射到新的哈希表
100.                         for (int i = 0; i<_tables.size(); ++i)
101.                         {
102.                                 if (_tables[i]._state == EXIST)
103.                                 {
104.                                         newhs.insert(_tables[i]._kv);
106.                                 }
107.                         }
108.                         _tables.swap(newhs._tables);
109.                 }
110.                 Hash hs;
111.                 size_t hash0 = hs(kv.first) % _tables.size();
112.                 size_t hashi = hash0;
113.                 size_t i = 1;
114.                 while (_tables[hashi]._state == EXIST)
115.                 {
116.                         //说明存在冲突
117.                         //使用线性探测解决冲突
118.                         hashi = (hash0 + i) % _tables.size();
119.                         ++i;
120.                 }
121.                 //说明该hashi的位置为EMPTY或DELETE
122.                 _tables[hashi]._kv = kv;
123.                 _tables[hashi]._state = EXIST;
124.                 ++_n;
125.                 return true;
126.         }
128.         HashData<K, V>* find(const K& key)
129.         {
130.                 Hash hs;
131.                 size_t hash0 = hs(key) % _tables.size();
132.                 size_t hashi = hash0;
133.                 size_t i = 1;
134.                 while (_tables[hashi]._state != EMPTY)
135.                 {
136.                         if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
137.                         {
138.                                 return &_tables[hashi];
139.                         }
140.                         //线性探测
141.                         hashi = (hash0 + i) % _tables.size();
142.                         ++i;
143.                 }
144.                 return nullptr;
145.         }
147.         bool erase(const K& key)
148.         {
149.                 HashData<K, V>* ret = find(key);
150.                 if (ret)
151.                 {
152.                         --_n;
153.                         ret->_state = DELETE;
154.                         return true;
155.                 }
156.                 return false;
157.         }
159. private:
160.         vector<HashData<K,V>> _tables; //直接用vector来作哈希表
161.         size_t _n; //表中存储数据个数
162. };

复制代码

4.2 链地点法

开放定址法虽然办理了哈希辩说，但是都是通过占用其他数据的位置来存放数据的，弊大于利，且开放定址法的所有数据都存放在哈希表中，但链地点法不是，链地点法不直接将数据存放在哈希表中，而是在哈希表中存放一个指针，没有数据映射这个位置时，该指针指向空，当有多个数据映射同一个位置时，就把这些辩说的数据链接成一个链表，挂在哈希表中映射到的位置下面，链地点法也叫作哈希桶。
链地点法如下图例：

从上面的举例来看，如许既办理了哈希辩说的问题，也办理了占用其他数据位置的问题，相较于开放定址法，该方法较优
链地点法的扩容问题
开放定址法的负载因子须小于1，而链地点法的负载因子就没有限定了，可以大于1，但是负载因子越大，哈希辩说的概率就越大，空间利用率也越高，所以将负载因子根本控制在1就好。stl中的unordered_map和unordered_set的最大负载因子也为1
4.2.1 用除留余数法和链地点法模拟实现简单的哈希表

1. #pragma once
2. #include <iostream>
3. #include <vector>
4. namespace hash_bucket
5. {
6.         //将存储的数据定义成结点
7.         template<class K,class V>
8.         struct HashNode
9.         {
10.                 pair<K, V> _kv;
11.                 HashNode<K, V>* _next;//指向下一个结点的指针
13.                 HashNode(const pair<K,V>& kv)
14.                         :_kv(kv)
15.                         ,_next(nullptr)
16.                 { }
17.         };
19.         template<class K>
20.         class HashFunc
21.         {
22.         public:
23.                 const size_t operator()(const K& key)
24.                 {
25.                         return (size_t)key;
26.                 }
27.         };
29.         //由于string作为关键字经常被用到，所以可以对string转整型的仿函数作特化
30.         template<>
31.         class HashFunc<string>
32.         {
33.         public:
34.                 const size_t operator()(const string& key)
35.                 {
36.                         size_t ret = 0;
37.                         for (auto& s : key)
38.                         {
39.                                 //使string的每个ASCII码值都参与运算，得到不同的关键字
40.                                 ret += s;
41.                                 ret *= 131;
42.                         }
43.                         return ret;
44.                 }
45.         };
47.         template<class K,class V,class Hash = HashFunc<K>>
48.         class HashTable
49.         {
50.                 typedef HashNode<K, V> Node;
51.         public:
52.                 inline unsigned long _stl_next_prime(unsigned long n)
53.                 {
54.                         static const int _stl_num_primes = 28;
55.                         static const unsigned long _stl_primes_list[_stl_num_primes] =
56.                         {
57.                                 53,        97,        193,        389,        769,
58.                                 1543,      3079,      6151,       12289,      24593,
59.                                 49157,     98317,     196613,     393241,     786433,
60.                                 1572869,   3145739,   6291469,    12582917,   25165843,
61.                                 50331653,  100663319, 201326611,  402653189,  805306457,
62.                                 1610612741,           3221225473,             4294967291
63.                         };
64.                         const unsigned long* first = _stl_primes_list;
65.                         const unsigned long* last = _stl_primes_list + _stl_num_primes;
66.                         const unsigned long* pos = lower_bound(first, last, n);
67.                         //lower_bound()在迭代器的范围内取>=n的最小值
68.                         return pos == last ? *(pos - 1) : *(pos);
69.                 }
70.                 HashTable()
71.                 {
72.                         //提前开好第一个质数大小的空间
73.                         _tables.resize(_stl_next_prime(1),nullptr);
74.                 }
75.                 ~HashTable()
76.                 {
77.                         //遍历哈希表，把每个桶都释放掉
78.                         for (int i = 0; i < _tables.size(); ++i)
79.                         {
80.                                 Node* cur = _tables[i];
81.                                 while (cur)
82.                                 {
83.                                         Node* next = cur->_next;
84.                                         delete cur;
85.                                         cur = next;
86.                                 }
87.                                 _tables[i] = nullptr;
88.                         }
89.                 }
90.                 bool insert(const pair<K, V>& kv)
91.                 {
92.                         if (find(kv.first))
93.                                 return false;
95.                         Hash hs;
97.                         //到负载因子到1时就扩容
98.                         if (_n == _tables.size())
99.                         {
100.                                 size_t newsize = _stl_next_prime(_tables.size() + 1);
102.                                 //创建一个新的指针数组，将旧表中的结点直接移动到新的指针数组中
103.                                 //直接对结点进行二次利用，避免了多次拷贝的问题
104.                                 vector<Node*> newtables(newsize, nullptr);
105.                                 //遍历就表，将结点移到newtables中
106.                                 for (int i = 0; i < _tables.size(); ++i)
107.                                 {
108.                                         Node* cur = _tables[i];
109.                                         while (cur)
110.                                         {
111.                                                 //从头开始将结点移动过去，所以要记录好下一个结点
112.                                                 Node* next = cur->_next;
113.                                                
114.                                                 //计算当前结点在新表中映射的位置
115.                                                 size_t hashi = hs(cur->_kv.first) % newtables.size();
116.                                                 //一样头插到新表中
117.                                                 cur->_next = newtables[hashi];
118.                                                 newtables[hashi] = cur;
120.                                                 cur = next;
121.                                         }
122.                                         //旧表的数据都被移走了，须置空
123.                                         _tables[i] = nullptr;
124.                                 }
125.                                 //最后再进行交换
126.                                 _tables.swap(newtables);
127.                         }
128.                        
129.                         size_t hashi = hs(kv.first) % _tables.size();
130.                         Node* newnode = new Node(kv);
132.                         //用头插的方式插到哈希桶里
133.                         newnode->_next = _tables[hashi];
134.                         _tables[hashi] = newnode;
135.                         ++_n;
136.                         return true;
137.                 }
139.                 Node* find(const K& key)
140.                 {
141.                         Hash hs;
142.                         size_t hashi = hs(key) % _tables.size();
143.                         Node* cur = _tables[hashi];
144.                         while (cur)
145.                         {
146.                                 if (cur->_kv.first == key)
147.                                 {
148.                                         return cur;
149.                                 }
150.                                 cur = cur->_next;
151.                         }
152.                         return nullptr;
153.                 }
155.                 bool erase(const K& key)
156.                 {
157.                         Hash hs;
158.                         size_t hashi = hs(key) % _tables.size();
159.                         Node* cur = _tables[hashi];
160.                         Node* prev = nullptr;
161.                         while (cur)
162.                         {
163.                                 if (cur->_kv.first == key)
164.                                 {
165.                                         if (prev == nullptr)
166.                                         {
167.                                                 //头删
168.                                                 _tables[hashi] = cur->_next;
169.                                         }
170.                                         else
171.                                         {
172.                                                 //先建立前后链接再删除
173.                                                 prev->_next = cur->_next;
174.                                         }
175.                                         delete cur;
176.                                         --_n;
177.                                         return true;
178.                                 }
179.                                 prev = cur;
180.                                 cur = cur->_next;
181.                         }
182.                         return false;
183.                 }
185.         private:
186.                 vector<Node*> _tables; //指针数组
187.                 size_t _n = 0;
188.         };
189. }

复制代码