【数据结构】哈希表：O(1) 查找的秘密

你一定经历过这种“爽到离谱”的时刻：

你想查一个用户 id 是否存在
你不想从头扫一遍数组（那是 O(n)，像在全班点名找人）
你掏出一个 Map / Object，get 一下就有了

然后你会听到一个经典结论：

哈希表查找是 O(1)。

问题是：

凭什么 O(1)？
冲突怎么办？
为什么有时候会退化？
为什么插入到一定数量后突然变慢一下？

如果你只停留在“背结论”，面试官下一句追问就能把你送走。

今天我们把哈希表讲到“能解释给别人听”的程度：

你能说清它的底层机制
你能写一个迷你实现（可运行）
你知道它在工程里什么时候会坑你

1. 哈希表到底是什么？先用一句人话

哈希表（Hash Table）的本质是：

用一个“函数”把 key 映射成数组下标，然后把值放进数组里。

它看起来像一个“字典”，但底层更像一个“用数学给数组开外挂”的结构。

你可以想象一个大楼（数组），每个房间都有门牌号（下标）。

你拿着一个名字（key）
通过“门牌号生成器”（哈希函数）算出门牌号
直接去对应房间找人

不需要全楼挨家挨户敲门，这就是它快的根源。

2. 为什么平均能做到 O(1)？关键在“数组 + 均匀分布”

如果哈希函数足够“均匀”，key 会平均散落到不同桶位：

查找：算下标 O(1) + 访问数组 O(1)
插入：同理

所以我们说哈希表是 平均 O(1)。

注意我说的是“平均”。因为哈希表的性能有一个致命前提：

key 必须分布得像撒胡椒粉一样均匀。

如果全撒在一个点上，那就从“哈希表”退化成“链表/数组”，直接 O(n)。

3. 冲突（Collision）：哈希表注定会发生“撞车”

现实很残酷：

哈希函数把“无限多的 key”映射到“有限个下标”
所以不同 key 映射到同一个下标是必然的

这就叫冲突。

哈希表的难点不是“怎么把 key 变成下标”，而是：

撞车以后怎么处理，才能还尽量快？

主流的冲突处理方案就两大类：

链地址法（Separate Chaining）：每个桶里放一个列表（链表/数组）。
开放寻址（Open Addressing）：桶里只能放一个元素，撞了就找下一个空位。

下面我们分别讲清楚。

4. 方案一：链地址法（最直观，也最常见）

链地址法的思路很朴素：

桶里不是只放一个值
而是放一个“集合”（常用数组/链表）

index 0: [ (k1,v1) -> (k2,v2) ]
index 1: [ ]
index 2: [ (k3,v3) ]

查找步骤：

index = hash(key) % capacity
去 buckets[index] 里线性找这个 key

这时候复杂度变成：

平均：桶里元素很少 → 近似 O(1)
最坏：全挤在一个桶 → O(n)

工程里，我们靠两件事把平均桶长控制住：

哈希函数尽量均匀
负载因子到阈值就扩容（后面会讲）

5. 方案二：开放寻址（更省内存，但更“脾气大”）

开放寻址法的规则更硬：

一个桶只能放一个元素
冲突了就找下一个空桶

最简单的是线性探测（Linear Probing）：

index = hash(key) % capacity
如果 index 被占了 → index+1 → index+2 ...（循环）

开放寻址的痛点：

删除很麻烦（需要 tombstone 标记，否则会断掉探测链）
容量接近满时性能会明显变差（探测距离变长）

你在面试里说出这两点，已经比大多数人强。

6. 负载因子（Load Factor）：哈希表性能的“体脂率”

负载因子定义：

$$\alpha = \frac{\text{元素数量}}{\text{桶数量}}$$

$\alpha$ 越大，桶越“挤”，冲突越多
$\alpha$ 越小，桶越“空”，内存浪费越大

典型策略：

当 $\alpha > 0.75$ 扩容
扩容通常是容量翻倍

这里有个很反直觉但很重要的点：

扩容不是简单地把数组变大，它会触发 rehash（重分布）。

因为下标是 % capacity 算出来的，capacity 变了，所有元素的桶位置都可能变。

所以扩容会有一次“突然变慢”的时刻：你在做一次大规模搬家。

这也是很多人看到“偶尔一次 set 很慢”的原因。

7. 手写一个迷你哈希表（可运行，链地址法 + 自动扩容）

我们用 JavaScript 写一个教学版的 HashTable：

key 支持字符串（够讲原理）
链地址法：每个桶是一个数组
负载因子超过 0.75 自动扩容并 rehash

class HashTable {
  constructor(initialCapacity = 16) {
    this._capacity = initialCapacity;
    this._size = 0;
    this._buckets = Array.from({ length: this._capacity }, () => []);
  }

  get size() {
    return this._size;
  }

  _hashString(key) {
    // djb2: 简单、好用、足够教学
    let hash = 5381;
    for (let i = 0; i < key.length; i++) {
      hash = (hash * 33) ^ key.charCodeAt(i);
    }
    // 转成非负 32 位整数
    return hash >>> 0;
  }

  _index(key) {
    const hash = this._hashString(key);
    return hash % this._capacity;
  }

  _findPair(bucket, key) {
    for (let i = 0; i < bucket.length; i++) {
      const pair = bucket[i];
      if (pair[0] === key) return { pair, index: i };
    }
    return null;
  }

  _loadFactor() {
    return this._size / this._capacity;
  }

  _rehash(newCapacity) {
    const oldBuckets = this._buckets;

    this._capacity = newCapacity;
    this._buckets = Array.from({ length: this._capacity }, () => []);
    this._size = 0;

    for (const bucket of oldBuckets) {
      for (const [key, value] of bucket) {
        this.set(key, value);
      }
    }
  }

  set(key, value) {
    if (typeof key !== 'string') {
      throw new TypeError('This demo HashTable only supports string keys.');
    }

    if (this._loadFactor() > 0.75) {
      this._rehash(this._capacity * 2);
    }

    const index = this._index(key);
    const bucket = this._buckets[index];
    const found = this._findPair(bucket, key);

    if (found) {
      found.pair[1] = value;
      return;
    }

    bucket.push([key, value]);
    this._size += 1;
  }

  get(key) {
    const index = this._index(key);
    const bucket = this._buckets[index];
    const found = this._findPair(bucket, key);
    return found ? found.pair[1] : undefined;
  }

  has(key) {
    return this.get(key) !== undefined;
  }

  delete(key) {
    const index = this._index(key);
    const bucket = this._buckets[index];
    const found = this._findPair(bucket, key);

    if (!found) return false;

    bucket.splice(found.index, 1);
    this._size -= 1;
    return true;
  }

  keys() {
    const result = [];
    for (const bucket of this._buckets) {
      for (const [key] of bucket) result.push(key);
    }
    return result;
  }
}

// quick demo
const ht = new HashTable();
ht.set('xiaoming', 18);
ht.set('xiaohong', 20);
ht.set('xiaoming', 19);
console.log(ht.get('xiaoming')); // 19
console.log(ht.has('nobody'));   // false
console.log(ht.keys());