跳到主要内容C++ 数据结构：哈希表原理与实现 | 极客日志C++算法
C++ 数据结构：哈希表原理与实现
综述由AI生成哈希表是基于映射思想的数据结构，利用哈希函数将键值转换为存储位置。内容涵盖哈希值生成、常用哈希函数如直接定址法和除留余数法，以及哈希冲突的两种解决方式：开放定址法和哈希桶。重点解析了 C++ STL 中 unordered_map 与 unordered_set 如何复用底层哈希桶模板类，包括模板参数设计、键值提取仿函数 KeyOfValue 的作用，以及自定义类型作为键时所需的哈希函数与相等比较器配置。
清酒独酌29 浏览 C++ 数据结构：哈希表原理与实现
理解哈希表
首先要理解哈希和哈希表有什么不同。哈希就是映射，是一种算法思想。哈希表就是映射表，是利用映射这种思想写出的一种数据结构。
所有的哈希表的算法流程都是类似的——拿到一个 key，利用哈希函数进行 hash(key)，得到的空间位置存放我们想要存放的数据 Value。
或者——拿到一个 key，利用哈希函数进行 hash(key)，从得到的空间位置取出我们想要查找的数据 Value。
哈希值（整形）
为什么要有哈希值？是因为哈希函数都是对一个整形进行哈希，比如直接定址、除留余数、平方取中，基数转换等等。最重要的是 STL 里面使用的也是除留余数（只不过不是传统的除留余数，标准库实现有其他优化）。
我们在用 STL 的时候，如果想要对一个自定义类型进行哈希，那么就必须提供这个自定义类型向哈希值的转换方法。本篇文章中我们以后称为'转换策略'。
有了这个转换策略，就可以将自定义类型转化为一个哈希值。然后再将这个哈希值交给 STL 底层的哈希函数进行哈希。得到的结果经过哈希冲突的处理得到映射位置，这个映射位置就是最后这一次哈希要存储的位置了。
转化哈希值一般要定义为一个仿函数，然后作为 unordered_map 的第三个模板参数传进去。这样就能让一个任意类型能够去进行哈希了。
要注意转化哈希值要注意速度快，离散高。常见的转化策略比如 string 类型向整形转化的 BKDR 哈希、DJB 哈希、多成员复杂结构，结构中含有整形和 string 的 hash_combine、以及对含少量成员的异或组合。里面有嵌套容器的递归哈希等等。
这里只挑选熟悉的演示：
BKDR 哈希
优点：实现简单，计算快；离散高，冲突少；不同种子可以计算出不同哈希值。
实现方法是选取一个种子 seed，然后对字符串里面的每一个字符进行处理：
size_t BKDRHash(const string &str) {
size_t seed = 131;
size_t hash = 1;
for (auto e : str) {
hash *= seed;
hash += e;
}
return hash & 0x7FFFFFFF;
}
这个种子的值可以是 31，131，1313，13131，131313...。
异或组合
优点：实现简单，计算快。缺点：冲突率高
struct PointHash {
size_t operator()(const vector<int> &vec) {
int hash = 0;
for (auto e : vec) {
hash ^= (e << );
}
hash;
}
};
1
return
hash_combine
template <typename T>
void hash_combine(std::size_t& seed, const T& val) {
seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
struct Person {
std::string name;
int age;
bool operator==(const Person& p) const {
return name == p.name && age == p.age;
}
};
struct PersonHash {
std::size_t operator()(const Person& p) const {
std::size_t seed = 0;
hash_combine(seed, p.name);
hash_combine(seed, p.age);
return seed;
}
};
哈希函数
直接定址法
哈希表进行哈希有可能产生哈希冲突。但是我们说哈希其实就是映射，在数学中也有映射，一元一次方程，一元二次方程其实都是映射。有没有那么一种映射关系，不会存在两个哈希值同时映射到一个空间上呢？其实是有的，比如直接定址法。
直接定址法就是数学中一个具有单调性的函数，每一个哈希值都对应唯一的一个映射位置（x 映射唯一的 y）。这样做的方法有利有坏，好处是没有哈希冲突，因为每一个哈希都有唯一的数组下标与其对应；坏处是如果这一组整形很分散，假如有 1，99999，那么消耗的空间很大。所以对于直接定址法只适用于很集中的一组数。
除留余数法
对哈希表的大小的进行取模。得到一个结果，这个就叫做除留余数法。一个哈希表的大小为 m，就要取一个不大于 m 的，接近 m 的质数 p 作为模数。
假如一个哈希表大小为 10，那么 p 可以取 7。想要对键值为 12，13，1 的键值对进行映射，那么就是用它们模 7，然后就能得到映射的区域。
平方取中法
平方取中法是通过取关键字的哈希值的平方数中间几位作为哈希地址。
例子 1：假如有一个哈希表 1000（0 ~ 999），一个键值对的 key 为 1234。运用平方取中法就是：1234 ^ 2 = 1522756。因为哈希表的大小为 1000，那么就要取平方数的中间三位。取得 227，这个 227 就是最后的哈希地址。
例子 2：假如有一个哈希表的大小为 50（0 ~ 49），一个键值对的 key 为 68。运用平方取中法就是：68 * 68 = 4624。因为哈希表的大小为 50，那么就要去平方数的中间两位。取得 62。但是 62 比 50 大，所以我们可以让他们取模得到 12。最后 12 就是哈希地址。
平方取中法的优点：
对于一些连续的键值能够将它们打散。比如 123，124，125 等。
不像除留余数法那样需要取值，防止取值不合适加剧冲突。
基数转换法
基数转换法就是将一个十进制数转化为其他进制的数字（比如十二进制，十三进制，十六进制），然后把转化后的数字看成是十进制，最后再把这个转化后的数字对哈希表的大小进行取模。但是如果转化后的数字里面有字母，就把这个字母看成他的 ASCII 码值。比如 255，转化成十六进制为 FF，看成十进制就是 7070。所以 255 进制基数转换后就是 7070。如果哈希表大小为 10，那么取模后就是 7070 % 10 = 0。
哈希冲突
上面的所有的哈希函数除了直接定址法，都有一个问题。就是有可能两个不同的键值映射到了同一个哈希地址上面。这种情况就叫做哈希冲突。哈希冲突也是哈希表的核心问题之一。
哈希表里面有负载因子的概念。负载因子 = 已插入数据的个数 / 表大小。负载因子越大，越容易发生哈希冲突。因为负载因子大，说明哈希表中的数据很多，再插入数据时就很容易映射到有数据的地址，就发生了冲突。
很明显，如果插入数据映射到有数据的地址，就要重新映射，这样效率非常低。所以哈希冲突会影响哈希表的效率。那么为了缓解冲突带来的影响，哈希冲突有两种常见的解决方案：开放定址法、哈希桶。
开放定址法
解决方法：开放定址法就是当哈希冲突时，键值对会向后偏移。比如 a 本来映射到 1 号位，但是 1 号位被占用了，那么 a 就按照规律向后偏移，直到遇到一个没有被占用的位置。
（这里的规律有两种：一种叫做线性探测，即一格一格的向后遍历，1 号位被占用，去探测 2 号位。2 号位没有，去探测 3 号位，依此类推。第二种叫做二次探测，即按照平方数进行探测。假如探测位置为 i，那么线性探测就是每次 i++，二次探测就是每次 (i++) ^ 2。）
负载因子：负载因子通常需要小于 0.7。如果太大探测次数就很多，效率就会很低。甚至插入数据的时间复杂度可能逼近 O(n) 了。
template <class K, class V>
class HashData {
public:
enum State { EMPTY, EXIST, DELETE };
public:
pair<K, V> _kv;
State _state;
};
template <class K, class V>
class HashTable {
public:
bool insert(const pair<K, V> &kv) {
if (_tables.size() == 0 || (_n * 10) / _tables.size() >= 7) {
UpMemory();
}
if (Find(kv.first)) return false;
int hashi = kv.first % _tables.size();
while (_tables[hashi]._state == HashData<K, V>::State::EXIST) {
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = HashData<K, V>::State::EXIST;
_n++;
}
HashData<K, V> *Find(const K &key)
{
int hashi = key % _tables.size();
int tmp = hashi;
while (_tables[hashi]._state != HashData<K, V>::EMPTY) {
if (_tables[hashi]._state == HashData<K, V>::EXIST && _tables[hashi]._kv.first == key) {
return &_tables[hashi];
}
hashi++;
hashi %= _tables.size();
if (hashi == tmp) return nullptr;
}
return nullptr;
}
bool Erase(const K &key)
{
HashData<K, V> *pdata = Find(key);
if (pdata == nullptr) return false;
pdata->_state = HashData<K, V>::DELETE;
--_n;
return true;
}
void Order() {
cout << _n << endl;
for (int i = 0; i < _tables.size(); i++) {
if (_tables[i]._state == HashData<K, V>::EXIST)
cout << _tables[i]._kv.first << " : " << _tables[i]._kv.second << endl;
}
}
private:
void UpMemory() {
int newsize = (_tables.size() == 0) ? 5 : 2 * _tables.size();
HashTable<K, V> NewHT;
NewHT._tables.resize(newsize);
for (int i = 0; i < _tables.size(); i++) {
if (_tables[i]._state == HashData<K, V>::EXIST) {
NewHT.insert(_tables[i]._kv);
}
}
_tables.swap(NewHT._tables);
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
public:
static void Test1() {
HashTable<int, int> hash;
hash.insert({1, 1});
hash.insert({12, 1});
hash.insert({13, 1});
hash.insert({16, 1});
hash.insert({161, 1});
hash.insert({162, 1});
hash.insert({163, 1});
hash.insert({164, 1});
hash.insert({165, 1});
hash.insert({16, 1});
hash.insert({-16, 1});
hash.Erase(16);
hash.Erase(161);
hash.Erase(162);
hash.Erase(163);
hash.insert({16, 1});
hash.Erase(16);
hash.insert({16, 1});
hash.Order();
}
};
哈希桶
如果说开放定址法的结构是一个数组。那么哈希桶本质上其实结构已经不单单是一个数组了，而是一个数组，但是这个数组里面挂上了一串串链表，如下图：
哈希桶解决哈希冲突的方法是在数组本该存放数据的位置不放数据了，改为数据节点的指针。以后如果有数据映射到了这个位置，就创建节点，将数据链入到该位置的链表里面。因为链表挂在数组上面就像一个桶，所以就叫做哈希桶。数组里面的每一个元素都叫做一个桶。
哈希桶效率比开放定址法要高。在负载因子为 1 的情况下（STL 下也为 1），只要不出现极端情况，插入几百万条随机数据，最长的桶的长度也会保持在 6，7，8 左右。也就是说，每次我们 hash 查找数据，是一个常数级别的时间复杂度。
C++ unordered_map 和 unordered_set 的底层就是用的哈希桶。接下来，我们就要讲解一下，在 STL 中，是怎么实现哈希桶的。
unordered_map 和 unordered_set 如何共用一个哈希桶模板类
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
template<class Key, class Hash, class Pred.......
template<class Key, class T, class Hash, class Pred......>
先来只看哈希桶里面的前两个模板参数。这里的 Key 和 Value 并不是传统意义上的键值对。因为 set 没有键值对，只有键值。而 map 有键值对。这就说明 unordered_set 不需要两个模板参数，unordered_map 需要两个模板参数。所以，为了解决 unordered_set 和 unordered_map 复用模板类的问题，大佬们把 unordered_set 里面那个哈希桶的第二个模板参数也传成了 Key。把 unordered_map 里面那个哈希桶的第二个模板参数直接传承了 pair<Key, T> 即：
template<class Key, class Hash, class Pred.....>
class unordered_set {
typedef HashBucket<Key, Key, ....>
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
typedef HashBucket<Key, pair<Key, T>, ....>
};
对于哈希桶的查找和删除，是一定，并且只会用到 Key，不管上层存储的是键值对还是单个键。就是利用键 Key 进行查找和删除。
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
Find(const Key &key);
Erase(const Key &key);
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
typedef HashBucket<Key, Key, ....> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
typedef HashBucket<Key, pair<Key, T>, ....> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
};
但是对于插入，unordered_set 和 unordered_map 是不一样的。因为前者插入的是一个 Key 类型数据，而后者插入的是一个 pair<Key, T> 类型的数据。正好 unordered_set 里面的哈希桶第二个模板参数是 Key，又恰好 unordered_map 里面的哈希桶的第二个模板参数是 pair<Key, T>。所以，在哈希桶内部的 Insert 的参数是 Value 类型的数据。但是在外层，其实 unordered_set 传的是 Key，unordered_map 传的是 pair<Key, T>。如下：
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
Find(const Key &key);
Erase(const Key &key);
Insert(const Value &data);
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
typedef HashBucket<Key, Key, ....> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
Insert(const Key &data) { return _ht.Insert(data); }
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
typedef HashBucket<Key, pair<Key, T>, ....> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
Insert(const pair<K, T> &data) { return _ht.Insert(data); }
};
上面我们讲解的是大佬们如何解决的 unordered_set 和 unordered_map 公用一个底层哈希桶的问题，是框架。现在我们讲解了这个框架的结构。然后就要去实现里面的细节。
STL 的哈希桶中 Insert 如何得到的键值
这里有两处细节，首先第一处细节：Insert 怎么得到键值？
我们上面说哈希桶的删除和查找，是一定，并且是只会用到键 Key 的。不管上层存储的是键值对还是单个键。所以 unordered_set 和 unordered_map 的 Find 和 Erase 直接按照逻辑实现代码就行。
而哈希桶的插入 unordered_set 和 unordered_map 传入的类型不同。那么得到键的方法就不一样了。unordered_set 是直接拿过来用就行。unordered_map 是要拿到里面的 first。这个时候聪明的小伙伴已经想到办法了，没错，就是利用仿函数。对于哈希桶，它要对外提供一个模板参数来来接受获取 Value 里面键值的方法。这，就是我们的哈希桶里面的第四个模板参数 ExtractKey（第三个是一个空间配置器，与本节没有关系）。以后，unordered_set 传送他的拿到键值的方法，unordered_map 传送他的拿到键值对方法，哈希桶只管接收，然后 Insert 想要用键 Key 的时候，就用传过来的方法对 data 进行处理，就能拿到这个键 Key。
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
Find(const Key &key);
Erase(const Key &key);
Insert(const Value &data);
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
struct KeyOfValue {
const K &operator()(const K &key) { return key; }
};
typedef HashBucket<Key, Key, Alloc, KeyOfValue..> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
Insert(const Key &data) { return _ht.Insert(data); }
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
struct KeyOfValue {
const K& operator()(const pair<K, V> &_kv) { return _kv.first; }
};
typedef HashBucket<Key, pair<Key, T>, Alloc, KeyOfValue, ...> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
Insert(const pair<K, T> &data) { return _ht.Insert(data); }
};
键为自定义类型的处理
最后一个细节，unordered_set 和 unordered_map 是怎么处理自定义类型的键的？
其实这篇文章在一开始就在为这一点做铺垫了，就是上面的哈希值。对于任意的自定义类型，都可以作为键，但是前提是实现这个自定义类型向整形转化的仿函数和自定义类型的==重载或 equal 仿函数。
哈希桶的底层插入或者查找或者删除，哈希函数用的是类似于除留余数法（标准库肯定做了特殊处理），如果是一个整形，比如 10，桶大小为 5。那么 10 % 5 == 0。此时这个值就放到 0 号桶里面了。下面 insert 的伪代码
insert(const Value &data) {
KeyOfT key;
int hashi = key(data) % _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
}
但是一个自定义类型是不能进行取模的。所以想到了办法：哈希值。就是先将自定义类型转化成一个哈希值。然后用哈希值去取模找桶。所以哈希桶就有提供了第五个模板参数 Hash。并且，又因为自定义类型是上层使用 unordered_map 和 unordered_set 的人自定义的，所以必须由上层的人提供这个转化策略。继而 unordered_map 和 unordered_set 也都新增了一个模板参数 Hash。这个模板参数就是 unordered_set 或者 unordered_map 接收到上层传过来的转化策略。然后 unordered_map 或者 unordered_set 传给哈希桶，哈希桶就能用这个方法拿到键的哈希值，然后就能找桶了。
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
Find(const Key &key);
Erase(const Key &key);
Insert(const Value &data);
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
struct KeyOfValue {
const K &operator()(const K &key) { return key; }
};
typedef HashBucket<Key, Key, Alloc, KeyOfValue, Hash, ...> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
Insert(const Key &data) { return _ht.Insert(data); }
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
struct KeyOfValue {
const K& operator()(const pair<K, V> &_kv) { return _kv.first; }
};
typedef HashBucket<Key, pair<Key, T>, Alloc, KeyOfValue, Hash, ...> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
Insert(const pair<K, T> &data) { return _ht.Insert(data); }
};
但是，这里还存在一个问题，就是查找的问题。查找要判断一个数据是否存在，就一定会用到比较。这个比较不能用哈希值进行比较。因为哈希值是整形，是有限的，而自定义类型的对象是无限的。所以一定会存在两个不同的自定义类型对象有着相同的哈希值。所以想要查找这个数据存在不存在，还是要用原生类型的比较。这里哈希桶和 unordered_map, unordered_set 都提供了一个模板参数 Pred。就是一个 equal 的仿函数。这里其实也可以直接重载==符号。
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
Find(const Key &key);
Erase(const Key &key);
Insert(const Value &data);
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
struct KeyOfValue {
const K &operator()(const K &key) { return key; }
};
typedef HashBucket<Key, Key, Alloc, KeyOfValue, Hash, Pred, ...> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
Insert(const Key &data) { return _ht.Insert(data); }
};
template<class Key, class T, class Hash, class Pred....>
class unordered_map {
struct KeyOfValue {
const K& operator()(const pair<K, V> &_kv) { return _kv.first; }
};
typedef HashBucket<Key, pair<Key, T>, Alloc, KeyOfValue, Hash, Pred, ...> HT;
HT _ht;
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
Insert(const pair<K, T> &data) { return _ht.Insert(data); }
};
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
