【C++ STL篇(十四)】哈希表实现：开放定址法与链地址法

大家好，欢迎来到 huangjin007_ 的博客
⭐
个人主页：huangjin007_
🔥
文章收录专栏：零基础入门C++

总会有一些坚持能从冰封的土地里培育出十万朵怒放的蔷薇

C++ STL篇(十四) —— 哈希表实现

  本篇文章将带你从零开始，吃透哈希表底层原理 。全程干货，坐稳发车~ ദ്ദി˶ｰ̀֊ｰ́ )✧

文章目录

• C++ STL篇(十四) —— 哈希表实现
• • 一、哈希表到底在解决什么问题？
  • • 1.1 直接定址法：理想状态下
    • 1.2 哈希冲突的出现
  • 二、衡量哈希表的关键指标：负载因子
  • 三、哈希函数的设计
  • • 3.1 除留余数法（除法散列法）
    • 3.2 乘法散列法（了解即可）
    • 3.3 全域散列法（了解即可）
    • 3.4 其他方法
  • 四、处理哈希冲突的两大流派
  • 五、开放定址法（线性探测）实现详解
  • • 5.1 状态标记：为什么不能随便删除？
    • 5.2 整体代码结构
    • 5.3 默认哈希函数与 string 特化
    • 5.4 质数表与扩容大小选择
    • 5.5 Insert：扩容与线性探测
    • 5.6 Find 与 Erase
  • 六、链地址法（哈希桶）实现详解
  • • 6.1 整体代码结构
    • 6.2 Insert：头插法 + 扩容
    • 6.3 Find 与 Erase
    • 6.4 拷贝构造、赋值与析构
    • • 析构函数
      • 拷贝构造函数
      • 赋值运算符（现代 C++ 写法）
  • 七、测试与使用示例
  • • 7.1 自定义类型作为 key
  • 八、两种实现方式的对比与选择
  • 结语：

一、哈希表到底在解决什么问题？

1.1 直接定址法：理想状态下

  假设你有一组学生的成绩，学号范围是 0~99，你想根据学号快速查到成绩。最直接的办法是开一个长度 100 的数组，学号是多少，就把成绩存到下标为多少的位置。查找时，拿着学号直接去对应下标取数据——时间复杂度 O(1)，完美！

  再比如，你只想存储小写字母 ‘a’~‘z’ 的出现次数，开一个长度 26 的数组，让 'a' 对应下标 0，'b' 对应下标 1……这只需要用 ch – 'a' 算出一个相对位置，也是 O(1)。

就像这道OJ题：

传送门：字符串中的第一个唯一字符

class Solution {
public:
int firstUniqChar(string s) {
int count[26]; // 数组大小为26，对应26个小写字母
for(auto ch : s)
{
count[ch – 'a']++;// 将字符转换为数组索引，并增加计数
}

for(size_t i = 0;i<s.size();i++)
{
// 如果当前字符的出现次数为1，说明是第一个不重复的字符
if(count[s[i] – 'a'] == 1)
return i;
}
return –1;
}
};

  这种方式叫直接定址法：关键字本身（或经过简单偏移）就直接作为存储位置的下标。

1.2 哈希冲突的出现

  直接定址法有个致命伤：它要求关键字的范围必须很集中、很有限。如果关键字是身份证号、手机号、或者任意字符串呢？哪怕只存几百个数据，你也不可能开一个能覆盖所有可能值的巨型数组（内存直接爆炸）!

  假设我们只有数据范围是[0,9999]的N个值，我们要映射到一个M个空间的数组中(一般情况下M>=N)，那么就要借助 哈希函数 (hashfunction) hf，关键字 key 被放到数组的 h(key) 位置，这里要注意的是 h(key) 计算出的值必须在[0,M)之间。

  但问题又来了：既然数组大小 M 是有限的，而可能的 Key 是无限的（或非常多的），必然会出现两个不同的 Key 被映射到同一个位置的情况，这叫哈希冲突（Hash Collision）。

  举个例子：数组大小 M = 10，哈希函数是 key % 10。那么 key = 15 和 key = 25 都会映射到位置 5，它俩就冲突了。

因此，设计哈希表时我们要同时解决两个核心问题：

二、衡量哈希表的关键指标：负载因子

  在深入具体方法之前，先介绍一个贯穿始终的概念——负载因子（Load Factor）。

  假设哈希表底层数组的大小为 M，目前已经存了 N 个数据，那么：

负载因子

=

N

M

负载因子 = \\frac{N}{M}

负载因子=MN​

负载因子的直观意义是“数组有多满”。它直接影响两个东西：

• 负载因子越大 -> 数组越满，冲突概率越高，但空间利用率高；
• 负载因子越小 -> 数组越空，冲突概率低，但空间利用率低，浪费内存。

  这是一个经典的 “时间换空间” 或 “空间换时间” 的权衡。在实际实现中，我们会设定一个阈值（比如 0.7 或 1.0），当负载因子超过这个值时，就对哈希表进行扩容，重新分配一个更大的数组，把所有数据重新哈希进去。

三、哈希函数的设计

  一个好的哈希函数应该能让关键字均匀地散列到各个位置，尽量避免“扎堆”。这里我们介绍几种经典的哈希函数设计方法。

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

  这是最常用、最直观的方法：用关键字除以哈希表大小 M，取余数作为下标。

h

(

k

e

y

)

=

k

e

y

%

M

h(key)=key\\%M

h(key)=key%M

  这个方法简单高效，但有一个关键细节：M 的取值要讲究。如果你选择 M = 2^X（比如 16、32、64……），那么 key % M 实际上就相当于只保留了 key 二进制形式的低 X 位。那些高位不同、低位相同的 key 就会全部冲突。（二进制规则： key % 2ⁿ = 只保留二进制最后n位）

  例如 M = 16 时，63（二进制 00111111）和 31（二进制 00011111）的低 4 位都是 1111，都映射到位置 15，尽管它们看起来毫不相关。同理，M 取 10^X（比如 100、1000）也会只保留十进制末尾几位，同样容易产生规律性冲突。

  所以经典的数据结构教材通常建议 M 选一个不太接近 2 的整数次幂的质数（素数），这样可以让 key 的所有位都参与到取模运算中，分布更均匀。

延伸思考：Java 的 HashMap 为什么用 2 的幂？

  Java的HashMap采用除法散列法时就是2的整数次幂做哈希表的大小M，这样玩的话，就不用取模，而可以直接位运算，相对而言位运算比模更高效一些。   但是他不是单纯的去取模，比如M是2^16次方，本质是取后16位，那么用key’=key>>16，然后把key和key’异或的结果作为哈希值。   也就是说我们映射出的值还是在[0,M)范围内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀一些即可。

3.2 乘法散列法（了解即可）

乘法散列法不要求 M 是质数。它的思路分两步：

h

(

k

e

y

)

=

f

l

o

o

r

(

M

×

(

(

A

×

k

e

y

)

%

1.0

)

)

h(key) = \\mathrm{floor}\\big(M \\times ((A \\times key)\\% 1.0)\\big)

h(key)=floor(M×((A×key)%1.0))

其中floor表示对表达式进行向下取整，A∈(0,1)。

Knuth 建议 A 取黄金分割比

(

5

−

1

)

/

2

≈

0.618

(\\sqrt{5}-1)/2 \\approx 0.618

(5

​−1)/2≈0.618。因为最后一步是乘 M，所以 key 的微小变化也能被放大到整个表的不同位置。

乘法散列法对哈希表大小

M

M

M 无取值约束，

设：

M

=

1024

,

k

e

y

=

1234

,

A

=

0.6180339887

M=1024,\\ \\mathit{key}=1234,\\ A=0.6180339887

M=1024, key=1234, A=0.6180339887

3.3 全域散列法（了解即可）

  如果存在一个恶意攻击者，他知道你用的哈希函数是什么，他就可以故意构造一批 key，让它们全部映射到同一个位置，把你的哈希表性能直接拉到最差（O(n) 查找）。这叫“哈希洪水攻击”。

  全域散列法通过在运行时随机选择哈希函数来对抗这种攻击。其典型形式是：

h

a

b

(

k

e

y

)

=

(

(

a

×

k

e

y

+

b

)

%

P

)

%

M

h_{ab}(key) = ((a \\times key + b) \\%P) \\% M

hab​(key)=((a×key+b)%P)%M

  其中 P 是一个比所有 key 都大的质数，a 从 [1, P-1] 中随机选一个任意整数，b 从 [0, P-1] 中随机选一个任意整数。这样哈希函数就有了随机性，攻击者无法事先确定用哪个函数，也就无法轻易构造冲突数据。

  需要注意，一旦哈希表初始化时选定了某个 a 和 b，后续的操作都得一直用它，不能每次查找时重新随机选，否则自己都找不着之前存的数据了。

h

a

b

(

k

e

y

)

=

(

(

a

×

k

e

y

+

b

)

%

P

)

%

M

h_{ab}(key) = ((a \\times key + b)\\%P)\\%M

hab​(key)=((a×key+b)%P)%M

假设

P

=

17

，

M

=

6

，

a

=

3

，

b

=

4

P=17，M=6，a=3，b=4

P=17，M=6，a=3，b=4， 则

h

34

(

8

)

=

(

(

3

×

8

+

4

)

%

17

)

%

6

=

5

h_{34}(8) = ((3 \\times 8 + 4)\\%17)\\%6 = 5

h34​(8)=((3×8+4)%17)%6=5

3.4 其他方法

  上面的几种方法是《算法导论》书籍中讲解的方法。

  《殷人昆 数据结构：用面向对象方法与C++语言描述（第二版）》和《[数据结构(C语言版)].严蔚敏_吴伟民》等教材型书籍上面还给出了平方取中法、折叠法、随机数法、数学分析法等，这些方法相对更适用于一些局限的特定场景，有兴趣可以去看看这些书籍。

四、处理哈希冲突的两大流派

  有了哈希函数，冲突还是不可避免。如何解决冲突，决定了哈希表的组织形态。主流方法分为两类：

• 开放定址法（Open Addressing）：冲突时，顺着某种探测序列在数组里找到下一个空位存进去。所有数据都老老实实待在数组里。
• 链地址法（Separate Chaining）：数组里不直接存数据，而是存一个链表的头指针。冲突的数据就挂在这个链表上。也叫 “拉链法” 或 “哈希桶” 。

下面我们结合代码，深入剖析这两种实现。

五、开放定址法（线性探测）实现详解

  开放定址法的核心思想是：冲突了，就顺着一条预先定好的“探测路径”找空位。常见的探测路径有三种：

1. 线性探测

  最简单的方法：发生冲突后，依次往后找，一个一个地探测，直到找到空位。如果走到表尾，就绕回表头继续。公式为：

hashi = (hash0 + i) % M (i = 1, 2, 3, …)

其中 hash0 = key % M 是初始位置。

例子：M=11，插入 {19, 30, 5, 36, 13, 20, 21, 12}。

• 19 % 11 = 8，位置 8 空，直接放入。
• 30 % 11 = 8，冲突，i=1，探测 9，空，放入。
• 5 % 11 = 5，放入。
• 36 % 11 = 3，放入。
• 13 % 11 = 2，放入。
• 20 % 11 = 9，探测 9 已占，i=1 探测 10，空，放入。
• 21 % 11 = 10，冲突，i=1 探测 0，空，放入。
• 12 % 11 = 1，放入。

  线性探测实现简单，但有一个明显问题：堆积（群集）。一旦某个连续区间被占满，后续映射到这个区间的任何 Key 都会去争抢区间之后的同一个空位，导致冲突进一步加剧。

2. 二次探测

  从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置；

• $h(key)=hash0=key\%M$
• 二次探测当 $hashi=(hash0-i^2)\%M$

例子：M=11，插入 {19, 30, 52, 63, 11, 22}。19、30、52、63 的 hash0 都是 8，产生连续冲突，通过平方步长可以更快找到空位。

3. 双重散列 (了解即可)

  第一个哈希函数算出的值发生冲突，使用第二个哈希函数算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。

• h

  1

  (

  k

  e

  y

  )

  =

  h

  a

  s

  h

  0

  =

  k

  e

  y

  %

  M

  h_1(key)=hash0=key \\% M

  h1​(key)=hash0=key%M，

  h

  a

  s

  h

  0

  hash0

  hash0位置冲突了，则双重探测公式为：

  h

  c

  (

  k

  e

  y

  ,

  i

  )

  =

  h

  a

  s

  h

  i

  =

  (

  h

  a

  s

  h

  0

  +

  i

  ×

  h

  2

  (

  k

  e

  y

  )

  )

  %

  M

  ,

  i

  =

  {

  1

  ,

  2

  ,

  3

  ,

  .

  .

  .

  ,

  M

  }

  hc(key,i)=hash_i=\\big(hash0 + i \\times h_2(key)\\big)\\%M,\\quad i=\\{1,2,3,…,M\\}

  hc(key,i)=hashi​=(hash0+i×h2​(key))%M,i={1,2,3,…,M}

• 要求

  h

  2

  (

  k

  e

  y

  )

  <

  M

  h_2(key) < M

  h2​(key)<M 且

  h

  2

  (

  k

  e

  y

  )

  h_2(key)

  h2​(key) 和

  M

  M

  M 互为质数，两种常用取值：

• $M$
• $M$

• 保证

  h

  2

  (

  k

  e

  y

  )

  h_2(key)

  h2​(key) 与

  M

  M

  M互质是因为根据固定的偏移量所寻址的所有位置将形成一个群，若最大公约数

  p

  =

  gcd

  ⁡

  (

  M

  ,

  h

  2

  (

  k

  e

  y

  )

  )

  >

  1

  p = \\gcd(M,h_2(key))>1

  p=gcd(M,h2​(key))>1，那么所能寻址的位置的个数为

  M

  P

  <

  M

  \\displaystyle\\frac{M}{P}<M

  PM​<M，使得对于一个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的位置为

  {

  1

  ,

  4

  ,

  7

  ,

  10

  }

  \\{1,4,7,10\\}

  {1,4,7,10}，寻址个数为

  12

  gcd

  ⁡

  (

  12

  ,

  3

  )

  =

  4

  \\displaystyle\\frac{12}{\\gcd(12,3)} = 4

  gcd(12,3)12​=4

• 下面演示

  {

  19

  ,

  30

  ,

  52

  ,

  74

  }

  \\{19,30,52,74\\}

  {19,30,52,74} 等这一组值映射到

  M

  =

  11

  M=11

  M=11的表中，设

  h

  2

  (

  k

  e

  y

  )

  =

  k

  e

  y

  %

  10

  +

  1

  h_2(key) = key\\%10 + 1

  h2​(key)=key%10+1

5.1 状态标记：为什么不能随便删除？

  开放定址法有一个容易踩的坑：删除一个元素后，不能简单地把位置清空。

  看这个例子M=11，插入 {19, 30, 5, 36, 13, 20, 21, 12}。

  插入 19（位置 8），插入 30（位置 8 冲突，线性探测到 9），插入 20（位置 9 冲突，探测到 10）。此时数组：

  现在我们删除 30。如果直接把位置 9 清空，再去查找 20 时：计算 hash(20)=9，发现位置 9 空了，按探测逻辑会认为“遇到空位，查找失败”。但实际上 20 在位置 10 存着呢！

解决办法是给数组的每个位置增加一个状态标记：

• EXIST：该位置存有数据
• EMPTY：该位置从未存过数据
• DELETE：该位置曾经有数据，但已被删除

  查找时，遇到 EMPTY 才停止，遇到 DELETE 继续往后探测。删除时，找到目标后直接把状态改为 DELETE 即可。

5.2 整体代码结构

我们先看开放定址法的完整代码，然后逐块剖析：

namespace open_address
{
// 状态枚举
enum State { EXIST, EMPTY, DELETE };

// 哈希表每个槽位存储的数据
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};

// 默认哈希函数（将 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)
{
size_t hash = 0;
for (auto ch : s) {
hash += ch;
hash *= 131; // 乘一个质数让分布更均匀
}
return hash;
}
};

// 质数表（用于扩容时选取新大小）
inline unsigned long __stl_next_prime(unsigned long n)
{
static const unsigned long 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
};
auto first = begin(primes);
auto last = end(primes);
auto pos = lower_bound(first, last, n);
return pos == last ? *(last – 1) : *pos;
}

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
HashTable()
:_tables(__stl_next_prime(0))
,_n(0)
{}

bool Insert(const pair<K, V>& kv);
HashData<K, V>* Find(const K& key);
bool Erase(const K& key);

private:
vector<HashData<K, V>> _tables;
size_t _n = 0; // 已存储的数据个数
};
}

5.3 默认哈希函数与 string 特化

  Key 可能是 int、string 甚至自定义结构体，它们不能直接用 % 运算。我们需要一个仿函数（函数对象）把 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)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131; // 乘一个质数让分布更均匀
}
return hash;
}
};

  如果用户自定义类型作为 Key，只需自己写一个仿函数, 通过模版参数传入即可。

  我们用 C++ 的模板特化语法 template<> struct HashFunc<string>，专门为 string 定制了这个版本。当用户声明 HashTable<string, int> 时，编译器会自动选用这个特化版本。

5.4 质数表与扩容大小选择

  前面说过，哈希表容量取质数有助于减少冲突。但扩容往往是按“约两倍”增长，两倍不一定是质数。这里我们借鉴了 STL 的 SGI 版本中的做法：预先算好一个将近两倍增长的质数表，每次扩容时用 lower_bound 找到第一个大于等于目标值的质数。

inline unsigned long __stl_next_prime(unsigned long n)
{
// 28 个经过挑选的质数，大致按 2 倍递增
static const unsigned long primes[] = { /* … */ };
auto first = begin(primes);
auto last = end(primes);
auto pos = lower_bound(first, last, n);
return pos == last ? *(last – 1) : *pos;
}

  lower_bound(first, last, n) 是在已排序的 primes 数组中用二分查找，找到第一个 >= n 的位置。如果 n 比表里所有质数都大，就返回表里最大的那个（兜底）。

  构造函数里我们用 __stl_next_prime(0) 来获取第一个质数 53 作为初始大小，这样哈希表一出生就是 53 个槽位。

5.5 Insert：扩容与线性探测

bool Insert(const pair<K, V>& kv)
{
// 1. 查重
if (Find(kv.first))
return false;

// 2. 负载因子 >= 0.7 就扩容
if (_n * 10 / _tables.size() >= 7)
{
HashTable<K, V, Hash> newht;
newht._tables.resize(__stl_next_prime(_tables.size() + 1));

for (auto& data : _tables)
{
if (data._state == EXIST)
newht.Insert(data._kv);
}
_tables.swap(newht._tables);
}

// 3. 线性探测插入
Hash hash;
size_t hash0 = hash(kv.first) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state == EXIST)
{
hashi = (hash0 + i) % _tables.size();
++i;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;

return true;
}

逐段解读：

• 查重：哈希表的 key 通常是唯一的，插入前先调用 Find 确认没有重复。
• 扩容判断：_n * 10 / _tables.size() >= 7 等价于 _n / _tables.size() >= 0.7，避免了浮点数运算。超过 0.7 时就创建一个新的哈希表，新表大小从质数表中获取（_tables.size() + 1 保证新表至少比旧表大）。然后遍历旧表，把所有 EXIST 的数据重新插入到新表（注意，这里会递归调用新表的 Insert，但新表是空的，不会再触发扩容）。最后用 swap 交换新旧两个数组的指针，旧数组随着 newht 被销毁而自动释放。
• 线性探测：
  • 先计算初始哈希值 hash0 = key % M。
  • 如果这个位置已经是 EXIST（说明冲突了），我们就依次探测 hash0+1, hash0+2, hash0+3 …，每次都对 M 取模，保证下标不越界且能绕回表头。
  • 当 _state != EXIST（即 EMPTY 或 DELETE）时，循环结束，这个位置就是我们要插入的空位。

5.6 Find 与 Erase

HashData<K, V>* Find(const K& key)
{
Hash hash;
size_t hash0 = hash(key) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
return &_tables[hashi];

hashi = (hash0 + i) % _tables.size();
++i;
}
return nullptr;
}

  Find 的探测逻辑与 Insert 完全一致：从初始位置出发，线性向后探测。只有当遇到 EMPTY 状态时，才能确认 key 一定不存在（因为如果有插入，它一定会在遇到 EMPTY 之前填入某个空位，而 DELETE 位并不代表查找终点）。

bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
—_n;
return true;
}
return false;
}

  删除操作非常简单：先找到目标，把它的状态标记为 DELETE，然后把计数减一。不会真正释放空间，也不会把那个位置变回 EMPTY，这正是前面状态标记存在的意义。

六、链地址法（哈希桶）实现详解

  开放定址法的最大问题是所有数据挤在同一个数组里，冲突会互相影响（比如线性探测的“堆积”现象）。而链地址法则彻底改变了组织方式：

• 数组里每个位置存的不是数据，而是一个链表的头指针。
• 当一个新数据映射到某个位置时，直接把它挂到该位置的链表上。
• 冲突再多，也只是链表变长一点，不会影响其他位置。

  因为数据可以挂链表，所以链地址法的负载因子可以大于 1。STL 中的 unordered_map 通常把最大负载因子设为 1，超过就扩容。

6.1 整体代码结构

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)
{}

// 拷贝构造、赋值、析构后面单独讲解

bool Insert(const pair<K, V>& kv);
Node* Find(const K& key);
bool Erase(const K& key);

private:
vector<Node*> _tables; // 每个桶存链表头指针
size_t _n = 0; // 数据总数
};
}

  这里 HashFunc 和质数表 __stl_next_prime 与开放定址法完全共用，不再重复列出。

6.2 Insert：头插法 + 扩容

bool Insert(const pair<K, V>& kv)
{
Hash hash;

// 扩容：当数据个数等于表大小时（负载因子 >= 1）
if (_n == _tables.size())
{
// 创建新表
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);
}

// 插入新节点
size_t hashi = hash(kv.first) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi]; // 新节点指向当前链表头
_tables[hashi] = newnode; // 新节点成为新的链表头
++_n;

return true;
}

关键点解析：

6.3 Find 与 Erase

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;
}

  查找非常简单：算出桶下标，然后在这个桶的链表里顺序遍历，找到就返回节点指针，没找到返回 nullptr。

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;
}
prev = cur;
cur = cur->_next;
}
return false;
}

  删除就是单链表的节点删除：维护一个 prev 前驱指针，找到目标后，分“删除头节点”和“删除中间/尾节点”两种情况处理。删除后记得 –_n。

6.4 拷贝构造、赋值与析构

  因为我们的哈希桶是自己管理内存（用 new 创建节点），所以必须处理好深拷贝和内存释放，否则会出现重复释放、内存泄漏等问题。

析构函数

~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;
}
}

  遍历每个桶，逐个删除链表节点，最后把所有桶指针置空。

拷贝构造函数

HashTable(const HashTable& ht)
:_tables(ht._tables.size(), nullptr)
,_n(ht._n)
{
for (size_t i = 0; i < ht._tables.size(); i++)
{
Node* cur = ht._tables[i];
Node* tail = nullptr;
while (cur)
{
Node* newnode = new Node(cur->_kv);
if (tail == nullptr)
_tables[i] = newnode;
else
tail->_next = newnode;
tail = newnode;
cur = cur->_next;
}
}
}

  拷贝构造要完成“深拷贝”。我们先将自己的 _tables 调整为与源表相同的大小，初始全为 nullptr。然后遍历源表每个桶，对于桶里的每个节点，用尾插法逐个复制，保持链表顺序不变。

赋值运算符（现代 C++ 写法）

void swap(HashTable& tmp)
{
_tables.swap(tmp._tables);
std::swap(_n, tmp._n);
}

HashTable& operator=(HashTable tmp)
{
swap(tmp);
return *this;
}

  这里采用了“拷贝并交换”惯用法。参数 tmp 是按值传递的，调用赋值运算符时会先利用拷贝构造函数生成一个临时副本。然后我们把自己和这个临时副本的内容交换一下，临时副本离开作用域时自动析构，顺带释放了旧数据。这种写法异常安全且代码简洁。

七、测试与使用示例

7.1 自定义类型作为 key

  当 key 是我们自己定义的类型（比如日期类），不能直接取模，需要提供专门的哈希仿函数：

struct Date
{
int _year, _month, _day;
Date(int year = 1, int month = 1, int day = 1)
:_year(year), _month(month), _day(day)
{}

bool operator==(const Date& d) const
{
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()
{
open_address::HashTable<Date, int, DateHashFunc> ht;
ht.Insert({{2026, 5, 30}, 1});
ht.Insert({{2026, 5, 31}, 1});
return 0;
}

  使用时，只需将仿函数作为第三个模版参数传入：HashTable<Date, int, DateHashFunc> ht;。这体现了 C++ 模版的灵活性——只要提供一个能将 Key 转为整数的仿函数，任何类型都能作为哈希表的 Key。

八、两种实现方式的对比与选择

实际应用中的选择：

• 在 C++ STL 中，unordered_map 和 unordered_set 底层采用的是链地址法（哈希桶），使用单向链表，当桶过长时可能转为红黑树（Java 的 HashMap 在桶长度超过 8 时会转为红黑树，防止极端退化）。

结语：

  今天的内容到这里就结束了，希望你能有所收获~

干货整理到手抖，觉得有用的话，赏个三连回回血？__(:ᗤ」ㄥ)_ _