外观
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