快速查找的秘密 —— 哈希表

如果数组是书架上按编号排列的书，那哈希表就是图书管理员——你告诉他书名，他直接告诉你在哪个位置，不用一本本翻找。

📋 开篇自测：你已经知道多少？

1. Python的字典（dict）为什么查找速度那么快？它背后的原理是什么？
2. 什么是”哈希冲突”？两个不同的key为什么有可能被映射到同一个位置？
3. 为什么有时候要给哈希表”扩容”？扩容会带来什么代价？

---

一、从查字典说起——为什么我们需要哈希表

假设你手里有一本1000页的英语词典，要查”zebra”这个词。你会怎么做？

方法A：从第1页开始，逐页翻找。 最坏情况下翻1000页。这就是线性查找，O(n)。

方法B：利用字母排序，翻到Z开头的部分。 这类似二分查找，O(log n)。

方法C：词典有一个目录页，告诉你Z开头的词从第950页开始。 你直接翻到第950页附近就行了。

哈希表的思路类似方法C，但更激进——它用一个数学函数直接把要查的内容（key）转换成一个位置编号（索引），然后直接去那个位置取数据。理想情况下，查找时间是 O(1)。

这就像你有一个超级图书管理员，你说”zebra”，他脑子里瞬间算出”第957页”，一翻就到。

---

二、哈希函数——把任意数据变成数字

哈希表的核心是哈希函数（Hash Function）。它的作用是把任意类型的键（key）转换成一个整数，这个整数就是数据在底层数组中的索引。

一个好的哈希函数应该满足：

• 确定性： 同一个key永远得到同一个结果
• 均匀性： 不同的key尽量映射到不同的位置
• 高效性： 计算速度要快

来看一个最简单的例子——用”除留余数法”把名字映射到一个长度为10的数组：

def simple_hash(key, table_size):
    """最简单的哈希函数：把字符串各字符的ASCII码加起来，再对表长取模"""
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % table_size

# 假设哈希表大小为10
print(simple_hash("apple", 10))   # 某个0-9的数字
print(simple_hash("banana", 10))  # 某个0-9的数字
print(simple_hash("cherry", 10))  # 某个0-9的数字

Python内置的 hash() 函数更加复杂和高效：

print(hash("hello"))       # 一个很大的整数
print(hash(42))            # 42（整数的哈希值通常就是自身）
print(hash((1, 2, 3)))     # 元组可以哈希
# hash([1, 2, 3])          # 列表不可以哈希（因为列表可变）

🤔 想一想 为什么Python规定列表（list）不能作为字典的key，但元组（tuple）可以？这和哈希函数的”确定性”要求有什么关系？

---

三、哈希冲突——两个人抢同一个座位

无论哈希函数设计得多好，总会遇到一个问题：两个不同的key被映射到了同一个位置。 这就是哈希冲突（Hash Collision）。

这很正常。想想看：如果你的数组只有10个位置，但你要存100个数据，至少有90个数据得和别人”挤在一起”。这就是鸽巢原理——10个巢穴塞100只鸽子，每个巢穴至少有10只鸽子。

解决冲突有两大流派。

方法一：链地址法（拉链法）

思路很简单：数组的每个位置不直接存数据，而是存一个链表。所有映射到同一位置的数据都挂在同一条链上。

就像一个公寓楼——每个门牌号对应的不是一个人，而是一整户人家。你来找人，先到对应的门牌号，再在这户人家里找。

class HashTableChaining:
    """用链地址法处理冲突的哈希表"""

    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

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

    def put(self, key, value):
        """插入或更新键值对"""
        index = self._hash(key)
        bucket = self.buckets[index]
        # 检查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):
        """根据key获取value"""
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(f"找不到键：{key}")

    def remove(self, key):
        """删除键值对"""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return v
        raise KeyError(f"找不到键：{key}")

# 使用示例
ht = HashTableChaining()
ht.put("name", "张三")
ht.put("age", 25)
ht.put("city", "北京")
print(ht.get("name"))   # 张三
print(ht.get("city"))   # 北京
ht.put("name", "李四")  # 更新
print(ht.get("name"))   # 李四

方法二：开放寻址法

另一种思路是：如果目标位置被占了，就往后找下一个空位。就像你去餐厅，发现预约的桌子被人占了，你就看看旁边的桌子有没有空的。

class HashTableOpenAddressing:
    """用开放寻址法（线性探测）处理冲突的哈希表"""

    EMPTY = None
    DELETED = "<DELETED>"  # 删除标记

    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.keys = [self.EMPTY] * capacity
        self.values = [self.EMPTY] * capacity

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

    def put(self, key, value):
        if self.size >= self.capacity * 0.7:  # 负载因子超过0.7就扩容
            self._resize()
        index = self._hash(key)
        while self.keys[index] is not self.EMPTY and self.keys[index] != self.DELETED:
            if self.keys[index] == key:
                self.values[index] = value  # 更新已有key
                return
            index = (index + 1) % self.capacity  # 线性探测：往后一位
        self.keys[index] = key
        self.values[index] = value
        self.size += 1

    def get(self, key):
        index = self._hash(key)
        start = index
        while self.keys[index] is not self.EMPTY:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.capacity
            if index == start:
                break
        raise KeyError(f"找不到键：{key}")

    def _resize(self):
        """扩容：创建一个更大的数组，把所有数据重新放一遍"""
        old_keys = self.keys
        old_values = self.values
        self.capacity *= 2
        self.keys = [self.EMPTY] * self.capacity
        self.values = [self.EMPTY] * self.capacity
        self.size = 0
        for i in range(len(old_keys)):
            if old_keys[i] is not self.EMPTY and old_keys[i] != self.DELETED:
                self.put(old_keys[i], old_values[i])

两种方法的对比

特性	链地址法	开放寻址法
内存使用	需要额外存储链表指针	不需要额外指针
冲突处理	可以无限挂链	受限于数组大小
缓存性能	链表分散在内存中，缓存不友好	数据在数组中相邻，缓存友好
实现复杂度	较简单	删除操作较复杂
适用场景	数据量不确定时	数据量可预估时

Python的dict使用的是开放寻址法的变体，因为它的缓存性能更好。

---

四、负载因子与扩容——什么时候该换个更大的房子

负载因子（Load Factor） = 已存数据量 / 哈希表容量

你可以把它想成”房间入住率”。当入住率太高，走廊里都是人，找房间就变得很慢。一般来说，当负载因子超过0.7~0.75时，就应该扩容了。

扩容的过程叫做Rehash（重新散列）：

1. 创建一个更大的数组（通常是原来的2倍）
2. 把所有现有数据重新计算哈希值，放入新数组
3. 抛弃旧数组

为什么要重新计算而不是简单复制？因为数组大小变了，hash(key) % capacity的结果也变了。

# 扩容前：capacity = 4
# "apple" -> hash("apple") % 4 = 2
# 扩容后：capacity = 8
# "apple" -> hash("apple") % 8 = 6  # 位置变了！

扩容的代价是O(n)——需要把所有数据搬一遍。但因为扩容不是每次操作都发生，均摊下来每次操作仍然是O(1)。这就像搬家很辛苦，但你不会每天都搬家。

🤔 想一想 Python的字典在什么时候会触发扩容？你能设计一个实验来观察吗？（提示：可以用sys.getsizeof()来观察字典占用的内存变化。）

---

五、哈希表的实际应用

应用1：两数之和——面试经典题

给定一个数组和一个目标值，找出数组中和为目标值的两个数的索引。

def two_sum(nums, target):
    """用哈希表实现两数之和，时间O(n)"""
    seen = {}  # 值 -> 索引
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))   # [0, 1]，因为2+7=9
print(two_sum([3, 2, 4], 6))         # [1, 2]，因为2+4=6

不用哈希表，你需要两层循环O(n²)。用了哈希表，只需要一次遍历O(n)。这就是”空间换时间”的教科书式案例。

应用2：统计词频

def word_frequency(text):
    """统计每个单词出现的次数"""
    freq = {}
    for word in text.lower().split():
        word = word.strip(".,!?;:")
        freq[word] = freq.get(word, 0) + 1
    return freq

text = "To be or not to be, that is the question. To be is to exist."
result = word_frequency(text)
for word, count in sorted(result.items(), key=lambda x: -x[1]):
    print(f"{word}: {count}")
# to: 4, be: 3, is: 2, ...

应用3：缓存——让重复计算不再重复

def fibonacci_with_cache(n):
    """用哈希表做缓存，避免重复计算斐波那契数"""
    cache = {}

    def fib(k):
        if k in cache:
            return cache[k]
        if k <= 1:
            return k
        result = fib(k - 1) + fib(k - 2)
        cache[k] = result
        return result

    return fib(n)

# 不用缓存：fib(40)可能需要数十秒
# 用缓存：瞬间完成
print(fibonacci_with_cache(40))  # 102334155

应用4：判断重复

def find_duplicates(items):
    """找出列表中所有重复的元素"""
    seen = set()  # 集合底层也是哈希表
    duplicates = set()
    for item in items:
        if item in seen:
            duplicates.add(item)
        seen.add(item)
    return list(duplicates)

print(find_duplicates([1, 3, 5, 3, 7, 1, 9]))  # [1, 3]

⚠️ 常见误区

• 误区1：“哈希表的查找永远是O(1)” —— 这是平均情况。在极端情况下（比如所有key都冲突到同一个位置），查找退化为O(n)。好的哈希函数和合理的负载因子可以让这种极端情况几乎不会发生。
• 误区2：“哈希表里的数据是有序的” —— 传统哈希表不保证任何顺序。Python 3.7+的dict保持插入顺序，这已被纳入语言规范（CPython 3.6是实现细节，3.7起正式成为语言保证）。但这不是哈希表的固有特性，其他语言的哈希表不一定保序。collections.OrderedDict仍有其独特价值——它支持move_to_end()方法，且两个OrderedDict的相等比较会考虑元素顺序，而普通dict不会。
• 误区3：“任何东西都可以当key” —— 只有”可哈希”的对象才能当key。在Python中，可变对象（如list、dict、set）不可哈希，因为它们的内容可能随时变化，导致哈希值不一致。

---

六、设计一个好的哈希函数

好的哈希函数应该让数据尽可能均匀地分散到各个位置。如果大量数据都挤在同一个位置，查找效率就会严重下降。

几种常见的哈希方法：

# 1. 除留余数法（最常见）
def hash_mod(key, size):
    return key % size

# 2. 乘法散列法
def hash_multiply(key, size):
    A = 0.6180339887  # 黄金比例的小数部分
    return int(size * ((key * A) % 1))

# 3. 字符串哈希（多项式哈希）
def hash_string(s, size):
    h = 0
    for char in s:
        h = h * 31 + ord(char)  # 31是一个常用的质数
    return h % size

为什么常用质数（如31、37、41）作为乘数？因为质数能让哈希值的分布更均匀。如果用合数（比如100），那所有100的倍数都会映射到位置0，造成大量冲突。

---

📝 掌握度自测

1. 概念题： 用自己的话解释哈希表的工作原理。它为什么平均查找时间是O(1)？
2. 分析题： 一个容量为100的哈希表，已经存了90个数据。此时插入一个新数据，链地址法和线性探测法各需要探测几次（平均情况下）？
3. 编码题： 实现一个函数，判断两个字符串是否是”字母异位词”（由相同字母重新排列而成），比如”listen”和”silent”。要求时间复杂度O(n)。
4. 设计题： 如果你要给一个在线游戏设计”用户名查重”功能（几百万用户），你会用什么数据结构？为什么？
5. 思考题： Python的dict在Python 3.6之前是无序的，3.7+变成了有序的。你猜它是怎么实现的？（提示：它用了两个数组。）

💡 自我评估

• 全部答对：你对哈希表的理解已经很深入了，可以在面试中自信地聊这个话题。
• 答对3-4题：掌握良好，建议深入研究一下Python dict的源码实现。
• 答对1-2题：重新阅读”冲突处理”和”负载因子”部分，这是哈希表的核心难点。
• 全部答错：哈希表是最重要的数据结构之一，值得多花时间。建议自己动手实现一个简单的哈希表。

---

前面学的数据结构都是”线性”的——元素排成一条线。但现实世界中很多关系是层级式的：文件夹套文件夹、公司组织架构、网页的 DOM 结构。下一章，我们进入非线性结构的世界——树与二叉树。