哈希表的两种灵魂：深入探索开放定址与链地址法的核心机密

Ne0inhk

14 Mar 2026 — 20 min read

🔥草莓熊Lotso：个人主页
❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受！

🎬 博主简介：

文章目录

前言：
一. 哈希表核心概念
二. 哈希函数设计
三. 哈希冲突解决策略
结尾：

前言：

哈希表是数据结构中的 “效率王者”，通过哈希函数建立 key 与存储位置的映射，实现增删查改平均 O (1) 的时间复杂度，广泛应用于 unordered_map、缓存、字典等场景。但很多开发者只知其然不知其所以然 —— 哈希冲突如何解决？不同哈希函数有何差异？开放定址法和链地址法该怎么实现？本文结合其中的核心知识点，从哈希表的基本概念入手，详解哈希函数设计、哈希冲突解决策略，最终完整实现开放定址法（线性探测） 和链地址法（哈希桶） 两种哈希表，帮你吃透哈希表的底层实现逻辑。

一. 哈希表核心概念

1.1 哈希表的本质

哈希表（散列表）是一种 “key-value” 存储结构，核心是哈希函数和冲突解决策略：

哈希函数：将 key 映射到哈希表的存储位置（下标），公式为 h(key) = 存储位置；
核心目标：让 key 均匀分布，减少冲突，保证 O (1) 平均效率。

1.2 哈希冲突

两个不同的 key 通过哈希函数计算出相同的存储位置，称为哈希冲突（哈希碰撞）。冲突无法避免，只能通过优化哈希函数和冲突解决策略减少影响。

1.3 负载因子

衡量哈希表拥挤程度的指标，公式为：负载因子(λ) = 存储的元素个数(N) / 哈希表大小(M)。

λ 越大：冲突概率越高，空间利用率越高；
λ 越小：冲突概率越低，空间利用率越低；
实践中：开放定址法 λ 通常控制在 0.7 以内，链地址法 λ 控制在 1 以内。

分析：假如哈希表中已经映射存储了N个值，哈希表的大小为M，那么通过负载因子 = N/M，负载因子有些地方也翻译为载荷因子/装载因子等，他的英文为 load factor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；

1.4 将关键字转为整数

我们将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后面代码实现中再进行细节展示。下面哈希函数部分我们讨论时，如果关键字不是整数，那么讨论的Key是关键字转换成的整数

二. 哈希函数设计

好的哈希函数能让 key 均匀分布，减少冲突，常用设计方法如下：

2.1 直接定址法

直接用 key 或 key 的线性变换作为存储位置，公式：h(key) = a*key + b。

适用场景：key 范围集中（如 0-99、a-z）；
优点：无冲突，效率高；
缺点：key 范围分散时浪费内存（如 key 为 1、10000，需开 10001 大小的数组）。
分析：在关键字的范围比较集中时，直接定值法就是非常高效的方法，比如一组关键字都在[0，99]之间，那么我们开一个100个数的数组，每个关键字1的值直接就算存储位置的下标。再比如一组关键字值都在[a，z]的小写字母，那么我们开一个26个数的数组，每个关键字ascill码和-a ascii码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法我们在计数排序部分已经用过了，其次在string章节的下面OJ也用过了。

实战举例：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

C++算法代码：

classSolution{public:intfirstUniqChar(string s){int count[26]={0};for(auto ch : s){ count[ch-'a']++;}for(int i =0; i < s.size();i++){if(count[s[i]-'a']==1){return i;}}return-1;}};

2.2 除法散列法（除留余数法）

最常用的哈希函数，公式：h(key) = key % M（M 为哈希表大小）。

关键优化：M 建议取不接近 2 的整数次幂的质数，避免 key 的后几位重复导致冲突（如 M=16 时，63 和 31 的余数都是 15）；
例外：Java HashMap 用 2 的整数次幂作为 M，通过位运算优化效率，同时用异或操作让 key 所有位参与计算，保证分布均匀。

2.3 其他方法（了解）

乘法散列法：h(key) = floor(M * ((A*key) % 1.0))，A 取黄金分割点 0.618，对 M 无要求；

全域散列法：通过随机选取哈希函数避免恶意攻击，公式：h_ab(key) = ((a*key + b) % P) % M（P 为大质数）；

字符串哈希：将字符串转为整数（如 BKDR 哈希，hash = hash*131 + 字符ASCII码），避免 “abcd” 和 “bcad” 这类字符串冲突。

2.4 字符串哈希实现（特化仿函数）

当 key 为字符串时，需手动实现哈希函数，将其转为整数：

// 哈希函数仿函数template<classK>structHashFunc{ size_t operator()(const K& key){return(size_t)key;// 默认直接转换}};// 特化string类型的哈希函数template<>structHashFunc<string>{// BKDR字符串哈希算法 size_t operator()(const string& key){ size_t hash =0;for(auto ch : key){ hash += ch;// 累加字符ASCII码 hash *=131;// 乘质数131，减少冲突}return hash;}};

三. 哈希冲突解决策略

冲突解决是哈希表实现的核心，主流分为 开放定址法 和 链地址法，其中链地址法更加重要一点，下面分别详解实现。

3.1 实现一：开放定址法（线性探测，二次探测）

开放定址法的核心：所有元素存储在哈希表数组中，冲突时按规则探测下一个空闲位置。

3.1.1 线性探测核心设计

状态标识：每个位置需标记 EMPTY（空）、EXIST（已存储）、DELETE（已删除），避免删除元素后影响后续查找；
探测规则：线性探测（冲突后依次向后查找空闲位置）；
扩容策略：负载因子≥0.7 时扩容，哈希表大小取质数（参考 SGI STL 的质数表，后面的代码实现里面有）。

分析补充：从发生哈希冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，就回绕到哈希表头的位置。

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1

3.1.2 完整代码实现

#pragmaonce#include<iostream>#include<vector>#include<algorithm>usingnamespace std;// 状态标识enumState{ EMPTY,// 空位置  EXIST,// 已存储元素 DELETE // 已删除元素};// 质数表(SGI STL 同款，用于扩容)staticconstint __stl_num_primes =28;staticconstunsignedlong __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};inlineunsignedlong__stl_next_prime(unsignedlong n){constunsignedlong* first = __stl_prime_list;constunsignedlong* last = __stl_prime_list + __stl_num_primes;// >= nconstunsignedlong* pos =lower_bound(first, last, n);return pos == last ?*(last -1):*pos;}// 哈希表结点结构template<classK,classV>structHashData{ pair<K, V> _kv;// 存储key-value对 State _state = EMPTY;//初始状态为空};// 哈希函数仿函数template<classK>structHashFunc{ size_t operator()(const K& key){return(size_t)key;// 默认直接转换}};// 特化string类型的哈希函数template<>structHashFunc<string>{// BKDR字符串哈希算法 size_t operator()(const string& key){ size_t hash =0;for(auto ch : key){ hash += ch;// 累加字符ASCII码 hash *=131;// 乘质数131，减少冲突}return hash;}};// 开放定址法哈希表(线性探测)template<classK,classV,classHash= HashFunc<K>>classHashTable{public:// 构造函数(初始化哈希表大小为第一个质数)HashTable():_tables(__stl_next_prime(1)){}// 插入 key-value对(去重)boolInsert(const pair<K, V>& kv){// 1.先查找，避免重复插入if(Find(kv.first))returnfalse;// 2.负载因子 >=0.7，扩容if((double)_n /(double)_tables.size()>=0.7){ HashTable<K, V, Hash> newht; newht._tables.resize(__stl_next_prime(_tables.size()+1));// 3.迁移旧表元素到新表for(size_t i =0; i < _tables.size(); i++){// 遍历旧表，旧表数据插入到newhtif(_tables[i]._state == EXIST){ newht.Insert(_tables[i]._kv);}}// 4.交换新旧表 _tables.swap(newht._tables);}// 5.线性探测找空闲位置 Hash hs; size_t hash0 =hs(kv.first)% _tables.size();// 线性探测 size_t i =1; size_t hashi = hash0;while(_tables[hashi]._state == EXIST){// 冲突，线性探测下一个位置 hashi =(hash0 + i)% _tables.size();++i;}// 6.插入元素 _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST;++_n;returntrue;}// 查找key，返回节点指针(nullptr表示未找到) HashData<K, V>*Find(const K& key){ Hash hs; size_t hash0 =hs(key)% _tables.size();// 线性探测 size_t i =1; size_t hashi = hash0;// 遇到EMPTY才停止查找(DELETE继续探测)while(_tables[hashi]._state != EMPTY){if(_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return&_tables[hashi];}// 线性探测下一个位置 hashi =(hash0 + i)% _tables.size();++i;}returnnullptr;}// 删除key(仅修改状态为DELETE,不实际删除元素)boolErase(const K& key){ HashData<K, V>* ret =Find(key);if(ret){// 标记为 DELETE,避免影响后续查找 ret->_state = DELETE;--_n;returntrue;}else{returnfalse;}}private: std::vector<HashData<K,V>> _tables;// 哈希表数组 size_t _n =0;// 已存储的数据个数};

测试代码：

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include<unordered_map>usingnamespace std;#include"HashTable.h"voidTestHT1(){int a[]={19,30,5,36,13,20,21,12,58}; HashTable<int,int> ht;for(auto e : a){ ht.Insert({ e, e });} ht.Insert({-2,2}); ht.Insert({22,22}); cout <<"删除5之前查找5,58结果："<< endl; cout << ht.Find(5)<< endl; cout << ht.Find(58)<< endl; ht.Erase(5); cout <<"删除5之后查找5,58结果："<< endl; cout << ht.Find(5)<< endl; cout << ht.Find(58)<< endl;/*for (size_t i = 0; i < 100; i++) { ht.Insert({ rand(), i }); }*/}structHashFuncString{// BKDR size_t operator()(const string& key){ size_t hash =0;for(auto ch : key){ hash += ch; hash *=131;}return hash;}};voidTestHT2(){//HashTable<string, string, HashFuncString> dict; HashTable<string, string> dict; dict.Insert({"string","字符串"}); dict.Insert({"string","字符串1"}); dict.Insert({"left","左边"}); dict.Insert({"right","右边"}); cout << dict.Find("string")<< endl; cout << dict.Find("left")<< endl; cout << dict.Find("left ")<< endl; HashFuncString hfs; cout <<hfs("abcd")<< endl; cout <<hfs("acbd")<< endl; cout <<hfs("aadd")<< endl; unordered_map<string, string> dictmap; dictmap.insert({"string","字符串"});// 编译报错，需要自己实现Hash的仿函数把key转成整形//unordered_map<pair<string, int>, string> um;//um.insert({ {"string", 1}, "字符串" });}intmain(){ cout <<"测试一:删除5后再查找"<< endl;TestHT1(); cout << endl; cout <<"测试二:测试string类型"<< endl;TestHT2();return0;}

测试结果如下：

关键细节:

状态标识：删除元素时不直接清空，而是标记为DELETE，确保后续查找冲突元素时能继续探测；
扩容逻辑：扩容后需重新映射所有元素（因为哈希表大小变化，存储位置改变）；
线性探测缺陷：容易出现 “群集（堆积）”（连续位置被占用，后续冲突集中争夺同一位置），可通过二次探测、双重探测优化

3.1.3 二次探测

从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置；
h(key) = hash0 = key%M，hash0位置冲突了，则二次探测公式为：h(key,i) = hashi = （hash0 +(-) i^2）% M，i = {1，2，3，……，M/2}
二次探测当 hashi = (hash0 - i^2) % M 时，当hashi<0时，需要hashi+=M
下面演示 {19,30,52,63,11,22} 等这一组值映射到M=11的表中

h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0

3.1.4 双重探测（了解）

第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。
h1(key) = hash0 = key % M ，hash0位置冲突了，则双重探测公式为：hc(key,i) = hashi = (hash0 + i ∗ h2 (key)) % M， i = {1, 2, 3, ..., M}、
要求 h2(key) < M 且 h2(key)和M互为质数，有两种简单的取值方法：1. 当M为2整数幂时，h2(key) 从 [0,M-1] 任选一个奇数；2. 当M为质数时，h2(key) = key % (M-1) + 1
保证 h2(key)与M 互质是因为根据固定的偏移量所寻址的所有位置将形成一个群，若最大公约数 p = gcd(M,h1(key)) > 1，那么所能寻址的位置的个数为 M/P < M，使得对于一个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的位置为{1，4，7，10}，寻址个数为 12/gcd(12,3) = 4
下面演示 {19,30,52,74} 等这⼀组值映射到M=11的表中，设 h2 (key) = key%10 + 1

3.2 实现二：链地址法（哈希桶）

链地址法的核心：哈希表数组存储链表头指针，冲突元素链接成链表（哈希桶），不占用其他位置。

结构：哈希表是指针数组，每个元素是链表头指针，冲突元素通过链表链接；
扩容策略：负载因子≥1 时扩容（链地址法负载因子可大于 1）；
优势：无群集问题，空间利用率高，实现简单。
分析补充：

扩容：

完整代码实现：

#pragmaonce#include<iostream>#include<vector>#include<algorithm>usingnamespace std;// 质数表(SGI STL 同款，用于扩容)staticconstint __stl_num_primes =28;staticconstunsignedlong __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};inlineunsignedlong__stl_next_prime(unsignedlong n){constunsignedlong* first = __stl_prime_list;constunsignedlong* last = __stl_prime_list + __stl_num_primes;// >= nconstunsignedlong* pos =lower_bound(first, last, n);return pos == last ?*(last -1):*pos;}// 哈希函数仿函数template<classK>structHashFunc{ size_t operator()(const K& key){return(size_t)key;// 默认直接转换}};// 特化string类型的哈希函数template<>structHashFunc<string>{// BKDR字符串哈希算法 size_t operator()(const string& key){ size_t hash =0;for(auto ch : key){ hash += ch;// 累加字符ASCII码 hash *=131;// 乘质数131，减少冲突}return hash;}};// 链地址法哈希表（哈希桶）namespace hash_bucket {template<classK,classV>structHashNode{ pair<K, V> _kv;// 哈希桶节点结构（链表节点） HashNode<K,V>* _next;HashNode(const pair<K,V>& kv):_kv(kv),_next(nullptr){}};template<classK,classV,classHash= HashFunc<K>>classHashTable{typedef HashNode<K, V> 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;} _n =0;}// 插入key-value对（头插法，支持重复插入，去重需先查找）boolInsert(const pair<K,V>& kv){if(Find(kv.first))returnfalse; Hash hs;// 1. 负载因子≥1，扩容（链地址法负载因子可大于1）if(_n == _tables.size()){ std::vector<Node*>newtables(__stl_next_prime(_tables.size()+1),nullptr);// 2. 迁移旧表节点到新表（直接移动节点，不新建，效率更高）for(size_t i =0; i < _tables.size(); i++){// 遍历旧表，旧表节点重新映射，挪动到新表 Node* cur = _tables[i];while(cur){ Node* next = cur->_next;// 3. 重新计算节点在新表的位置 size_t hashi =hs(cur->_kv.first)% newtables.size();// 4. 头插入新表 cur->_next = newtables[hashi]; newtables[hashi]= cur; cur = next;} _tables[i]=nullptr;} _tables.swap(newtables);} size_t hashi =hs(kv.first)% _tables.size();// 5. 头插入当前节点 Node* newnode =newNode(kv); newnode->_next = _tables[hashi]; _tables[hashi]= newnode;++_n;returntrue;}// 查找key，返回节点指针（nullptr表示未找到） Node*Find(const K& key){ Hash hs; size_t hashi =hs(key)% _tables.size(); Node* cur = _tables[hashi];while(cur){if(cur->_kv.first == key){return cur;} cur = cur->_next;}returnnullptr;}// 删除key（链表节点删除）boolErase(const K& key){ Hash hs; size_t hashi =hs(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;}--_n;delete cur;returntrue;} prev = cur; cur = cur->_next;}returnfalse;}private: std::vector<Node*> _tables;// 指针数组（存储链表头指针） size_t _n;};}

关键细节：

节点迁移：扩容时直接移动旧表节点到新表，不新建节点，减少内存开销；
链表操作：插入用头插法（效率高），删除需记录前驱节点；
极端优化：Java8 的 HashMap 中，当链表长度超过 8 时，会将链表转为红黑树，避免单桶过长导致效率退化到 O (N)。

测试代码：

namespace hash_bucket {voidTestHT1(){int a[]={19,30,5,36,13,20,21,12,58}; HashTable<int,int> ht;for(auto e : a){ ht.Insert({ e,e });} ht.Insert({-2,2}); ht.Insert({22,22}); ht.Insert({44,44}); ht.Erase(58); ht.Erase(36);}voidTestHT2(){ HashTable<string, string> dict; dict.Insert({"string","字符串"}); dict.Insert({"string","字符串1"}); dict.Insert({"left","左边"}); dict.Insert({"right","右边"}); cout << dict.Find("string")<< endl; cout << dict.Find("left")<< endl; cout << dict.Find("left ")<< endl;}}intmain(){ cout <<"测试2:"<< endl; hash_bucket::TestHT1(); cout << endl; cout <<"测试3:"<< endl; hash_bucket::TestHT2();}

3.3 两种实现对比

对比维度	开放定址法（线性探测）	链地址法（哈希桶）
空间利用率	较低（需预留空闲位置，装载因子λ通常≤0.7）	较高（冲突元素链成链表，装载因子λ可以≥1）
冲突处理	线性探测，易产生"一次群集"现象	链表存储，冲突元素被归入同一桶中，无群集问题
实现复杂度	较高（需处理状态标识、扩容迁移逻辑复杂）	较低（主要是链表操作，逻辑相对简单）
查找效率	平均O(1)，最坏O(N)（群集严重时退化）	平均O(1)，最坏O(k)（k为单个桶的链表长度）
适用场景	空间充足、数据量固定或可预测的场景	高频插入删除、数据量动态变化的场景（如C++ `unordered_map`)
缓存性能	更好（数据连续存储， locality 高）	较差（链表节点在内存中不连续，访问可能跳跃）
扩容操作	成本高（所有元素需要重新哈希并迁移到新表）	成本相对较低（只需重新哈希，节点可重新挂载）

结尾：

🍓 我是草莓熊 Lotso！若这篇技术干货帮你打通了学习中的卡点： 👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长 ❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量 ⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用 💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑 🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解 技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！

结语：哈希表的核心是 “哈希函数 + 冲突解决”：好的哈希函数保证 key 均匀分布，合理的冲突策略保证效率稳定。开放定址法适合空间充足的场景，链地址法因实现简单、无群集问题，成为工业级实现的首选（如 C++ 的 unordered_map、Java 的 HashMap）。本文实现的两种哈希表，覆盖了哈希表的核心细节：质数扩容、字符串哈希、元素迁移、状态标识等。掌握这些细节后，不仅能理解 STL 容器的底层实现，更能根据实际场景选择合适的哈希表设计。

✨把这些内容吃透超牛的！放松下吧✨ʕ˘ᴥ˘ʔづきらど