【C++】哈希
文章目录
- 一、哈希的概念及性质
- 1、哈希概念
- 2、哈希函数
- 3、哈希冲突
- 二、闭散列
- 1、线性探测法
- 2、哈希表的基本框架
- 3、哈希表的插入删除与查找
- 4、哈希表的扩容
- 5、哈希表的仿函数
- 6、字符串哈希算法
- 7、整体代码实现
- 8、二次探测法
- 三、开散列
- 1、开散列的概念
- 2、开散列的节点结构
- 3、开散列的插入删除与查找
- 4、开散列的扩容
- 5、开散列整体代码实现
- 四、素数做除数与哈希桶结构问题
一、哈希的概念及性质
1、哈希概念
在顺序结构以及平衡树中，由于元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较；比如顺序表中需要从表头开始依次往后比对寻找，查找时间复杂度为 O(N)，平衡树中需要从第一层开始逐层往下比对寻找，查找时间复杂度为 O(logN)；即搜索的效率取决于搜索过程中元素的比较次数。
尽管平衡树的查找方式已经很快了，但我们仍然认为该方法不够极致，理想的搜索方法是 可以不经过任何比较，直接从表中得到要搜索的元素。那么该如何实现上面这种搜索方法呢？
如果构造一种存储结构，可以通过某种函数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一对一的映射关系，那么在查找时通过该函数就可以很快找到该元素；当向该结构中：
- 插入元素时：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放；
- 搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
该方法即为 哈希 (散列) 方法，哈希方法中使用的转换函数称为哈希 (散列) 函数，构造出来的结构称为哈希表 (Hash Table) (或者称散列表)。
特别注意：我们上面提到的不管是顺序搜索、平衡树搜索还是哈希搜索，其 key 值都是唯一的，也就是说，搜索树中不允许出现相同 key 值的节点，哈希表中也不允许出现相同 key 值的元素，我们下文所进行的所有操作也都是在这前提之上进行的。
2、哈希函数
哈希函数有如下设计原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有m个地址时，其值域必须在0到m-1之间；
- 哈希函数计算出来的地址要尽量能均匀分布在整个空间中；
- 哈希函数应该比较简单。
我们有如下常见的哈希函数：
1、直接定址法 (常用)
直接定址法是最简单的哈希函数，顾名思义，直接定址就是根据 key 值直接得到存储位置，最多再进行一个简单的常数之间的转换，其哈希函如下：
Hash（Key）= A*Key + B (A B 均为常数)
直接定址法的优点是简单，且不会引起哈希冲突 – 哈希冲突是指多个不同的 key 值映射到同一个存储位置，由于直接定址法的 key 值经过哈希函数转换后得到的值一定是唯一的，所以不存在哈希冲突。
直接定址法适用于数据范围集中的情况，这样 key 值映射到哈希表后，哈希表的空间利用率高，浪费的空间较少；如下：
但是直接定址法不适用于数据范围分散的情况，因为这样会导致哈希表的空间利用率很低，会浪费很多空间，比如：
int arr[] = { 123, 126, 125, 138, 122331, 1};
下面这道题是哈希直接定址法的典型例子：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）
class Solution {
public:
int firstUniqChar(string s) {
//相对映射 -- 65~122 -> 57
int arr[58] = { 0 };
int i = 0;
for(i=0; i<s.size(); i++)
{
arr[s[i] - 65]++;
}
for(i=0; i<s.size(); i++)
{
if(arr[s[i] - 65] == 1)
return i;
}
return -1;
}
};
2、除留余数法 (常用)
为了应对数据范围分散的情况，有人设计出了除留余数法 – 设哈希表中允许的地址数为m，取一个不大于m，但最接近或者等于m的素数p作为除数，按照 哈希函数 Hash(key) = key % p (p<=m), 将关键码转换成哈希地址；
简单来说就是用 key 值除以哈希表的大小得到的余数作为哈希映射的地址，将 key 保存到该地址中；除留余数的优点是可以处理数据范围分散的数据，缺点是会引发哈希冲突；例如对于数据集合 {1，7，6，4，5，9}，它的哈希表如下：
此时如果我们再插入元素 44，通过哈希函数我们计算出 44 应该存储在下标为 4 的位置，但是 4 下标位置之前已经被元素 4 占用了，此时就会发生哈希冲突。
3、哈希冲突
如果对于两个数据元素的关键字 k i k_i ki 和 k j k_j kj (i != j)，有 k i k_i ki != k j k_j kj，但有 Hash( k i k_i ki) == Hash( k j k_j kj)，即不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
哈希冲突有两种常见的解决办法：
- 闭散列 (开放定址法)：当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去；
- 开散列 (链地址法)：首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码 (哈希冲突) 归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中；也就是说，当发生哈希冲突时，把 key 直接链接在该位置的下面。
下面我们来具体探讨这两种解决哈希冲突的方法。
二、闭散列
闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去；那如何寻找下一个空位置呢？有两种方法 – 线性探测法和二次探测法。
1、线性探测法
线性探测法是指从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止；比如上面我们插入 44 时由于 4 下标的位置已经被占用，则我们可以向后寻找第一个空位置即下标为 8 的位置进行插入：
下面我们来模拟实现哈希函数的除留余数法，并使用闭散列的线性探测法来解决哈希冲突。
2、哈希表的基本框架
哈希表节点结构的定义如下：
//标识每个存储位置的状态--空、存在与删除
enum State {
EMPTY,
EXIST,
DELETE
};
//哈希表每个下标位置存储的数据的结构
template<class K, class V>
struct HashData {
pair<K, V> _kv;
State _state = EMPTY; //默认为空
};
template<class K, class V>
class HashTable {
typedef HashData<K, V> Data;
private:
vector<Data> _tables;
size_t _n; //记录表中有效数据的个数
};
如上，为了方便，在哈希表中我们使用了 vector 来存储数据，并增加了一个变量 n 来记录表中有效数据的个数；同时，哈希表的每个下标位置存储的数据都是一个 KV 模型的键值对，这些都很好理解，但奇怪的是，我们在哈希表的每个位置的数据中还增加了一个 state 变量来记录该位置的状态，这是为什么呢？
我们以一个例子来进行说明，假设我们现在要将 arr 映射到哈希表中，设哈希表的大小为 10，则哈希函数为：
int arr[] = { 18, 8, 7, 27, 57, 3, 38};
hash(key) = key % HashTable.size() //10
映射完毕后的哈希表如下：
注意：当key映射的下标位置被占用时，key会向后寻找下一个空位置进行插入，但如果key走到数组尾都还没找到空位置，那么key就会从数组起始位置重新往后寻找。比如插入27时由于7、8、9位置都被占用，所以它只能从数组起始位置重新寻找空位置插入。
到目前为止，大家肯定认为插入的逻辑就是利用哈希函数算出余数，然后找到余数对应下标，观察该下标是否被占用，没有就插入，有就向后寻找；那么如果我现在将27删除掉之后再插入17呢？这里会存在两个问题：
- 27如何删除，即我们应该将27原来位置的数据置为几？貌似这里置为几都不合适，因为你要删除的数据可能和你用于标识删除状态的数字恰好相同 (比如删除后将对应位置的数据置为0/-1，但是key也有可能等于0/-1，此时是删了还是没删呢？)；
- 删除后我们再插入17，此时17按道理来说应该插入到27原来的位置，因为此时27已经被删除，0号下标的位置就空出来了；但是17如何知道0号下标位置是空的呢？-- 我们上面说了27删除后该位置的数据被置为几都不合适；
即使我们能够找到一个数字来标定删除，这里也还有一个问题，我们查找数据时是先根据key和哈希函数算出余数，然后将余数下标位置的数据与key进行比较，相同就代表找到，不同那么数据还可能放在后面的位置，所以继续向后比较查找，如果当查找到空时还没找到，说明key不存在；
现在如果我们删除了27，则0号下标位置的数据被置为那个用来标定删除的数字，此时0号位置已经为空了，那么现在我们要查找57还能不能找到呢？答案是找不到，因为查找57时查到到空即0号下标的位置就会停止查找并返回false；可能有的同学会说，我们删除27之后将后面的元素向前挪一位就可以了，这里我们先不谈效率的问题，而是一旦挪动了数据，则原来已经插入的key与数组下标的映射关系就改变了，比如挪动数据后我们还能找到3吗？
所以，在哈希表的每个位置的数据中还增加了一个 state 变量来记录该位置的状态 (存在、删除、空) 是非常有必要的。
3、哈希表的插入删除与查找
有了 state 变量，我们就可以很方便的进行插入、删除和查找操作了：
- 插入：通过哈希函数得到余数即数组下标，如果该下标的状态为删除或为空则插入，如果为存在则向后寻找下一个状态为删除/空的位置进行插入；
- 查找：通过哈希函数得到余数即数组下标，取出小标位置的key与目标key进行比较，相等就返回该位置的地址，不相等就继续往后查找，如果查找到状态为空的下标位置就返回 nullptr；注意：这里有三个细节：
- 当遇到状态为空的下标位置才返回 nullptr，而不是遇到状态为 删除的位置就返回 nullptr，因为你要查找的数据可能在已删除位置的后面；
- 将查找函数返回值定义为 Data*，而不是 bool，这样可以方便我们进行删除和修改 (修改 key 对应的 value) – 查找到之后直接通过指针解引用来修改 value 与 state；
- 哈希表经过不断插入删除，最终可能会出现一种极端情况 – 哈希表中元素的状态全为 EXIST 和 DELETE，此时如果我们找空就会造成死循环，所以我们需要对这种情况单独进行处理；
- 删除：复用查找函数，查找到就通过查找函数的返回值将小标位置数据的状态置为 删除，找不到就返回 false。
代码实现如下：
#pragma once
#include <vector>
#include <utility>
using std::pair;
using std::vector;
//标识每个存储位置的状态--空、存在与删除
enum State {
EMPTY,
EXIST,
DELETE
};
//哈希表每个下标位置存储的数据的结构
template<class K, class V>
struct HashData {
pair<K, V> _kv;
State _state = EMPTY; //默认为空
};
//哈希表
template<class K, class V>
class HashTable {
typedef HashData<K, V> Data;
public:
HashTable()
: _n(0)
{
//将哈希表的大小默认给为10
_tables.resize(10);
}
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//除留余数法 && 线性探测法
//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置，如果该位置被占用往后放
size_t hashi = kv.first % _tables.size();
//不能放在EXIST的位置，DELETE和EMPTY都能放
while (_tables[hashi]._state == EXIST) {
++hashi;
if (hashi == _tables.size()) hashi = 0; //如果探测到末尾则从头开始重新探测
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
//将find的返回值定义为Data的地址，可以方便我们进行删除以及修改V
Data* find(const K& key) {
Hash hash; //仿函数对象
size_t hashi = hash(key) % _tables.size();
//记录hashi的起始位置，避免哈希表中元素全为EXIST和DELETE时导致死循环
size_t starti = hashi;
//最多找到空
while (_tables[hashi]._state != EMPTY) {
//key相等并且state为EXIST才表示找到
if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
return &_tables[hashi];
++hashi;
//如果找到尾还没找到，就从0重新找
if (hashi == _tables.size()) hashi = 0;
//如果找一圈还没找到，就跳出循环
if (hashi == starti) break;
}
return nullptr;
}
bool erase(const K& key) {
//找不到就不删，找到就把状态置为DELETE即可
Data* ret = find(key);
if (ret) {
ret->_state = DELETE;
return true;
}
return false;
}
private:
vector<Data> _tables;
size_t _n; //记录表中有效数据的个数
};
4、哈希表的扩容
可以发现，我们上面的实现中并没有扩容操作，那么哈希表应该如何扩容呢？哈希表的扩容和普通顺序表容器的扩容不同，它不是容器满了才扩容，而是会有一个负载因子，也叫载荷因子，当载荷因子超过一定大小时就立即扩容，书上对载荷因子的表述如下：
所以哈希表的扩容函数如下：
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//如果大于标定的载荷因子就扩容，这里我们将载荷因子标定为0.7
//扩容现代写法--复用insert接口
if ((1.0 * _n / _tables.size()) >= 0.7) {
HashTable<K, V> newHT;
newHT._tables.resize(_tables.size() * 2);
for (auto& e : _tables)
newHT.insert(e._kv);
_tables.swap(newHT._tables);
}
//除留余数法 && 线性探测法
//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置，如果该位置被占用往后放
size_t hashi = kv.first % _tables.size();
//不能放在EXIST的位置，DELETE和EMPTY都能放
while (_tables[hashi]._state == EXIST) {
++hashi;
if (hashi == _tables.size()) hashi = 0; //如果探测到末尾则从头开始重新探测
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
这里同样有两个细节：
- 由于哈希表中的有效元素个数与哈希表长度都是整数，且有效元素个数一定小于哈希表长度，所以它们的商一定为0 (整数除法)，所以我们需要在前面乘以一个小数使得它们的商为小数；
- 哈希表的扩容并不是简单的扩大空间，而是需要将已经插入哈希表的元素取出全部重新插入一遍，因为扩容后哈希表的长度改变，那么 key 通过哈希函数映射到的位置也会改变；比如17扩容前插入的位置为7，扩容后插入位置就变为17，所以需要将其取出重新插入。
现在，我们就可以对我们的哈希表进行简单的测试了，大家可以自己根据测试用例先画一画图，然后与调试结果进行比对：
5、哈希表的仿函数
我们上面实现的哈希表的 key 值只能是整数，因为我们要让 key 与哈希表长度取模得到映射位置，那么如果我们 key 是一个字符串呢？比如我们要统计水果的数量；此时我们就需要进行两层转换 – 先将字符串转换为整数，再将该整数作为 key 转换为下标；
那么我们可不可以将代码改成这样呢？即将字符串的第一个字符作为 key 来映射下标：
size_t hashi = kv.first[0] % _tables.size();
这种做法显然是不行的，因为哈希表在实现的时候并不知道用户会将 key 定义为什么类型，虽然上面这种做法可以成功映射字符串，但如果 key 是整形呢？整形能取 [] 吗？
所以这种问题还是得依靠仿函数这种专业人士来解决 – 我们可以为哈希表增加一个模板参数，该模板参数是一个仿函数，仿函数分为设计者提供的默认仿函数和用户提供的仿函数，系统默认的仿函数可以将一些常见的 key 的类型全部转化为整形，比如字符串、指针、整数；而用户提供的仿函数则可以根据用户自己的 key 类型将其转化为整形，比如 People 类 (身份证号)、Date 类 等等；如下：
//哈希表的仿函数--系统默认仿函数可以处理字符串类型、指针类型以及整形
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return key;
}
};
//类模板特化
template<>
struct HashFunc<string> {
size_t operator()(const string& key) {
return key[0];
}
};
//哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
typedef HashData<K, V> Data;
public:
HashTable()
: _n(0)
{
//将哈希表的大小默认给为10
_tables.resize(10);
}
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//如果大于标定的载荷因子就扩容，这里我们将载荷因子标定为0.7
//扩容现代写法--复用insert接口
if ((1.0 * _n / _tables.size()) >= 0.7) {
HashTable<K, V, Hash> newHT;
newHT._tables.resize(_tables.size() * 2);
for (auto& e : _tables)
newHT.insert(e._kv);
_tables.swap(newHT._tables);
}
//除留余数法 && 线性探测法
//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置，如果该位置被占用往后放
Hash hash; //仿函数对象
size_t hashi = hash(kv.first) % _tables.size(); //用仿函数对象将key转换为整形
//不能放在EXIST的位置，DELETE和EMPTY都能放
while (_tables[hashi]._state == EXIST) {
++hashi;
if (hashi == _tables.size()) hashi = 0; //如果探测到末尾则从头开始重新探测
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
//将find的返回值定义为Data的地址，可以方便我们进行删除以及修改V
Data* find(const K& key) {
Hash hash; //仿函数对象
size_t hashi = hash(key) % _tables.size(); //用仿函数对象将key转换为整形
//最多找到空
while (_tables[hashi]._state != EMPTY) {
//key相等并且state为EXIST才表示找到
if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
return &_tables[hashi];
++hashi;
//如果找到尾还没找到，就从0重新找
if (hashi == _tables.size()) hashi = 0;
}
return nullptr;
}
private:
vector<Data> _tables;
size_t _n; //记录表中有效数据的个数
};
可以看到，在有了仿函数以后，我们只需要在 key 与 TableSize 取模的地方使用仿函数对象将 key 转换为整形即可；这样，对于常见的 key 类型，哈希表可以通过内置的默认仿函数来完成下标映射，对于用户自定义的 key 类型，哈希表可以根据用户提供的仿函数来完成下标映射。
注：这里哈希表使用仿函数来将字符串转化为整形与上一节红黑树使用仿函数来实例化出符合K模型的 set 和符合KV模型的 map 的两个不同的类有异曲同工之处，可以看到，仿函数能够成为 STL 六大组件之一是当之无愧的。
6、字符串哈希算法
我们上面使用字符串第一个字符作为 key 的方法虽然可以将成功映射到下标，但是它很容易发生哈希冲突 – 只要字符串首字母相同就会发生冲突；所以我们可以考虑将字符串所有字符的 ASCII 码加起来作为 key，如下：
template<>
struct HashFunc<string> {
size_t operator()(const string& key) {
size_t sum = 0;
for (auto ch : key)
sum += ch;
return sum;
}
};
但是它还是不够好，因为只要字符串的 ASCII 码相同还是会发生冲突，比如 “abc” 与 “acb” “bac” “bca” “aad” …：
所有就有人专门去研究字符串哈希算法，即如何将字符转换为整形可以使得哈希冲突率变低，下面是一位大佬介绍字符串哈希算法的博客，里面包含了多种优秀的字符串哈希算法，大佬在文中对各种算法进行了测试打分，大家可以看看：各种字符串Hash函数 - clq - 博客园 (cnblogs.com)
其中 BKDR 哈希字符串算法是最出名也是平均得分最高的，所以这里我们采用它，其思路很简单，在每次与字符的 ASCII 相加之前除以一个数即可，这个数一般为 131/31，如下：
template<>
struct HashFunc<string> {
size_t operator()(const string& key) {
//BKDR字符串哈希算法
size_t sum = 0;
for (auto ch : key)
sum = sum * 131 + ch;
return sum;
}
};
7、整体代码实现
到这里，哈希函数的除留余数法 (使用闭散列的线性探测法来解决哈希冲突) 的模拟实现就基本完成了，其中哈希表的拷贝构造、析构、赋值重载我们使用编译器默认生成的即可 – 对于自定义类型编译器会调用自定义类型的拷贝构造、析构、赋值重载，由于 tables 是 vector 类型的变量，而 vector 中实现了深拷贝与析构，所以我们不用再自己实现。
同时，由于线性探测法发生哈希冲突的概率较高，导致数据插入与搜索的效率较低，所以我们的学习重点不在这里，所以我们也就不再去它的实现迭代器了，这些内容我们会在下文的开散列中去实现。
HashTable.h：
#pragma once
#include <vector>
#include <utility>
#include <string.>
using std::pair;
using std::vector;
using std::string;
//标识每个存储位置的状态--空、存在与删除
enum State {
EMPTY,
EXIST,
DELETE
};
//哈希表每个下标位置存储的数据的结构
template<class K, class V>
struct HashData {
pair<K, V> _kv;
State _state = EMPTY; //默认为空
};
//哈希表的仿函数
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return key;
}
};
//类模板特化
template<>
struct HashFunc<string> {
size_t operator()(const string& key) {
//BKDR字符串哈希算法
size_t sum = 0;
for (auto ch : key)
sum = sum * 131 + ch;
return sum;
}
};
//哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
typedef HashData<K, V> Data;
public:
HashTable()
: _n(0)
{
//将哈希表的大小默认给为10
_tables.resize(10);
}
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//如果大于标定的载荷因子就扩容，这里我们将载荷因子标定为0.7
//扩容现代写法--复用insert接口
if ((1.0 * _n / _tables.size()) >= 0.7) {
HashTable<K, V, Hash> newHT;
newHT._tables.resize(_tables.size() * 2);
for (auto& e : _tables)
newHT.insert(e._kv);
_tables.swap(newHT._tables);
}
//除留余数法 && 线性探测法
//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置，如果该位置被占用往后放
Hash hash; //仿函数对象
size_t hashi = hash(kv.first) % _tables.size();
//不能放在EXIST的位置，DELETE和EMPTY都能放
while (_tables[hashi]._state == EXIST) {
++hashi;
if (hashi == _tables.size()) hashi = 0; //如果探测到末尾则从头开始重新探测
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
//将find的返回值定义为Data的地址，可以方便我们进行删除以及修改V
Data* find(const K& key) {
Hash hash; //仿函数对象
size_t hashi = hash(key) % _tables.size();
//最多找到空
while (_tables[hashi]._state != EMPTY) {
//key相等并且state为EXIST才表示找到
if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
return &_tables[hashi];
++hashi;
//如果找到尾还没找到，就从0重新找
if (hashi == _tables.size()) hashi = 0;
}
return nullptr;
}
bool erase(const K& key) {
//找不到就不删，找到就把状态置为DELETE即可
Data* ret = find(key);
if (ret) {
ret->_state = DELETE;
return true;
}
return false;
}
private:
vector<Data> _tables;
size_t _n; //记录表中有效数据的个数
};
test.cpp：
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include "HashTable.h"
using namespace std;
void HashTable_test1() {
int arr[] = { 18, 8, 7, 27, 57, 3, 38 };
HashTable<int, int> ht;
for (auto e : arr)
ht.insert(make_pair(e, e));
//此时再插入元素会发生扩容
ht.insert(make_pair(26, 26));
ht.insert(make_pair(18, 18));
ht.insert(make_pair(6, 6));
cout << ht.find(7) << endl;
cout << ht.find(8) << endl;
cout << ht.erase(7) << endl;
cout << ht.find(7) << endl;
cout << ht.find(8) << endl;
}
void HashTable_test2() {
string arr[] = { "苹果", "西瓜", "芒果", "西瓜", "苹果", "梨子", "西瓜","苹果", "香蕉", "西瓜", "香蕉" };
HashTable<string, int> countHT;
for (auto& str : arr) {
auto ret = countHT.find(str);
if (ret)
ret->_kv.second++;
else
countHT.insert(make_pair(str, 1));
}
}
void HashTable_test3() {
string arr[] = { "abc", "acb", "bac", "bca", "aad" };
HashFunc<string> hash;
for (auto& str : arr) {
cout << hash(str) << endl;
}
}
int main() {
//HashTable_test1();
//HashTable_test2();
HashTable_test3();
return 0;
}
8、二次探测法
线性探测优点是实现非常简单，缺点是一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。(我的空间被别人占了，我就去占别人的，别人的空间被占了再去占别人的，形成恶性循环，影响效率)
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： H i H_i Hi = ( H 0 H_0 H0 + i 2 i^2 i2 ) % m, 或者： H i H_i Hi = ( H 0 H_0 H0 - i 2 i^2 i2 ) % m。其中：i =1,2,3…， H 0 H_0 H0是通过散列函数Hash(x) 对元素的关键码 key 进行计算得到的位置，m是表的大小。即根据余数找到下标位置，如果该位置被占用，不是去紧挨着的下一个位置找，而是去 余数 + i 2 i^2 i2 的位置找插入位置，其中 i 是寻找的次数。
研究表明：当表的长度为质数且表载荷因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。最后，虽然二测探测法在一定程度上减轻了哈希冲突的概率，但它并没有从本质上解决问题，所以我们不再去模拟实现它，如果对它有兴趣的同学，可以自己尝试着实现一下，将我们上面的插入和查找函数的逻辑改一下即可。
三、开散列
1、开散列的概念
开散列法又叫 链地址法 (开链法)，首先对关键码集合用散列函数计算散列地址，即 key 映射的下标位置，具有相同地址的关键码 (哈希冲突) 归于同一子集合，每一个子集合称为一个桶 (哈希桶)，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中；也就是说，当发生哈希冲突时，把 key 作为一个节点直接链接到下标位置的哈希桶中。
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素；由于开散列的不同冲突之间不会互相影响 – 同一冲突都链接在自己下标位置的哈希桶中，并不会去占用别人的下标位置；所以不管是在插入还是查找方面，开散列都比闭散列要高效，所以 C++ STL 中的unordered_map 和 unordered_set 容器以及 Java 中的 HashMap 和 HashSet 容器其底层哈希表都是使用开散列来实现的，只是某些细节方面有些不同；所以开散列也是我们学习哈希表的重点。
2、开散列的节点结构
由于开散列的不同冲突之间不会互相影响，所以开散列不再需要 state 变量来记录每个下表位置的状态；同时，因为开散列每个下标位置链接的都是一个哈希桶，所以 vector 中的每个元素都是一个节点的指针，指向单链表的第一个元素，所以 _tables 是一个指针数组；最后，为了是不同类型的 key 都能够计算出映射的下标位置，所以我们这里也需要传递仿函数；如下；
//开散列
namespace BucketHash {
//哈希表的节点结构--单链表
template<class K, class V>
struct HashNode {
pair<K, V> _kv;
HashNode<K, V>* next;
HashNode(const pair<K, V>& kv)
: _kv(kv)
, next(nullptr)
{}
};
//哈希表的仿函数
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return key;
}
};
//类模板特化
template<>
struct HashFunc<string> {
size_t operator()(const string& key) {
//BKDR字符串哈希算法
size_t sum = 0;
for (auto ch : key)
sum = sum * 131 + ch;
return sum;
}
};
//哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
typedef HashNode<K, V> Node;
private:
vector<Node*> _tables; //指针数组
size_t _n; //表中有效数据的个数
};
}
3、开散列的插入删除与查找
开散列的插入
开散列插入的前部分和闭散列一样，根据 key 与哈希表大小得到映射的下标位置，与闭散列不同的是，由于哈希表中每个下标位置都是一个哈希桶，即一个单链表，那么对于发现哈希冲突的元素我们只需要将其链接到哈希桶中即可，这里一共有两种链接方式：
- 将发生冲突的元素链接到单链表的末尾，即尾插；
- 将发生冲突的元素链接到单链表的开头，即头插。
这里显然是选择将冲突元素进行头插，因为尾插还需要找尾，会导致效率降低；插入部分代码如下：
//插入
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//调用仿函数的匿名对象来将key转换为整数
size_t hashi = Hash()(kv.first) % _tables.size();
//哈希桶头插
Node* newNode = new Node(kv);
newNode->next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
开散列的查找
开散列的查找也很简单，根据余数找到下标，由于下标位置存储的是链表首元素地址，所以我们只需要取出首元素地址，然后顺序遍历单链表即可：
//查找
Node* find(const K& key) {
size_t hashi = Hash()(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key)
return cur;
cur = cur->next;
}
return nullptr;
}
开散列的删除
和闭散列不同的是，开散列的删除不能直接通过查找函数的返回值来进行删除，因为单链表在删除节点时还需要改变父节点的指向，让其指向目标节点的下一个节点，所以我们需要通过遍历单链表来进行删除：
//删除
bool erase(const K& key) {
//由于单链表中删除节点需要改变上一个节点的指向，所以这里不能find后直接erase
size_t hashi = Hash()(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
//删除还要分是否为头结点
if (cur->_kv.first == key) {
if (cur == _tables[hashi])
_tables[hashi] = cur->next;
else
prev->next = cur->next;
delete cur;
--_n;
return true;
}
//迭代
prev = cur;
cur = cur->next;
}
return false;
}
4、开散列的扩容
由于开散列桶的个数是一定的，即哈希表的长度，所以随着元素的不断插入，每个桶中元素的个数会不断增多；那么在极端情况下，可能会导致一个桶中链表的节点非常多，这样会影响哈希表的性能 – 查找与删除效率变低，因此在一定条件下需要对哈希表进行增容；
那么增容条件该怎么确认呢？开散列最好的情况是每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突；因此，在元素个数刚好等于桶的个数时，可以给考虑哈希表增容，即载荷因子为1时。
代码实现如下：
//析构--手动释放哈希表中的每个元素，以及每个元素指向的哈希桶
~HashTable() {
//释放每个元素的哈希桶
for (size_t i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->next;
delete cur;
cur = next;
}
}
//释放哈希表
_tables.clear();
}
//插入
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//扩容--当载荷因子达到1时我们进行扩容
if (_n == _tables.size()) {
//法一：采用闭散列的扩容方法--复用insert接口
//优点：实现简单；
//缺点：先开辟节点再释放节点代价大
//HashTable<K, V, Hash> newHT;
//newHT._tables.resize(_tables.size() * 2, nullptr);
//for (size_t i = 0; i < _tables.size(); ++i) {
// Node* cur = _tables[i];
// while (cur) {
// newHT.insert(cur->_kv);
// cur = cur->next;
// }
//}
//_tables.swap(newHT._tables);
//法二：取原表中的节点链接到当前表中
//缺点：实现比较复杂
//优点：不用再去开辟新节点，也不用释放旧节点，消耗小
vector<Node*> newTables;
newTables.resize(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->next;
//重新计算映射关系--调用仿函数的匿名对象来将key转换为整数
size_t hashi = Hash()(cur->_kv.first) % newTables.size();
cur->next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
}
_tables.swap(newTables);
newTables.clear(); //不写也可以，局部的vector变量出作用域自动调用析构
}
//调用仿函数的匿名对象来将key转换为整数
size_t hashi = Hash()(kv.first) % _tables.size();
//哈希桶头插
Node* newNode = new Node(kv);
newNode->next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
可以看到，这里我们给出了两种扩容的办法，一种是闭散列的方法 – 通过复用 insert 函数接口来进行扩容，但是这种扩容方法的效率很低，因为我们将旧表节点插入到新表时需要重新开辟节点，在插入并交换完毕后，我们又需要释放掉旧表中的节点，而 new 和 delete 的代价是很大的，特别是当 KV 是自定义类型时；
所以这里我们选择第二组方法进行扩容 – 取出旧表中的每个节点链接到新表中，然后再交换旧表与新表；这样做就减少了 new 和 delete 的过程，大大提高了扩容的效率。(注：这里不能将原表中的整个哈希桶链接到新表中，因为新表的大小改变后原表中的元素可能会映射到新表的其他位置)
同时，开散列的析构函数是需要我们自己实现的，因为默认生成的析构函数并不会释放掉哈希桶。
5、开散列整体代码实现
//开散列
namespace BucketHash {
//哈希表的节点结构--单链表
template<class K, class V>
struct HashNode {
pair<K, V> _kv;
HashNode<K, V>* next;
HashNode(const pair<K, V>& kv)
: _kv(kv)
, next(nullptr)
{}
};
//哈希表的仿函数
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return key;
}
};
//类模板特化
template<>
struct HashFunc<string> {
size_t operator()(const string& key) {
//BKDR字符串哈希算法
size_t sum = 0;
for (auto ch : key)
sum = sum * 131 + ch;
return sum;
}
};
//哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
typedef HashNode<K, V> Node;
public:
//构造
HashTable()
: _n(0)
{
_tables.resize(10, nullptr);
}
//析构--手动释放哈希表中的每个元素，以及每个元素指向的哈希桶
~HashTable() {
//释放每个元素的哈希桶
for (size_t i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->next;
delete cur;
cur = next;
}
}
//释放哈希表
_tables.clear();
}
//插入
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//扩容--当载荷因子达到1时我们进行扩容
if (_n == _tables.size()) {
//法一：采用闭散列的扩容方法--复用insert接口
//优点：实现简单；
//缺点：先开辟节点再释放节点代价大
//HashTable<K, V, Hash> newHT;
//newHT._tables.resize(_tables.size() * 2, nullptr);
//for (size_t i = 0; i < _tables.size(); ++i) {
// Node* cur = _tables[i];
// while (cur) {
// newHT.insert(cur->_kv);
// cur = cur->next;
// }
//}
//_tables.swap(newHT._tables);
//法二：取原表中的节点链接到当前表中
//缺点：实现比较复杂
//优点：不用再去开辟新节点，也不用释放旧节点，消耗小
vector<Node*> newTables;
newTables.resize(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->next;
//重新计算映射关系--调用仿函数的匿名对象来将key转换为整数
size_t hashi = Hash()(cur->_kv.first) % newTables.size();
cur->next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
}
_tables.swap(newTables);
newTables.clear(); //不写也可以，局部的vector变量出作用域自动调用析构
}
//调用仿函数的匿名对象来将key转换为整数
size_t hashi = Hash()(kv.first) % _tables.size();
//哈希桶头插
Node* newNode = new Node(kv);
newNode->next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
//查找
Node* find(const K& key) {
size_t hashi = Hash()(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key)
return cur;
cur = cur->next;
}
return nullptr;
}
//删除
bool erase(const K& key) {
//由于单链表中删除节点需要改变上一个节点的指向，所以这里不能find后直接erase
size_t hashi = Hash()(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
//删除还要分是否为头结点
if (cur->_kv.first == key) {
if (cur == _tables[hashi])
_tables[hashi] = cur->next;
else
prev->next = cur->next;
delete cur;
--_n;
return true;
}
//迭代
prev = cur;
cur = cur->next;
}
return false;
}
private:
vector<Node*> _tables; //指针数组
size_t _n; //表中有效数据的个数
};
}
四、素数做除数与哈希桶结构问题
我们上面在介绍除留余数法时给出的定义是这样的：设哈希表中允许的地址数为m，取一个不大于m，但最接近或者等于m的素数p作为除数，按照 哈希函数 Hash(key) = key % p (p<=m), 将关键码转换成哈希地址；
那么这里为什么要选择素数 (质数) 作为除数而不是单纯使用哈希表的大小作为除数呢？这是因为使用素数可以减少哈希冲突的概率：
- 当使用素数作为除数时，能够更加均匀地散列 key 值，减少了哈希冲突的发生，而如果使用合数（即非素数）作为除数，那么就会有更多的键被映射到相同的索引上，从而增加哈希冲突的概率 – 合数有多个因子，取模后产生的余数可能比较集中，所以不能很好地散列 key 值。
因此，哈希表的除数通常是严格的素数或者质数，比如 C++ STL 中的 unordered_map 和 unordered_set，其底层哈希表都是使用素数作为除数；
但并不是所有的哈希表实现都使用严格的素数或者质数作为除数，在某些情况下，不使用严格的素数或质数作为除数也可以实现较好的效果；比如 Java 中的 HashMap 就使用一个大小为 2 的幂次方，例如16、32等非素数作为除数。
哈希表要实现使用素数作为除数也很简单，因为哈希表每次扩容都在二倍左右，所以我们只需要写出每个与2倍接近的一个素数，然后将它们放在一个数组中，哈希表每次扩容时都从该数组中确定扩容后的大小即可；
STL 源码中的实现如下：
// 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
};
inline unsigned long __stl_next_prime(unsigned long n)
{
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;
}
这里还存在一个问题，在我们上面的实现中，哈希桶是一个单链表，并且当哈希表的载荷因子等于1时，我们就进行扩容，这样在大多数情况下，每个哈希桶中的节点数都在1~2个，最坏情况下应该也不会超过 3~5 节点；这样我们查找时每次经过常数次查找就能够找到，即查找效率为 O(1)；
但是在某些极端情况下，或者面对某些碰撞攻击时 (对方如果知道了你哈希表的长度即除数，可能会专门向你传递属于同一冲突的数据，比如全部为哈希表长度的倍数)，那么就会导致单链表过长，从而降低哈希表的查询与删除效率；
为了应对这种情况，在 Java 8 中，如果一个桶中元素的数量超过了阈值，就会将其转换为红黑树，红黑树可以保证查找、插入和删除操作的时间复杂度都是 O(log n)，比链表快得多，而对于较小的桶，仍然使用链表来存储元素；即 Java 8 中的 HashMap 使用红黑树来优化哈希冲突的极端情况，从而提高了 HashMap 的性能和效率。
同样，C++11 也引入了一个新的数据结构 – 开放定址哈希表 (open addressing hash table)，用于存储哈希冲突时的元素；开放定址哈希表是一种不使用链表来解决冲突的哈希表实现方式。在这种实现方式中，如果一个槽（slot）已经被占据了，就会尝试找到下一个可用的槽，直到找到一个空槽。因此，开放定址哈希表可以更好地利用缓存，从而提高查找性能。
也就是说，在 C++11 及以后的版本中，unordered_map 的哈希桶使用了两种不同的数据结构，包括单链表和开放定址哈希表 – 当桶中元素数量较少时，使用链表；当桶中元素数量超过一定阈值时，会自动转换为开放定址哈希表。