C++算法
哈希表实现详解：开放定址法与链地址法
哈希表通过哈希函数映射键值对，实现平均 O(1) 查找。核心在于哈希冲突处理。常见解决策略包括开放定址法和链地址法。开放定址法将元素存入数组，冲突时线性或二次探测空闲位置，需处理删除标记和扩容。链地址法使用链表存储冲突元素，空间利用率高且无群集问题。本文详细解析了哈希函数设计（直接定址、除留余数、字符串哈希）、冲突解决代码实现（C++ 模板类）及两种方法的性能对比与适用场景。
哈希表通过哈希函数映射键值对，实现平均 O(1) 查找。核心在于哈希冲突处理。常见解决策略包括开放定址法和链地址法。开放定址法将元素存入数组，冲突时线性或二次探测空闲位置，需处理删除标记和扩容。链地址法使用链表存储冲突元素，空间利用率高且无群集问题。本文详细解析了哈希函数设计（直接定址、除留余数、字符串哈希）、冲突解决代码实现（C++ 模板类）及两种方法的性能对比与适用场景。
哈希表（散列表）是一种 'key-value' 存储结构，核心是哈希函数和冲突解决策略：
h(key) = 存储位置；两个不同的 key 通过哈希函数计算出相同的存储位置，称为哈希冲突（哈希碰撞）。冲突无法避免，只能通过优化哈希函数和冲突解决策略减少影响。
衡量哈希表拥挤程度的指标，公式为：负载因子 (λ) = 存储的元素个数 (N) / 哈希表大小 (M)。
我们将关键字映射到数组中位置，一般是整数好做映射计算。如果不是整数，需要转换成整数。下面哈希函数部分讨论时，如果关键字不是整数，那么讨论的 Key 是关键字转换成的整数。
好的哈希函数能让 key 均匀分布，减少冲突，常用设计方法如下：
直接用 key 或 key 的线性变换作为存储位置，公式：h(key) = a*key + b。
在关键字的范围比较集中时，直接定址法非常高效。比如一组关键字都在 [0, 99] 之间，开一个 100 个数的数组，每个关键字的值直接算作存储位置的下标。
参考 LeetCode 387. 字符串中的第一个唯一字符。
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（已删除），避免删除元素后影响后续查找；从发生哈希冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，就回绕到哈希表头的位置。
#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> {
size_t operator()(const string& key) {
size_t hash = 0;
for (auto ch : key) {
hash += ch;
hash *= 131;
}
return hash;
}
};
// 开放定址法哈希表 (线性探测)
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:
HashTable() : _tables(__stl_next_prime(1)) {}
bool Insert(const pair<K, V>& kv) {
if (Find(kv.first)) return false;
if ((double)_n / (double)_tables.size() >= 0.7) {
HashTable<K, V, Hash> newht;
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++) {
if (_tables[i]._state == EXIST) {
newht.Insert(_tables[i]._kv);
}
}
_tables.swap(newht._tables);
}
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;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
HashData<K, V>* Find(const K& key) {
Hash hs;
size_t hash0 = hs(key) % _tables.size();
size_t i = 1;
size_t hashi = hash0;
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;
}
bool Erase(const K& key) {
HashData<K, V>* ret = Find(key);
if (ret) {
ret->_state = DELETE;
--_n;
return true;
} else {
return false;
}
}
private:
std::vector<HashData<K, V>> _tables;
size_t _n = 0;
};
从发生冲突的位置开始，依次左右按二次方跳跃式探测。
h(key,i) = (hash0 + (-) i^2) % M，i = {1, 2, 3, ..., M/2}hashi < 0 时，需要 hashi += M。使用第二个哈希函数计算出一个跟 key 相关的偏移量值，不断往后探测。
hc(key,i) = (hash0 + i * h2(key)) % Mh2(key) < M 且 h2(key) 和 M 互为质数。链地址法的核心：哈希表数组存储链表头指针，冲突元素链接成链表（哈希桶），不占用其他位置。
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;
}
bool Insert(const pair<K, V>& kv) {
if (Find(kv.first)) return false;
Hash hs;
if (_n == _tables.size()) {
std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hs(cur->_kv.first) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(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 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;
}
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;
};
}
| 对比维度 | 开放定址法（线性探测） | 链地址法（哈希桶） |
|---|---|---|
| 空间利用率 | 较低（需预留空闲位置，装载因子λ通常≤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