前言

很多人第一次接触哈希表，会先背一句话：
“查找复杂度是 O(1)。”

但一到面试或实战又会卡住：
为什么是 O(1)？冲突了怎么办？什么时候会退化？

这篇不绕概念，按“能理解 + 能讲清 + 能写个简版”来讲：

• 哈希表到底在做什么
• 为什么平均快
• 冲突处理常见方案
• 手写一个最小可用版本（伪代码）

---

一、哈希表到底是什么

你可以把它想成一个“数组 + 索引计算规则”：

1. 先准备一个数组（桶数组）
2. 把 key 交给哈希函数，算出一个整数
3. 把这个整数映射到数组下标
4. 数据就放在对应下标的位置

核心公式常见写法：

index = hash(key) % capacity

所以哈希表快的本质，不是“神奇优化”，而是：
把“遍历比较”变成“直接定位下标”。

---

二、为什么平均是 O(1)

假设数组长度是 16，哈希函数分布也比较均匀。
你查一个 key 时，通常只需要：

• 算一次 hash
• 找到一个桶
• 在桶里做很少量比较

这就是“平均 O(1)”的来源。

但注意是“平均”，不是“永远”。
如果大量 key 都落到同一个桶，就会退化。

---

三、冲突是必然的，不是异常

不同 key 可能算出同一个下标，这叫哈希冲突。

常见处理方式有两类：

1) 拉链法（链地址法）

每个桶里不是只放一个元素，而是放一个链表（或其他结构）。

• 插入：挂到桶链表里
• 查找：先定位桶，再在桶内遍历

优点：实现直观，扩容逻辑清晰。
缺点：桶内元素过多时会变慢。

2) 开放寻址法

冲突时不挂链表，而是继续找下一个空位（线性探测、二次探测等）。

优点：内存连续，缓存友好。
缺点：删除和装载率控制更复杂。

多数主流语言/框架都做了很多工程优化，你入门先把拉链法吃透就够了。

---

四、两个关键指标：装载因子与扩容

装载因子（load factor）

loadFactor = size / capacity

size 越接近 capacity，冲突概率越高。
所以哈希表通常会设置阈值（比如 0.75）：

• 超过阈值就扩容

扩容（rehash）

扩容不是只“换个更大数组”，还要：

1. 新建更大的桶数组
2. 把旧元素重新计算 index 后搬过去

这一步叫 rehash，单次成本高，但摊到多次操作上通常可接受。

---

五、手写一个最小 HashMap（伪代码）

下面用拉链法写一个简化版思路（省略泛型、线程安全、红黑树优化等）：

class Node {
  key
  value
  next
}

class MyHashMap {
  buckets = array(capacity = 16)
  size = 0
  loadFactor = 0.75

  function put(key, value):
    if size / capacity >= loadFactor:
      resize()

    index = hash(key) % capacity
    head = buckets[index]

    // 已存在则覆盖
    cur = head
    while cur != null:
      if cur.key == key:
        cur.value = value
        return
      cur = cur.next

    // 头插法新增
    newNode = Node(key, value, head)
    buckets[index] = newNode
    size++

  function get(key):
    index = hash(key) % capacity
    cur = buckets[index]
    while cur != null:
      if cur.key == key:
        return cur.value
      cur = cur.next
    return null
}

这个版本已经能覆盖 80% 入门理解：
定位桶 + 桶内查找 + 冲突拉链 + 超阈值扩容。

---

六、常见踩坑

1. 把 O(1) 当绝对结论
   冲突严重时会退化，平均 O(1) 才是准确说法。

2. 忽略 key 的 equals/hashCode（或等价规则）一致性
   这是很多“明明 put 了却 get 不到”的根源。

3. 扩容后忘记 rehash
   只复制数组不重算索引，会导致数据分布错误。

4. 装载因子设置极端
   太大冲突多，太小浪费内存，需要权衡。

---

总结

记住这一句话：
哈希表快，是因为“计算位置”替代了“大量比较”；但冲突控制和扩容策略决定了它能快多久。

如果你把这篇吃透，下次再看到 HashMap 相关题目，就不会只会背 O(1)，而是能讲清原理、边界和取舍。

欢迎点赞关注，一起进步~~~