跳到主要内容 哈希表原理、冲突解决与 C++ 实现 | 极客日志
C++ 算法
哈希表原理、冲突解决与 C++ 实现 哈希表通过键值对存储实现快速定位，核心在于哈希函数设计与冲突解决。常见冲突解决方法包括开放定址法（线性探测、二次探测、双重探测）和链地址法。负载因子影响性能，链地址法因实现简单且支持高负载被广泛使用，如 STL unordered_map。文章详细讲解了哈希表原理、冲突处理机制，并提供了基于 C++ 的链地址法完整代码实现，涵盖插入、查找、删除及扩容逻辑。
全栈工匠 发布于 2026/3/22 更新于 2026/4/23 一、哈希表的概念
哈希又称散列，本质是通过一种键值对存储的高效组织方式。通过一个哈希函数，将数据的关键字直接映射到存储的数据中，实现快速的定位。
就像在图书馆中可以根据图书的编号来快速查找图书的位置。
二、直接定址法
直接借用关键字作为存储位置的下标，
class Solution {
public :
int first (string s) int count[26 ] = { 0 };
for (auto e : s) {
count[e - 'a' ]++;
}
for (size_t i = 0 ; i < s.size (); i++) {
if (count[s[i] - 'a' ] == 1 ) {
return i;
}
}
return -1 ;
}
};
注：查找数组中唯一出现的字符，字符只有 26 个，直接定义一个数组来记录每个字母出现的次数。
如果数据集中，没有哈希冲突，而且效率高，但是数据如果分散，会造成数据的浪费，甚至内存浪费。
三、哈希冲突
在使用哈希函数进行映射的时候，不可避免地会出现两个不同的关键字映射到同一个下标的情况，这就是哈希冲突。
比如：用'关键字对 11 取模'作为哈希函数（M=11），关键字 19 和 30 的计算结果都是 8（19%11=8，30%11=8），这就产生了冲突。
理想情况下，我们希望哈希函数能让关键字均匀分布在数组中，减少冲突，但实际场景中冲突无法完全避免——就像图书馆的书架位置有限，总会有新书的编号对应已被占用的位置。因此，哈希表的设计核心包含两部分：
设计优秀的哈希函数，减少冲突次数；
设计高效的冲突解决机制，处理已发生的冲突。
我们还要介绍一下负载因子：
是衡量哈希表拥挤程度的核心指标，直接影响冲突概率。
负载因子 α = 哈希表中存储的元素个数（N） / 哈希表的数组大小（M）
负载因子与哈希表性能的关系是：
α 越大：哈希表越拥挤，冲突概率越高，查询效率越低；
α 越小：哈希表越宽松，冲突概率越低，但空间利用率越低。
不同冲突解决机制对应的负载因子阈值不同：
开放定址法：α 必须小于 1（因为所有元素都存储在数组中，数组满了就无法插入）；
链地址法：α 可以大于 1（冲突元素会以链表形式挂在数组下标下），STL 的 unordered_map 默认将 α 阈值设为 1，超过则扩容。
四、哈希冲突解决：当关键字'撞车'了怎么办？
相关免费在线工具 加密/解密文本 使用加密算法（如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
无论哈希函数设计得多优秀，冲突都无法完全避免。实战中处理哈希冲突的核心方法有两种：开放定址法和链地址法（拉链法）。其中链地址法因实现简单、性能稳定，被广泛应用于 STL 的 unordered_map、Java 的 HashMap 等容器中。
开放定址法的核心逻辑是：所有元素都存储在哈希表的数组中，当某个关键字的哈希位置被占用时，按照某种规则在数组中寻找下一个空位置存储。
它的约束是：负载因子 α 必须小于 1（数组不能满，否则没有空位可找）。常用的寻找规则有三种：线性探测、二次探测、双重探测。
用哈希函数计算初始位置 hash0 = Key % M；
如果 hash0 被占用，依次探测 hash0+1、hash0+2、…，直到找到空位置；
若探测到数组末尾，回绕到数组开头继续探测（循环探测）。
数学表达式为：h_i(Key) = (hash0 + i) % M（i=1,2,...,M-1）
假设 M=11（数组下标 0-10），关键字集合 {19,30,5,36,13,20,21,12}：
19%11=8 → 下标 8（空，存储 19）；
30%11=8 → 下标 8（被占用，探测 9→空，存储 30）；
5%11=5 → 下标 5（空，存储 5）；
36%11=3 → 下标 3（空，存储 36）；
13%11=2 → 下标 2（空，存储 13）；
20%11=9 → 下标 9（被占用，探测 10→空，存储 20）；
21%11=10 → 下标 10（被占用，探测 0→空，存储 21）；
12%11=1 → 下标 1（空，存储 12）。
最终数组存储结果（下标 0-10）：21、12、13、36、空、5、空、空、19、30、20。
线性探测的缺点是很明显的：如果某个区域的位置被连续占用，后续冲突的关键字都会往这个区域聚集，形成'群集'（比如下标 8、9、10 被占用后，后续映射到这些下标的关键字都会探测下标 0）。群集会导致探测次数增多，查询效率下降。
二次探测的核心是通过平方数跳跃探测，避免线性探测的群集问题。规则是：
初始位置 hash0 = Key % M；
若 hash0 被占用，依次探测 hash0+1²、hash0-1²、hash0+2²、hash0-2²、…；
探测范围限制在 i ≤ M/2（避免重复探测），若探测到负数或超出数组范围，需调整到 [0, M-1] 区间。
数学表达式为：h_i(Key) = (hash0 ± i²) % M（i=1,2,...,M/2）
假设 M=11，关键字集合 {19,30,52,63,11,22}：
19%11=8 → 下标 8（空，存储 19）；
30%11=8 → 探测 8+1²=9（空，存储 30）；
52%11=8 → 探测 8+1²=9（被占用）→ 8-1²=7（空，存储 52）；
63%11=8 → 探测 8+1²=9（被占用）→ 8-1²=7（被占用）→ 8+2²=12→1（空，存储 63）；
11%11=0 → 下标 0（空，存储 11）；
22%11=0 → 探测 0+1²=1（被占用）→ 0-1²=-1→10（空，存储 22）。
二次探测能有效减少群集，但无法完全避免 —— 如果关键字的哈希值分布不均匀，仍可能出现局部群集。
双重探测（也叫双散列）的核心是用第二个哈希函数计算探测的偏移量，让探测路径更分散。规则是：
第一个哈希函数计算初始位置 hash0 = h1(Key) = Key % M；
第二个哈希函数计算偏移量 step = h2(Key)（要求 step < M 且与 M 互质）；
若 hash0 被占用，依次探测 hash0+step、hash0+2×step、…，直到找到空位置。
数学表达式为：h_i(Key) = (hash0 + i×h2(Key)) % M（i=1,2,...,M-1）
h2(Key) 必须与 M 互质（最大公约数为 1），否则探测路径会局限在部分位置，无法遍历整个数组。常用的 h2(Key) 设计：
当 M 为 2 的整数次幂时，h2(Key) 取奇数（奇数与 2 的整数次幂互质）；
当 M 为质数时，h2(Key) = Key % (M-1) + 1（确保 step 在 [1, M-1] 之间，且与 M 互质）。
示例演示
假设 M=11（质数），h2(Key)=Key%10+1，关键字集合 {19,30,52,74}：
19%11=8 → 下标 8（空，存储 19）；
30%11=8 → step=30%10+1=1 → 探测 8+1=9（空，存储 30）；
52%11=8 → step=52%10+1=3 → 探测 8+3=11→0（空，存储 52）；
74%11=8 → step=74%10+1=5 → 探测 8+5=13→2（空，存储 74）。
双重探测的探测路径最分散，能最大程度避免群集，是开放定址法中性能最优的方案，但实现相对复杂。
开放定址法的一个关键问题是删除元素不能直接置空—— 如果直接将某个位置置空，后续探测该位置的关键字会误以为'前面没有冲突元素'，导致查找失败。
比如前面的线性探测示例中，若删除下标 9 的 30，直接将下标 9 置空，后续查找 20 时，探测到下标 9 为空就会停止，无法找到下标 10 的 20。
EMPTY：初始状态，该位置从未存储过元素；
EXIST：该位置当前存储着元素；
DELETE：该位置的元素已被删除，可重新存储。
查找时，只有遇到 EMPTY 状态才停止探测；删除时，将状态改为 DELETE 而非置空；插入时，可将元素存储到 DELETE 或 EMPTY 状态的位置。
链地址法是实战中最常用的冲突解决机制，STL 的 unordered_map、Java 的 HashMap 都采用这种方式。它的核心逻辑是：
哈希表的底层是一个指针数组（桶数组），每个元素是一个链表的头指针；
用哈希函数计算关键字的桶下标（hash = Key % M）；
若该桶为空，直接将元素作为链表头节点插入；
若该桶已有关键字（冲突），将元素插入到链表的头部或尾部。
简单说，链地址法是将冲突的关键字'串成链表'，挂在对应的桶下面，因此也叫'哈希桶'。
假设 M=11，关键字集合 {19,30,5,36,13,20,21,12,24,96}：
19%11=8 → 桶 8 链表：19；
30%11=8 → 桶 8 链表：30 → 19；
5%11=5 → 桶 5 链表：5；
36%11=3 → 桶 3 链表：36；
13%11=2 → 桶 2 链表：13；
20%11=9 → 桶 9 链表：20；
21%11=10 → 桶 10 链表：21；
12%11=1 → 桶 1 链表：12；
24%11=2 → 桶 2 链表：24 → 13；
96%11=8 → 桶 8 链表：96 → 30 → 19。
最终桶数组结构如下（下标 0-10）：
无群集问题：冲突元素只在各自的链表中存储，不影响其他桶；
负载因子可大于 1：链表可以无限延长（理论上），无需严格限制负载因子；
删除简单：直接删除链表节点即可，无需状态标识；
空间利用率高：桶数组可以按需扩容，链表节点只在有冲突时创建。
链地址法的唯一缺点是：如果某个桶的链表过长（比如恶意攻击或关键字分布极端），查询效率会降至 O(n)。为了解决这个问题，Java 8 的 HashMap 引入了优化：当链表长度超过阈值（默认 8）时，将链表转换为红黑树，查询效率提升至 O(log n)。
STL 的 unordered_map 没有这个优化，因为它假设哈希函数足够优秀，链表过长的场景极少发生。实际开发中，只要哈希函数设计合理，无需额外处理。
五、实现链地址法 #include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
template <class K >
struct HashFunc {
size_t operator () (const K& key) return (size_t )key;
}
};
template <>
struct HashFunc <string> {
size_t operator () (const string& key) size_t hash = 0 ;
for (auto ch : key) {
hash = hash * 131 + ch;
}
return hash;
}
};
namespace hash_bucket {
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 , class V , class Hash = HashFunc<K>>
class HashTable {
private :
typedef HashNode<K, V> Node;
vector<Node*> _tables;
size_t _n = 0 ;
static const unsigned long __stl_prime_list[];
static const int __stl_num_primes;
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;
}
public :
HashTable () {
_tables.resize (__stl_next_prime(0 ), 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[i] = nullptr ;
}
}
bool Insert (const pair<K, V>& kv) if (Find (kv.first) != nullptr ) {
return false ;
}
if (_n == _tables.size ()) {
size_t newSize = __stl_next_prime(_tables.size () + 1 );
vector<Node*> newTables (newSize, nullptr ) ;
Hash hash;
for (size_t i = 0 ; i < _tables.size (); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hash (cur->_kv.first) % newTables.size ();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr ;
}
_tables.swap (newTables);
}
Hash hash;
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) {
Hash hash;
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) size_t hashi = hash (key) % _tables.size ();
Node* prev = nullptr ;
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key) {
if (prev == nullptr ) {
_tables[hashi] = cur->_next;
} else {
prev->_next = cur->_next;
}
delete cur;
--_n;
return true ;
}
prev = cur;
cur = cur->_next;
}
return false ;
}
size_t Size () const return _n;
}
bool Empty () const return _n == 0 ;
}
void Print () for (size_t i = 0 ; i < _tables.size (); ++i) {
cout << "桶" << i << ": " ;
Node* cur = _tables[i];
while (cur) {
cout << cur->_kv.first << "→" << cur->_kv.second << " " ;
cur = cur->_next;
}
cout << endl;
}
cout << "当前元素个数：" << _n << endl;
cout << "当前负载因子：" << (double )_n / _tables.size () << endl;
}
HashTable (const HashTable&) = delete ;
HashTable& operator =(const HashTable&) = delete ;
};
template <class K , class V , class Hash >
const unsigned long HashTable<K, V, Hash>::__stl_prime_list[] = {
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
};
template <class K , class V , class Hash >
const int HashTable<K, V, Hash>::__stl_num_primes = sizeof (__stl_prime_list) / sizeof (__stl_prime_list[0 ]);
}
int main () int > ht;
ht.Insert ({"apple" , 10 });
ht.Insert ({"banana" , 20 });
ht.Insert ({"orange" , 30 });
ht.Insert ({"grape" , 40 });
ht.Insert ({"pear" , 50 });
ht.Insert ({"watermelon" , 60 });
ht.Insert ({"pineapple" , 70 });
cout << "插入后哈希表：" << endl;
ht.Print ();
cout << endl;
auto orange = ht.Find ("orange" );
if (orange) {
cout << "查找 orange：" << orange->_kv.first << " → " << orange->_kv.second << endl;
} else {
cout << "查找 orange：未找到" << endl;
}
auto peach = ht.Find ("peach" );
if (peach) {
cout << "查找 peach：" << peach->_kv.first << " → " << peach->_kv.second << endl;
} else {
cout << "查找 peach：未找到" << endl;
}
cout << endl;
bool ret = ht.Erase ("grape" );
cout << "删除 grape：" << (ret ? "成功" : "失败" ) << endl;
cout << "删除后哈希表：" << endl;
ht.Print ();
cout << endl;
ret = ht.Insert ({"apple" , 15 });
cout << "插入重复的 apple：" << (ret ? "成功" : "失败" ) << endl;
cout << "最终哈希表：" << endl;
ht.Print ();
return 0 ;
}
注：哈希表的冲突和扩容需要结合具体的情况来解决！！！
