哈希——哈希表处理哈希冲突的方法

处理哈希冲突

实践中哈希表⼀般还是选择除法散列法作为哈希函数。

当然哈希表无论选择什么哈希函数也避免不了冲突（主要作用就是减少冲突），那么插入数据时，如何解决冲突呢？主要有两种两种方法，开放定址法和链地址法。

开放定址法

线性探测

从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置。
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;		    // 表中存储数据个数};
}