哈希表实现：散列函数与冲突解决

哈希表的底层逻辑：从散列函数到冲突解决

在程序世界里，数组提供了最快的随机访问速度（O(1)时间复杂度），但它的索引必须是整数，且范围往往有限。哈希表（Hash Table），又称散列表，正是通过一个叫做“散列函数”的魔法，将任意类型的键（字符串、对象等）映射为数组的有效索引，从而让数组的极速访问能力能够服务于复杂键值对存储。

理解哈希表实现的核心，就是理解两个关键设计：散列函数的设计与哈希冲突的解决。本文将以最直观的方式，带你从零实现一个简易但完整的哈希表。

1. 核心基石：散列函数

散列函数（Hash Function）肩负着将输入的键（Key）转换为固定大小整数值（通常称为哈希值或散列值）的任务。这个整数值再经过取模运算，就变成了底层数组的有效下标。

一个理想的散列函数应满足：

• 确定性：相同的输入永远产生相同的输出。
• 高效性：计算过程应尽可能快速，不能成为性能瓶颈。
• 均匀分布：将键尽可能均匀地映射到整个数组空间，避免扎堆。这是衡量散列函数优劣的最关键指标。

1.1 简单散列函数的实现（以整数键为例）

如果键本身就是整数，最简单的散列函数就是取模运算：

def hash_function(integer_key, array_size):
    return integer_key % array_size

但若键不是整数（如字符串），则需要先将其转换为整数。

1.2 字符串散列：多项式滚动哈希

在工程中，字符串键占有极大比例。一种经典且传播极广的方法是基于多项式求值的“滚动哈希”，它将每个字符视为一个系数：

def string_hash(s, array_size):
    hash_val = 0
    # 选择一个质数作为基数，31在Java中被广泛使用，效果优良
    prime = 31
    for char in s:
        hash_val = (hash_val * prime + ord(char)) % array_size
    return hash_val

此算法利用霍纳法则将多项式高效计算出来，并且通过不断取模防止整数溢出。基数的选择会影响分布，通常选用一个与字符集大小互质的质数（31、37、131 等）。

注意：真实的哈希表并不会直接用 % array_size 作为最终散列函数，而是先计算一个与容量无关的原始哈希码，然后在插入时再根据当前容量进行取模。例如 Java 中 hashCode() 方法返回 int，后由 HashMap 内部进行 (n - 1) & hash 优化取模。

2. 来自空间的挑战：哈希冲突

散列函数的目标是把无限的输入空间映射到有限的数组索引空间。根据鸽巢原理，无论散列函数多么精妙，不同键计算出相同索引的概率始终存在——这就是哈希冲突（Hash Collision）。

冲突无法避免，但可以经由优秀的结构设计来化解。主流实现方案分为两大类：链地址法 与 开放寻址法。

3. 冲突解决策略一：链地址法

链地址法（Separate Chaining）是最直观、最经典的冲突处理方法。它将哈希表的每一个槽位（Bucket）不直接存储单个元素，而是存储一个集合结构（如链表、红黑树）。

• 插入：计算索引，若槽位为空则新建链表，将键值对追加到链表末尾（或头部）。
• 查找：计算索引，在对应链表中顺序遍历，逐一比较键。
• 删除：计算索引，在链表中找到该键并移除节点。

3.1 基于链表的简易实现（Python 示例）

class HashTable:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.buckets = [ [] for _ in range(capacity) ]  # 每个槽位是一个空列表
        self.size = 0

    def _hash(self, key):
        # 简单字符串哈希
        hash_val = 0
        for ch in str(key):
            hash_val = (hash_val * 31 + ord(ch)) % self.capacity
        return hash_val

    def put(self, key, value):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        # 更新已存在的键
        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)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        raise KeyError(f"键 '{key}' 不存在")

    def remove(self, key):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return
        raise KeyError(f"键 '{key}' 不存在")

3.2 链地址法的退化与优化

链地址法在冲突严重时，链表会太长，导致查找退化至 O(n)。成熟的实现（如 Java HashMap、C++ std::unordered_map）会在链表长度超过阈值（如 8）时，将链表树化为红黑树，将最坏查找时间优化至 O(log n)。这通常与动态扩容配合使用，以保证负载因子（元素数 / 槽位数）处于健康范围。

4. 冲突解决策略二：开放寻址法

开放寻址法（Open Addressing）完全不使用额外的链表结构。当发生冲突时，它会在哈希表中探测另一个空闲的槽位，并将元素直接存入那里。所有元素都散落在数组内部，因此内存占用更紧凑，缓存友好性更好，但删除操作较为复杂。

根据探测序列的规则，开放寻址法分为几种主流变体：

4.1 线性探测

线性探测是最简单的探测方法。若索引 i 被占用，就依次检查 i+1, i+2, i+3 … 直到找到空位。

• 插入：若位置被占，线性向后找空位。
• 查找：从散列位置开始，顺序比较键，直到遇到空槽位则判定为不存在。
• 删除：不能简单地将槽位置空，否则会切断探测链，导致后续元素丢失。必须使用惰性删除，将槽位标记为“已删除”而非“空”。

线性探测的简单实现（包含惰性删除）

class OpenAddressingHashTable:
    DELETED = "<DELETED>"  # 惰性删除标记

    def __init__(self, capacity=16):
        self.capacity = capacity
        self.table = [None] * capacity
        self.size = 0

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

    def _probe(self, key):
        """生成线性探测序列"""
        start = self._hash(key)
        for i in range(self.capacity):
            idx = (start + i) % self.capacity
            yield idx, self.table[idx]

    def put(self, key, value):
        for idx, entry in self._probe(key):
            if entry is None or entry is self.DELETED or (isinstance(entry, tuple) and entry[0] == key):
                self.table[idx] = (key, value)
                self.size += 1
                return
        raise Exception("哈希表已满")

    def get(self, key):
        for idx, entry in self._probe(key):
            if entry is None:
                break  # 遇到空位，说明键不存在
            if isinstance(entry, tuple) and entry[0] == key:
                return entry[1]
        raise KeyError(key)

    def remove(self, key):
        for idx, entry in self._probe(key):
            if entry is None:
                break
            if isinstance(entry, tuple) and entry[0] == key:
                self.table[idx] = self.DELETED
                self.size -= 1
                return
        raise KeyError(key)

线性探测容易出现一次聚集（primary clustering）现象，即连续占用的槽位会逐渐连成一片，新元素落入此区域时探测长度激增，性能下降。

4.2 二次探测

为了解决一次聚集，二次探测（Quadratic Probing）采用步长按二次函数递增的跳跃探测：索引序列为 (i + 1^2) % M, (i + 2^2) % M, (i + 3^2) % M …

• 优点：有效避免了一次聚集。
• 要点：容量 M 通常取质数，并且负载因子保持在较低水平（如 0.5），以保证能覆盖所有槽位。

4.3 双散列法

双散列（Double Hashing）使用两个独立的散列函数 h1(key) 与 h2(key)，探测序列为 (h1(key) + k * h2(key)) % M。h2(key) 必须与容量 M 互质，且不能返回 0。这是开放寻址法中理论上分布最均匀的方法，显著减少了聚集现象。

5. 不可回避的话题：动态扩容

无论是链地址法还是开放寻址法，当哈希表中元素过多时，冲突概率急剧上升，性能恶化。因此，必须监控负载因子（Load Factor，α = 元素数量 / 槽位数量）。当 α 超过预设阈值（例如链地址法 0.75，开放寻址法 0.5~0.7）时，触发扩容：

1. 创建一个更大的新数组（通常是原容量的两倍）。
2. 遍历旧表中的所有有效元素，重新计算散列值并将其插入新表（该过程称为 rehashing）。
3. 替换旧表。

这是一个相对耗时的 O(n) 操作，但由于分摊到多次插入中，平均加入成本仍可视为 O(1)。

6. 场景选择与工程建议

• 多数主流语言的通用哈希表（如 Java HashMap、C# Dictionary）采用链地址法+树化，因其在极端情况下表现稳定。
• 对性能极致要求、内存敏感且键值对生命周期简单的场景（如编程语言符号表），可采用开放寻址法（Python 的 dict 采用优化的开放寻址法）。

7. 手写哈希表的关键检查点

当你自己实现一个哈希表时，请确保涵盖以下测试场景：

• 正常插入、查找、更新、删除。
• 冲突处理：插入多个散列值相同的键，验证查找正确。
• 删除后查找：确保惰性删除不会破坏探测链。
• 扩容后数据完整性：扩容后所有旧元素仍能被访问。
• 边界情况：键为 None、空字符串、容量为 1 等。

理解散列函数与冲突解决，你就掌握了哈希表这座数据宫殿的承重墙。无论语言本身的字典功能多么强大，剖开其内核，不外乎就是本文所描述的这一系列精巧的结构化思维。