C++算法
哈希表核心实现：开放定址法与链地址法详解
哈希表利用哈希函数建立键值映射以实现高效存取。文章解析哈希冲突处理机制与负载因子影响，阐述直接定址、除法散列等函数设计策略。重点对比开放定址法与链地址法的实现差异，包含线性探测、二次探测及哈希桶的具体代码逻辑，涵盖增删查改与扩容优化，为理解 unordered_map 等底层结构提供实践参考。
哈希表利用哈希函数建立键值映射以实现高效存取。文章解析哈希冲突处理机制与负载因子影响，阐述直接定址、除法散列等函数设计策略。重点对比开放定址法与链地址法的实现差异，包含线性探测、二次探测及哈希桶的具体代码逻辑，涵盖增删查改与扩容优化，为理解 unordered_map 等底层结构提供实践参考。
哈希表是数据结构中的'效率王者'，通过哈希函数建立 key 与存储位置的映射，实现增删查改平均 O(1) 的时间复杂度，广泛应用于 unordered_map、缓存、字典等场景。但很多开发者只知其然不知其所以然——哈希冲突如何解决？不同哈希函数有何差异？开放定址法和链地址法该怎么实现？本文结合其中的核心知识点，从哈希表的基本概念入手，详解哈希函数设计、哈希冲突解决策略，最终完整实现**开放定址法（线性探测）和链地址法（哈希桶）**两种哈希表，帮你吃透哈希表的底层实现逻辑。
哈希表（散列表）是一种'key-value'存储结构，核心是哈希函数和冲突解决策略：
h(key) = 存储位置；两个不同的 key 通过哈希函数计算出相同的存储位置，称为哈希冲突（哈希碰撞）。冲突无法避免，只能通过优化哈希函数和冲突解决策略减少影响。
衡量哈希表拥挤程度的指标，公式为：负载因子 (λ) = 存储的元素个数 (N) / 哈希表大小 (M)。
分析：假如哈希表中已经映射存储了 N 个值，哈希表的大小为 M，那么通过负载因子 = N/M，负载因子有些地方也翻译为载荷因子/装载因子等，他的英文为 load factor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。
我们将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后面代码实现中再进行细节展示。下面哈希函数部分我们讨论时，如果关键字不是整数，那么讨论的 Key 是关键字转换成的整数。
好的哈希函数能让 key 均匀分布，减少冲突，常用设计方法如下：
直接用 key 或 key 的线性变换作为存储位置，公式：h(key) = a*key + b。
分析：在关键字的范围比较集中时，直接定址法就是非常高效的方法，比如一组关键字都在 [0, 99] 之间，那么我们开一个 100 个数的数组，每个关键字 1 的值直接就算存储位置的下标。再比如一组关键字值都在 [a, z] 的小写字母，那么我们开一个 26 个数的数组，每个关键字 ascii 码和 -a ascii 码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法我们在计数排序部分已经用过了，其次在 string 章节的下面 OJ 也用过了。
C++ 算法代码：
class Solution {
public:
int firstUniqChar(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;
}
};
最常用的哈希函数，公式：h(key) = key % M（M 为哈希表大小）。
h(key) = floor(M * ((A*key) % 1.0))，A 取黄金分割点 0.618，对 M 无要求；
h_ab(key) = ((a*key + b) % P) % M（P 为大质数）；
当 key 为字符串时，需手动实现哈希函数，将其转为整数：
// 哈希函数仿函数
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key; // 默认直接转换
}
};
// 特化 string 类型的哈希函数
template<>
struct HashFunc<string> {
// BKDR 字符串哈希算法
size_t operator()(const string& key) {
size_t hash = 0;
for (auto ch : key) {
hash += ch; // 累加字符 ASCII 码
hash *= 131; // 乘质数 131，减少冲突
}
return hash;
}
};
冲突解决是哈希表实现的核心，主流分为 开放定址法 和 链地址法，其中链地址法更加重要一点，下面分别详解实现。
开放定址法的核心：所有元素存储在哈希表数组中，冲突时按规则探测下一个空闲位置。
EMPTY（空）、EXIST（已存储）、DELETE（已删除），避免删除元素后影响后续查找；分析补充：从发生哈希冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，就回绕到哈希表头的位置。
h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1
#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 状态标识
enum State {
EMPTY, // 空位置
EXIST, // 已存储元素
DELETE // 已删除元素
};
// 质数表 (SGI STL 同款，用于扩容)
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
};
inline 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;
}
// 哈希表结点结构
template<class K, class V>
struct HashData {
pair<K, V> _kv; // 存储 key-value 对
State _state = EMPTY; // 初始状态为空
};
// 哈希函数仿函数
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key; // 默认直接转换
}
};
// 特化 string 类型的哈希函数
template<>
struct HashFunc<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<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:
// 构造函数 (初始化哈希表大小为第一个质数)
HashTable() : _tables(__stl_next_prime(1)) {}
// 插入 key-value 对 (去重)
bool Insert(const pair<K, V>& kv) {
// 1.先查找，避免重复插入
if (Find(kv.first)) return false;
// 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++) {
// 遍历旧表，旧表数据插入到 newht
if (_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;
return true;
}
// 查找 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;
}
return nullptr;
}
// 删除 key(仅修改状态为 DELETE，不实际删除元素)
bool Erase(const K& key) {
HashData<K, V>* ret = Find(key);
if (ret) {
// 标记为 DELETE，避免影响后续查找
ret->_state = DELETE;
--_n;
return true;
} else {
return false;
}
}
private:
std::vector<HashData<K, V>> _tables; // 哈希表数组
size_t _n = 0; // 已存储的数据个数
};
测试代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <unordered_map>
using namespace std;
#include "HashTable.h"
void TestHT1() {
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 });
}*/
}
struct HashFuncString {
// BKDR
size_t operator()(const string& key) {
size_t hash = 0;
for (auto ch : key) {
hash += ch;
hash *= 131;
}
return hash;
}
};
void TestHT2() {
// 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}, "字符串" });
}
int main() {
cout << "测试一：删除 5 后再查找" << endl;
TestHT1();
cout << endl;
cout << "测试二：测试 string 类型" << endl;
TestHT2();
return 0;
}
测试结果如下：
关键细节:
DELETE，确保后续查找冲突元素时能继续探测；h(key,i) = hashi = （hash0 +(-) i^2）% M，i = {1，2，3，……，M/2}{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
hc(key,i) = hashi = (hash0 + i ∗ h2 (key)) % M，i = {1, 2, 3, ..., M}、{19,30,52,74} 等这⼀组值映射到 M=11 的表中，设 h2 (key) = key%10 + 1
链地址法的核心：哈希表数组存储链表头指针，冲突元素链接成链表（哈希桶），不占用其他位置。
扩容：
完整代码实现：
#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 质数表 (SGI STL 同款，用于扩容)
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
};
inline 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;
}
// 哈希函数仿函数
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key; // 默认直接转换
}
};
// 特化 string 类型的哈希函数
template<>
struct HashFunc<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<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 {
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 对（头插法，支持重复插入，去重需先查找）
bool Insert(const pair<K, V>& kv) {
if (Find(kv.first)) return false;
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 = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
// 查找 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;
}
return nullptr;
}
// 删除 key（链表节点删除）
bool Erase(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;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
std::vector<Node*> _tables; // 指针数组（存储链表头指针）
size_t _n;
};
}
关键细节：
测试代码：
namespace hash_bucket {
void TestHT1() {
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);
}
void TestHT2() {
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;
}
}
int main() {
cout << "测试 2:" << endl;
hash_bucket::TestHT1();
cout << endl;
cout << "测试 3:" << endl;
hash_bucket::TestHT2();
}
| 对比维度 | 开放定址法（线性探测） | 链地址法（哈希桶） |
|---|---|---|
| 空间利用率 | 较低（需预留空闲位置，装载因子λ通常≤0.7） | 较高（冲突元素链成链表，装载因子λ可以≥1） |
| 冲突处理 | 线性探测，易产生'一次群集'现象 | 链表存储，冲突元素被归入同一桶中，无群集问题 |
| 实现复杂度 | 较高（需处理状态标识、扩容迁移逻辑复杂） | 较低（主要是链表操作，逻辑相对简单） |
| 查找效率 | 平均 O(1)，最坏 O(N)（群集严重时退化） | 平均 O(1)，最坏 O(k)（k 为单个桶的链表长度） |
| 适用场景 | 空间充足、数据量固定或可预测的场景 | 高频插入删除、数据量动态变化的场景（如 C++ unordered_map) |
| 缓存性能 | 更好（数据连续存储， locality 高） | 较差（链表节点在内存中不连续，访问可能跳跃） |
| 扩容操作 | 成本高（所有元素需要重新哈希并迁移到新表） | 成本相对较低（只需重新哈希，节点可重新挂载） |
哈希表的核心是'哈希函数 + 冲突解决'：好的哈希函数保证 key 均匀分布，合理的冲突策略保证效率稳定。开放定址法适合空间充足的场景，链地址法因实现简单、无群集问题，成为工业级实现的首选（如 C++ 的 unordered_map、Java 的 HashMap）。本文实现的两种哈希表，覆盖了哈希表的核心细节：质数扩容、字符串哈希、元素迁移、状态标识等。掌握这些细节后，不仅能理解 STL 容器的底层实现，更能根据实际场景选择合适的哈希表设计。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online