目录
1. 哈希的概念 (是什么)
2. 实现哈希的两种方式 (哈希函数)
2.1. 直接定址法
2.2. 除留余数法
2.2.1. 哈希冲突
3. 补充知识
3.1. 负载因子
3.2. 线性探测和二次探测
4. 闭散列实现哈希表 (开放定址法)
4.1. 开放定址法的实现框架
4.2. Xq::hash_table::insert 的实现
4.3. Xq::hash_table::find 的实现
4.4. Xq::hash_table::erase 的实现
4.5. 开放定址法实现哈希表的完整代码
5. 开散列实现哈希表 (拉链法)
5.1. 拉链法的实现框架
5.2. 哈希表扩容问题 (表的大小的设计问题)
5.3. Xq::hash_table::insert 的实现
5.4. Xq::hash_table::find 的实现
5.5. Xq::hash_table::erase 的实现
5.6. 拉链法的完整实现 (初始版本)
5.7. 解决取模操作的限制
5.8. 拉链法的完整实现 (更新版本)
1. 哈希的概念 (是什么)
哈希也叫做散列，本质是一种映射关系，key 和存储位置建立映射（关联）关系，哈希or散列是一种思想(映射)。
2. 实现哈希的两种方式 (哈希函数)
哈希函数（Hash Function）是一种将任意长度的输入数据（也称为消息、键或原始数据）转换为固定长度的输出（哈希值或摘要）的算法。
常见的哈希函数有两种：
- 直接定址法；
- 除留余数法。
2.1. 直接定址法
直接定址法（Direct Addressing）也被称为确定性哈希函数（Deterministic Hash Function）。
具体来说，直接定址法会将键直接映射到索引值上，不需要进行任何复杂的计算或处理。
比如下面这个例子：
我们要将 a 数组中的元素全部映射到这张表中， 比如，你是2，我就映射到下标为2的空间中；如果你是0，我就映射到下标为0的地址空间中。
可以看到， 直接定址法的基本思想就是，将键的某个属性或组合 (比如这里键自身的值) 作为索引来直接访问哈希表的特定位置。这样一来，每个键都会与唯一的索引位置相对应，即映射关系是唯一的。
直接定址法的优点：
- 插入和查找操作的时间复杂度为 O(1)；
- 不存在哈希冲突 (因为映射关系是唯一的)。
但是直接定址法在某些场景下会暴露它的缺点，比如，如下场景：
可以看到，我要映射的数据不过寥寥几个，但由于数据波动范围非常大，同时，直接定址法要求映射关系唯一，换言之，此时映射的这张表的空间就需要非常大，但由于数据非常少，导致空间利用率极低。
因此，我们对直接定址法的总结：
- 直接定址法，简单高效，查找和插入的时间复杂度为 O(1)；
- 因为直接定址法要求映射关系唯一，故不存在哈希冲突；
- 也正因为直接定址法要求映射关系唯一，对于波动范围比较大的数据，可能会导致空间消耗过大，且空间利用率低；
因此直接定址法的应用场景是非常局限的：只适用于关键字的波动范围比较小的场景，对于波动范围比较大的场景，直接定址法不适用，因此人们提出了除留余数法。
2.2. 除留余数法
除留余数法（Division Method）是一种常见的哈希函数处理方法，用于将输入键映射到哈希表中的索引位置。
除留余数法的基本思想是，将输入键模 (%) 一个特定的数（通常是哈希表的大小），得到余数作为最终的哈希值或索引位置。
具体来说，除留余数法的步骤如下：
- 1. 选择一个用于取模的常数，通常为一个较大的素数，例如哈希表的大小；
- 2. 对于给定的键，使用取模 (%) 运算将其除以选择的常数；
- 3. 得到的余数作为最终的哈希值或索引位置。
例如，下面这种情况，现在有一个数组 {23, 45, 11, 57, 36}，同时，哈希表的大小为10。
按照除留余数法的步骤：
- 选择一个用于取模的常数，在这里就是 10；
- Hash(key) = key % 10；
- Hash(Key) 作为最终的哈希值。
具体如下：
我们发现，上面的数据都可以对应到一个独特的位置，因此查找的时候，我们可以根据同样的方式查找这个数是不是存在。
但是，如果我现在还要继续插入25这个元素，会发生什么问题呢？
我们发现，Hash(25) % 10 = 5，可是 5 这个位置已经被占用了啊，那该怎么办呢？
首先，我们将这种情况称之为哈希冲突/哈希碰撞，即不同的关键字映射到了哈希表的同一个位置。
2.2.1. 哈希冲突
哈希冲突（Hash Collision）或者称之为哈希碰撞，它是指不同的键（Key）被哈希函数映射到相同的哈希值（Hash Value）或哈希表（Hash Table）的同一个位置的情况。
在哈希结构中，哈希函数将键映射到固定长度的哈希值或索引位置。由于哈希函数的输出空间通常要比键的输入空间小得多，因此不同的键可能会产生相同的哈希值。
解决哈希冲突的常见方法包括：
- 1. 开放寻址法（Open Addressing）：开放寻址法也称之为闭散列 ，在哈希表的冲突位置寻找下一个可用的空槽来存储键值对。常见的开放寻址方法包括线性探测、二次探索等；
- 2. 拉链法(哈希桶)：拉链法也称之为开散列，在哈希表的每个索引位置上维护一个单链表，将具有相同哈希值的键值对存储在链表中。在插入、查找或删除时，根据哈希值找到对应的链表，然后在链表中进行操作；
- 3. 增加哈希函数的复杂度：通过改变哈希函数的设计，可以尽量减少哈希冲突的发生。例如，使用更复杂的哈希函数算法、增加哈希表的大小等。
接下来，我们就要以除留余数法为基本思想实现哈希表 (直接定址法实现哈希表价值不大)，由于除留余数法的映射关系并不唯一，因此会有哈希冲突，而我们为了解决哈希冲突，选择两个方案解决，分别是：
- 闭散列，即开放定址法；
- 开散列，即拉链法。
3. 补充知识
3.1. 负载因子
负载因子（load factor）是指哈希表中已经存储的有效元素数量与哈希表总大小之间的比率。它可以用来衡量哈希表的装填程度或密度。
一般情况下，负载因子的计算公式：
- 负载因子 = 已存储的有效元素个数 / 哈希表大小；
在哈希表中，负载因子的数值范围通常为 0 到 1 之间：
- 负载因子越接近 1，表示哈希表中存储的有效元素越多，装填程度越高，哈希冲突的概率也就越高，空间利用率高；
- 负载因子越接近 0，表示哈希表中存储的有效元素较少，装填程度较低，哈希冲突的概率也就越低，空间利用率低。
从这里应该可以看出，负载因子不可太大，也不可太小，而应该适中。
一般来说，负载因子会有一个阈值（例如 0.7 或 0.8）时，我们通常会考虑对哈希表进行扩容操作，以保持合理的负载因子。
总而言之，较低的负载因子可以提供较好的性能，但会占用更多的内存空间；较高的负载因子则可以节省内存空间，但可能会带来更多的哈希冲突和性能下降。
3.2. 线性探测和二次探测
线性探测（Linear Probing）是一种常见的解决哈希冲突的方法，用于处理哈希表中的元素冲突问题。
当发生哈希冲突时，线性探测会尝试在哈希表中找到下一个可用的位置来存储冲突的元素。具体的操作是，如果哈希表中的某个槽位已经被占用，则线性探测会依次检查下一个槽位，直到找到一个空闲的槽位，然后将元素存储在该位置。
当需要查找或删除特定元素时，也需要使用线性探测来定位目标元素所在的位置。如果目标元素不在哈希表的初始位置上，线性探测会按照相同的方式，依次检查下一个槽位，直到找到目标元素或遇到空槽位。
线性探测的优点是实现简单，不需要维护额外的数据结构。然而，线性探测也有一些限制。当装填因子较高时，线性探测容易引发聚集现象，即一些相邻聚集位置连续冲突，可能形成 "踩踏" ，导致哈希表的性能下降。此外，线性探测也可能导致元素的聚集在表的一侧，造成不均匀的分布。
为了克服线性探测的缺点，还有其他的解决冲突方法，如二次探测等，二次探测，缓解线性探测的 "踩踏" ，在实际运用中，可以根据具体的场景和需求选择适合的解决方案。
- 线性探测：pos++；
- 二次探测：pos + i ^ 2；
4. 闭散列实现哈希表 (开放定址法)
4.1. 开放定址法的实现框架
在实现闭散列之前，我们需要讨论一个问题：
如何判定一个位置是否有值呢？ 当某个位置存在值的同时，如何判定这个值是否有效呢？
因为，除留余数法的映射关系并不唯一，存在哈希冲突，而闭散列解决哈希冲突，是通过线性探测或者二次探测，而探测是需要找一个空位置，此时就需要判定，某个位置是否有值， 且这个值是否有效。
事实上，对于一个位置无非就三种情况：
- 存在有效值；
- 存在无效值 (该位置的值已被删除)；
- 不存在值 (该位置没有被赋值过)；
我们的解决方案是，通过枚举解决，如下：
enum state
{
EXIST, // (存在有效值)
EMPTY, // 存在无效值 (该位置的值已被删除)
DELETE // 不存在值 (该位置没有被赋值过)；
};正因为要区分位置的状态，而哈希表有存储相应的值，故哈希表的数据应该是一个自定义类型，将状态和值封装起来，如下：
template<class K, class V>
struct hash_data
{
std::pair<K, V> _kv;
state _st;
hash_data(const std::pair<K, V>& kv = std::pair<K, V>())
:_kv(kv)
, _st(EMPTY)
{}
};同时，为了获得负载因子，我们需要保存有效元素的个数。
有了上面，我们的哈希表的框架如下：
namespace Xq
{
template<class K, class V>
class hash_table
{
private:
typedef hash_data<K, V> Node;
public:
bool insert(const std::pair<K, V>& kv) {}
bool find(const K& key) {}
bool erase(const K& key) {}
private:
std::vector<Node> _table;
size_t _size; // 有效元素个数
};
}4.2. Xq::hash_table::insert 的实现
首先，暂不考虑扩容和去重问题，如何实现 insert 呢？
bool insert(const std::pair<K, V>& kv)
{
// 除留余数法, 计算位置
// 注意：这里不能模capacity, 因为 vector 的 operator[] 会强制见检查 pos < size()
// 因此实际中, 最好让 size == capacity, 即开空间 or 扩容用 resize 即可.
size_t pos = kv.first % _table.size();
// 如果这个位置已经有值了, 说明出现了哈希冲突, 在这里采用线性探测
// 线性探测: 当发生哈希冲突的位置开始，依次向后探测，直到寻找到下一个空位置(没有被占用的位置)
while (_table[pos]._st == EXIST)
{
++pos;
// 如果 pos 走到了表的结尾, 让 pos 回到表的开始
if (pos == _table.size())
pos = 0;
}
_table[pos]._kv = kv;
_table[pos]._st = EXIST;
++_size;
return true;
}当处理完上面的逻辑后，我们需要考虑扩容问题：
void broaden_capacity(size_t new_size)
{
// 在这里重新构造一个哈希表，复用insert
hash_table<K, V> new_table;
new_table._table.resize(new_size);
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i]._st == EXIST)
{
new_table.insert(_table[i]._kv);
}
}
//更新完数据后,交换新表和旧表
std::swap(new_table._table, _table);
// 新表出了函数作用域, 自动调用析构, 释放资源.
}
bool insert(const std::pair<K, V>& kv)
{
// 去重
if (find(kv.first)) return false;
// 处理扩容
// 空表或者负载因子大于等于0.7进行扩容
// 扩容不可以将数据直接拷贝下来, 因为扩容后, 原来的映射关系会受到影响 (表的大小改变)
// 此时需要重新映射, 将旧表的数据重新映射到新表, 因此,
// 哈希表的扩容代价是很大的，比 vector 的扩容代价还大
if (_table.size() == 0 || _size * 10 / _table.size() >= 7)
{
size_t new_size = _table.size() == 0 ? 10 : 2 * _table.size();
broaden_capacity(new_size);
}
// 插入数据逻辑, 在这里省略.
}当处理完这个问题，此时我们还需要考虑去重问题，解决方案很简单，写一个 find， 如果这个 Key 已经存在，不插入即可，如下：
bool insert(const std::pair<K, V>& kv)
{
// 去重
if (find(kv.first)) return false;
// 处理扩容逻辑, 省略
// 插入数据逻辑, 省略.
return true;
}4.3. Xq::hash_table::find 的实现
find 的处理逻辑很简单：
- 如果表为空，直接返回fasle；
- 如果表不为空：
- 计算这个 key 的初始位置；
- 如果当前位置没有，线性探测下一个位置；
- 如果在线性探测过程中，某个位置的状态为 EMPTY，说明没有这个值，返回 false；
- 如果走到表的结尾，回到表的开始；
- 如果走到了初始位置，代表没有这个值，返回 false。
实现如下：
bool find(const K& key)
{
// 如果没有数据,直接返回false
if (_size == 0) return false;
size_t pos = key % _table.size();
size_t start = pos;
// 如果走到空,说明没有这个值
while (_table[pos]._st != EMPTY)
{
if (_table[pos]._kv.first == key)
{
return true;
}
++pos;
if (pos == _table.size())
pos = 0;
// 遍历了一圈也没找到,说明不存在,避免死循环
if (pos == start)
return false;
}
return false;
}4.4. Xq::hash_table::erase 的实现
由于我们对哈希表的每个位置都设置了状态，因此，删除就很简单了，只需要将某个位置的状态设置为 DELETE 即可，实现如下：
bool erase(const K& key)
{
// 如果目标 key 不存在, 返回false即可
if (_size == 0 || !find(key)) return false;
// 如果目标 key 存在, 只需要将目标位置的状态置为DELETE即可
size_t pos = key % _table.size();
// 由于存储元素是线性探测的方式存储的, 因此删除也需要按照线性探测的方式查找
while (_table[pos]._kv.first != key)
{
++pos;
if (pos == _table.size())
pos = 0;
}
// 将目标 key 所在的位置的状态置为 DELETE
_table[pos]._st = DELETE;
// 并--有效元素的个数
--_size;
return true;
}4.5. 开放定址法实现哈希表的完整代码
namespace Xq
{
// 用三种状态标记哈希表的每个空间的情况
enum state
{
EXIST, // (存在有效值)
EMPTY, // 存在无效值 (该位置的值已被删除)
DELETE // 不存在值 (该位置没有被赋值过)；
};
template<class K, class V>
struct hash_data
{
std::pair<K, V> _kv;
state _st;
hash_data(const std::pair<K, V>& kv = std::pair<K, V>())
:_kv(kv)
, _st(EMPTY)
{}
};
template<class K, class V>
class hash_table
{
private:
typedef hash_data<K, V> Node;
public:
hash_table() :_size(0){}
void broaden_capacity(size_t new_size)
{
// 在这里重新构造一个哈希表，复用insert
hash_table<K, V> new_table;
new_table._table.resize(new_size);
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i]._st == EXIST)
{
new_table.insert(_table[i]._kv);
}
}
//更新完数据后,交换新表和旧表
std::swap(new_table._table, _table);
// 新表出了函数作用域, 自动调用析构, 释放资源.
}
bool insert(const std::pair<K, V>& kv)
{
// 去重
if (find(kv.first)) return false;
// 处理扩容
// 空表或者负载因子大于等于0.7进行扩容
// 扩容不可以将数据直接拷贝下来, 因为扩容后, 原来的映射关系会受到影响 (表的大小改变)
// 此时需要重新映射, 将旧表的数据重新映射到新表, 因此,
// 哈希表的扩容代价是很大的，比 vector 的扩容代价还大
if (_table.size() == 0 || _size * 10 / _table.size() >= 7)
{
size_t new_size = _table.size() == 0 ? 10 : 2 * _table.size();
broaden_capacity(new_size);
}
// 除留余数法, 计算位置
// 注意：这里不能模capacity, 因为 vector 的 operator[] 会强制见检查 pos < size()
// 因此实际中, 最好让 size == capacity, 即开空间 or 扩容用 resize 即可.
size_t pos = kv.first % _table.size();
// 如果这个位置已经有值了, 说明出现了哈希冲突, 在这里采用线性探测
// 线性探测: 当发生哈希冲突的位置开始，依次向后探测，直到寻找到下一个空位置(没有被占用的位置)
while (_table[pos]._st == EXIST)
{
++pos;
// 如果 pos 走到了表的结尾, 让 pos 回到表的开始
if (pos == _table.size())
pos = 0;
}
_table[pos]._kv = kv;
_table[pos]._st = EXIST;
++_size;
return true;
}
bool find(const K& key)
{
// 如果没有数据,直接返回false
if (_size == 0) return false;
size_t pos = key % _table.size();
size_t start = pos;
// 如果走到空,说明没有这个值
while (_table[pos]._st != EMPTY)
{
if (_table[pos]._kv.first == key)
{
return true;
}
++pos;
if (pos == _table.size())
pos = 0;
// 遍历了一圈也没找到,说明不存在,避免死循环
if (pos == start)
return false;
}
return false;
}
bool erase(const K& key)
{
// 如果目标 key 不存在, 返回false即可
if (_size == 0 || !find(key)) return false;
// 如果目标 key 存在, 只需要将目标位置的状态置为DELETE即可
size_t pos = key % _table.size();
// 由于存储元素是线性探测的方式存储的, 因此删除也需要按照线性探测的方式查找
while (_table[pos]._kv.first != key)
{
++pos;
if (pos == _table.size())
pos = 0;
}
// 将目标 key 所在的位置的状态置为 DELETE
_table[pos]._st = DELETE;
// 并--有效元素的个数
--_size;
return true;
}
private:
std::vector<Node> _table;
size_t _size; // 有效元素个数
};
}5. 开散列实现哈希表 (拉链法)
拉链法实现哈希表，是如何解决哈希冲突的呢？
拉链法实现的哈希表也称之为哈希桶，本质上是哈希表中每个位置中存储的并不仅仅是一个节点，而是一个单链表，当产生哈希冲突时，就会将相同位置的节点链入到一个链表中，如下所示：
5.1. 拉链法的实现框架
#pragma once
#include <iostream>
#include <utility>
#include <vector>
namespace Xq
{
template<class K, class V>
struct hash_table_node
{
struct hash_table_node<K, V>* _next;
std::pair<K, V> _kv;
hash_table_node(const std::pair<K, V>& kv = std::pair<K, V>())
:_kv(kv)
, _next(nullptr)
{}
};
template <class K, class V>
class hash_table
{
private:
typedef hash_table_node<K, V> Node;
public:
hash_table() :_size(0){}
bool insert(const std::pair<K, V>& kv) {}
Node* find(const K& key) {}
bool erase(const K& key) {}
private:
std::vector<Node*> _table;
size_t _size; // 存储有效数据的个数
};
}5.2. 哈希表扩容问题 (表的大小的设计问题)
在闭散列中实现哈希表时，我们所用的哈希表的初始大小为10，且后续扩容是以2倍的方式进行的，但我们在直接说过，由于除留余数法存在哈希冲突，故为了减少哈希冲突，人们发现，如果表的大小为一个素数，就会减小哈希冲突的可能。
同时，我们可以看看 SGI-STL 版本的哈希表如何处理表的大小的问题的，如下：
可以发现，STL 中哈希表的大小都是一个素数，我们也照葫芦画瓢，如下：
#pragma once
#include <iostream>
#include <utility>
#include <vector>
namespace Xq
{
template<class K, class V>
struct hash_table_node
{
// 省略 ...
};
template <class K, class V>
class hash_table
{
private:
typedef hash_table_node<K, V> Node;
static const size_t _table_size = 28; // 静态数组的大小
static const size_t _table_count_arr[_table_size]; // 哈希表的大小(每个都是素数)
public:
hash_table() :_size(0){}
bool insert(const std::pair<K, V>& kv) {}
Node* find(const K& key) {}
bool erase(const K& key) {}
private:
std::vector<Node*> _table;
size_t _size; // 存储有效数据的个数
};
template<class K, class V>
const size_t hash_table<K, V>::_table_count_arr[hash_table<K, V>::_table_size] = // 哈希表的大小(每个都是素数)
{
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
};
}因为扩容需要得到新的表的大小，故我们写一个接口，用于获取哈希表新的大小，如下：
// 用来获取下一次扩容后的表的大小
size_t get_prime_size(size_t size)
{
for (size_t i = 0; i < _table_size; ++i)
{
if (i == 28) break;
if (_table_count_arr[i] > size)
return _table_count_arr[i];
}
return -1;
}5.3. Xq::hash_table::insert 的实现
分三个大致逻辑：
- 插入数据 (头插)；
- 扩容；
- 去重。
实现如下：
bool insert(const std::pair<K, V>& kv)
{
// 去重逻辑
if (find(kv.first)) return false;
// 扩容逻辑
// 空表或者负载因子>=1 进行扩容
if (_table.size() == 0 || _size * 10 / _table.size() >= 10)
{
// 创建新表
std::vector<Node*> new_table;
// 获得新表的大小
new_table.resize(get_prime_size(_table.size()), nullptr);
// 将旧表的有效节点摘下来, 头插到新表
for (size_t i = 0; i < _table.size(); ++i)
{
// 如果当前位置有节点, 不为空
// 那么保存下一个节点, 并获取当前节点在新表的位置, 链入到新表中
// 遍历下一个节点
while (_table[i])
{
Node* next = _table[i]->_next;
size_t pos = _table[i]->_kv.first % new_table.size();
_table[i]->_next = new_table[pos];
new_table[pos] = _table[i];
_table[i] = next;
}
}
// 交换两个表,扩容结束
std::swap(_table, new_table);
}
// 插入数据逻辑
size_t pos = kv.first % _table.size();
Node* newnode = new Node(kv);
// 这里采用头插, 因为是单链表, 时间复杂度为 O(1)
newnode->_next = _table[pos];
_table[pos] = newnode;
++_size;
return true;
}5.4. Xq::hash_table::find 的实现
Node* find(const K& key)
{
// 空表, 直接返回空
if (_size == 0) return nullptr;
// 非空表, 计算目标位置
size_t obj_pos = key % _table.size();
// 搜索这个单链表
Node* cur = _table[obj_pos];
while (cur)
{
if (cur->_kv.first == key)
return cur;
cur = cur->_next;
}
return nullptr;
}5.5. Xq::hash_table::erase 的实现
事实上，这里就是一个单链表的删除，代码如下：
bool erase(const K& key)
{
if (!find(key) || _size == 0) return false;
size_t pos = key % _table.size();
//头删
Node* cur = _table[pos];
if (cur->_kv.first == key)
{
Node* next = cur->_next;
delete cur;
_table[pos] = next;
}
// !头删
else
{
while (cur->_next->_kv.first != key)
{
cur = cur->_next;
}
Node* next = cur->_next->_next;
delete cur->_next;
cur->_next = next;
}
--_size;
return true;
}5.6. 拉链法的完整实现 (初始版本)
#pragma once
#include <iostream>
#include <utility>
#include <vector>
namespace Xq
{
template<class K, class V>
struct hash_table_node
{
struct hash_table_node<K, V>* _next;
std::pair<K, V> _kv;
hash_table_node(const std::pair<K, V>& kv = std::pair<K, V>())
:_kv(kv)
, _next(nullptr)
{}
};
template <class K, class V>
class hash_table
{
private:
typedef hash_table_node<K, V> Node;
static const size_t _table_size = 28; // 静态数组的大小
static const size_t _table_count_arr[_table_size]; // 哈希表的大小(每个都是素数)
public:
hash_table() :_size(0){}
// 用来获取下一次扩容后的表的大小
size_t get_prime_size(size_t size)
{
for (size_t i = 0; i < _table_size; ++i)
{
if (i == 28) break;
if (_table_count_arr[i] > size)
return _table_count_arr[i];
}
return -1;
}
bool insert(const std::pair<K, V>& kv)
{
// 去重逻辑
if (find(kv.first)) return false;
// 扩容逻辑
// 空表或者负载因子>=1 进行扩容
if (_table.size() == 0 || _size * 10 / _table.size() >= 10)
{
// 创建新表
std::vector<Node*> new_table;
// 获得新表的大小
new_table.resize(get_prime_size(_table.size()), nullptr);
// 将旧表的有效节点摘下来, 头插到新表
for (size_t i = 0; i < _table.size(); ++i)
{
// 如果当前位置有节点, 不为空
// 那么保存下一个节点, 并获取当前节点在新表的位置, 链入到新表中
// 遍历下一个节点
while (_table[i])
{
Node* next = _table[i]->_next;
size_t pos = _table[i]->_kv.first % new_table.size();
_table[i]->_next = new_table[pos];
new_table[pos] = _table[i];
_table[i] = next;
}
}
// 交换两个表,扩容结束
std::swap(_table, new_table);
}
// 插入数据逻辑
size_t pos = kv.first % _table.size();
Node* newnode = new Node(kv);
newnode->_next = _table[pos];
_table[pos] = newnode;
++_size;
return true;
}
Node* find(const K& key)
{
// 空表, 直接返回空
if (_size == 0) return nullptr;
// 非空表, 计算目标位置
size_t obj_pos = key % _table.size();
// 搜索这个单链表
Node* cur = _table[obj_pos];
while (cur)
{
if (cur->_kv.first == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool erase(const K& key)
{
if (!find(key) || _size == 0) return false;
size_t pos = key % _table.size();
//头删
Node* cur = _table[pos];
if (cur->_kv.first == key)
{
Node* next = cur->_next;
delete cur;
_table[pos] = next;
}
// !头删
else
{
while (cur->_next->_kv.first != key)
{
cur = cur->_next;
}
Node* next = cur->_next->_next;
delete cur->_next;
cur->_next = next;
}
--_size;
return true;
}
private:
std::vector<Node*> _table;
size_t _size; // 存储有效数据的个数
};
// 哈希表的大小(每个都是素数)
template<class K, class V>
const size_t hash_table<K, V>::_table_count_arr[hash_table<K, V>::_table_size] =
{
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
};
}5.7. 解决取模操作的限制
上面的代码，存在问题，假如此时的这个K是一个 string，那么会带来什么样的问题呢？
如下 demo ：
void Test1(void)
{
std::string str[] = { "老虎", "狮子", "大熊猫", "长颈鹿", "孔雀" };
srand((unsigned int)time(nullptr));
Xq::hash_table<std::string, int> my_hash;
for (size_t i = 0; i < 10; ++i)
{
std::string tmp = str[rand() % 5];
Xq::hash_table_node<std::string, int>* ret = my_hash.find(tmp);
// 如果该动物没存在,就插入map中,并将Value赋值为1
if (!ret)
my_hash.insert(std::make_pair(tmp, 1));
// 如果该动物存在,将Value值++即可
else
++ret->_kv.second;
}
}现象如下：
因为此时的 key 是一个 string， 而默认情况下， string 是不支持取模操作的，故编译报错，如何解决？
我们需要利用仿函数和特化机制，让哈希表具有一种功能，能够让特定的类型支持取模操作，在这里，具体操作就是，让哈希表这个类模板具有第三个模板参数，这个模板参数是一个仿函数类型，通过这个仿函数，让特定类型支持取模操作，如下：
// hash_func这个仿函数的主要目的: 将 key 转换为 size_t, 以便于支持取模操作
template<class K>
struct hash_func
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 例如在这里,string默认是不可以进行取模运算的
// 因此在这里利用类模板的特化,针对string特殊处理
template<>
struct hash_func<std::string>
{
size_t operator()(const std::string& str)
{
size_t ret = 0;
for (auto ch : str)
{
ret *= 131;
ret += ch;
}
return ret;
}
};
template <class K, class V, class Hash = hash_func<K>>
class hash_table {};可以看到，上面的代码中，当我们需要将一个 string 类型的 key 转为整形的时候，我们会让其每个字符乘等于131，这是为什么呢？
首先，我们将 string 类的 key 转化为整形的目的是：为了让其可以进行取模，但是如果是以下场景：
- string str1 = "ate";
- string str2 = "eat";
我们可以发现，如果我们让其的每个字符直接进行相加求和，那么带来的问题就是它们最后结果是一致的，那么就会带来增大哈希冲突的可能性，因此为了减少哈希冲突，将其每个字符都 *= 131，至于这里为什么是 131，原因如下：
- 131是一个较大的质数，质数具有较好的散列性质，可以减少哈希冲突的概率。
有了这个模板参数 (Hash)，未来哈希表只要涉及到取模操作，都需要让 key 通过这个仿函数进行取模，在这里只演示 insert 如下：
bool insert(const std::pair<K, V>& kv)
{
if (find(kv.first)) return false;
// #####################################################
// 实例化这个仿函数对象
Hash hash_func;
// #####################################################
if (_table.size() == 0 || _size * 10 / _table.size() >= 10)
{
std::vector<Node*> new_table;
new_table.resize(get_prime_size(_table.size()), nullptr);
for (size_t i = 0; i < _table.size(); ++i)
{
while (_table[i])
{
Node* next = _table[i]->_next;
// #####################################################
// 只要涉及到取模操作, 都需要通过这个模板参数
size_t pos = hash_func(_table[i]->_kv.first) % new_table.size();
// #####################################################
_table[i]->_next = new_table[pos];
new_table[pos] = _table[i];
_table[i] = next;
}
}
std::swap(_table, new_table);
}
// #####################################################
// 只要涉及到取模操作, 都需要通过这个模板参数
size_t pos = hash_func(kv.first) % _table.size();
// #####################################################
Node* newnode = new Node(kv);
newnode->_next = _table[pos];
_table[pos] = newnode;
++_size;
return true;
}5.8. 拉链法的完整实现 (更新版本)
#pragma once
#include <iostream>
#include <utility>
#include <vector>
namespace Xq
{
template<class K, class V>
struct hash_table_node
{
struct hash_table_node<K, V>* _next;
std::pair<K, V> _kv;
hash_table_node(const std::pair<K, V>& kv = std::pair<K, V>())
:_kv(kv)
, _next(nullptr)
{}
};
// hash_func这个仿函数的主要目的: 将 key 转换为 size_t, 以便于支持取模操作
template<class K>
struct hash_func
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 例如在这里,string默认是不可以进行取模运算的
// 因此在这里利用类模板的特化,针对string特殊处理
template<>
struct hash_func<std::string>
{
size_t operator()(const std::string& str)
{
size_t ret = 0;
// 具体这里为什么要乘于131,请看解释(1)
for (auto ch : str)
{
ret *= 131;
ret += ch;
}
return ret;
}
};
template <class K, class V, class Hash = hash_func<K>>
class hash_table
{
private:
typedef hash_table_node<K, V> Node;
static const size_t _table_size = 28; // 静态数组的大小
static const size_t _table_count_arr[_table_size]; // 哈希表的大小(每个都是素数)
public:
hash_table() :_size(0){}
// 用来获取下一次扩容后的表的大小
size_t get_prime_size(size_t size)
{
for (size_t i = 0; i < _table_size; ++i)
{
if (i == 28) break;
if (_table_count_arr[i] > size)
return _table_count_arr[i];
}
return -1;
}
bool insert(const std::pair<K, V>& kv)
{
// 去重逻辑
if (find(kv.first)) return false;
// 实例化这个仿函数对象
Hash hash_func;
// 扩容逻辑
// 空表或者负载因子>=1 进行扩容
if (_table.size() == 0 || _size * 10 / _table.size() >= 10)
{
// 创建新表
std::vector<Node*> new_table;
// 获得新表的大小
new_table.resize(get_prime_size(_table.size()), nullptr);
// 将旧表的有效节点摘下来, 头插到新表
for (size_t i = 0; i < _table.size(); ++i)
{
// 如果当前位置有节点, 不为空
// 那么保存下一个节点, 并获取当前节点在新表的位置, 链入到新表中
// 遍历下一个节点
while (_table[i])
{
Node* next = _table[i]->_next;
// 只要涉及到取模操作, 都需要通过这个模板参数
size_t pos = hash_func(_table[i]->_kv.first) % new_table.size();
_table[i]->_next = new_table[pos];
new_table[pos] = _table[i];
_table[i] = next;
}
}
// 交换两个表,扩容结束
std::swap(_table, new_table);
}
// 插入数据逻辑
// 只要涉及到取模操作, 都需要通过这个模板参数
size_t pos = hash_func(kv.first) % _table.size();
Node* newnode = new Node(kv);
newnode->_next = _table[pos];
_table[pos] = newnode;
++_size;
return true;
}
Node* find(const K& key)
{
Hash hash_func;
// 空表, 直接返回空
if (_size == 0) return nullptr;
// 非空表, 计算目标位置
size_t obj_pos = hash_func(key) % _table.size();
// 搜索这个单链表
Node* cur = _table[obj_pos];
while (cur)
{
if (cur->_kv.first == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool erase(const K& key)
{
Hash hash_func;
if (!find(key) || _size == 0) return false;
size_t pos = hash_func(key) % _table.size();
//头删
Node* cur = _table[pos];
if (cur->_kv.first == key)
{
Node* next = cur->_next;
delete cur;
_table[pos] = next;
}
// !头删
else
{
while (cur->_next->_kv.first != key)
{
cur = cur->_next;
}
Node* next = cur->_next->_next;
delete cur->_next;
cur->_next = next;
}
--_size;
return true;
}
private:
std::vector<Node*> _table;
size_t _size; // 存储有效数据的个数
};
// 哈希表的大小(每个都是素数)
template<class K, class V, class Hash = hash_func<K>>
const size_t hash_table<K, V, Hash>::_table_count_arr[hash_table<K, V, Hash>::_table_size] =
{
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
};
}下篇博客，我们就要讨论哈希表的封装，即 unordered_set 和 unordered_map。
