【数据结构与算法】哈希表
👨💻 关于作者：会编程的土豆
“不是因为看见希望才坚持，而是坚持了才看见希望。”
你好，我是会编程的土豆，一名热爱后端技术的Java学习者。
📚正在更新中的专栏：
《数据结构与算法》😊😊😊
《leetcode hot 100》🥰🥰🥰🤩🤩🤩
《数据库mysql》
💕作者简介：后端学习者
前言
哈希表是算法面试和开发中绕不开的数据结构。但初学者常被"哈希函数"、"冲突"、"拉链法"这些词劝退。
这篇文章用一个存包柜的比喻，帮你彻底搞懂哈希表的底层原理，并附上 C++ 手写实现。
一、什么是哈希表？
1.1 一句话定义
哈希表就是带编号的存包柜，根据编号能快速找到你的包。
1.2 为什么需要哈希表？
| 数据结构 | 查找时间 | 缺点 |
|---|---|---|
| 数组 | O(1) | 下标必须是整数，不能是字符串 |
| 链表 | O(n) | 慢 |
| 哈希表 | O(1) | 几乎完美 |
哈希表能让你用任意类型（字符串、对象）当"下标"，快速找到对应的值。
二、核心概念
2.1 哈希函数——"算尾号"
哈希函数的作用：把任意类型的 key 转换成一个整数。
就像存包柜系统：不管你叫什么名字，只看你手机尾号，决定你去几号柜子。
// 简单的字符串哈希函数 int hashFunc(string key, int capacity) { int hash = 0; for (char c : key) { hash = (hash * 131 + c) % capacity; } return hash; }2.2 哈希冲突——"尾号相同怎么办？"
两个不同的 key，算出了相同的哈希值，都要去同一个柜子——这就是哈希冲突。
张三（尾号 23）和李四（尾号 23）都想存 23 号柜，冲突了。
解决办法只有两招：
| 方法 | 比喻 | 专业术语 |
|---|---|---|
| 一个柜子里挂一排包 | 挂钩法 | 拉链法 / 开散列 |
| 往后找空柜子存 | 往后挪法 | 开放寻址法 / 闭散列 |
三、拉链法（挂钩法）详解
3.1 核心思想
哈希表的每个位置不是一个格子，而是一根挂钩（链表）。冲突的 key 都挂在这根钩子上。
实际就是遇到相同的key更新覆盖value为 最新值；
3.2 结构示意图
桶[0] -> (张三, 100) -> (李四, 200) -> NULL 桶[1] -> NULL 桶[2] -> (王五, 300) -> NULL 桶[3] -> (赵六, 400) -> (钱七, 500) -> (孙八, 600) -> NULL3.3 存包过程
算哈希值，找到对应的桶。
顺着挂钩找，看有没有同名的包。
有 → 换包（覆盖 value）。
没有 → 挂个新包在钩子末尾。
3.4 取包过程
算哈希值，找到桶。
顺着挂钩一个一个看名字。
找到了 → 拿走。
找完了都没看到 → 没存过。
3.5 C++ 手写实现
#include <iostream> #include <list> #include <vector> #include <string> using namespace std; class MyHashMap { private: vector<list<pair<string, int>>> table; int capacity; int hashFunc(const string& key) { int hash = 0; for (char c : key) { hash = (hash * 131 + c) % capacity; } return hash; } public: MyHashMap(int cap = 1000) : capacity(cap) { table.resize(capacity); } // 存包 void put(const string& key, int value) { int idx = hashFunc(key); for (auto& p : table[idx]) { if (p.first == key) { p.second = value; // 换包 return; } } table[idx].push_back({key, value}); // 挂新包 } // 取包（安全查找） int get(const string& key) { int idx = hashFunc(key); for (auto& p : table[idx]) { if (p.first == key) { return p.second; } } return -1; // 没找到 } // 删包 void remove(const string& key) { int idx = hashFunc(key); auto& bucket = table[idx]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) { bucket.erase(it); return; } } } };3.6 一个重要误区
Q：挂钩上挂了一串，是不是一个 key 对应多个 value？
A：不是！
挂钩上挂的是不同的 key（它们只是哈希冲突了），不是同一个 key 的多个值。
同一个 key 再次插入，会直接覆盖，不会挂新包。
四、开放寻址法（往后挪法）详解
4.1 核心思想
一个柜子只存一个包。如果自己的柜子被占了，就往后找，直到找到空柜子。
4.2 存包过程
算哈希值，去对应柜子。
有人？看下一个。
还有人？继续看下一个。
找到空的，存进去。
4.3 取包过程
算哈希值，去对应柜子。
看名字，是我的吗？
不是？继续往后看。
遇到空柜子？说明没存过。
4.4 关键问题解答
Q：我往后挪，不是把别人的位置占了吗？
A：不会。因为别人来取包时，也是从自己的柜子开始往后找。看到你的包（名字不对），他会继续往后走，不会拿错。
Q：那尾号 24 的人来，发现 24 号被尾号 23 的人占了，怎么办？
A：他很委屈，但只能继续往后找空柜子。
Q：这样不就乱套了吗？
A：这就是线性探测最大的缺点——连累邻居。队伍会越来越长，叫做聚集现象。
4.5 删除的坑
开放寻址法不能直接删。
张三（尾号23）存 23 号，李四（尾号23）存 24 号。
张三删包走人，23 号空了。
李四来取包：去 23 号→空的→"哦，我没存过"→拿不到自己的包！
解决办法：删的时候不真删，放个"墓碑"标记，表示这里曾经有人。
4.6 C++ 手写实现（线性探测）
class MyHashMap_OpenAddressing { private: vector<pair<string, int>> table; vector<bool> occupied; // 是否有人 vector<bool> tombstone; // 墓碑标记 int capacity; int hashFunc(const string& key) { int hash = 0; for (char c : key) hash = (hash * 131 + c) % capacity; return hash; } public: MyHashMap_OpenAddressing(int cap = 2000) : capacity(cap) { table.resize(capacity); occupied.resize(capacity, false); tombstone.resize(capacity, false); } void put(const string& key, int value) { int idx = hashFunc(key); while (occupied[idx] && table[idx].first != key) { idx = (idx + 1) % capacity; } table[idx] = {key, value}; occupied[idx] = true; tombstone[idx] = false; } int get(const string& key) { int idx = hashFunc(key); while (occupied[idx] || tombstone[idx]) { if (occupied[idx] && table[idx].first == key) { return table[idx].second; } idx = (idx + 1) % capacity; } return -1; } void remove(const string& key) { int idx = hashFunc(key); while (occupied[idx] || tombstone[idx]) { if (occupied[idx] && table[idx].first == key) { occupied[idx] = false; tombstone[idx] = true; // 留墓碑 return; } idx = (idx + 1) % capacity; } } };五、拉链法 vs 开放寻址法
| 拉链法 | 开放寻址法 | |
|---|---|---|
| 比喻 | 一个柜子挂一串 | 往后找空柜子 |
| 优点 | 实现简单，删除方便 | 省空间，缓存友好 |
| 缺点 | 需要额外指针空间 | 删除麻烦，可能聚集 |
| Java HashMap | ✅ | ❌ |
| C++ unordered_map | ✅ | ❌ |
| Python dict | ❌ | ✅（随机探测） |
六、C++ unordered_map 使用避坑指南
6.1[]的坑
unordered_map<string, int> mp; cout << mp["张三"]; // 张三不存在，但不会报错！[]如果 key 不存在，会自动插入一个 (key, 0)。
6.2 安全写法
// 只查找，不插入 auto it = mp.find("张三"); if (it != mp.end()) { cout << it->second; } // 或者用 C++11 的 at（不存在会抛异常） cout << mp.at("张三");七、总结
哈希表 = 带编号的存包柜
哈希函数 = 根据 key 算柜子编号
哈希冲突 = 多个人想去同一个柜子
拉链法 = 一个柜子挂一串包
开放寻址法 = 柜子被占就往后找空柜子
mp[key]有坑，安全查找用find()