C++ 哈希表通过哈希函数将关键字映射到存储位置，实现高效查找。涵盖哈希概念、冲突处理（开放定址法、链地址法）、哈希函数设计及扩容策略，并提供基于 C++ 的完整代码实现，帮助开发者掌握哈希在实际开发中的应用。
在 C++ 编程中，高效的数据查找和存储是核心需求之一。哈希（Hash）技术凭借其近似 O(1) 的查找效率，成为解决这一需求的重要手段。本文将从哈希的基本概念出发，逐步深入 C++ 中的哈希实现，包括 STL 哈希容器、哈希函数设计、哈希冲突解决等关键知识点，并结合实例帮助大家掌握哈希在实际开发中的应用。
哈希 (hash) 又称散列，是一种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出 Key 存储的位置，进行快速查找。
当关键字的范围比较集中时，直接定址法就是非常简单高效的方法，比如一组关键字都在 [0,99] 之间，那么我们开一个 100 个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在 [a,z] 的小写字母，那么我们开一个 26 个数的数组，每个关键字 ascii 码 - a ascii 码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法我们在计数排序部分已经用过了，其次在 string 章节的下面 OJ 也用过了。
示例：
字符串中的第一个唯一字符 - LeetCode
C++ 代码实现（哈希）：
class Solution {
public:
int firstUniqChar(string s) {
// 每个字母的 ascii 码-'a'的 ascii 码作为下标映射到 count 数组，数组中存储出现的次数
int count[26]={0};
// 统计次数
for(auto ch:s) {
count[ch-'a']++;
}
for(size_t i=0;i<s.size();++i) {
if(count[s[i]-'a']==1) return i;
}
return -1;
}
};
直接定址法的缺点非常明显，当关键字的范围比较分散时，会很浪费内存甚至内存不够用。假设我们只有数据范围是 [0,9999] 的 N 个值，要映射到一个 M 个空间的数组中（一般情况下 M >= N），那么就要借助哈希函数 (hash function) hf，关键字 key 被放到数组的 h(key) 位置，这里要注意的是 h(key) 计算出的值必须在 [0, M) 之间。
这里存在的一个问题就是，两个不同的 key 可能会映射到同一个位置去，这种问题我们叫做哈希冲突，或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。
假设哈希表中已经映射存储了 N 个值，哈希表的大小为 M，那么 负载因子 = N / M，负载因子有些地方也翻译为载荷因子 / 装载因子等，其英文为 load factor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。
我们将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后面代码实现中再进行细节展示。下面哈希函数部分我们讨论时，如果关键字不是整数，那么我们讨论的 Key 是关键字转换成的整数。
一个好的哈希函数应该让 N 个关键字被等概率的均匀的散列分布到哈希表的 M 个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计。
h(key) = key % Mkey % 2^X 本质相当于保留 key 的后 X 位，那么后 x 位相同的值，计算出的哈希值都是一样的，就冲突了。如：{63,31} 看起来没有关联的值，如果 M 是 16（即 2^4），那么计算出的哈希值都是 15，因为 63 的二进制后 8 位是 00111111，31 的二进制后 8 位是 00011111。如果是 10^X，就更明显了，保留的都是 10 进值的后 x 位，如：{112,12312}，如果 M 是 100（即 10^2），那么计算出的哈希值都是 12素数：指大于 1 的自然数中，除了 1 和它本身外，无法被其他自然数整除的数
关键特征：最小的素数是 2，也是唯一的偶数素数。大于 2 的素数都是奇数，但奇数不一定是素数（比如 9 能被 3 整除）。素数的因数只有 1 和它自身，没有其他约数
与哈希函数的关联：
在除法散列法中，哈希表大小 M 取素数，能让关键字的哈希值分布更均匀，减少哈希冲突。这也是你之前学习哈希函数时，M 建议取素数的核心原因
需要说明的是，实践中也是八仙过海，各显神通，Java 的 HashMap 采用除法散列法时就是 2 的整数次幂做哈希表的大小 M，这样不用取模，可直接位运算（位运算比模更高效）。但它不是单纯取模，比如 M 是 2^16，本质是取后 16 位，通过 key' = key>>16，再将 key 和 key'异或的结果作为哈希值，尽量让 key 所有位都参与计算，使哈希值更均匀。所以我们上面建议 M 取质数的理论是多数数据结构书籍的理论，实践中需灵活运用，抓住本质，不可死读书。
实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了冲突，那么插入数据时，如何解决冲突呢？主要有两种方法，开放定址法和链地址法（哈希桶）。
在开放定址法中所有的元素都放到哈希表里，当一个关键字 key 用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于 1 的。这里的规则有三种：线性探测、二次探测、双重探测。
从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。
线性探测的比较简单且容易实现，线性探测的问题假设，hash0 位置连续冲突，hash0，hash1，hash2 位置已经存储数据了，后续映射到 hash0，hash1，hash2，hash3 的值都会争夺 hash3 位置，这种现象叫做群集 / 堆积。下面的二次探测可以一定程度改善这个问题。
如果我们要将一些数存放到哈希表中例如：{19,30,5,36,13,20,21,12}
我们就可以发现 30 与 19 发生哈希冲突，30 只能放到下标为 9 的位置，然后 20 又与 30 发生冲突.......这样造成的连续哈希冲突，我们就叫作群集 / 堆积。
那么如何解决呢？接下来讲解二次探测。
开放定址法在实践中，不如下面讲的链地址法，因为开放定址法解决冲突不管使用哪种方法，占用的都是哈希表中的空间，始终存在互相影响的问题。所以开放定址法，我们简单选择线性探测实现即可。
enum State { EXIST, EMPTY, DELETE };
template<class K, class V> struct HashData {
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K, class V> class HashTable {
private:
vector<HashData<K, V>> _tables;
size_t _n = 0; // 表中存储数据个数
};
要注意的是这里需要给每个存储值的位置加一个状态标识，否则删除一些值以后，会影响后面冲突的值的查找。如下图，我们删除 30，会导致查找 20 失败，当我们给每个位置加一个状态标识 {EXIST,EMPTY,DELETE}，删除 30 就可以不用删除值，而是把状态改为 DELETE，那么查找 20 时是遇到 EMPTY 才能，就可以找到 20。
这里我们哈希表负载因子控制在 0.7，当负载因子到 0.7 以后我们就需要扩容了，我们还是按照 2 倍扩容，但是同时我们要保持哈希表大小是一个质数，第一个是质数，2 倍后就不是质数了。那么如何解决了，一种方案就是上面 2.1 除法散列中我们讲的 Java HashMap 的使用 2 的整数次幂，但是计算时不能直接取模的改进方法。另外一种方案是 sgi 版本的哈希表使用的方法（我们要讲解的版本），给了一个近似 2 倍的质数表，每次去质数表获取扩容后的大小。
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;
// >= n
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
当 key 是 string/Date 等类型时，key 不能取模，那么我们需要给 HashTable 增加一个仿函数，这个仿函数支持把 key 转换成一个可以取模的整形，如果 key 可以转换为整形并且不容易冲突，那么这个仿函数就用默认参数即可，如果这个 Key 不能转换为整形，我们就需要自己实现一个仿函数传给这个参数，实现这个仿函数的要求就是尽量 key 的每值都参与到计算中，让不同的 key 转换出的整形值不同。string 做哈希表的 key 非常常见，所以我们可以考虑把 string 特化一下。
template<class K> struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
// 特化
template<> struct HashFunc<string> {
// 字符串转换成整形，可以把字符 ascii 码相加即可
// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
// 这里我们使用 BKDR 哈希的思路，用上次的计算结果去乘以一个质数，
// 这个质数一般去 31, 131 等效果会比较好
size_t operator()(const string& key) {
size_t hash = 0;
for (auto ch : key) {
hash += ch;
hash *= 131;
}
return hash;
}
};
template<class K, class V, class Hash = HashFunc<K>> class HashTable {
public:
private:
vector<HashData<K, V>> _tables;
size_t _n = 0; // 表中存储数据个数
};
开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。
链地址法本质就是：完全避免哈希冲突
⚠️思考：链地址法这么好用，为什么还要学习开放地址发，直接学开放地址法不就行了吗，那么链地址法就真的没有弊端吗？
示例：将{19,30,5,36,13,20,21,12,24,96}插入到 M=11 的表中
开放定址法负载因子必须小于 1，链地址法的负载因子没有限制，可以大于 1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；stl 中 unordered_xxx 的最大负载因子基本控制在 1，大于 1 就扩容，我们下面实现也使用这个方式。
思考：哈希表如果扩容了，那么原来在同一个桶里挂的节点还在一起吗？
如果极端场景下，某个桶特别长怎么办？其实我们可以考虑使用全域散列法，这样就不容易被针对了。但假设不是被针对，用了全域散列法，却偶然出现某个桶很长、查找效率很低的情况怎么办？在 Java8 的 HashMap 中，当桶的长度超过阈值 (8) 时，会把链表转换成红黑树。一般情况下，不断扩容后单个桶很长的场景比较少，下面我们实现时不搞这么复杂，大家了解这个解决极端场景的思路即可。
哈希桶有一个缺点：当我们插入的数据越来越多的时候，它会突然有波动，而随着数据越来越多，这种波动就会越来越剧烈。
template<class T> struct HashNode {
T _data;
HashNode<T>* _next;
HashNode(const T& data) :_data(data) , _next(nullptr) { }
};
pair<Iterator, bool> Insert(const T& data) {
KeyOfT kot;
if (auto it = Find(kot(data)); it != End()) return { it, false };
Hash hs;
// 负载因子 == 1 就开始扩容
if (_n == _tables.size()) {
std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
for (size_t i = 0; i < _tables.size(); i++) {
// 遍历旧表，旧表节点重新映射，挪动到新表
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
// 头插
size_t hashi = hs(kot(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(kot(data)) % _tables.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return { Iterator(newnode, this), true };
}
Iterator Find(const K& key) {
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) {
return { cur, this };
}
cur = cur->_next;
}
return { nullptr, this };
}
bool Erase(const K& key) {
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) {
// 删除
if (prev == nullptr) {
// 桶中第一个节点
_tables[hashi] = cur->_next;
} else {
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
#include<vector>
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;
// >= n
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
template<class K> struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
// 特化
template<> struct HashFunc<string> {
// 字符串转换成整形，可以把字符 ascii 码相加即可
// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
// 这里我们使用 BKDR 哈希的思路，用上次的计算结果去乘以一个质数，
// 这个质数一般去 31, 131 等效果会比较好
size_t operator()(const string& key) {
size_t hash = 0;
for (auto ch : key) {
hash += ch;
hash *= 131;
}
return hash;
}
};
namespace hash_bucket {
template<class T> struct HashNode {
T _data;
HashNode<T>* _next;
HashNode(const T& data) :_data(data) , _next(nullptr) { }
};
// 前置声明
template<class K, class T, class KeyOfT, class Hash> class HashTable;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> struct HTIterator {
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const HT* _pht;
HTIterator(Node* node, const HT* pht) :_node(node) , _pht(pht) { }
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
Self& operator++() {//9:11
if (_node->_next) // 当前桶没走完
{
_node = _node->_next;
} else // 当前桶走完了，找到下一个桶的第一个节点
{
KeyOfT kot;
Hash hs;
// 算出当前桶的位置
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
++hashi;
while (hashi < _pht->_tables.size()) {
if (_pht->_tables[hashi]) // 找到下一个不为空的桶
{
_node = _pht->_tables[hashi];
break;
} else {
++hashi;
}
}
if (hashi == _pht->_tables.size()) // 最后一个桶走完了，要++到 end() 位置
{
// end() 中_node 是空
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s) const { return _node != s._node; }
bool operator==(const Self& s) const { return _node == s._node; }
};
// hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
// hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
template<class K, class T, class KeyOfT, class Hash> class HashTable {
// 友元声明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct HTIterator;
typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
Iterator Begin() {
if (_n == 0) { return End(); }
for (size_t i = 0; i < _tables.size(); i++) {
if (_tables[i]) { return Iterator(_tables[i], this); }
}
return End();
}
Iterator End() { return Iterator(nullptr, this); }
ConstIterator Begin() const {
if (_n == 0) { return End(); }
for (size_t i = 0; i < _tables.size(); i++) {
if (_tables[i]) { return ConstIterator(_tables[i], this); }
}
return End();
}
ConstIterator End() const { return Iterator(nullptr, this); }
HashTable() :_tables(__stl_next_prime(1), nullptr) , _n(0) { }
~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[i] = nullptr;
}
_n = 0;
}
pair<Iterator, bool> Insert(const T& data) {
KeyOfT kot;
if (auto it = Find(kot(data)); it != End()) return { it, false };
Hash hs;
// 负载因子 == 1 就开始扩容
if (_n == _tables.size()) {
std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
for (size_t i = 0; i < _tables.size(); i++) {
// 遍历旧表，旧表节点重新映射，挪动到新表
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
// 头插
size_t hashi = hs(kot(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(kot(data)) % _tables.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return { Iterator(newnode, this), true };
}
Iterator Find(const K& key) {
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) {
return { cur, this };
}
cur = cur->_next;
}
return { nullptr, this };
}
bool Erase(const K& key) {
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) {
// 删除
if (prev == nullptr) {
// 桶中第一个节点
_tables[hashi] = cur->_next;
} else {
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
std::vector<Node*> _tables; // 指针数组
size_t _n;
// std::vector<std::list<K, V>> _tables;
};
}
#include<iostream>
#include<unordered_map>
using namespace std;
#include"HashTable.h"
void Print(const hash_bucket::HashTable<int, int>& s) {
hash_bucket::HashTable<int, int>::Iterator it = s.Begin();
while (it != s.End()) {
cout << *it << " ";
++it;
}
cout << endl;
}
int main() {
hash_bucket::HashTable<int, int> us;
us.Insert(3);
us.Insert(1000);
us.Insert(2);
us.Insert(102);
us.Insert(2111);
us.Insert(22);
hash_bucket::HashTable<int, int>::Iterator it = us.Begin();
while (it != us.End()) {
cout << *it << " ";
++it;
}
cout << endl;
Print(us);
hash_bucket::HashTable<string, string> dict;
dict.Insert({ "string", "字符串" });
dict.Insert({ "left", "左边" });
dict.Insert({ "right", "右边" });
dict.Insert({ "map", "图" });
for (auto& [k, v] : dict) {
cout << k << ":" << v << endl;
}
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online