跳到主要内容 哈希表详解:概念、冲突解决与 C++ 实现 | 极客日志
C++ 算法
哈希表详解:概念、冲突解决与 C++ 实现 哈希表的基本概念,包括直接定址法、哈希冲突的定义及负载因子的影响。详细讲解了两种主要的冲突解决机制:开放定址法(线性探测、二次探测、双重探测)及其删除问题处理,以及链地址法(拉链法)的原理与优势。最后提供了基于 C++ 模板实现的链地址法哈希表完整代码,包含插入、查找、删除、扩容等功能,并辅以测试用例演示。
SqlMaster 发布于 2026/3/30 更新于 2026/4/13 3 浏览一。哈希表的概念
哈希又称散列,本质是通过一种键值对存储的高效组织方式。通过一个哈希函数,将数据的关键字直接映射到存储的数据中,实现快速的定位。
就像在图书馆中可以根据图书的编号来快速查找图书的位置。
二。直接定址法
直接借用关键字作为存储位置的下标。
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,超过则扩容。
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法(如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) {
Hash hash;
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 () {
hash_bucket::HashTable<string, 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 ;
}
注:哈希表的冲突和扩容需要结合具体的情况来解决!!!