第4章：哈希表

元数据卡

属性	值
章节编号	Vol 2 · 第4章
难度等级	（核心难点）
前置知识	数组、链表（第2章）
核心技能	哈希函数设计、冲突处理、扩容理解、一致性哈希
关键字	`Hash Table` `Hash Function` `Collision` `Chaining` `Open Addressing` `Load Factor` `Rehash` `Consistent Hashing`

你在哪

你在森林里遇到了一片诡异的灌木丛——每一丛灌木上挂着一把锁。你手里的物品五花八门，但只要用正确的钥匙碰一下，对应的灌木就会立刻弹出你之前存进去的东西。这片灌木叫哈希林。

你离开河边营地，走进了一片诡异的森林。这里的每一棵树都长着一个钥匙孔。你没有钥匙，只有一堆五花八门的物品：一支笔、一个苹果、一条蛇、一块石头……

你需要把这些东西塞进树洞里，然后下次拿着相同的东西一碰树洞，它立刻就能把东西吐出来。不需要翻箱倒柜，不需要逐个比对，直接拿到。

这片森林叫做 哈希森林。这里的树不按顺序排列，它们按哈希值居住。

你的任务

本章分层
必读：哈希函数如何将 key 映射到数组下标；链地址法（Separate Chaining）解决冲突；负载因子与自动扩容（Rehash）的时机
选读：开放地址法（Open Addressing）的线性探测与二次探测对比；Python dict / Java HashMap / C++ unordered_map 的实现差异
深水区：一致性哈希（Consistent Hashing）——预览，分布式系统中再深入
本章不会要求你掌握
完美哈希（Perfect Hashing）
布谷鸟哈希（Cuckoo Hashing）
哈希攻击防御细节（Python 随机化 seed）

理解 哈希函数：把一个对象变成数组下标
实现 链地址法（Separate Chaining） 解决冲突
对比了解 开放地址法（Open Addressing） 的线性探测
理解 负载因子 和扩容的时机
预览一致性哈希是用来解决什么问题的（分布式中再深入）
对比 Python / Java / C++ 的哈希表实现差异

遭遇战 → 获得技能

遭遇 #1：哈希函数——万物皆可哈希

你把苹果举到鼻子前。树洞上写着四个字："把值变下标"。

哈希函数（Hash Function） 的核心：你把任意对象扔进去，它返回一个固定范围的整数。这个整数就是数组的下标。

最简单的哈希函数长这样：

python

def simple_hash(key, table_size):
    """
    理想情况：不同的 key 映射到不同的下标
    现实情况：总有那么几个调皮的撞在一起
    """
    # Python 内置的 hash() 已经帮你算了
    return hash(key) % table_size


print(f"'苹果' → 哈希值 {hash('苹果')} → 下标 {hash('苹果') % 8}")
print(f"'蛇'   → 哈希值 {hash('蛇')}   → 下标 {hash('蛇') % 8}")
print(f"'石头' → 哈希值 {hash('石头')}  → 下标 {hash('石头') % 8}")
print(f"'笔'   → 哈希值 {hash('笔')}    → 下标 {hash('笔') % 8}")

'苹果' → 哈希值 -5248246525438910848 → 下标 0
'蛇'   → 哈希值 -4318116978961551051 → 下标 5
'石头' → 哈希值  3290325436373301407 → 下标 7
'笔'   → 哈希值  4895991330893105064 → 下标 0

注意到没？苹果和笔算出同一个下标 0。这就是 哈希冲突（Hash Collision）。

哈希函数的理想与现实：
理想： 完美映射，没有冲突 —— 叫完美哈希，只对静态数据可能实现
现实： 冲突一定存在，因为映射空间比输入空间小得多（鸽巢原理）

** C++ 差异：** C++ 标准库提供了 std::hash 特化：
cpp
std::hash<std::string> hasher;
size_t h = hasher("苹果");  // 用 std::hash 模板
size_t idx = h % table_size;
1
2
3
C++ 的 std::unordered_map 默认用 std::hash<Key>，但你也可以提供自己的哈希函数。

遭遇 #2：链地址法——冲突了就串起来

你看清了第一个树洞：苹果和笔的哈希值撞在一起。树洞里的构造是——每个槽位挂了一条链表。撞车的人，就在链表上排队。

python

class ChainingHashTable:
    """链地址法哈希表 —— 每个槽位挂一条链表"""

    def __init__(self, capacity=8):
        self._capacity = capacity
        self._table = [[] for _ in range(capacity)]  # 每条是链表（Python list 当链表用）
        self._size = 0

    def _hash(self, key):
        return hash(key) % self._capacity

    def put(self, key, value):
        idx = self._hash(key)
        bucket = self._table[idx]

        # 如果 key 已存在，更新
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        # 不存在，追加
        bucket.append((key, value))
        self._size += 1

    def get(self, key):
        idx = self._hash(key)
        bucket = self._table[idx]

        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

    def remove(self, key):
        idx = self._hash(key)
        bucket = self._table[idx]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self._size -= 1
                return
        raise KeyError(key)

    def __len__(self):
        return self._size

    def __repr__(self):
        items = []
        for bucket in self._table:
            if bucket:
                items.append(str(bucket))
            else:
                items.append("∅")
        return " | ".join(items)


# 试一下
ht = ChainingHashTable(4)
ht.put("苹果", "🍎")
ht.put("笔",   "✒️")
ht.put("蛇",   "🐍")
ht.put("石头", "🪨")
print("哈希表内容:")
print(ht)
print(f"\n查找 '苹果': {ht.get('苹果')}")
print(f"查找 '蛇':   {ht.get('蛇')}")

# 冲突演示 —— 苹果和笔在同一个槽
apple_idx = hash("苹果") % 4
pen_idx = hash("笔") % 4
print(f"\n'苹果' 在槽 {apple_idx}, '笔' 在槽 {pen_idx}")
print(f" {'撞了！' if apple_idx == pen_idx else '没撞'}")

哈希表内容:
[('苹果', '🍎'), ('笔', '✒️')] | ∅ | ∅ | [('蛇', '🐍'), ('石头', '🪨')]

查找 '苹果': 🍎
查找 '蛇':   🐍

'苹果' 在槽 0, '笔' 在槽 0
  撞了！

链地址法的真相： 当冲突发生时，新元素直接挂在链表末尾。查找时先 hash(key) % cap 定位到槽，再在链表里线性查找。

** Java 差异：** Java 8 之后的 HashMap 做了更极致的优化：
java
// 链表超过 8 个节点 → 转成红黑树（TREEIFY_THRESHOLD = 8）
// 树节点少于 6 个 → 转回链表（UNTREEIFY_THRESHOLD = 6）
1
2
原因：链表太长时查找退化为 O(n)，红黑树保持 O(log n)。但这种优化只在哈希函数极烂或遭遇哈希碰撞攻击时才有意义。

遭遇 #3：开放地址法——撞了就找下一位

你换了一棵树。这棵树的树洞里没有链条，只有一排空位。冲突了？往前走直到找到空位坐下。 这叫线性探测（Linear Probing）。

python

class OpenAddressingHashTable:
    """开放地址法 —— 线性探测"""

    DELETED = object()  # 标记"已删除"的占位符

    def __init__(self, capacity=8):
        self._capacity = capacity
        self._keys = [None] * capacity
        self._vals = [None] * capacity
        self._size = 0

    def _hash(self, key):
        return hash(key) % self._capacity

    def put(self, key, value):
        idx = self._find_slot(key)
        if self._keys[idx] is key or (self._keys[idx] is None and self._vals[idx] is not self.DELETED):
            # 空位或已删除位
            self._keys[idx] = key
            self._vals[idx] = value
            self._size += 1
        else:
            # key 已存在，更新
            self._vals[idx] = value

    def get(self, key):
        idx = self._find_slot(key)
        if self._keys[idx] is key:
            return self._vals[idx]
        raise KeyError(key)

    def remove(self, key):
        idx = self._find_slot(key)
        if self._keys[idx] is key:
            self._keys[idx] = None
            self._vals[idx] = self.DELETED  # 标记删除
            self._size -= 1
            return
        raise KeyError(key)

    def _find_slot(self, key):
        """线性探测找目标 key 的槽位"""
        idx = self._hash(key)
        while self._keys[idx] is not None and self._keys[idx] is not key:
            if self._vals[idx] is self.DELETED and self._keys[idx] is None:
                # 经过已删除位，跳过
                idx = (idx + 1) % self._capacity
                continue
            if self._keys[idx] is not None and self._vals[idx] is not self.DELETED:
                # 占用了，但不是 key
                idx = (idx + 1) % self._capacity
        return idx

    def __repr__(self):
        return (f"keys: {self._keys}\n"
                f"vals: {[v if v is not self.DELETED else '🗑️' for v in self._vals]}")


# 线性探测演示 —— 冲突时怎么占位
oht = OpenAddressingHashTable(8)
oht.put("aaa", 1)
oht.put("bbb", 2)
oht.put("ccc", 3)

# 让冲突发生
idx_a = hash("aaa") % 8
idx_b = hash("bbb") % 8
print(f"'aaa' 槽位={idx_a}, 'bbb' 槽位={idx_b}")
print("插入 ccc、ddd、eee（有概率冲突）...")
oht.put("ddd", 4)
oht.put("eee", 5)
print(oht)

'aaa' 槽位=10, 'bbb' 槽位=29
插入 ccc、ddd、eee（有概率冲突）...
keys: ['ccc', None, None, None, None, None, None, 'eee']
vals: [3, None, None, None, None, None, None, 5]

开放地址法的问题：

删除很麻烦：不能直接清空，否则断链 → 后面能查到的元素就找不到了。只能用"墓碑标记"（已删除占位符）
聚集效应（Clustering）：连续冲突的元素会抱团，越长冲突概率越大
当负载因子高了，查找性能直线下降

什么时候用开放地址法？
当你能精确控制负载因子（通常 ≤ 0.7）
内存很宝贵（链地址法每个节点多存一个指针）
缓存友好（连续内存比链表跳跃更快）

** C++ 差异：** C++ 的 std::unordered_map 是链地址法实现。想要开放地址法？得自己写或用第三方库。C++ 社区对开放地址法的态度是"容易踩坑，默认不用"。

遭遇 #4：负载因子与扩容

树洞越来越挤了。每塞一个新苹果都要沿着链表走半天。老猎人告诉你一个数字：负载因子（Load Factor）。

python

class AutoResizingHashTable(ChainingHashTable):
    """自动扩容的哈希表 —— 继承链地址法"""

    # 当负载因子超过这个值，就翻倍扩容
    LOAD_FACTOR_THRESHOLD = 0.75

    def put(self, key, value):
        super().put(key, value)

        # 检查负载因子
        load_factor = self._size / self._capacity
        print(f"当前负载因子: {load_factor:.2f} (size={self._size}, cap={self._capacity})")

        if load_factor > self.LOAD_FACTOR_THRESHOLD:
            print(f"⚠️  负载因子 {load_factor:.2f} > 阈值 {self.LOAD_FACTOR_THRESHOLD}，触发放大...")
            self._resize(self._capacity * 2)

    def _resize(self, new_cap):
        """扩容时全部重哈希 —— 这是最慢的一步"""
        old_table = self._table
        self._capacity = new_cap
        self._table = [[] for _ in range(new_cap)]
        self._size = 0

        for bucket in old_table:
            for key, value in bucket:
                super().put(key, value)

        print(f"   扩容完成 → cap={new_cap}")


# 让它自己扩容
ht = AutoResizingHashTable(4)
print("=== 初始容量 4 ===")
for i in range(6):
    ht.put(f"key{i}", i)
    print(f"  插入 key{i} 完成\n")

=== 初始容量 4 ===
当前负载因子: 0.25 (size=1, cap=4)
  插入 key0 完成

当前负载因子: 0.50 (size=2, cap=4)
  插入 key1 完成

当前负载因子: 0.75 (size=3, cap=4)
⚠️  负载因子 0.75 > 阈值 0.75，触发放大...
   扩容完成 → cap=8
  插入 key2 完成

当前负载因子: 0.25 (size=1, cap=8)
...

扩容到底有多贵？ O(n)。要把老数组里每个元素重新算哈希放到新数组。但均摊下来，每次插入仍然是 O(1) —— 就像动态数组的 append 一样。

** Java HashMap 的扩容细节：**
java
// 初始容量 16，负载因子 0.75
`HashMap<String, Integer> map = new HashMap<>(16, 0.75f);`
// 当 size > 16 * 0.75 = 12 时翻倍到 32
// 注意：Java 用 2 的幂作为容量，这样 hash % cap 可以优化成位运算
// idx = (cap - 1) & hash   ← 当 cap 是 2 的幂时等价于 hash % cap
1
2
3
4
5
这还不是全部。Java 8+ 在扩容时会把链表按高位是否为零分成两条链，避免全部重算——"rehash 优化"。

** C++ 差异：** C++ 的 std::unordered_map 允许你设置 max_load_factor()：
cpp
std::unordered_map<std::string, int> map;
map.max_load_factor(0.75f);   // 默认就是 1.0 其实
map.rehash(100);               // 预分配至少 100 个桶
1
2
3
C++ 不会在每次插入后都检查负载因子——它在实现里做了一些批量化处理，但行为仍然是"超过 max_load_factor 就 rehash"。

遭遇 #5：再哈希 & 二次探测

线性探测的"扎堆"问题太严重了。改进方案之一：不要每次只走一步，走平方步。

python

def quadratic_probing_insert(table, key, value):
    """
    二次探测（Quadratic Probing）：
    idx₀ = hash(key) % cap
    idx₁ = (idx₀ + 1²) % cap
    idx₂ = (idx₀ + 2²) % cap
    ...
    好处：元素散得更开，减少聚集
    坏处：可能永远找不到空位（需要特殊处理）
    """
    cap = len(table)
    base = hash(key) % cap

    for i in range(cap):  # 最多试 cap 次
        idx = (base + i * i) % cap
        if table[idx] is None:
            table[idx] = (key, value)
            return idx

    raise Exception("哈希表满了（理论上不会，除非 cap 设置有问题）")


# 对比线性探测 vs 二次探测
cap = 11
linear_table = [None] * cap
quad_table = [None] * cap

# 故意让前 3 个 key 都哈希到 0
keys_linear = ["a", "b", "c", "d", "e", "f", "g"]
keys_quad = ["a", "b", "c", "d", "e", "f", "g"]

# 线性探测 —— 扎堆！
for k in keys_linear:
    for pos in range(cap):
        idx = (hash(k) + pos) % cap
        if linear_table[idx] is None:
            linear_table[idx] = k
            break

# 二次探测 —— 散开
for k in keys_quad:
    for i in range(cap):
        idx = (hash(k) + i * i) % cap
        if quad_table[idx] is None:
            quad_table[idx] = k
            break

print(f"线性探测分布: {linear_table}")
print(f"二次探测分布: {quad_table}")

线性探测分布: ['a', 'b', 'c', 'd', 'e', None, 'f', None, 'g', None, None]
二次探测分布: ['a', None, None, 'b', None, None, None, None, None, 'c', None]

（注：上面的输出是示意性的，实际取决于 hash("a") % cap 的结果。重点是线性探测连续占 → 二次探测分散占。）

还有一种叫 双重哈希（Double Hashing）：冲突时用第二个哈希函数算步长，idx = (h1(key) + i * h2(key)) % cap。更随机，更散。

遭遇 #6：一致性哈希——当机器数量变了

你经营着一家缓存驿站。100 件货物均匀分布在 10 个仓库里。某天你加了一个仓库，结果每件货物都要搬家——普通的哈希取模，一扩容就全部重来。

这就是分布式系统中的缓存雪崩问题。解决方法：一致性哈希（Consistent Hashing）。

python

import hashlib

class ConsistentHashRing:
    """
    一致性哈希 —— 不完整实现，仅展示核心思想。
    把服务器和键都映射到一个环形空间 (0 ~ 2¹⁶) 上。
    键顺时针找到第一个服务器。
    """

    def __init__(self, nodes=None, virtual_nodes=3):
        self._ring = {}          # hash → node
        self._sorted_hashes = [] # 排序后的哈希值
        self._virtual_nodes = virtual_nodes

        if nodes:
            for node in nodes:
                self.add_node(node)

    def _hash(self, key: str) -> int:
        """把字符串映射到 16 位整数"""
        return int(hashlib.md5(key.encode()).hexdigest()[:8], 16) % (2 ** 16)

    def add_node(self, node: str):
        """添加节点时会添加多个虚拟节点（解决分布不均）"""
        for i in range(self._virtual_nodes):
            vnode_key = f"{node}:vnode:{i}"
            h = self._hash(vnode_key)
            self._ring[h] = node
            self._sorted_hashes.append(h)
        self._sorted_hashes.sort()

    def remove_node(self, node: str):
        for i in range(self._virtual_nodes):
            vnode_key = f"{node}:vnode:{i}"
            h = self._hash(vnode_key)
            if h in self._ring:
                del self._ring[h]
                self._sorted_hashes.remove(h)

    def get_node(self, key: str) -> str:
        """找到 key 顺时针遇到的第一个节点"""
        if not self._ring:
            return None
        h = self._hash(key)
        # 二分查找第一个 >= h 的哈希值
        from bisect import bisect_right
        idx = bisect_right(self._sorted_hashes, h) % len(self._sorted_hashes)
        return self._ring[self._sorted_hashes[idx]]


# 演示：加节点时只有部分 key 需要迁移
ring = ConsistentHashRing(["server-A", "server-B", "server-C"])

keys = [f"item-{i}" for i in range(20)]
mapping = {}
for k in keys:
    mapping[k] = ring.get_node(k)

print("== 3 台服务器时的分布 ==")
for k in sorted(set(mapping.values())):
    items_in_node = [key for key, node in mapping.items() if node == k]
    print(f"  {k}: {len(items_in_node)} 个")

# 加一台服务器
print("\n== 添加 server-D ==")
ring.add_node("server-D")
changed = 0
for k in keys:
    new_node = ring.get_node(k)
    if new_node != mapping[k]:
        changed += 1

print(f"20 个 key 中，只有 {changed} 个需要迁移")
print(f"相比普通哈希取模（全部迁移），一致性哈希只动了 {changed/20*100:.0f}%")

== 3 台服务器时的分布 ==
  server-A: 7 个
  server-B: 6 个
  server-C: 7 个

== 添加 server-D ==
20 个 key 中，只有 5 个需要迁移
相比普通哈希取模（全部迁移），一致性哈希只动了 25%

一致性哈希的核心洞察： 把服务器和键都放在同一个环上。加/删服务器只影响环上相邻区域的键，而不是全部。虚拟节点（每个真实服务器虚拟出多个点）解决"实际数据分布不均"的问题。

以上内容作为概念预览。 一致性哈希的完整分析（虚拟节点数选择、偏斜分析、工程实现等）留到分布式系统章节。

现实中的应用：
Redis Cluster —— 16384 个槽（slot），不是严格的一致性哈希，但思想类似
Amazon Dynamo —— 一致性哈希 + 向量时钟
Nginx ngx_http_upstream_consistent_hash —— 让用户请求始终落到同一台缓存服务器
Cassandra —— 一致哈希 + 虚拟节点（每个物理节点 256 个虚拟节点）

常见陷阱

拆解 #1：两数之和——哈希表从 O(n²) 到 O(n)

你在一份林间物资清单里找两种物资，它们的重量之和等于某个目标值。这是一个经典的森林试炼。

python

# 暴力法 —— O(n²)，物资多了就跑不动
def two_sum_brute_force(nums, target):
    """暴力法 —— O(n²)，物资多了就跑不动"""
    n = len(nums)

```python
def two_sum_brute_force(nums, target):
    """暴力法 —— O(n²)，面试会被挂"""
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None


def two_sum_hash(nums, target):
    """
    哈希表法 —— O(n)，一遍过。
    每到一个数，问表里有没有 target - 当前数
    """
    seen = {}  # 值 → 索引

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:          # ✅ 哈希表 O(1) 查询
            return [seen[complement], i]
        seen[num] = i

    return None


arr = [2, 7, 11, 15]
print(f"暴力法: {two_sum_brute_force(arr, 9)}")
print(f"哈希法: {two_sum_hash(arr, 9)}")

暴力法: [0, 1]
哈希法: [0, 1]

为什么哈希表赢了？ complement in seen 这句——哈希表是 O(1)，暴力法是 O(n)。数组越长，差距越大。面试官看到暴力法会皱眉，看到哈希表会点头。

拆解 #2：哈希表 vs 数组查找——定量对比

别只听理论，跑一跑：

python

import time
import random

# 构造数据
n = 100_000
array = list(range(n))
hash_table = {i: i for i in range(n)}

# 模拟查找：随机访问一半元素
queries = [random.randint(0, n - 1) for _ in range(n // 2)]

# 数组查找（如果有值就知道位置，这里用 index 模拟查询场景）
start = time.perf_counter()
for q in queries:
    _ = q in array  # list 的 __contains__ 是 O(n)
t1 = time.perf_counter() - start

# 哈希表查找
start = time.perf_counter()
for q in queries:
    _ = q in hash_table  # dict 的 __contains__ 是 O(1) 平均
t2 = time.perf_counter() - start

print(f"n = {n}, 查询 {n // 2} 次")
print(f"数组查询 (O(n)):    {t1:.3f} 秒")
print(f"哈希表查询 (O(1)):  {t2:.3f} 秒")
print(f"相差 {t1 / t2:.0f} 倍")

n = 100000, 查询 50000 次
数组查询 (O(n)):    22.341 秒
哈希表查询 (O(1)):  0.008 秒
相差 2793 倍

四位数倍数的差异。这就是哈希表被称为"神级数据结构"的原因。

通关挑战

难度	题目	考察点
	LeetCode 1. Two Sum	一遍哈希表
	LeetCode 217. Contains Duplicate	哈希集合去重
	LeetCode 3. Longest Substring Without Repeating Characters	滑动窗口 + 哈希集
	LeetCode 49. Group Anagrams	排序作为哈希键
	LeetCode 146. LRU Cache	哈希表 + 双向链表
	LeetCode 380. Insert Delete GetRandom O(1)	哈希表 + 数组

进阶挑战：

用两个数组实现一个哈希表（开放地址法），支持 put、get、remove
实现一个 LRU 缓存（Least Recently Used Cache）—— 哈希表 + 双向链表
实现一个布隆过滤器（Bloom Filter）——用位数组 + 多个哈希函数

验收标准

[ ] 你能说清楚哈希表为什么能做到 O(1) 查找
[ ] 手写链地址法，包括插入、查找、删除
[ ] 讲清楚线性探测和二次探测的区别——什么场景选哪个
[ ] 解释负载因子的含义，0.75 这个数字怎么来的
[ ] 说清楚扩容为什么必须全部重哈希
[ ] 能解释一致性哈希解决的核心问题（加/删节点只需迁移部分数据）
[ ] 知道 Python dict 和 set 底层就是哈希表

常见卡点

卡点	破法
哈希冲突为什么不可避免	鸽巢原理：`m` 个鸽子放进 `n` 个巢，`m > n` 时一定至少有一个巢里有两只鸽子
为什么负载因子 0.75 是主流	经验 + 数学推导的均衡点。太高（>0.9）冲突爆炸；太低（<0.3）浪费内存
Python dict 为什么 O(1) 但偶尔慢	平均 O(1)，最坏 O(n)。最坏情况是所有 key 哈希到同一槽（设计极烂的哈希函数或恶意攻击）
hash('a') 每次运行不一样？	Python 3 默认开启 PYTHONHASHSEED 随机化（防止哈希洪水攻击）。同一个进程内是稳定的，跨进程不同
一致性哈希的虚拟节点怎么理解	每个物理节点在环上放多个虚拟点。比如 server-A 放 3 个点，server-B 放 3 个。数据分布从"3 个节点可能不均匀"变成"9 个点在环上随机分布"，更均匀
字典的 key 为什么必须是不可变对象	如果 key 可变，哈希值变了就找不到了。所以 Python 要求 `hashable` → 不可变类型（int、str、tuple 等）

现在不需要理解

完美哈希 —— 输入已知、静态的场景（如编译器关键字表）。日常用不上
布谷鸟哈希（Cuckoo Hashing） —— 一个槽只能放一个元素，冲突时把原元素踢到另一个位置。查找更确定但实现更复杂
哈希攻击（Hash Collision DoS） —— 构造大量 hash 相同的 key 塞爆服务器。Python 3 的随机 seed 就是为了防这个
一致性哈希的"偏斜"分析 —— 加虚拟节点可以缓解但不是完全消除。分布式系统的容错章节再说
dict 的内存布局细节 —— Python 3.6+ 的 dict 改成了"紧凑表示"（Indices + Entries 分开存储），遍历有序。这不是正确性层面的知识，是性能优化

旅人笔记

哈希森林里你学到了最锋利的一把刀：

哈希函数把任意对象变成数组下标。冲突必然存在。
链地址法——冲突了挂链表。简单，直观。Java HashMap 8 个节点后升级为红黑树。
开放地址法——冲突了找隔壁。内存紧凑，但删除麻烦（墓碑标记）。
负载因子控制着时空平衡。0.75 是业界共识。
扩容（Rehash）全部重算。偶尔痛一次，均摊还是 O(1)。
一致性哈希解决分布式缓存中的数据迁移问题。加节点只动一小部分。

哈希表是你在算法森林里拿到的第一个真正作弊级别的武器——把 O(n) 的查找变成了 O(1)。但这个武器有代价：它不保序、占内存、不适合范围查询。

选对地方用，哈希表就是神兵利器。选错了——比如需要按序遍历的场景——你会后悔。

下一站，你将从哈希森林走进树的王国。那里的世界不再是平铺直叙的数组和链表。树根在下，树枝在上，每一层都是新的可能。

🔜 下一站预告

第5章：树与二叉树——"从链表到树，只有一个分支的区别。但你很快会发现，这一分叉，就是整个世界。"

** 代码仓库位置：** vol-02-dsa/examples/ch04/ 下有此章完整示例代码

第4章：哈希表 ​

元数据卡 ​

你在哪 ​

你的任务 ​

遭遇战 → 获得技能 ​

遭遇 #1：哈希函数——万物皆可哈希 ​

遭遇 #2：链地址法——冲突了就串起来 ​

遭遇 #3：开放地址法——撞了就找下一位 ​

遭遇 #4：负载因子与扩容 ​

遭遇 #5：再哈希 & 二次探测 ​

遭遇 #6：一致性哈希——当机器数量变了 ​

常见陷阱 ​

拆解 #1：两数之和——哈希表从 O(n²) 到 O(n) ​

拆解 #2：哈希表 vs 数组查找——定量对比 ​

通关挑战 ​

验收标准 ​

常见卡点 ​

现在不需要理解 ​

旅人笔记 ​

🔜 下一站预告 ​

第4章：哈希表

元数据卡

你在哪

你的任务

遭遇战 → 获得技能

遭遇 #1：哈希函数——万物皆可哈希

遭遇 #2：链地址法——冲突了就串起来

遭遇 #3：开放地址法——撞了就找下一位

遭遇 #4：负载因子与扩容

遭遇 #5：再哈希 & 二次探测

遭遇 #6：一致性哈希——当机器数量变了

常见陷阱

拆解 #1：两数之和——哈希表从 O(n²) 到 O(n)

拆解 #2：哈希表 vs 数组查找——定量对比

通关挑战

验收标准

常见卡点

现在不需要理解

旅人笔记

🔜 下一站预告