跳到主要内容
哈希表原理与哈希桶实现详解 | 极客日志
C++ 算法
哈希表原理与哈希桶实现详解 综述由AI生成 哈希表的基本概念、哈希函数的设计方法（包括除留余数法、乘法散列法和全域散列法）以及哈希冲突的处理策略。内容涵盖直接定址法、负载因子定义、关键字转换等基础理论，并深入对比了开放定址法（线性探测、二次探测）与链地址法（哈希桶）的实现差异。文章提供了 C++ 模板实现的完整代码示例，展示了哈希表的插入、查找、删除及扩容机制，特别强调了链地址法在实际工程中减少堆积问题的优势。
花里胡哨 发布于 2026/3/23 更新于 2026/5/9 前言
在数据结构中，哈希表是兼顾时间与空间效率的经典方案，它以近乎 O(1) 的读写性能，成为缓存、数据库等场景的核心支撑。本文将从底层原理到实战应用，拆解哈希表的设计逻辑与工程价值。
一、哈希概念
哈希 (hash) 又称散列，是一种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出 Key 存储的位置，进行快速查找。
二、直接定址法
当关键字的范围比较集中时，直接定址法就是非常简单高效的方法，比如一组关键字都在 [0,99] 之间，那么我们开一个 100 个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字都在 [a,z] 的小写字母，那么我们开一个 26 个数的数组，每个关键字 ascii 码就是存储位置的下标，也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法在我们计数排序部分已经用过了，其次在 string 章节的下面 OJ 也用过了。
字符串中的第一个唯一字符（leetcode）
class Solution {
public :
int firstUniqChar (string s) int array[26 ] = {0 };
for (auto & ch : s){
array[ch-'a' ]++;
}
for (size_t i = 0 ; i<s.size ();i++){
if (array[s[i]-'a' ]){
return i;
}
}
return -1 ;
}
};
三、必会概念
3.1 哈希冲突
直接定址法的缺点非常明显，当关键字比较分散时，就很浪费内存空间。假设我们只有数据范围时 [0,9999] 的 N 个值，用直接定址法就很浪费空间。那么我们就要借助哈希函数 (hash function) hf，关键字 key 被放到数据的 h(key) 位置，这里要注意的是 h(key) 计算出的值必须在 [0,M)（左闭右开）之间。
这里存在的一个问题就是，两个不同的 key 可能会映射到同一个位置去，这种问题我们叫做哈希冲突 或哈希碰撞 。理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。
3.2 负载因子 假设哈希表中已经映射存储了 N 个值，哈希表的大小为 M，那么负载因子=N/M，英文名为 load factor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。
就拿上面讲解哈希冲突例子举例，原先数组有 6 个，哈希表的大小为 8，所以负载因子为 6/8，也就是 0.75。但是其存在哈希冲突 (10 与 2)，其空间利用率还是挺高的，但是哈希冲突的概率也随之上升。
3.3 将关键字转为整数 我们将关键字映射到数组中位置，一般要转为整数才好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节后续会详细讲解。
四、哈希函数 一个好的哈希函数应该让 N 个关键字被等概率地均匀散列分布到哈希表的 M 个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计。
4.1 除留余数法
除留余数法，顾名思义，假设哈希表的大小为 M，那么通过 key 除以 M 的余数作为映射位置的下标，也就是哈希函数：h(key) = key%M。
当使用除留余数法时，要尽量避免 M 为某些值，如 2 的幂，10 的幂等。如果是 2 的 x 次方，那么 key%(2 的 x 次方) 本质相当于保留 key 的后 x 位，那么后 x 位相同的值，计算出的哈希值就是一样的，就冲突了。如：{63，31} 看起来没有任何关联的值，如果 M 是 16，也就是2 的 4 次方 ，那么计算出的值都是 15（63%16 = 15，31%16=15），因为 63 的二进制的后 8 位是 00111111，31 的二进制后 8 位是 00011111（后 4 位均是 1111，所以取模后都相同 ）。如果 M 是 10 的 x 次方，就更明显了，保留的都是 10 进制的后 x 位，如{112，12312}，如果 M 是 100，也就是 10 的 2 次方，那么计算出的哈希值都是 12。（两者后两位均为 12 ）
4.2 乘法散列法（了解）
乘法散列法对哈希表大小 M 没有要求，它的大思路第一步：用关键字 K 乘上常数 A (0<A<1)，并抽取出 kA 的小数部分。第二步：后再用 M 乘以 k A 的小数部分，再向下取整。
h(key) = floor(M × ((A × key)%1.0)),其中 floor 标识对表达式进行向下取整，A∈(0,1)，这⾥最重要的是 A 的值应该如何设定，Knuth 认为 (A = ( (根号 5) − 1)/2 = 0.6180339887…黄⾦分割点) 比较好。
乘法散列法对哈希表⼤⼩ M 是没有要求的，假设 M 为 1024，key 为 1234，A = 0.6180339887, Akey= 762.6539420558，取⼩数部分为 0.6539420558,M×((A×key)%1.0)=0.6539420558 1024=669.6366651392，那么 h(1234) = 669。
4.3 全域散列法（了解）
如果存在⼀个恶意的对⼿，他针对我们提供的散列函数，特意构造出⼀个发⽣严重冲突的数据集，⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决⽅法⾃然是见招拆招，给散列函数增加随机性，攻击者就⽆法找出确定可以导致最坏情况的数据。这种⽅法叫做全域散列。
hab (key) = ((a × key + b)%P )%M，P 需要选⼀个⾜够⼤的质数，a 可以随机选 [1,P-1] 之间的任意整数，b 可以随机选 [0,P-1] 之间的任意整数，这些函数构成了⼀个 P*(P-1) 组全域散列函数组。假设 P=17,M=6,a = 3，b = 4, 则 h34 (8) = ((3 × 8 + 4)%17)%6 = 5。
需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的 key 了。
五、处理哈希冲突 哈希冲突就是我们使用哈希表最大的一个麻烦，所以处理哈希冲突是最最重要的，那有哪些方法可以减少哈希冲突？1.开放定址法 2.链地址法
5.1 开放定址法 在开放定址法中所有的元素都放到哈希表里，当一个关键字 key 用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储 ，开放定址法中负载因子一定是小于 1 的。这里的规则有三种：线性探测、二次探测、双重探测。
从发生冲突的位置开始，依次线性向后探测，直到寻找下一个没有存储数据的位置为止，如果走到哈希表尾，则返回到哈希表头的位置。
h（key） = hash0 = key % M，hash0 的位置冲突了（已经有别的值存在这个位置上了），则线性探测的公式为：hc（key，i） = （hashi+i）%M，i = {1，2，3…，M-1}，因为负载因子小于 1，则最多探测 M-1 次，一定能找到一个存储 key 的位置
线性探测的比较简单且容易实现，线性探测的问题假设，hash0 位置连续冲突，hash0，hash1，hash2 位置已经存储数据了，后续映射到 hash0，hash1，hash2，hash3 的值都会争夺 hash3 位置，这种现象叫做群集、堆积 。下面的二次探测可以一定程度改善这个问题。
从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。
h（key） = hash0 = key%M，hash0 位置冲突了，则二次探测公式为：
hc（key，i） = （hash0 ± i 的平方 ）%M，i = {1,2,3…,M/2}
二次探测当 hashi = （hash0 - i 的平方 ）%M 时，当 hashi<0,需要 hashi+=M
下面演示{19,30,52,63,11,22}等这一组值映射到 M=11 的哈希表中。
下面演示{19，30，5，36，13，20，21，12}等这一组值映射到 M=11 的哈希表中。
enum Status { EXIST, EMPTY, DELETE };
template <classK>
struct HashDate {
K _key;
Status _status = EMPTY;
};
template <classK>
struct HashFunc {
size_t operator () (K key) return (size_t )key;}
};
template <classK,classHash= HashFunc<K>>
class HashTable{
public :
HashTable (){ _table.resize (__stl_next_prime(0 ));}
bool insert (const K& key) if (!Find (key))return false ;
if ((double )_n /(double )_table.size ()>=0.7 ){
HashTable<K, Hash> newHt;
newHt._table.resize (__stl_next_prime(_table.size ()+1 ));
for (size_t i =0 ; i < _table.size (); i++){
if (_table[i]._status == EXIST){
newHt.insert (_table[i]._key);
}
}
_table.swap (newHt._table);
}
Hash hs;
size_t hash0 =hs (key)% _table.size ();
size_t hashi = hash0;
size_t i =1 ;
while (_table[hashi]._status == EXIST){
hashi =(hashi + i)% _table.size ();
i++;
}
_table[hashi]._key = key;
_table[hashi]._status = EXIST;
++_n;
return true ;
}
HashDate<K>* Find (const K& key) {
Hash hs;
size_t hash0 =hs (key)% _table.size ();
size_t hashi = hash0;
size_t i =1 ;
while (_table[hashi]._status == EXIST){
if (_table[hashi]._key == key)return &_table[hashi];
hashi =(hashi + i)% _table.size ();
i++;
if (i == _table.size ())break ;
}
return nullptr ;
}
bool Erase (const K& key) Find (key);
if (ptr ==nullptr )return false ;
else {
ptr->_status = DELETE;
--_n;
return true ;
}
}
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;
}
private :
vector<HashDate<K>> _table;
size_t _n =0 ;
};
扩容
这里我们哈希表负载因子控制在 0.7，当负载因子达到 0.7 就要进行扩容了，我们可以按照质数表函数 (__stl_next_prime) 来进行扩容，你传一个数字 n 过去，它会返回一个大于等于这个 n 的数字，例如你传 0，那么就返回 53；你传 54 就返回 97。
key 不能取模的问题
当 key 是 string/Date 等类型时，key 不能直接取模，那么我们需要给 HashTable 增加一个仿函数，这个仿函数支持把 key 转换成一个可以取模的整形，如果 key 可以转换成整形并且不容易冲突，那么这个仿函数就用默认参数即可，如果 key 不能转换成整形，我们就要自己写一个仿函数支持 key 转换成整形。
5.2 链地址法（哈希桶） 开放定址法中所有的元素都放到哈希表中，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，该指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫挂链法或者哈希桶。
下面演示{19,30,5,36,13,20,21,12,24,96}等这一组值映射到 M=11 的表中
h(19) = 8 ，h(30) = 8 ，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1,h(24) = 2,h(96) = 8。
开放定址法负载因⼦必须⼩于 1，链地址法的负载因⼦就没有限制了，可以⼤于 1。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；stl 中 unordered_xxx 的最⼤负载因⼦基本控制在 1，⼤于 1 就扩容，我们下⾯实现也使⽤这个⽅式。
template <classK>
struct HashFunc {
size_t operator () (const K& key) return (size_t )key;}
};
template <>
struct HashFunc <string>{
size_t operator () (const string& str) size_t hash =0 ;
for (auto ch : str){
hash += ch;
hash *=131 ;
}
return hash;
}
};
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;
}
template <classT>
struct HashNode {
T _data;
HashNode<T>* _next;
HashNode (const T& data):_data(data),_next(nullptr ){}
};
template <classK,classT,classKeyOfT,classHash= HashFunc<K>>
class HashTable{
typedef HashNode<T> Node;
public :
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 ;
}
}
bool Insert (const T& data) if (Find (kot (data)))return false ;
Hash hs;
if (_n == _tables.size ()){
vector<Node*>newtables (__stl_next_prime(_tables.size ()+1 ));
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 true ;
}
Node* 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;
cur = cur->_next;
}
return nullptr ;
}
bool Erase (const K& key) 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;
}
delete cur;
return true ;
}
prev = cur;
cur = cur->_next;
}
return false ;
}
private :
vector<Node*> _tables;
size_t _n =0 ;
};
总结 本文为大家讲解了哈希，重点掌握哈希中的除留余数法以及链地址法，实战中，链地址法（哈希桶）使用频率更高，因为它减少了哈希表的堆积 问题。
相关免费在线工具 加密/解密文本 使用加密算法（如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
