哈希表原理与开放定址法C++实现

目录

• 前言
• 一、什么是哈希表
• 二、三大核心问题
• 三、哈希函数——从 key 到下标的桥梁
  • 3.1 基本形式
  • 3.2 整型 key 的哈希函数
  • 3.3 字符串 key 的哈希函数——BKDR Hash
  • 3.4 自定义类型的哈希函数
• 四、开放定址法——冲突了就往旁边挪
  • 4.1 线性探测
  • 4.2 代码实现——Insert
  • 4.3 代码实现——Find
• 五、懒惰删除——为什么不能直接清空
  • 5.1 问题场景
  • 5.2 解决方案：三态标记
• 六、扩容——装太满了就要换个大房子
  • 6.1 为什么需要扩容
  • 6.2 不能"原地扩容"
  • 6.3 扩到多大？——质数优化
  • 6.4 扩容的代码实现
• 七、完整代码整合
• 八、测试验证
• 九、开放定址法的优缺点
  • 优点
  • 缺点
• 十、总结与预告

前言

假如你是一个图书管理员，有10万本书要管理。读者每次还书，你必须快速判断这本书该放回哪个书架。如果一本书一本书地去翻找，效率显然太低了。

有没有一种方法，看一眼书名，就能直接算出它该放的位置？

这就是哈希表（Hash Table） 的核心思想——建立 key 与存储位置的直接映射。

本文带你从零开始，用开放定址法手撕一个哈希表。链地址法留到下一篇再聊。

一、什么是哈希表

哈希表是一种 key-value 存储结构，通过哈希函数把 key 转换成数组下标，从而实现 O(1) 的平均查找效率。

key ──> 哈希函数 ──> 下标 ──> 直接访问数组元素

听起来很美好，但现实很骨感——两个不同的 key 完全可能算出同一个下标，这就是哈希冲突。

解决哈希冲突有两大流派：

• 开放定址法（Open Addressing）：冲突了就在数组里找下一个空位
• 链地址法（Separate Chaining）：数组每个位置挂一个链表，冲突了就往后接

本文聚焦开放定址法。

二、三大核心问题

实现一个可用的哈希表，需要解决三个问题：

下面逐一攻破。

三、哈希函数——从 key 到下标的桥梁

3.1 基本形式

size_t hash = hashFunc(key) % _tables.size();

分两步：先用 hashFunc 把 key 映射成整数，再取模映射到数组下标范围。

3.2 整型 key 的哈希函数

整型 key 最简单——直接当 size_t 用就行：

template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

对于 int、char、long 等类型，直接用隐式类型转换即可。

3.3 字符串 key 的哈希函数——BKDR Hash

字符串才是最常见的 key 类型。把字符串的每个字符加起来当作哈希值？太容易冲突了："abc" 和 "cba" 会算出一样的值。

工程上常用BKDR Hash，核心是把字符累加并不断乘以一个质数（如 131），打乱字符顺序的影响：

template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131; // 每次乘131，打乱排列顺序
}
return hash;
}
};

这是 C++ 的模板特化——当 K 是 string 时，编译器自动匹配这个版本。

3.4 自定义类型的哈希函数

如果你用自定义类型（比如 Date）做 key，需要自己写哈希仿函数：

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

使用时作为模板参数传入：

HashTable<Date, int, DateHashFunc> ht;

四、开放定址法——冲突了就往旁边挪

4.1 线性探测

开放定址法的思路很朴素：

你要放的位置被人占了？那往旁边挪一格看看。还被占？再挪一格……直到找到空位。

用公式表达：

hashi = (hash0 + i) % tablesize （i = 1, 2, 3, …）

这称为线性探测（Linear Probing）。hash0 是第一次算出的位置，每次冲突后探测距离 +1。

4.2 代码实现——Insert

bool Insert(const pair<K, V>& kv)
{
// 1. 查重：key 已存在则插入失败
if (Find(kv.first))
return false;

// 2. 负载因子 >= 0.7，触发扩容（后面细讲）
if (_n * 10 / _tables.size() >= 7)
{
// … 扩容逻辑
}

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

// 4. 插入数据
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}

关键细节：

• 先查重再插入：防止同一个 key 插入两次
• 探测循环：只要位置状态是 EXIST 就继续找，直到遇到 EMPTY 或 DELETE
• 取模保证下标不越界：每次 % _tables.size() 让探测路径在数组内循环

4.3 代码实现——Find

查找与插入的探测逻辑完全相同：

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

查找的终止条件是 _state == EMPTY：遇到真正的空位就停止，说明 key 不在表中。为什么不遇到 DELETE 就停？因为 DELETE 只是"曾经有人，现在走了"，探测链不能断。

五、懒惰删除——为什么不能直接清空

5.1 问题场景

假如数组里有三个元素 A、B、C，它们发生冲突后依次存放在位置 3、4、5：

下标: … [3] [4] [5] [6] …
状态: … EXIST EXIST EXIST EMPTY …
元素: … A B C …

如果我们直接删掉 B（把位置 4 设为 EMPTY），查找 C 时：算出的 hash0=3 → 发现 A ≠ C → 探测到 4 → 看到 EMPTY → 直接返回 nullptr，但其实 C 就在位置 5！

5.2 解决方案：三态标记

用三个状态区分节点的生命周期：

enum State
{
EXIST, // 存着有效数据
EMPTY, // 从未使用过
DELETE // 曾经有数据，现在被删了
};

template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY; // 默认是空
};

删除时标记为 DELETE，而非恢复为 EMPTY：

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

DELETE 的作用就是告诉查找函数：“这里曾经有人，你继续往下找，别停。”

六、扩容——装太满了就要换个大房子

6.1 为什么需要扩容

开放定址法的性能严重依赖负载因子（load factor）：

负载因子 = 元素个数 / 表长

负载因子越大，冲突概率越高，探测路径越长，性能退化越严重。一般把阈值设在 0.7，超过就扩容。

6.2 不能"原地扩容"

你可能会想：直接 resize 成原来的两倍不就行了？

不行！ 因为数组长度变了，每个元素的哈希取模结果也跟着变了——原来在位置 5 的元素，扩容后可能要去位置 11。所以扩容 = 申请新数组 + 全部重新插入。

6.3 扩到多大？——质数优化

如果表长取 2 的幂（16、32、64…），取模运算 key % size 会退化为只取低位，分布可能非常不均匀。

工程上通常取一个质数作为表长（STL 里就是这么干的）：

inline unsigned long __stl_next_prime(unsigned long n)
{
static const unsigned long __stl_prime_list[28] = {
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 + 28;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last – 1) : *pos;
}

这是 SGI STL 源码中的质数表，用 lower_bound 二分查找第一个 ≥ n 的质数，确保表长始终在一个优质值上增长。

6.4 扩容的代码实现

// 负载因子 >= 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);
}

步骤很清晰：

七、完整代码整合

把以上各部分拼起来，就得到一个可用的开放定址法哈希表：

#pragma once
#include <vector>
#include <string>
using namespace std;

enum State
{
EXIST,
EMPTY,
DELETE
};

template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};

// 默认哈希函数——适用于整型
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

// 特化：string 的 BKDR Hash
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131;
}
return hash;
}
};

// SGI STL 质数表
inline unsigned long __stl_next_prime(unsigned long n)
{
static const unsigned long __stl_num_primes = 28;
static const unsigned long __stl_prime_list[28] = {
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 + 28;
const unsigned long* 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(11)
, _n(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 (auto& data : _tables)
{
if (data._state == EXIST)
{
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;
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 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;
}

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

private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
};

八、测试验证

int main()
{
// 测试1：string → string
const char* words[] = { "abcd", "sort", "insert" };
HashTable<string, string> ht1;
for (auto e : words)
{
ht1.Insert({ e, e });
}

// 测试2：int → int（触发冲突和扩容）
int nums[] = { 19, 30, 5, 36, 13, 20, 21, 12 };
HashTable<int, int> ht2;
for (auto e : nums)
{
ht2.Insert({ e, e });
}

// 测试3：自定义类型 key
HashTable<Date, int, DateHashFunc> ht3;
ht3.Insert({ { 2024, 10, 12 }, 1 });
ht3.Insert({ { 2024, 12, 10 }, 1 });

return 0;
}

验证要点：

• ht1 测试了模版特化后的 BKDR 字符串哈希
• ht2 用 _tables 初始大小 11，插入 8 个元素后负载因子 = 8/11 ≈ 0.73，超过 0.7，触发扩容
• ht3 验证了自定义哈希仿函数的机制

九、开放定址法的优缺点

优点

• 内存紧凑：所有数据存在一个数组里，没有额外的链表指针开销
• 缓存友好：数据在内存中连续，CPU Cache 命中率高
• 实现简单：相比链地址法，不需要维护额外的链表结构

缺点

• 对负载因子敏感：装得越满，性能退化越严重
• 删除麻烦：必须用懒惰删除，否则会打断探测链
• 扩容代价大：扩容时所有元素都要重新哈希插入

十、总结与预告

本文用 C++ 从零实现了一个基于开放定址法的哈希表，核心知识点回顾：

下一篇预告：链地址法——每个桶挂一个链表，彻底告别"探测链"的烦恼。同时还会对比两种方法在实际工程中的应用场景（std::unordered_map 用的就是链地址法）。

如有纰漏，欢迎指正！