哈希表实现
哈希表是基于哈希函数实现的高效数据结构，通过关键字与存储位置的映射关系，达成O(1)级别的查找、插入、删除效率，是数据结构与算法中的核心考点，本文从基础概念、冲突解决到代码实现，全方位拆解哈希表核心知识。
1. 哈希概念
哈希（hash）又称散列，是一种组织数据的方式。本质是通过哈希函数把关键字 Key 跟存储位置建立映射关系，查找时通过这个哈希函数计算出 Key 存储的位置，进行快速查找。
1.1 直接定址法
当关键字的范围比较集中时，直接定址法非常简单高效。
本质：用关键字计算出一个绝对位置或者相对位置，把关键字的值直接作为存储位置的下标。
例子：
关键字在 [0, 99] 之间 → 开一个 100 个数的数组，每个关键字的值就是数组下标。
关键字是小写字母 [a, z] → 开一个 26 个数的数组，每个关键字 acii码 - 'a' 作为数组下标。
应用：计数排序、字符串统计（如 LeetCode 387. 字符串中的第一个唯一字符）。
LeetCode 387 示例代码：
题目要求：找出第一个出现一次的字母
class Solution {
public:
int firstUniqChar(string s) {
// 每个字母的 ascii 码 - 'a' 的 ascii 码作为下标映射到 count 数组
// 数组中存储出现的次数
int count[26] = {0};
// 统计次数
for (auto ch : s)
{
count[ch - 'a']++;
}
for (size_t i = 0; i < s.size(); ++i)
{
if (count[s[i] - 'a'] == 1)
return i;
}
return -1;
}
};
1.2 哈希冲突
直接定址法的缺点：当关键字的范围比较分散时，会浪费内存甚至内存不够用。
哈希函数：h(key)，关键字 key 被放到数组的 h(key) 位置，h(key) 计算出的值必须在 [0, M) 之间。
哈希冲突（哈希碰撞）：两个不同的 key 可能会映射到同一个位置。
理想情况：设计优秀的哈希函数，减少冲突次数，同时设计解决冲突的方案。
1.3 负载因子
定义：负载因子 = \frac{N}{M} ，其中 N 是哈希表中已存储的个数，M 是哈希表的大小。
影响：
负载因子越大 → 哈希冲突概率越高，空间利用率越高。
负载因子越小 → 哈希冲突概率越低，空间利用率越低。
1.4 将关键字转为整数
将关键字映射到数组中位置，一般是整数好做映射计算。如果不是整数，需要想办法转换成整数（如字符串转 BKDR 哈希值）。
1.5 哈希函数
一个好的哈希函数应让 N 个关键字被等概率、均匀地散列分布到 M 个空间中。
1.5.1 除法散列法 / 除留余数法
公式：h(key) = key % M，其中 M 是哈希表大小。
注意：避免 M 为某些值，如 2 的幂（2^k），因为 key % 2^k 本质是保留 key 的后 k 位，后 k 位相同的 key 会冲突。
例：M=16=2^4，63 和 31 的后 4 位都是 1111，哈希值都是 15。
建议 M 取不太接近 2 的整数次幂的质数。
实践：Java 的 HashMap 用 2 的整数次幂做表大小，但计算时不用取模，而是直接位运算 key' = key >> 16，再把 key 和 key' 异或，让所有位都参与计算，使映射更均匀。
1.5.2 乘法散列法（了解）
思路：
1. 用关键字 K 乘上常数 A(0 < A < 1)，并取出 K * A 的小数部分。
2. 再用 M 乘以这个小数部分，再向下取整。
公式：h(key) = [ M * ((A * key) % 1.0) ]
推荐 A = (\sqrt{5}-1)/2 = 0.6180339887...（黄金分割点）。
1.5.3 全域散列法（了解）
背景：如果散列函数是公开确定的，恶意对手可构造数据集让所有关键字全部落入同一个位置，实现攻击。
解决：给散列函数增加随机性，每次初始化哈希表时，随机选取一个散列函数使用。
公式：h_{ab}(key) = ((a * key + b) % P) % M，其中 P 是足够大的质数，a 属于 [1, P-1]，b 属于 [0, P-1]。
1.5.4 其他方法（了解）
《算法导论》：平方取中法、折叠法、随机数法、数学分析法等。
这些方法更适用于一些局限的特定场景。
1.6 处理哈希冲突
实践中一般选择除法散列法，冲突不可避免，主要有两种解决方法：开放定址法和链地址法。
1.6.1 开放定址法
所有元素都放到哈希表里，当一个关键字 key 用哈希函数计算出的位置冲突了，就按照某种规则找到下一个没有存储数据的位置进行存储。
负载因子一定小于 1。
规则有三种：线性探测、二次探测、双重探测。
线性探测
思路：从发生冲突的位置开始，依次线性向后探测，直到找到下一个没有存储数据的位置为止；如果走到哈希表尾，则回到表头。
公式：
h(key) = hash0 = key % M
hc(key, i) = hashi = (hash0 + i) % M，i = {1, 2, 3, ..., M-1}
问题：容易产生聚集/堆积问题，即 hash0 位置连续冲突，后续映射到 hash0、hash1、hash2 的值都会争夺 hash3 位置。
示例：将 {19, 30, 5, 36, 13, 20, 21, 12} 映射到 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
插入后表：[21, 12, 13, 36, _ , 5, _ , _ , 19, 30, 20]
二次探测
思路：从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到找到下一个没有存储数据的位置为止。
公式：
h(key) = hash0 = key % M
hc(key, i) = hashi = (hash0 + i^2) % M，i = {1, 2, 3, ..., M/2 }
注意：当 hashi = (hash0 - i^2) % M < 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
插入后表：[11, 63, _, _, _, _, _, _, 30, 19, 52, 22]
双重散列（了解）
思路：第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟 key 相关的偏移量，不断往后探测，直到找到下一个没有存储数据的位置为止。
公式：
h_1(key) = hash0 = key % M
hc(key, i) = hashi = (hash0 + i * h_2(key)) % M，i = {1, 2, 3, ..., M}
要求：h_2(key) 与 M 互质，这样所有寻址位置会形成一个群。
示例：将 {19, 30, 52, 74} 映射到 M=11 的表中，设 h_2(key) = key % 10 + 1。
1.6.2 开放定址法代码实现
开放定址法在实践中不如链地址法常用，这里选择线性探测实现。
开放定址法的哈希表结构
// 定义哈希表状态枚举
// 用于标识哈希表中每个位置的状态（开放寻址法需要）
enum State
{
EXIST, // 存在有效数据
EMPTY, // 空，从未使用过
DELETE // 已删除（伪删除标记，避免查找断链）
};
// 哈希桶存储结构
// 每个位置存储：键值对 + 状态
template<class K, class V>
struct HashData
{
// 存储的键值对
pair<K, V> _kv;
// 当前位置状态，默认初始化为EMPTY
State _state = EMPTY;
};
// 哈希表类（开放寻址法 / 线性探测 / 二次探测实现）
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
private:
// 哈希表本体：动态数组，每个元素是HashData
vector<HashData<K, V>> _tables;
// 哈希表中**实际有效数据的个数**
size_t _n = 0;
};
关键说明：状态标识
删除一些值后，会影响后面冲突值的查找。因此，删除时不删除值，而是把状态改为 DELETE，查找时遇到 EMPTY 才能停止。
开放寻址法（线性探测）哈希表 —— 核心思路
1. 整体结构
底层用数组存储，每个位置存：键值对 _kv；状态 _state（EMPTY/EXIST/DELETE）；冲突时往后找空位，不使用链表。
2. 状态枚举作用
EMPTY：空位置，查找遇到它就停止。
EXIST：存有有效数据。
DELETE：伪删除标记，查找时不能停，要继续往后找。
3. 插入思路：先用哈希函数算出位置 hash0。如果该位置被占，线性探测往后找（+1、+2…）。找到 EMPTY 或 DELETE 的位置就插入。负载因子 ≥ 0.7 时扩容（扩成下一个质数大小，重新插入所有数据）。
4. 查找思路：算出哈希位置，开始线性探测。遇到 EXIST 就比较 key，相等则找到。遇到 EMPTY 才说明真的没有。遇到 DELETE 继续往后走。
5. 删除思路：不真正清空数据，只标记为 DELETE(伪删除)，防止后面的元素因为前面空了而查找断链
6. 扩容思路：负载因子太大冲突变多，所以要扩容。新表大小取质数，让哈希分布更均匀。把旧表有效数据重新插入到新表。
扩容
负载因子控制在 0.7，当负载因子到 0.7 以后需要扩容。哈希表大小保持为质数，使用 SGI 版本的质数表获取扩容后的大小。
// 获取大于等于n的最小质数（用于哈希表扩容，保证表长为质数，减少哈希冲突）
inline unsigned long __stl_next_prime(unsigned long n)
{
// 注意：假设unsigned long 至少是32位
static const int __stl_num_primes = 28;
// 预先定义好的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;
// 在质数表中找到第一个 >= n 的质数（二分查找）
const unsigned long* pos = lower_bound(first, last, n);
// 如果n比最大质数还大，返回最大质数；否则返回找到的那个质数
return pos == last ? *(last - 1) : *pos;
}
这个函数就是哈希表扩容专用：当需要扩容时，不随便扩，而是扩成下一个质数，目的是让哈希分布更均匀，减少冲突。
key 不能取模的问题
当 key 是 string/Date 等类型时，需要给 HashTable 增加一个仿函数，支持把 key 转换成一个可以取模的整形。
// 默认哈希仿函数
// 通用版本：针对可以直接转成整数的 key 类型（如 int, long, 指针等）
template<class K>
struct HashFunc
{
// 重载 ()，实现哈希函数
size_t operator()(const K& key)
{
// 直接将 key 强制转换为 size_t 作为哈希值
return (size_t)key;
}
};
// 全特化：string 类型的哈希函数 —— BKDR 哈希算法
template<>
struct HashFunc<string>
{
// 重载 ()，对 string 计算哈希
size_t operator()(const string& key)
{
// 哈希初始值
size_t hash = 0;
// 遍历字符串每个字符，计算哈希
for (auto e : key)
{
// BKDR 经典公式：hash = hash * 131 + 当前字符
hash *= 131;
hash += e;
}
// 返回最终计算出的哈希值
return hash;
}
};
通用版 HashFunc：适合整数类型，直接强转成地址/下标用的整数。
string 特化版：用 BKDR 哈希算法（乘131累加），把字符串转成均匀分布的整数。
配合前面的哈希表使用，让 HashTable 支持 int / string 等不同键类型。
完整代码实现（开放寻址）
#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;
}
};
// string 特化（BKDR 哈希）
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash *= 131;
hash += e;
}
return hash;
}
};
// 开放寻址法命名空间
namespace open_address
{
// 每个位置的状态枚举
enum State
{
EXIST, // 存在有效数据
EMPTY, // 空，从未使用
DELETE // 已删除（伪删除标记）
};
// 哈希表存储节点：键值对 + 状态
template<class K, class V>
struct HashData
{
pair<K, V> _kv; // 存储的键值对
State _state = EMPTY; // 当前位置状态，默认 EMPTY
};
// 开放寻址哈希表（线性探测）
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
// 获取 >= n 的最小质数（用于扩容）
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;
// 二分查找第一个 >= n 的质数
const unsigned long* pos = lower_bound(first, last, n);
// 超出范围返回最大质数，否则返回找到的质数
return pos == last ? *(last - 1) : *pos;
}
// 构造函数：初始化表大小为第一个质数
HashTable()
{
_tables.resize(__stl_next_prime(0));
}
// 插入键值对
bool Insert(const pair<K, V>& kv)
{
// 键已经存在，不允许重复插入
if (Find(kv.first))
return false;
// 负载因子 >= 0.7 时扩容（避免冲突过多）
if (_n * 10 / _tables.size() >= 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 hash;
size_t hash0 = hash(kv.first) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
// 线性探测：找到第一个非 EXIST 的空位
while (_tables[hashi]._state == EXIST)
{
hashi = (hash0 + i) % _tables.size();
++i;
}
// 放入数据并标记为存在
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
// 查找 key，找到返回节点地址，否则返回 nullptr
HashData<K, V>* Find(const K& key)
{
Hash hash;
size_t hash0 = hash(key) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
// 遇到 EMPTY 才停止查找（DELETE 位置要继续走）
while (_tables[hashi]._state != EMPTY)
{
// 是有效数据且 key 相等
if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
// 线性探测
hashi = (hash0 + i) % _tables.size();
++i;
}
// 没找到
return nullptr;
}
// 删除 key（伪删除，只打标记）
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
// 不存在，删除失败
return false;
}
else
{
// 伪删除：标记为 DELETE，不真正清空
ret->_state = DELETE;
--_n;
return true;
}
}
private:
vector<HashData<K, V>> _tables; // 哈希表底层数组
size_t _n = 0; // 有效元素个数
};
}
整体思路
1. 结构设计：底层用 vector 数组 存储。每个单元存：键值对 + 状态。
状态三种：EMPTY：空，从未使用 EXIST：存有有效数据 DELETE：伪删除标记（查找不能停）
2. 哈希函数：整数：直接转成 size_t。 字符串：用 BKDR 哈希（乘131累加）。
3. 插入思路
1） 先调用 Find，key 已存在则不插入。
2） 负载因子 ≥ 0.7 就扩容：新表大小取下一个质数。把旧表有效数据重新插入新表。
3） 计算哈希位置 hash0。
4） 线性探测：位置被占就 +1 往后找。
5） 找到空位（EMPTY/DELETE），存入数据，标记 EXIST。
4. 查找思路
1） 计算哈希位置。
2） 线性探测查找：遇到 EXIST 就比较 key，相等则返回。遇到 DELETE 继续往后。遇到 EMPTY 说明不存在，返回空。
5. 删除思路：先调用 Find 找到节点。不真正删除，只把状态改为 DELETE（伪删除）。防止查找断链。
6. 扩容思路：负载因子太高冲突严重。新表大小用质数，使哈希分布更均匀。旧数据重新哈希插入，完成扩容。
7. 核心特点：不开链表，全部存在一个数组里。冲突靠往后找空位解决。删除用标记法，不破坏探测链。
1.6.3 链地址法
解决冲突的思路：开放定址法中所有元素都放到哈希表里；链地址法中所有数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射到这个位置时指针为空，有多个数据映射到这个位置时，把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面。链地址法也叫拉链法或哈希桶。
示例：将 {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
插入后表：
桶号: 0 1 2 3 4 5 6 7 8 9 10
┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐
│∅ │──│12│──│24│──→13 │36│──│∅ │──│5 │──│∅ │──│∅ │──│96│──→30──→19│20│──│21│
└──┘ └──┘ └──┘ └──┘ └──┘ └──┘ └──┘ └──┘ └──┘ └──┘ └──┘
扩容
开放定址法负载因子必须小于 1，链地址法的负载因子没有限制，可以大于 1。
STL 中 unordered_xxx 的最大负载因子基本控制在 1，大于 1 就扩容。
极端场景
如果某个桶特别长：可以使用全域散列法，或在 Java8 的 HashMap 中，当桶的长度超过一定阈值（8）时，把链表转换成红黑树，提高查找效率。
1.6.4 链地址法代码实现
#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;
}
};
// string 特化版本（BKDR 哈希）
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash = hash * 131 + e;
}
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:
// 获取比 n 大的最小质数（用于扩容）
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;
// 二分查找第一个 >= n 的质数
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
// 构造函数：初始化表为质数大小，全部置空
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;
}
}
// 插入键值对（头插法，负载因子到1扩容）
bool Insert(const pair<K, V>& kv)
{
Hash hs;
size_t hashi = hs(kv.first) % _tables.size();
// 负载因子 == 1 时扩容
if (_n == _tables.size())
{
// 新建更大的表
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 newhashi = hs(cur->_kv.first) % newtables.size();
// 头插到新表对应桶
cur->_next = newtables[newhashi];
newtables[newhashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
// 交换，完成扩容
_tables.swap(newtables);
// 扩容后重新计算当前插入位置
hashi = hs(kv.first) % _tables.size();
}
// 新建节点，头插到对应桶
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;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
// 没找到
return false;
}
private:
vector<Node*> _tables; // 哈希表：指针数组，每个位置是一条链表
size_t _n = 0; // 有效数据个数
};
}
哈希桶（拉链法）整体思路
1. 结构思路：底层用 vector<节点指针>，每个位置是一个桶（链表头）。冲突的元素 挂在同一个桶的链表上，不覆盖、不断链。节点存：key-value + next指针。
2. 哈希函数思路：整数：直接转成 size_t。字符串：用 BKDR哈希（乘131累加），转成整数再取模。
3. 插入思路（头插）
1） 计算哈希位置：hashi = key % 表长。
2） 负载因子 == 1 就扩容：开新的质数大小表。把旧节点重新映射、头插到新表。
3） 新建节点，头插到对应桶的链表前面。 有效个数 _n++。
4. 查找思路：算哈希位置，找到对应桶。在桶的链表里 逐个遍历 比较 key。找到返回节点，没找到返回空。
5. 删除思路：找到对应桶的链表。用 prev 和 cur 双指针找节点。找到就：改指针跳过该节点，delete 节点，_n--
6. 扩容思路：负载因子到 1 才扩容。新表大小用 下一个质数，减少冲突。不复制数据，直接把旧节点重新哈希挂到新表，效率高。
7. 析构思路：遍历每个桶，把整条链表节点逐个 delete，防止内存泄漏。
2. 完整代码
HashTable.h
#pragma once // 防止头文件被重复包含
#include <iostream>
#include <vector>
#include <algorithm> // 引入算法库，用于 lower_bound（找质数表用）
using namespace std;
// 哈希表节点状态枚举
enum State
{
EXIST, // 当前位置存在有效数据
EMPTY, // 当前位置为空，从未使用
DELETE // 当前位置数据被删除（伪删除，开放寻址专用）
};
// 开放寻址法的哈希节点结构体
template <class K, class V>
struct HashData
{
// 存储键值对
pair<K, V> _kv;
// 节点状态，默认初始为空
State _state = EMPTY;
};
// 通用哈希仿函数
// 对通用类型 K，直接将 key 强转为 size_t 作为哈希值
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 &s)
{
// BKDR 哈希算法（字符串常用哈希）
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131; // 乘上一个常数，让哈希分布更均匀
}
return hash;
}
};
// 获取下一个质数（STL 原版实现，用于哈希表扩容）; 哈希表容量用质数，能减少哈希冲突
inline unsigned long __stl_next_prime(unsigned long n)
{
// 假设 long 至少 32 位
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;
// 找到第一个 >= n 的质数
const unsigned long *pos = lower_bound(first, last, n);
// 超出表范围就返回最后一个
return pos == last ? *(last - 1) : *pos;
}
// 开放寻址法实现的哈希表
namespace open_address
{
// K：键类型 V：值类型 Hash：哈希仿函数（默认使用上面的HashFunc）
template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
// 构造函数
// 初始化表大小为第一个质数，有效数据个数为0
HashTable()
: _tables(__stl_next_prime(0)), _n(0)
{
}
// 拷贝构造函数
HashTable(const HashTable &other)
: _tables(other._tables), // vector 会自动深拷贝每个元素
_n(other._n)
{
// 由于 HashData 是简单结构体，vector 的默认拷贝构造已足够
}
// 赋值运算符重载（现代写法：拷贝交换法）
HashTable &operator=(HashTable other) // 传值，自动调用拷贝构造
{
// 交换 *this 和临时对象 other 的内容
_tables.swap(other._tables);
swap(_n, other._n);
return *this;
}
// 插入键值对
bool Insert(const pair<K, V> &kv)
{
// 键已经存在，不允许重复插入，返回false
if (Find(kv.first))
return false;
// 负载因子 >= 0.7 时需要扩容（开放寻址法负载因子不能太大）
// _n：有效数据数 _tables.size()：表总大小
if (_n * 10 / _tables.size() >= 7)
{
// 【被注释的旧扩容写法】
// 思路：开新表，遍历旧表，把有效数据重新映射到新表
// vector<HashData<K, V>> newtables(_tables.size()*2);
// for (auto& data : _tables)
//{
// // 只处理有效数据
// if (data._state == EXIST)
// {
// // 计算在新表中的位置
// size_t hash0 = data._kv.first % newtables.size();
// // 后面需要线性探测找位置，这里没写完
// }
// }
//_tables.swap(newtables);
// 【当前采用的扩容写法】
// 新建一个哈希表对象，大小取质数表的下一个质数
HashTable<K, V, Hash> newht;
// newht._tables.resize(_tables.size() * 2);
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
// 遍历旧表，把有效数据重新插入到新哈希表
for (auto &data : _tables)
{
// 只处理有效数据
if (data._state == EXIST)
{
// 复用Insert接口，自动做哈希、探测、插入
newht.Insert(data._kv);
}
}
// 交换新旧表，完成扩容
_tables.swap(newht._tables);
}
// 实例化哈希仿函数
Hash hash;
// 计算初始哈希位置
size_t hash0 = hash(kv.first) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
int flag = 1;
// 线性探测：当前位置已被占用，就往后找空位置
while (_tables[hashi]._state == EXIST)
{
// 线性探测：每次往后走一步
hashi = (hash0 + i) % _tables.size();
++i;
// 【被注释的二次探测写法】
// 步长为 i²，减少聚集问题
/*hashi = (hash0 + (i*i*flag)) % _tables.size();
if (hashi < _tables.size())
hashi += _tables.size();
// 正负交替，避免一直往一个方向走
if (flag == 1)
{
flag = -1;
}
else
{
++i;
flag = 1;
}*/
}
// 找到空位置，存入数据并标记为存在
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
// 有效数据个数+1
++_n;
return true;
}
// 查找 key 对应的节点，返回节点指针，找不到返回nullptr
HashData<K, V> *Find(const K &key)
{
Hash hash;
// 计算初始哈希位置
size_t hash0 = hash(key) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
// 遇到 EMPTY 才停止，因为 DELETE 位置后面可能还有目标数据
while (_tables[hashi]._state != EMPTY)
{
// 当前位置是有效数据，并且key相等，说明找到了
if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
// 线性探测往后找
hashi = (hash0 + i) % _tables.size();
++i;
}
// 走到空位置还没找到，说明不存在
return nullptr;
}
// 删除 key 对应的数据
bool Erase(const K &key)
{
// 先查找
HashData<K, V> *ret = Find(key);
if (ret)
{
// 开放寻址不能真删，只能伪删除（标记为DELETE）
// 否则会打断探测链，导致后面数据查不到
ret->_state = DELETE;
return true;
}
else
{
// 没找到，删除失败
return false;
}
}
private:
// 底层用vector实现开放寻址表
vector<HashData<K, V>> _tables;
size_t _n; // 有效数据个数
};
}
// 链式哈希表（开散列 / 哈希桶）实现
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(0)), _n(0)
{
}
// 拷贝构造函数
HashTable(const HashTable &other)
: _tables(other._tables.size(), nullptr), // 初始化新表，大小相同，所有桶为空
_n(0) // 有效数据个数置0
{
// 遍历旧表的每个桶
for (size_t i = 0; i < other._tables.size(); ++i)
{
Node *cur = other._tables[i];
while (cur != nullptr)
{
// 为旧表中的每个节点创建一个新的副本
this->Insert(cur->_kv);
cur = cur->_next;
}
}
}
// 赋值运算符重载（现代写法：拷贝交换法）
HashTable &operator=(HashTable other) // 传值，自动调用拷贝构造
{
// 交换 *this 和临时对象 other 的内容
_tables.swap(other._tables);
swap(_n, other._n);
return *this;
}
// 析构函数：释放所有链表节点
~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)
{
// key 已存在，不允许重复插入
if (Find(kv.first))
return false;
Hash hash;
// 链式哈希表负载因子 == 1 时扩容
if (_n == _tables.size())
{
// 【被注释的简单扩容写法】
// 思路：开新表，遍历旧表，重新Insert所有数据
// 缺点：效率低，重复计算哈希、找位置、链表操作
/*HashTable<K, V> newht;
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
newht.Insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newht._tables);*/
// 【当前高效扩容写法】
// 直接开新的指针数组，节点复用，不重新new
vector<Node *> newTable(__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 = hash(cur->_kv.first) % newTable.size();
// 头插到新表对应桶中
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
// 旧表桶置空（节点已经移到新表了）
_tables[i] = nullptr;
}
// 交换完成扩容
_tables.swap(newTable);
}
// 计算当前key落在哪个桶
size_t hashi = hash(kv.first) % _tables.size();
// 新建节点，头插到对应桶（头插效率高）
Node *newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
// 有效数据个数+1
++_n;
return true;
}
// 查找 key
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;
}
// 删除 key 对应节点
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;
}
else
{
// 继续往后找
prev = cur;
cur = cur->_next;
}
}
// 没找到，删除失败
return false;
}
private:
// 指针数组：每个位置是一条链表的头指针
vector<Node *> _tables;
size_t _n = 0; // 表中有效数据个数
// 【进阶写法：链表+红黑树（类似C++ unordered_map）】
// 当链表长度 <=8 用链表，>8 转红黑树，提高查找效率
// struct Data
//{
// ListNode* _head;
// RBTreeNode* _root;
// size_t _len; // <= 8 存链表，>8 存红黑树
// };
// vector<Data> _tables;
// size_t _n = 0;
// struct Data
//{
// list<pair<K, V>> _list;
// map<K, V> _map;
// size_t _len; // <= 8 存链表，>8 存红黑树
// };
// vector<Data> _tables;
// size_t _n = 0;
};
}
test.cpp
#include"HashTable.h"
#include<iostream>
using namespace std;
// int main()
// {
// //int a[] = { 19,30,52,63,11,22 };
// int a[] = { 19,30,5,36,13,20,21,12 };
// open_address::HashTable<int, int> ht;
// for (auto e : a)
// {
// ht.Insert({ e, e });
// }
// //ht.Insert({ 15, 15 });
// ht.Erase(30);
// if (ht.Find(20))
// {
// cout << "找到了" << endl;
// }
// if (ht.Find(30))
// {
// cout << "找到了" << endl;
// }
// else
// {
// cout << "没有找到" << endl;
// }
// return 0;
// }
//struct StringHashFunc
//{
// size_t operator()(const string& s)
// {
// size_t hash = 0;
// for (auto ch : s)
// {
// hash += ch;
// }
//
// return hash;
// }
//};
struct Date
{
int _year;
int _month;
int _day;
Date(int year = 1, int month = 1, int day = 1)
:_year(year)
, _month(month)
, _day(day)
{}
bool operator==(const Date& d)
{
return _year == d._year
&& _month == d._month
&& _day == d._day;
}
};
struct DateHashFunc
{
size_t operator()(const Date& d)
{
size_t hash = 0;
hash += d._year;
hash *= 131;
hash += d._month;
hash *= 131;
hash += d._day;
hash *= 131;
return hash;
}
};
// int main()
// {
// //int a[] = { 19,30,52,63,11,22 };
// const char* a1[] = { "abcd", "sort", "insert" };
// open_address::HashTable<string, string> ht1;
// for (auto& e : a1)
// {
// ht1.Insert({ e, e });
// }
// cout << HashFunc<string>()("abcd") << endl;
// cout << HashFunc<string>()("bcad") << endl;
// cout << HashFunc<string>()("aadd") << endl;
// int a2[] = { -19,-30,5,36,13,20,21,12 };
// open_address::HashTable<int, int> ht2;
// for (auto e : a2)
// {
// ht2.Insert({ e, e });
// }
// // 哈希冲突
// open_address::HashTable<Date, int, DateHashFunc> ht;
// ht.Insert({ { 2024, 10, 12 }, 1});
// ht.Insert({ { 2024, 12, 10 }, 1 });
// return 0;
// }
int main()
{
int a2[] = { 19,30,5,36,13,20,21,12,24,96 };
hash_bucket::HashTable<int, int> ht2;
for (auto e : a2)
{
ht2.Insert({ e, e });
}
ht2.Insert({ 100, 100 });
ht2.Insert({ 101, 101 });
return 0;
}
哈希表的核心价值在于平衡了时间与空间效率，其思想不仅体现在 unordered_map 等容器的实现中，更渗透在分布式存储、数据库索引等高级领域。从开放寻址的紧凑存储到链地址法的灵活扩容，两种实现方式各有千秋。希望本文的拆解能帮助你真正吃透哈希表的底层逻辑，在算法题与工程实践中做到游刃有余。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
9
0- 0
已为社区贡献4条内容
所有评论(0)