【C++进阶】哈希表的介绍及实现
【C++进阶】哈希表的介绍及实现
🥕个人主页：开敲🍉
🔥所属专栏：C++🥭
🌼文章目录🌼
1. 哈希的概念
1.1 直接定址法
1.2 哈希冲突
1.3 负载因子
1.4 将关键字转为整数
2. 哈希函数
2.1 除法散列法/除留余数法
2.2 乘法散列法
2.3 全域散列法
3. 处理哈希冲突
3.1 开放定址法
3.2 开放定址法代码实现
3.3 链地址法
3.4 链地址法代码实现
1. 哈希的概念
哈希(hash)又称散列，是⼀种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进行快速查找。
1.1 直接定址法
当关键字的范围比较集中时，直接定址法就是非常简单高效的方法，比如⼀组关键字都在[0,99]之间，那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[a,z]的小写字母，那么我们开⼀个26个数的数组，每个关键字acsii码-a ascii码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。相关OJ算法题：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）
1.2 哈希冲突
直接定址法的缺点也非常明显，当关键字的范围比较分散时，就很浪费内存甚至内存不够用。假设我们只有数据范围是[0, 9999]的N个值，我们要映射到⼀个M个空间的数组中(⼀般情况下M >= N)，那么就要借助哈希函数(hash function)hf，关键字key被放到数组的h(key)位置，这里要注意的是h(key)计算出的值必须在[0, M)之间。
这里存在的⼀个问题就是，两个不同的key可能会映射到同一个位置去，这种问题我们叫做哈希冲突，或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。
1.3 负载因子
假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么 负载因子 ＝ N/M，负载因子有些地方也翻译为载荷因子/装载因子等，他的英文为load factor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。
1.4 将关键字转为整数
我们将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后面代码实现中再进行细节展示。下⾯哈希函数部分我们讨论时，如果关键字不是整数，那么我们讨论的Key是关键字转换成的整数。
2. 哈希函数
⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计。
2.1 除法散列法/除留余数法
① 除法散列法也叫做除留余数法，顾名思义，假设哈希表的大小为M，那么通过key除以 M 的余数作为映射位置的下标，因此哈希函数：h(key) = h(key%M)。
② 当使用除法散列法时，要尽量避免M为某些值，如 2的幂，10 的幂等。如果是 2^X，那么 key%2^X 本质上相当于保留了 key 的后 X 位，那么只要遇到后 X 位相同的 key，最后计算出的结果都是一样的，比如：M ＝ 8，key1 = 1234，key2 = 234；key1%M = 1234%8 = 2，key2%M = 234%8 = 2，这样就会导致两个数存储在同一个位置，造成冲突。
③ 当使用除法散列法时，建议 M 取不太接近2的整数次幂的一个质数(素数)。
④ 需要说明的是，实践中也是八仙过海，各显神通，Java的HashMap采用除法散列法时就是2的整数次冥做哈希表的大小M，这样玩的话，就不用取模，而可以直接位运算，相对而言位运算比模更高效⼀些。但是他不是单纯的去取模，比如M是2^16次方，本质是取后16位，那么用key’ =
key>>16，然后把key和key' 异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围
内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀一些即可。所以我们上面建
议M取不太接近2的整数次冥的一个质数的理论是大多数数据结构书籍中写的理论吗，但是实践中，灵活运用，抓住本质，而不能死读书。
2.2 乘法散列法
① 乘法散列法对哈希表大小M没有要求，他的⼤思路第一步：用关键字 K 乘上常数 A (0<A<1)，并抽取出 k*A 的小数部分。第二步：后再用M乘以k*A 的小数部分，再向下取整。
② h(key) = floor(M×((A×key)%1.0))，其中floor表示对表达式向下取整，A∈(0,1)，这里比较重要的是 A 的取值。Kunth认为 A ＝ (√5 - 1)/2 = 0.6180339887....(黄金分割点)比较好。
2.3 全域散列法
① 如果存在⼀个恶意的对手，他针对我们提供的散列函数，特意构造出⼀个发生严重冲突的数据集，比如，让所有关键字全部落入同一个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。
② Hab(key) = ((a×key+b)%P)%M，P需要选一个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了一个P*(P-1)组全域散列函数组。
③ 需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，查找又是一个散列函数，就会导致找不到插入的 key 了。
3. 处理哈希冲突
实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了冲突，那么插入数据时，如何解决冲突呢？主要有两种两种方法，开放定址法和链地址法。
3.1 开放定址法
在开放定址法中所有的元素都放到哈希表里，当一个关键字key用哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于的。这里的规则有三种：线性探测、二次探测、双重探测。
线性探测
① 从发生冲突的位置开始，依次线性向后探测，知道寻找到下一个没有存储数据的位置为止，如果走到哈希表末尾，则绕回头部位置。
② h(key) = key%M，hash(key) 位置冲突了则线性探测公式为：(key%M)+i ，i = (1,2,3,.....,M-1)，因为负载因子＜1，因此最多寻找 M - 1次一定能找到一个存储 key 的位置。
③ 下面演示 {19,30,5,36,13,20,21,12}这一组值映射到M = 11的数组中：
这一组数据有许多的冲突，根据线性探测，遇到冲突时从冲突位置开始向后查找空位置(遇到末尾回到头部)，查找到空位置直接存入。
二次探测
① 从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。
② h(key) = key%M，hash(key) 位置冲突了则二次探测公式为：(key%M)±i^2，i = {1,2,3,...,M/2}。
③ 二次探测当下标＜ 0时，需要将下标+=M。
④ 下面演示 {19,30,52,63,11,22} 这一组数映射到 M = 11的哈希表中：
双重散列
① 第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟 key 相关的偏移量值，不断往后探测，知道寻找到下一个没有存储数据的位置为止。
② h(key) = key%M，如果 h(key) 位置冲突了，则双重探测公式为：((key%M)+i*h1(key)%M)，i = {1,2,3,.....,M}。
③ 要求 h1(key) ＜ M并且 h1(key) 和 M 互为质数。
④ 下面演示 {19,30,52} 这一组数映射到 M = 11 的哈希表中：
3.2 开放定址法代码实现
#pragma once
#include <iostream>
#include <vector>
using namespace std;
namespace gjk
{
enum State
{
EXIST,
EMPTY,
DELETE
};
template <class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//实例化出string
//template <class string>
//struct HashFunc
//{
// size_t operator()(const string& key)
// {
// size_t sum = 0;
// for (auto e : key)
// {
// sum *= 31;
// sum += e;
// }
// return sum;
// }
//};
template <class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};
template <class K,class V,class HashF = HashFunc<K>>
class Hash
{
public:
Hash(size_t size)
{
_arr.resize(size);
_n = 0;
}
HashData<K,V>* Find(const K& key)//查找
{
HashF hf;
size_t sub = hf(key) % _arr.size();
while (_arr[sub]._state != EMPTY)
{
if (_arr[sub]._state == EXIST && _arr[sub]._kv.first == key) return &_arr[sub];
sub++;
sub %= _arr.size();
}
return nullptr;
}
bool Insert(const pair<K,V>& kv)//插入
{
if (Find(kv.first)) return false;
if (_n * 10 / _arr.capacity() >= 7)
{
Hash<K, V,HashF> newhash(2*_arr.capacity());
for (int i = 0; i < _arr.size(); i++)
if (_arr[i]._state == EXIST) newhash.Insert(_arr[i]._kv);
_arr.swap(newhash._arr);
}
HashF hf;
size_t sub = hf(kv.first) % _arr.size();
while (_arr[sub]._state == EXIST)
{
sub++;
sub %= _arr.size();
}
_arr[sub]._kv = kv;
_arr[sub]._state = EXIST;
_n++;
return true;
}
bool Erase(const K& key)//删除
{
HashData<K, V>* ret = Find(key);
if (!ret) return false;
else
{
ret->_state = DELETE;
return true;
}
}
void Printf()
{
for (int i = 0; i < _arr.capacity(); i++)
if (_arr[i]._state == EXIST) cout << _arr[i]._kv.first << " ";
cout << endl;
}
private:
vector<HashData<K, V>> _arr;
size_t _n;//数组中存储数据的个数
};
}3.3 链地址法
解决冲突的思路
开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。
① 下面演示 {19,30,5,36,13,20,21,12,24,96} 这一组数映射到 M = 11 的表中。
扩容
开放定址法负载因子必须小于1，链地址法的负载因子就没有限制了，可以大于1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；stl中unordered_xxx的最大负载因⼦基本控制在1，大于1就扩容，我们下面实现也使用这个方式。
极端场景
如果极端场景下，某个桶特别长怎么办？其实我们可以考虑使用全域散列法，这样就不容易被针对了。但是假设不是被针对了，用了全域散列法，但是偶然情况下，某个桶很长，查找效率很低怎么办？这里在Java8的HashMap中当桶的长度超过⼀定阀值(8)时就把链表转换成红黑树。⼀般情况下，不断扩容，单个桶很长的场景还是长较少的，下面我们实现就不搞这么复杂了，这个解决极端场景的思路，了解⼀下即可。
3.4 链地址法代码实现
#pragma once
#include <iostream>
#include <vector>
using namespace std;
namespace gjk
{
enum State
{
EXIST,
EMPTY,
DELETE
};
template <class K, class V>//这里的链节点采用 next、parent结构，方便后面删除
struct HashDataNode
{
pair<K, V> _kv;
HashDataNode<K, V>* _next = nullptr;
HashDataNode<K, V>* _parent = nullptr;
State _state = EMPTY;
};
template <class K>
struct GetK
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template <>
struct GetK<string>
{
size_t operator()(const string& key)
{
size_t sum = 0;
for (auto e : key)
{
sum *= 31;
sum += e;
}
return sum;
}
};
template <class K,class V,class getk = GetK<K>>
class Hash
{
typedef HashDataNode<K, V> Node;
public:
Hash(size_t size = 10)
{
_arr.resize(size);
_n = 0;
}
bool Insert(const pair<K,V>& kv)
{
getk gk;
if (Find(kv)) return false;
if (_n * 10 / _arr.size() >= 10)
{
Hash<K, V> newhash;
newhash._arr.resize(2 * _arr.size());
for (size_t i = 0; i < _arr.size(); i++)
{
if (_arr[i]&&_arr[i]->_state == EXIST)
{
newhash._arr[i] = _arr[i];
Node* cur = _arr[i]->_next;
Node* move = newhash._arr[i];
while (cur)
{
Node* tmp = move;
move->_next = cur;
cur = cur->_next;
move = move->_next;
move->_parent = tmp;
}
}
}
_arr.swap(newhash._arr);
}
size_t sub = gk(kv.first) % _arr.size();
Node* newnode = new Node;
newnode->_kv = kv;
newnode->_state = EXIST;
if (!_arr[sub] || _arr[sub]->_state != EXIST) _arr[sub] = newnode;
else
{
Node* cur = _arr[sub];
while (cur->_next) cur = cur->_next;
cur->_next = newnode;
newnode->_parent = cur;
}
_n++;
return true;
}
Node* Find(const pair<K,V>& kv)
{
getk gk;
size_t sub = gk(kv.first) % _arr.size();
if (!_arr[sub]) return nullptr;
else
{
Node* cur = _arr[sub];
while (cur)
{
if (cur->_kv.second == kv.second) return cur;
cur = cur->_next;
}
}
return nullptr;
}
bool Erase(const pair<K,V>& kv)
{
Node* ret = Find(kv);
if (!ret) return false;
Node* prev = ret->_parent;
Node* next = ret->_next;
if (next) next->_parent = prev;
if (prev) prev->_next = next;
delete ret;
return true;
}
void Printf()
{
for (size_t i = 0; i < _arr.size(); i++)
{
if (_arr[i])
{
Node* cur = _arr[i];
while (cur)
{
cout << cur->_kv.second << "";
cur = cur->_next;
}
}
}
cout << endl;
}
private:
vector<Node*> _arr;
size_t _n;
};
}