大名鼎鼎的哈希表是啥？
“我需要快速查找某个元素，它到底在不在集合里？”
你是一个常写代码和算法题的小帅，有一天你遇见了一个上面这样的问题。
假如用数组，得从头到尾遍历 → O(n) ；
用二叉搜索树（BST） → O(log n) ；
以上的方法都是很常规也很容易理解的方法。
但如果能做到 O(1) 呢？
那你就可以使用——哈希表（Hash Table） 。
1. 哈希表是啥？
哈希表是一种通过哈希函数，把“键”映射到数组下标，从而实现快速存取的结构。
它核心依赖两部分：
- 哈希函数（Hash Function） ：把 key 转换成一个整数（索引）。
- 存储结构（桶，Bucket） ：用数组存储元素，索引就是哈希值。
比如，你想存 "Alice" 这个名字，哈希函数可能把它算成 12345，然后对数组大小取模，落到 12345 % N 这个位置。
查找时再哈希一次，一下就跳到那个位置。
2. 哈希冲突怎么解决？
问题来了：不同的 key 可能哈希到同一个位置，这就是 冲突。
哈希表的设计关键就在于如何解决冲突。下面是常见两种方案~
① 开放寻址（Open Addressing）
- 如果当前位置被占，就找下一个空位置（线性探测 / 二次探测 / 双重哈希）。
- 优点：只需要一个数组，内存连续。
- 缺点：装载因子（元素/容量）过高时，性能急剧下降。
② 拉链法（Separate Chaining）
- 每个数组位置存一条链表（或红黑树）。
- 冲突时把新元素挂到链表上。
- 优点：扩展灵活，装载因子高时仍能工作。
- 缺点：需要额外指针，内存不连续，可能 cache 不友好。
现代 STL 的 unordered_map 就是基于拉链法实现的。
3. 哈希表的复杂度
在理想情况下：
- 查找、插入、删除 → 平均复杂度：O(1)
- 但在最坏情况下（比如哈希函数很差，全冲突），就会退化成 O(n)
因此，哈希表的效率 高度依赖哈希函数 和 负载因子（装载率）。
- 负载因子 = 元素个数 / 桶数。
- 当负载因子过高时，哈希表需要 扩容（rehash），重新分配更大的数组。
4. 实际应用
哈希表几乎无处不在：
- 编程语言字典：Python 的
dict、Java 的HashMap、C++ 的unordered_map - 去重集合：比如
set、unordered_set - 缓存系统：那个也是大名鼎鼎的Redis 就是基于哈希表 + 链表 + 跳表
- 编译器：符号表（变量名映射到地址）
如果你写业务代码，几乎每天都在用哈希表。
5. 哈希表的缺点
虽然哈希表快，但它也有局限：
- 无序
元素在数组中分布杂乱，不像 BST 那样能维持顺序。
如果你需要“区间查找”或“有序遍历”，哈希表就不适合。 - 内存占用高
为了避免冲突，需要留出不少空位。装载率低时内存浪费严重。 - 扩容开销大
当容量不足时，需要 rehash，即把所有元素重新分配，代价很高。
6. 小结
- 哈希表 就是 使用数组存储数据，然后使用哈希函数来进行存储。平均复杂度 O(1) 的超大优势让它在所有数据结构中都显得如此光芒万丈。
一般来说，你不知道怎么更快，那就无脑哈希吧~
