处理哈希冲突
- 实践中哈希表⼀般还是选择除法散列法作为哈希函数。
当然哈希表无论选择什么哈希函数也避免不了冲突（主要作用就是减少冲突），那么插入数据时，如何解决冲突呢？主要有两种两种方法，开放定址法和链地址法。
开放定址法
线性探测
- 从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置。
- h(key) = hash0 = key % M, hash0位置冲突了，则线性探测公式为：hc(key, i) = hashi = (hash0 + i) % M，i = {1, 2, 3, ..., M - 1}，因为负载因子小于1，则最多探测M-1次，⼀定能找到⼀个存储key的位置。
- 线性探测的比较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1，hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。下面的⼆次探测可以⼀定程度改善这个问题。
简单点说，就是线性探测会发生堆积问题，以下面的图来说，19占了（8）的位置，30经过哈希函数也是要插到（8）的位置，但（8）有值， 就往后插了；20要插（9）也往后插了，以此类推；这种就是堆积；
也不是说堆积不好，但相同的哈希key（h(key)）在一起，总感觉不太好
线性探测的插入
//线性探测
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
//我们哈希表负载因⼦控制在0.7
//if (_n * 10 / _tables.size() > 7)
//{
// //.....
// //重复线性探测的过程
// vector<HashData<K, V>> newtable(_tables.size() * 2);
// size_t hhash0 = kv.first % newtable.size();
// size_t hhashi = hhash0;
// //为什么没有显示
// while (newtable[hhashi]._state == EMPTY)
// {
// //线性探测;
// hhashi++;
// hhashi = hhashi % newtable.size();
// }
// newtable[hhashi]._state = EXIST;
// newtable[hhashi]._kv = kv;
// ++_n;
// _tables.swap(newtable);
//}
if (_n * 10 / _tables.size() >= 7)
{
//自我实现扩大的是两倍
//HashTable<K, V> newt;
//newt._tables.resize(_tables.size() * 2);
//c++实现
HashTable<K, V, Hash> newt;
//lower_bound(first, last, n); +1 正好能找到比他大的
newt._tables.resize(__stl_next_prime(_tables.size() + 1)); //素数表
for (auto e : _tables)
{
if (e._state == EXIST)
{
newt.Insert(e._kv);
}
}
_tables.swap(newt._tables);
}
//线性探测
//不是 capacity size才是哈希表的容积
Hash hash;
size_t hsah0 = hash(kv.first) % _tables.size();
size_t hashi = hsah0;
//为什么没有显示
while (_tables[hashi]._state != EMPTY)
{
//线性探测;
hashi++;
hashi = hashi % _tables.size();
}
_tables[hashi]._state = EXIST;
_tables[hashi]._kv = kv;
++_n;
return true;
}
二次探测
- 从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下⼀个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置；
如下图：
- h(key) = hash0 = key % M, hash0位置冲突了，则⼆次探测公式为：
hc(key, i) = hashi = (hash0 ± i2) % M， i = {1, 2, 3, ..., }
- 二次探测当 hashi = (hash0 - i2)%M 时，当hashi<0时，需要hashi += M
下面演⽰ {19,30,52,63,11,22} 等这一组值映射到M=11的表中。
二次探测的插入
//二次探测 bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; if (_n * 10 / _tables.size() >= 7) { //自我实现扩大的是两倍 //HashTable<K, V> newt; //newt._tables.resize(_tables.size() * 2); //c++实现 HashTable<K, V> newt; //lower_bound(first, last, n); +1 正好能找到比他大的 newt._tables.resize(__stl_next_prime(_tables.size() + 1)); for (auto e : _tables) { if (e._state == EXIST) { newt.Insert(e._kv); } } _tables.swap(newt._tables); } //不是 capacity size才是哈希表的容积 size_t hsah0 = kv.first % _tables.size(); size_t hashi = hsah0; size_t i = 1; int flag = 1; //为什么没有显示 while (_tables[hashi]._state != EMPTY) { //二次探测 hashi = (hashi + i * i * flag) % _tables.size(); if (flag > 0) { flag = -1; } else if(flag < 0) { flag = 1; i++; } //当然 既然插入的方法变了， 那么查找的方法也肯定有变化，但在这里就不演示了 } _tables[hashi]._state = EXIST; _tables[hashi]._kv = kv; ++_n; return true; }
双重散列
- 第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止
- h1(key) = hash0 = key % M, hash0位置冲突了，则双重探测公式为：hc(key, i) = hashi = (hash0 + i ∗ h2(key)) % M， i = {1, 2, 3, ..., M}
- 要求 h2(key) < M 且 h2(key) 和M互为质数，
有两种简单的取值方法：
- 当M为2整数冥时， 从[0，M-1]任选⼀个奇数；（其中要保证 每个key对应的 h2(key)是一致的）
- 当M为质数时， h2(key) = key % (M - 1) + 1
- 保证 与M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群，若最大公约数p = gcd(M, h1(key)) > 1，那么所能寻址的位置的个数为 M / P < M，使得对于⼀个关键字来说无法充分利⽤整个散列表。（简单来说就是充分利用整个散列表，尽量在减少堆积的同时也减少散列表的空位置）
举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的位置为{1, 4, 7, 10}，寻址个数为 12/ gcd(12, 3) = 4。（这个是反例）
（为什么要保证是互质总的来说就是，散列表的位置很多都用不到。还有就是这个公式可以最大的程度利用，其中具体情况 可以自行搜索了解其数学解法哦）
下面演示 {19,30,52} 等这⼀组值映射到M=11的表中，设 h2(key) = key%10 + 1
二次探测
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
if (_n * 10 / _tables.size() >= 7)
{
//自我实现扩大的是两倍
//HashTable<K, V> newt;
//newt._tables.resize(_tables.size() * 2);
//c++实现
HashTable<K, V> newt;
//lower_bound(first, last, n); +1 正好能找到比他大的
newt._tables.resize(__stl_next_prime(_tables.size() + 1));
for (auto e : _tables)
{
if (e._state == EXIST)
{
newt.Insert(e._kv);
}
}
_tables.swap(newt._tables);
}
//不是 capacity size才是哈希表的容积
size_t hsah0 = kv.first % _tables.size();
size_t hashi = hsah0;
size_t i = 1;
int flag = 1;
//为什么没有显示
while (_tables[hashi]._state != EMPTY)
{
//二次探测
hashi = (hashi + i * i * flag) % _tables.size();
if (flag > 0)
{
flag = -1;
}
else if(flag < 0)
{
flag = 1;
i++;
}
//当然 既然插入的方法变了， 那么查找的方法也肯定有变化，但在这里就不演示了
}
_tables[hashi]._state = EXIST;
_tables[hashi]._kv = kv;
++_n;
return true;
}链地址法
解决冲突的思路:
开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。
下面演示 {19,30,5,36,13,20,21,12,24,96} 等这一组值映射到M=11的表中。
- h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1,h(24) = 2,h(96) = 88
扩容
开放定址法负载因子必须小于1（这与开放性地址的扩容条件不太一样），链地址法的负载因子就没有限制了，可以大于1。
- 负载因子越大，哈希冲突的概率越高，空间利用率越高；
- 负载因子越小，哈希冲突的概率越低，空间利用率越低；
这里就在 负载因子 == 1 时扩容；
stl中unordered_xxx的最大负载因⼦基本控制在1，大于1就扩容，之后手动实现unordered_xxx也使用这个方式。
- 如果极端场景下，某个桶特别长怎么办？其实我们可以考虑使用全域散列法，这样就不容易被针对了。但是假设不是被针对了，用了全域散列法，但是偶然情况下，某个桶很长，查找效率很低怎么办？
在Java8的HashMap中当桶的长度超过⼀定阀值(8)时就把链表转换成红黑树。这是一个解决极端场景的思路，大家可以了解一下。
其实一般也不会很长，毕竟会扩容；扩容的时候哈希表的数据会重新，经过哈希函数分到不同位置；
链地址法代码实现
namespace hash_bucket { template<class K, class V> struct HashData { public: pair<K, V> _kv; HashData* next; HashData(const pair<K, V>& kv) :_kv(kv) , next(nullptr) {} }; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; //如果不想每次实现都自己传，可以利用全特化，将其设置为默认模板 //以string 为例子 template<> struct HashFunc<string> { size_t operator()(const string& s) { size_t num = 0; for (auto ch : s) { num += ch; //为什么要乘 131 //这涉及到BKDR-哈希表算法 //这可以最大程度避免冲突的情况，具体如何实现可以上网搜索 num *= 131; } return num; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: typedef HashData<K, V> Node; inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes = 28; static const unsigned long __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } HashTable() //:_tables(__stl_next_prime(0)) :_tables(11) ,_n(0) {} bool Insert(const pair<K, V>& kv) { // 负载因子 == 1时扩容 // // 这种没必要，有多少节点还有删多少节点，复制多少节点；效率很低； // 而且vector的默认析构函数还不能将 节点上的全部节点都删掉；还有自己实现 //if (_n == _tables.size()) //{ // HashTable newtb; // newtb._tables.resize(__stl_next_prime(_tables.size() + 1)); // for (size_t i = 0; i < _tables.size(); i++) // { // Node* cur = _tables[i]; // while (cur) // { // newtb.Insert(cur->_kv); // cur = cur->next; // } // } // _tables.swap(newtb._tables); //} //负载因子 == 1时扩容 if (_n == _tables.size()) { vector<Node*> newtb; newtb.resize(__stl_next_prime(_tables.size() + 1)); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Hash hhash; Node* next = cur->next; size_t hhash0 = hhash(cur->_kv.first) % newtb.size(); //头插 cur->next = newtb[hhash0]; newtb[hhash0] = cur; cur = next; } } _tables.swap(newtb); } Hash hash; size_t hash0 = hash(kv.first) % _tables.size(); Node* newnode = new Node(kv); //头插 newnode->next = _tables[hash0]; _tables[hash0] = newnode; _n++; return true; } Node* Find(const K& key) { Hash hash; size_t hash0 = hash(key) % _tables.size(); Node* cur = _tables[hash0]; while (cur) { if (cur->_kv.first == key) { return cur; } else { cur = cur->next; } } return nullptr; } bool Erase(const K& key) { Hash hash; size_t hash0 = hash(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hash0]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) { _tables[hash0] = cur->next; } else { prev->next = cur->next; } delete cur; --_n; return true; } else { prev = cur; cur = cur->next; } } return false; } private: vector<Node*> _tables; // 指针数组 size_t _n = 0; // 表中存储数据个数 }; }
