哈希表详解：原理、代码与时间复杂度

哈希表解决什么问题

假设你保存了一百万条用户记录，需要按邮箱查找其中一条。扫描列表是 O(n)。把列表排好序可以用二分查找做到 O(log n)，但插入会变慢。哈希表无论有多少条记录，查找记录的平均时间都是 O(1)，插入和删除同样快。

这就是哈希表无处不在的原因：编程语言中的字典和集合、数据库的哈希索引、缓存、编译器中的符号表，以及去重。

用大白话理解哈希表

想象一个有 100 个编号挂钩的衣帽间。管理员不会在所有挂钩里找你的外套，而是根据你的名字算出一个挂钩编号，直接走过去。计算这个编号的函数就是哈希函数。好的哈希函数速度快，同一个键总是得到同一个数字，并且能把不同的键均匀分散到各个挂钩上。

1. 计算 h = hash(key)。
2. 确定桶：index = h % capacity。
3. 只在这个桶里查找该键。

示例演练：拉链法处理冲突

取一个有 4 个桶的哈希表，并使用一个玩具哈希函数：字母序号之和（a = 1，b = 2，……）。

act 和 bee 与 cat 发生了冲突。现在查找 bee 就要检查桶 0 中的三个条目。如果哈希函数很差（字母之和忽略了顺序）或桶太少，链就会变长，哈希表也会变慢。真实的哈希函数会混合键的所有位，真实的哈希表在装得太满时会扩容。

用 Python 实现拉链法

每个桶是一个由 [key, value] 对组成的列表。当元素数量超过桶数的 0.75 倍（即负载因子）时，哈希表会把容量翻倍并重新插入所有元素。

class HashTable:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]
    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # update existing key
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            self._resize()
    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default
    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False
    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        self.size = 0
        for k, v in old:
            self.put(k, v)

t = HashTable()
for i, word in enumerate(["red", "green", "blue", "cyan", "pink", "gold", "gray"]):
    t.put(word, i)
t.put("red", 100)
t.delete("blue")
print(t.get("red"), t.get("blue"), t.size, len(t.buckets))  # 100 None 6 16

冲突处理策略对比

CPython 的 dict 使用开放寻址，探测序列带扰动，并且从 Python 3.7 起保证遍历顺序与插入顺序一致。Java 的 HashMap 使用拉链法，并把过长的链转换成平衡树。

时间与空间复杂度

平均 O(1) 取决于良好的哈希函数和受控的负载因子。Python 会为每个进程随机化字符串哈希（哈希种子），这样攻击者就很难发送大量相互冲突的键，把服务器拖慢到每个请求 O(n)。

常见错误

• 用可变对象做键，或者在类上定义了 __eq__ 却没有对应的 __hash__。相等的对象必须有相等的哈希值。
• 期望得到有序结果。哈希表提供的是快速查找，而不是顺序；需要范围查询或最小键时，请使用有序列表或平衡树（二叉搜索树）。
• 跨运行依赖 hash() 的值：除非固定 PYTHONHASHSEED，字符串哈希在不同 Python 进程之间会变化。需要稳定的哈希请用 hashlib。
• 把哈希表当作安全原语。哈希表使用快速的非加密哈希；密码需要专用的密码哈希函数。

何时使用，以及典型的面试题

只要你需要快速回答“我见过这个吗？”或“这个键对应什么值？”，就用哈希表。如果还需要顺序、范围或最近的键，请使用二叉搜索树或有序数组。

经典问题：两数之和（保存每个数的下标，查找 target - x）、统计频率（collections.Counter）、按排序后的字母对字母异位词分组、检测重复，以及在动态规划中做记忆化。

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)