【数据结构与算法】哈希表

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的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: vectorlistpairstring, 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 对应多个 valueA不是挂钩上挂的是不同的 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: vectorpairstring, int table; vectorbool occupied; // 是否有人 vectorbool 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_mapstring, int mp; cout mp[张三]; // 张三不存在但不会报错[]如果 key 不存在会自动插入一个 (key, 0)。6.2 安全写法// 只查找不插入 auto it mp.find(张三); if (it ! mp.end()) { cout it-second; } // 或者用 C11 的 at不存在会抛异常 cout mp.at(张三);七、总结哈希表 带编号的存包柜哈希函数 根据 key 算柜子编号哈希冲突 多个人想去同一个柜子拉链法 一个柜子挂一串包开放寻址法 柜子被占就往后找空柜子mp[key]有坑安全查找用find()