哈希表（Hash Table）可能是日常写代码里用得最多的数据结构：Java 的 HashMap、Go 的 map、Python 的 dict，本质上都是它。

它的核心卖点是：增删查平均都是 O(1)。

但”为什么是 O(1)”，恰恰是最多人答不清楚的地方。今天把它彻底搞懂。

哈希表的本质：数组 + 哈希函数

哈希表底层是一块数组。数组按下标访问是 O(1)，这是它快的根本原因。

问题在于：现实中的 key 通常不是整数下标（比如”用户 ID 是字符串”），怎么把一个任意的 key 映射成数组下标？

答案是哈希函数：

1
hash(key) → 数组下标

理想情况下，不同的 key 映射到不同的下标，那增删查就都是 O(1)。

但理想情况几乎不可能——因为 key 的取值空间通常远大于数组的大小，所以必然出现哈希冲突：两个不同的 key，算出了同一个下标。

冲突怎么解决

解决哈希冲突有两种主流思路：

1. 链地址法（拉链法）

同一个下标上挂一条链表，冲突的 key 都放在这条链表里。

查找时：先算哈希找到下标，再在链表里逐个比对 key。

Java 的 HashMap 用的就是这种方法。

2. 开放寻址法

冲突时，按照一定规则往后找下一个空位置。

查找时：先算哈希，如果位置被占了且 key 不对，就往后探测，直到找到空位或目标 key。

ThreadLocal 用的是这种方法。

为什么说”平均 O(1)”

关键在于负载因子（load factor）。

负载因子 = 已存储元素数 / 数组容量。

  • 负载因子低：冲突少，链表短，接近 O(1)
  • 负载因子高：冲突多，链表长，退化到 O(n)

所以哈希表会动态扩容：当负载因子超过阈值（比如 Java HashMap 是 0.75），就把数组翻倍，重新计算所有元素的哈希并放进去（rehash）。

正是靠”控制负载因子 + 扩容”，哈希表才能维持平均 O(1)。

注意”平均”二字——最坏情况下（所有 key 都冲突到同一个位置），它会退化成链表，O(n)。

Java HashMap 的一个进化细节

早期 Java 的 HashMap，冲突就是纯链表，最坏退化 O(n)。

Java 8 之后做了个优化：当链表长度超过 8 时，链表会转换成红黑树，把最坏情况从 O(n) 降到 O(log n)。

这背后的思路值得记住：没有任何数据结构是银弹，工程上总是用”组合”来兜底最坏情况。

哈希函数的要求

一个好的哈希函数要满足：

  1. 计算快——哈希本身的开销不能比直接遍历还大
  2. 分布均匀——让 key 尽量分散到不同下标，减少冲突
  3. 确定性——同一个 key，永远算出同一个结果

顺带提一个经典面试题：为什么 String 的 hashCode 用 31 作为乘数？

因为 31 是质数，能让结果分布更均匀，减少冲突；而且 31 可以用移位优化（31 * i = (i << 5) - i），计算快。

哈希表的应用

  • 缓存（如 Redis、本地缓存）
  • 去重（HashSet）
  • 计数（统计词频）
  • 快速查找（判断元素是否存在）
  • 数据库索引的哈希索引

一个小提醒

哈希表虽然快，但不是万能：

  1. 不能范围查询——“找 key 在 100 到 200 之间的所有元素”，哈希表做不了，得用有序结构（如跳表、B+ 树）
  2. 内存开销大——要预留一定空间维持低负载因子
  3. 无序——遍历顺序不保证

所以 Redis 的 ZSet 用跳表，MySQL 索引用 B+ 树，而不是一味用哈希表。

小结

记住这条主线就够了：

哈希表 = 数组（快）+ 哈希函数（映射）+ 冲突解决（兜底）+ 负载因子控制（维持 O(1)）。

搞懂这条主线，”为什么是 O(1)”这种问题就再也难不住你了。