跳到主要内容C++ 哈希表核心原理与 STL 实现解析 | 极客日志C++算法
C++ 哈希表核心原理与 STL 实现解析
哈希表是 C++ STL 中 unordered_map 和 unordered_set 的底层数据结构，以 O(1) 平均时间复杂度提供高效的查找能力。文章详细解析了哈希函数的设计原则、冲突处理策略（开放定址法与链地址法）以及扩容机制。通过对比 set/map 与 unordered_set/unordered_map 的差异，结合 C++ 源码实现，深入探讨了负载因子、质数扩容及哈希仿函数的具体应用，为高性能数据结构选型提供理论支撑与实践参考。
C++ 哈希表核心原理与 STL 实现解析
unordered_map 和 unordered_set 的使用
在深入哈希表底层之前，先对比一下 C++ STL 中常用的容器。unordered_map 和 unordered_set 基于哈希表实现，而 map 和 set 基于红黑树。
unordered_set 类介绍
unordered_set 与 set 功能高度相似，但底层结构不同。它默认要求 Key 支持转换为无符号整型且支持相等比较。如果 Key 类型不支持（如自定义结构体），需要自行实现仿函数传入模板参数。
template<class Key,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator<Key>>
class unordered_set;
底层使用哈希桶实现，增删查平均效率为 O(1)。迭代器遍历无序，因此命名为 unordered_set。
unordered_set 与 set 的差异
- Key 的要求：
set 要求 Key 支持小于比较；unordered_set 要求 Key 支持转成整形且支持等于比较。
- 迭代器差异：
set 是双向迭代器，遍历有序；unordered_set 是单向迭代器，遍历无序。
- 性能差异：整体而言，
unordered_set 的增删查改更快。红黑树操作复杂度为 O(logN)，而哈希表平均为 O(1)。
以下代码演示了两者在插入、查找和删除上的性能对比：
#include <unordered_set>
#include <set>
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
int test_set_performance() {
N = ;
unordered_set<> us;
set<> s;
vector<> v;
v.(N);
(());
( i = ; i < N; ++i) {
v.(() + i);
}
begin1 = ();
( e : v) s.(e);
end1 = ();
cout << << end1 - begin1 << endl;
begin2 = ();
us.(N);
( e : v) us.(e);
end2 = ();
cout << << end2 - begin2 << endl;
m1 = , m2 = ;
begin3 = ();
( e : v) { (s.(e) != s.()) ++m1; }
end3 = ();
cout << << end3 - begin3 << << m1 << endl;
begin4 = ();
( e : v) { (us.(e) != us.()) ++m2; }
end4 = ();
cout << << end4 - begin4 << << m2 << endl;
;
}
{
();
;
}
const
size_t
1000000
int
int
int
reserve
srand
time
0
for
size_t
0
push_back
rand
size_t
clock
for
auto
insert
size_t
clock
"set insert: "
size_t
clock
reserve
for
auto
insert
size_t
clock
"unordered_set insert: "
int
0
0
size_t
clock
for
auto
if
find
end
size_t
clock
"set find: "
"->"
size_t
clock
for
auto
if
find
end
size_t
clock
"unordered_set find: "
"->"
return
0
int main()
test_set_performance
return
0
unordered_map 与 map 的差异
逻辑与上述类似。map 底层是红黑树，Key 有序；unordered_map 底层是哈希表，Key 无序。性能上 unordered_map 通常更优，除非你需要有序的 Key。
哈希表实现原理
既然 unordered_map/set 底层是哈希表，那么它是如何实现 O(1) 效率的呢？
哈希概念
哈希（Hash）又称散列，是一种组织数据的方式。本质是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系。查找时通过该函数计算出 Key 存储的位置，进行快速查找。
直接定址法
当关键字范围比较集中时，直接定址法非常高效。例如关键字都在 [0, 99] 之间，开一个 100 个数的数组，下标即为关键字值。
class Solution {
public:
int firstUniqChar(string s) {
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;
}
};
总结：直接定址法简洁高效，但受限于数据集中程度，离散数据会导致空间浪费。
哈希冲突
当关键字范围分散时，不同的 Key 可能会映射到同一个位置，这就是哈希冲突。理想情况是避免冲突，但实际场景中冲突不可避免，我们需要设计优秀的哈希函数减少冲突，并制定解决冲突的方案。
负载因子
假设哈希表中已存储 N 个值，大小为 M，则负载因子 α = N / M。
- 负载因子越大，冲突概率越高，空间利用率越高。
- 负载因子越小，冲突概率越低，空间利用率越低。
将关键字转为整数
为了映射到数组位置，通常需要将 Key 转为整数。对于非整数类型（如 string），需要自定义仿函数将其转换为可取模的整形。
哈希函数设计
一个好的哈希函数应让 N 个关键字均匀分布到 M 个空间中。
除法散列法
公式：h(key) = key % M。建议 M 取不太接近 2 的整数次幂的质数，以避免低位冲突。
乘法散列法
公式：h(key) = floor(M × ((A × key)%1.0))，其中 A 常取黄金分割点 0.618。对 M 没有特殊要求。
哈希防御措施：全域散列
为防止恶意构造数据导致严重冲突，可采用全域散列。每次初始化哈希表时随机选取一个散列函数，增加随机性。
开放定址法
所有元素都放入哈希表内。发生冲突时，按规则寻找下一个空位。负载因子必须小于 1。
- 线性探测：依次向后探测。易产生'群集'现象。
- 二次探测：左右跳跃式探测，改善群集问题。
开放定址法代码实现
需要给每个位置添加状态标识（EXIST, EMPTY, DELETE），否则删除节点会影响后续查找。
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 HashFunc = HashFunc<K>>
class HashTable {
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
HashFunc _hash_func;
inline unsigned long __stl_next_prime(unsigned long n) {
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
};
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;
}
public:
HashTable() : _tables(__stl_next_prime(0)), _n(0) {}
bool insert(const pair<K, V>& kv) {
if (Find(kv.first)) return false;
if (_n * 10 / _tables.size() >= 7) {
HashTable newht;
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
for (auto& e : _tables) {
if (e._state == EXIST) newht.insert(e._kv);
}
_tables.swap(newht._tables);
}
size_t hash0 = _hash_func(kv.first) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state == EXIST) {
hashi = (hash0 + i) % _tables.size();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
HashData<K, V>* Find(const K& key) {
size_t hash0 = _hash_func(key) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state != EMPTY) {
if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key) {
return &_tables[hashi];
}
hashi = (hash0 + i) % _tables.size();
i++;
}
return nullptr;
}
bool erase(const K& key) {
HashData<K, V>* ret = Find(key);
if (!ret) return false;
ret->_state = DELETE;
return true;
}
};
链地址法
链地址法（拉链法）中，哈希表存储指针，冲突的数据链接成链表挂在对应位置下。
template<class T>
struct Bucket_Node {
T _data;
Bucket_Node<T>* _next;
Bucket_Node(const T& data) : _data(data), _next(nullptr) {}
};
template<class K, class T, class KeyOfT, class HashFunc>
class hash_bucket {
private:
size_t _n = 0;
vector<Bucket_Node<T>*> _tables;
HashFunc _hash_func;
KeyOfT _key_of_t;
inline unsigned long __stl_next_prime(unsigned long n) {
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
};
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;
}
public:
hash_bucket() : _n(0), _tables(__stl_next_prime(0)) {}
~hash_bucket() {
for (size_t i = 0; i < _tables.size(); i++) {
Bucket_Node<T>* cur = _tables[i];
while (cur) {
Bucket_Node<T>* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
bool insert(const T& data) {
if (_n / _tables.size() >= 1) {
vector<Bucket_Node<T>*> newtables(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++) {
Bucket_Node<T>* cur = _tables[i];
while (cur) {
Bucket_Node<T>* next = cur->_next;
size_t hashi = _hash_func(_key_of_t(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = _hash_func(_key_of_t(data)) % _tables.size();
Bucket_Node<T>* newnode = new Bucket_Node<T>(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
bool erase(const K& key) {
size_t hashi = _hash_func(key) % _tables.size();
Bucket_Node<T>* prev = nullptr;
Bucket_Node<T>* cur = _tables[hashi];
while (cur) {
if (_key_of_t(cur->_data) == key) {
if (prev) prev->_next = cur->_next;
else _tables[hashi] = cur->_next;
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
};
链地址法在实践中比开放定址法更常用，因为它解决了冲突占用空间的问题，且扩容更容易处理。
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，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
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
