外观
Hash Table（哈希表）与 C++ 实现
学数据结构时，哈希表通常会给人一种“很神奇”的感觉：为什么它查找一个元素，经常可以快到接近 O(1)？
如果把查找问题想得更朴素一点，其实它做的事并不复杂：
- 先准备一个数组；
- 再想办法把 key 直接映射到数组下标；
- 然后就能绕过大部分线性扫描。
这篇文章想讲清楚三件事：
- 哈希表到底为什么快；
- 冲突是怎么产生的，又该怎么处理；
- 如何用 C++ 手写一个最基本的哈希表。
从查找问题开始
假设我们要存一批键值对，比如：
(1, "one")
(8, "eight")
(15, "fifteen")如果用普通数组或链表来存，查找一个 key 时，往往要一个个比对过去。这种做法在数据量不大时没什么问题，但一旦元素很多，查找成本就会逐渐接近 O(n)。
哈希表的思路是：不要再“挨个找”，而是尽量“直接定位”。
也就是说，给定一个 key，希望它能先经过一个函数，直接落到某个数组位置：
key -> hash(key) -> index -> data最常见的形式就是：
index = hash(key) % table_size;比如：
key: "apple"
hash("apple") -> 123456
index = 123456 % 10 = 6那么这个数据就可以放进：
table[6]这样一来，只要 hash 函数设计得合理，查找时就不需要从头扫到尾，而是直接去某个位置看看，大部分时候都会快很多。
为什么它常常是 O(1)
哈希表最吸引人的地方，就是它在理想情况下的时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| 查找 | O(1) |
| 插入 | O(1) |
| 删除 | O(1) |
这里的 O(1) 并不是说“永远只做一步”，而是说它的平均开销不会随着数据量线性增长。
本质原因很简单：
它把“查找元素”这个问题，转成了“计算下标”这个问题。
只要下标能算得准、分布也比较均匀，访问速度就会非常接近数组随机访问的效率。
但冲突是躲不掉的
哈希表再快，也不可能保证两个不同的 key 永远落到不同位置。
例如：
hash("a") -> 5
hash("b") -> 5这就是所谓的哈希冲突：两个不同的 key 被映射到了同一个桶里。
冲突并不意味着哈希表失效，只是说明我们需要额外的规则来处理“同一个位置里塞进多个元素”。
常见方法有两类。
两种常见的冲突处理方法
1. 链地址法
链地址法（separate chaining）的思路最直观：每个桶里不只放一个元素，而是放一个链表，或者任何能容纳多个元素的容器。
如果两个 key 都落到 index 5，就把它们串起来：
index 5 -> ("a", 1) -> ("b", 2)这样查找时，先找到桶，再在桶内部做一次小范围搜索。
这种做法实现简单，也很容易理解，所以教学和手写实现时很常见。
2. 开放寻址
开放寻址（open addressing）则是另一种思路：既然当前位置被占了，那就继续往后找空位。
例如：
index 5 -> 占用
-> 6 -> 7 -> ...这种方式不需要额外链表，数据仍然存在同一块数组里，但对探测策略、删除逻辑、装载因子控制都会更敏感。
很多工业实现都会用这类思路，例如现代哈希表实现里常见的线性探测、二次探测、Robin Hood hashing 等。直观起见，这篇文章后面还是用更容易解释的链地址法来写一个 C++ 版本。
用 C++ 手写一个最基本的哈希表
下面实现一个非常简化的版本：
- 底层用
vector作为桶数组； - 每个桶里放一个
list<pair<int, string>>； - hash 函数直接用
key % capacity； - 支持插入、查找、删除和包含判断。
#include <iostream>
#include <vector>
#include <list>
#include <string>
using namespace std;
class HashTable {
private:
vector<list<pair<int, string>>> table;
int capacity;
int hashFunction(int key) {
return key % capacity;
}
public:
HashTable(int size) {
capacity = size;
table.resize(capacity);
}
void insert(int key, const string& value) {
int index = hashFunction(key);
for (auto& p : table[index]) {
if (p.first == key) {
p.second = value;
return;
}
}
table[index].push_back({key, value});
}
string get(int key) {
int index = hashFunction(key);
for (auto& p : table[index]) {
if (p.first == key) {
return p.second;
}
}
return "NOT FOUND";
}
void erase(int key) {
int index = hashFunction(key);
for (auto it = table[index].begin(); it != table[index].end(); ++it) {
if (it->first == key) {
table[index].erase(it);
return;
}
}
}
bool contains(int key) {
int index = hashFunction(key);
for (auto& p : table[index]) {
if (p.first == key) {
return true;
}
}
return false;
}
void print() {
for (int i = 0; i < capacity; i++) {
cout << i << ": ";
for (auto& p : table[i]) {
cout << "(" << p.first << ", " << p.second << ") ";
}
cout << endl;
}
}
};这个实现没有追求“工业级完整”，但已经足够说明哈希表最核心的结构。
代码里最关键的部分
先看桶的定义：
vector<list<pair<int, string>>> table;这行代码表示：
table是一个数组；- 数组里的每个元素是一个链表；
- 链表中的每个节点保存一个
(key, value)对。
这正是“链地址法”的直接实现。
再看 hash 函数：
int hashFunction(int key) {
return key % capacity;
}它的作用就是把 key 映射到 0 ~ capacity-1 之间的某个桶。
插入时，程序会先找到对应桶，再检查这个 key 是否已经存在：
- 如果已存在，就更新 value；
- 如果不存在，就把新的键值对追加到链表末尾。
查找、删除、contains 的逻辑也类似：先定位桶，再在桶内部遍历。
运行一个简单例子
int main() {
HashTable ht(7);
ht.insert(1, "one");
ht.insert(8, "eight");
ht.insert(15, "fifteen");
ht.print();
cout << ht.get(8) << endl;
ht.erase(8);
cout << ht.contains(8) << endl;
return 0;
}这里特意选了 1、8、15 这三个 key，因为它们会产生冲突：
1 % 7 = 1
8 % 7 = 1
15 % 7 = 1也就是说，这三个元素都会落到同一个桶里。最终这个桶里的内容会像这样：
1: (1, one) (8, eight) (15, fifteen)这正好能说明链地址法是如何工作的：桶数组只负责“粗定位”，真正的冲突则在桶内部解决。
工程里一般不会自己手写
在实际开发里，大多数时候不会自己从零实现哈希表，而是直接使用标准库。
#include <unordered_map>
unordered_map<int, string> mp;
mp[1] = "one";
mp[2] = "two";unordered_map 本质上就是哈希表。它已经帮我们处理了很多工程细节，例如：
- 更合理的哈希策略；
- 扩容与重哈希；
- 装载因子控制；
- 更完整的接口设计。
手写哈希表的意义，不在于“替代标准库”，而在于真正理解它背后的结构。
总结
哈希表的本质，是把查找问题转化为下标定位问题。
它之所以快，是因为很多时候不需要线性扫描；它之所以复杂，是因为不同的 key 可能映射到同一个位置，也就是冲突。
只要理解了“数组 + hash 函数 + 冲突处理”这三个部分，哈希表就不神秘了。
版权所有
版权归属：Guisong Wu