如何理解 Map 的哈希碰撞与扩容

在高性能编程中，Map（哈希表）是处理键值对的首选工具。然而，随着存储数据的增长，Map 如何处理键冲突以及如何平滑扩容是决定系统稳定性的关键。本文将深入解析哈希碰撞的成因及现代扩容技术的演进。

1. 哈希碰撞：当两条路通往同一个出口

哈希表的底层通常是一个数组。当我们插入一个键值对时，哈希函数会将键（Key）计算为一个数字索引。

哈希碰撞发生在不同的键被映射到同一个数组索引时。最常见的解决方法是拉链法（Chaining）：每个数组槽位（Bucket）不再直接存值，而是指向一个链表。当碰撞发生时，新元素直接追加到链表末尾。

2. 扩容的必要性：性能退化的临界点

如果数组固定不变，随着数据量增加，链表会变得越来越长。原本 $O(1)$ 的查找效率会退化为 $O(n)$。

为了解决这个问题，Map 会引入负载因子（Load Factor）。例如 Java HashMap 的默认负载因子是 0.75。当 元素数量 / 数组容量 > 0.75 时，Map 就会触发扩容。

3. 全量扩容 vs 渐进式扩容

全量扩容（Full Rehash）

传统做法是：申请一个两倍大的新数组，将旧数组中的所有元素重新计算哈希并搬移到新数组中。这种做法在数据量大时会产生明显的阻塞（Stop-the-world）。

渐进式扩容（Incremental Rehash）

为了避免长耗时停顿，诸如 Redis 和部分 Golang 实现采用了渐进式扩容。它维护两个哈希表（ht[0] 和 ht[1]），扩容期间，每次对 Map 的增删改查操作都会顺带迁移一部分旧数据到新表，直到旧表清空。

4. 实战模拟：简单的拉链法 Map 实现

以下是用 Python 模拟的一个支持拉链法和基本扩容思路的简单实现：

class TinyMap:
    def __init__(self, initial_capacity=4):
        self.capacity = initial_capacity
        self.count = 0
        self.buckets = [[] for _ in range(self.capacity)]

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

    def put(self, key, value):
        # 检查是否需要扩容（此处演示逻辑简化，仅做概念展示）
        if self.count / self.capacity > 0.75:
            self._resize()

        idx = self._hash(key)
        # 碰撞处理：遍历链表查看 Key 是否已存在
        for item in self.buckets[idx]:
            if item[0] == key:
                item[1] = value
                return
        # 不存在则追加到链表末尾
        self.buckets[idx].append([key, value])
        self.count += 1

    def _resize(self):
        # 扩容两倍并重新分配数据
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.count = 0
        for bucket in old_buckets:
            for k, v in bucket:
                self.put(k, v)

# 使用示例
my_map = TinyMap()
my_map.put(\"name\", \"Dev\")
print(my_map.capacity)  # 初始容量 4

通过理解从基础链表到高效迁移的演进过程，开发者可以在设计高并发系统时，更好地评估不同语言 Map 实现的性能开销。