一、哈希表初探：从一次“查找噩梦”说起
我记得刚工作那会儿，接手了一个用户管理系统。数据量不大，也就几万条。但每次用户登录，都要等上好几秒。老板站在我身后，那眼神……嗯，你们懂的。
问题出在哪？查找太慢了。当时用的链表，查找一个用户要遍历整个表。几万条数据，平均每次要比较一半。我心想：有没有一种结构，能在常数时间内找到数据？
后来我遇到了哈希表。说白了，它就像一本字典——你想查“苹果”这个词，直接翻到拼音索引“P”那一页，而不是从第一页开始翻。哈希表的核心思想，就是通过一个函数，把数据的位置直接算出来。
1.1 什么是哈希表
哈希表，也叫散列表。它是一种根据键（Key）直接访问内存存储位置的数据结构。
它的工作流程很简单：
- 你给一个键，比如用户ID
- 哈希函数把这个键映射成一个整数
- 这个整数就是数组的下标
- 直接去那个位置取数据
举个例子：
// 假设有一个哈希函数 hash(key) = key % 10
// 存储用户ID为 12345 的用户信息
index = 12345 % 10; // 结果是 5
// 直接存到数组的第5个位置
users[5] = userInfo;下次查找用户12345，同样计算 12345 % 10 = 5，直接去 users[5] 取数据。一步到位，不需要遍历。
核心思想总结：哈希表 = 数组 + 哈希函数。用空间换时间，把查找问题转化为计算问题。
1.2 哈希表的核心思想
哈希表的核心就三个字：算位置。
传统的数据结构，比如数组，你要找某个值，得挨个比较。链表更慢，得从头走到尾。哈希表不一样，它通过哈希函数，直接把键映射成存储位置。
这个过程有点像：
- 存数据时：把键扔进哈希函数，算出位置，放进去
- 取数据时：把键扔进哈希函数，算出位置，直接取
你想想看，这多省事。不需要比较，不需要遍历，一步到位。
但这里有个坑——哈希冲突。不同的键可能算出相同的位置。比如 key1 % 10 = 5，key2 % 10 也等于 5。怎么办？
我项目中常用的办法是链地址法：每个数组位置挂一个链表，冲突的元素链在一起。查找时先算位置，再在链表里遍历。虽然链表遍历慢了点，但只要哈希函数设计得好，链表长度通常很短，影响不大。
个人经验：哈希函数的设计很关键。我一般用质数取模，或者用位运算。尽量避免所有键都映射到同一个位置——那哈希表就退化成链表了，性能直接崩。
1.3 哈希表 vs 数组 vs 链表
这三种结构，各有各的脾气。我画了张图，帮你快速理解：
从图上能看出来：
- 数组：按索引查找飞快（O(1)），但按值查找得遍历（O(n)）。插入删除要移动元素，慢。
- 链表：插入删除快（头插O(1)），但查找必须从头遍历（O(n)）。
- 哈希表：查找、插入、删除平均都是O(1)。这才是我们想要的。
注意：哈希表的O(1)是平均情况。如果哈希函数设计得不好，或者负载因子太高，冲突多了，性能会退化到O(n)。我曾经在一个项目里见过哈希表退化成链表——查找一次要几百毫秒，后来改了哈希函数才恢复正常。
1.4 哈希表的时间复杂度分析
咱们来认真聊聊时间复杂度。这是面试常考的点，也是实际开发中必须关注的。
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 查找 | O(1) | O(n) |
| 插入 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
为什么平均是O(1)？
因为哈希函数把键均匀分布到数组里。每个位置上的元素很少，查找时只需要常数次操作。
为什么最坏是O(n)？
如果所有键都映射到同一个位置，那哈希表就变成了一个链表。查找就得遍历所有元素。
我个人的经验是：控制负载因子。负载因子 = 元素个数 / 数组长度。一般建议保持在0.75以下。超过这个值，就该扩容了。
避坑指南：我曾经在一个高并发系统里，忘了设置负载因子阈值。结果数据量一上来，哈希表频繁扩容，每次扩容都要重新哈希所有数据，系统直接卡死。后来我加了扩容阈值，提前扩容，问题就解决了。
还有一点要注意：哈希函数本身的计算时间。如果哈希函数太复杂，计算一次要好几微秒，那O(1)的常数就很大。我一般用简单的位运算或者取模，够用就行。
1.5 什么时候用哈希表
说白了，哈希表适合的场景就一个：快速查找。
- 用户登录验证：根据用户名查用户信息
- 缓存系统：根据key查value
- 去重：判断一个元素是否出现过
- 统计频率：统计单词出现次数
不适合的场景：
- 需要有序遍历：哈希表是无序的，想要有序得用树
- 范围查询：比如查所有年龄在20-30岁之间的用户，哈希表搞不定
- 数据量极小：比如只有几个元素，用数组遍历更快
嗯，这一章就到这里。哈希表的核心思想其实不复杂——用计算代替查找。下一章咱们会深入哈希函数的设计，看看怎么写出一个好的哈希函数。