第 2 课我们认识了四种线性数据结构，并且得出一条关键结论：数组"按下标读"是 O(1)，但它"按值找"是 O(n)。

想想这件事有多憋屈：你有一个存了 100 万个人名的列表，想知道"张三在不在里面"，只能从头一个个比过去——最坏要翻 100 万次。

难道就没有一种结构，既能"按名字直接定位"，又不用事先排好顺序吗？

有。它就是这一课的主角——哈希表（hash table）。它是工程界和面试里出现频率最高的数据结构，没有之一。你每天都在用的 Python 字典（dict）、集合（set）、缓存、数据库索引，底层全是它的思想。

一、先回到"查字典"：哈希表的直觉

第一课我们拿字典打过比方。现在把这个比方再往前推一步：

普通列表查名字，就像一本没有目录的书，你只能一页页翻，O(n)。

哈希表查名字，就像你脑子里有个"瞬间定位法"：

拿到"张三"这个名字 → 脑子里立刻算出"他应该在第 7 格" → 直接走到第 7 格看一眼 → 完事。

这个"拿到名字、立刻算出位置"的魔法函数，就叫哈希函数（hash function）。

所以哈希表的定义朴素到惊人：

哈希表 = 一个数组 + 一个哈希函数。 哈希函数负责把任意"键"（名字）映射成数组里的"下标"（格子号）。

有了它，理想情况下查找、插入、删除都只需要"算一下下标 + 看一眼"，也就是 O(1)——不管表里有 10 个还是 1 亿个数据，速度一样快。

二、哈希函数：怎么把"张三"变成一个数字

数组的下标必须是整数，而我们要存的"键"可能是任何东西：字符串、数字、甚至对象。哈希函数干的事就是：

hash("张三")  ->  某个整数

这个整数再对"格子总数"取模，就落到了某个格子：

index = hash(key) % table_size

一个好哈希函数要满足两条：

  1. 快——每次算下标都很快，否则 O(1) 就泡汤了。
  2. 散得开——不同的键尽量映射到不同的下标，别全挤到一格里。

Python 内置的 hash() 就是这个角色：

print(hash("张三"))       # 每次运行可能不同（Python 加了随机化）
print(hash("李四"))
print(hash(42))
注意：hash() 的值每次运行可能不一样（Python 为了安全做了随机化），但同一次运行内，同一个键的 hash 值一定相同，这是哈希表能工作的前提。

那"散不开"怎么办？——碰撞

假设表只有 10 个格子，却有 100 个名字。鸽笼原理告诉你：一定有不同名字被算到同一个格子。这就叫碰撞（collision）。

碰撞是必然的、躲不掉的。哈希表要解决的不是"消除碰撞"，而是"碰撞发生了怎么优雅地处理"。主流有两派：

三、碰撞处理的两大流派

流派一：链地址法（separate chaining）

每个格子不直接存一个数据，而是存一条链表。碰撞了，就往这个格子的链表里再挂一个。

格子 7: [张三] -> [王五] -> None   # 两个名字都算到了 7，串成链表

查找时：先算下标 → 走到格子 → 在链表里挨个比对。只要链表短，依然接近 O(1)。

流派二：开放定址法（open addressing）

每个格子只存一个数据。碰撞了，就按固定规则往后面找空位（比如顺延一格、或按平方跳）。

张三 想进 7，发现 7 被占了 → 看 8 → 8 空，坐下。

Python 的 dict 底层用的就是开放定址法（具体是"平方探测 + 伪随机"），这也是为什么 Python 字典特别快。

两种流派这样记：链地址是"一格挂一串"，开放定址是"没位就往后挪"。

四、复杂度：为什么说它是 O(1)，但又不是绝对的 O(1)

理想情况：哈希函数完美散开，每个格子最多一个数据 → 查找 O(1)。

但现实有碰撞。极端最坏情况：所有键都算到同一格（比如你的哈希函数烂到"不管什么键都返回 7"），那哈希表就退化成了一条链表，查找变成 O(n)。

所以严谨的说法是：

操作平均（摊还）最坏
查找 / 插入 / 删除O(1)O(n)

工程上我们靠两件事把"最坏"摁住，让它几乎不发生：

  1. 好的哈希函数：散得开，不让所有键挤一起。
  2. 动态扩容：见下一条。

五、负载因子：哈希表"快不快"的命门

负载因子（load factor）= 已存数据量 / 格子总数。

  • 负载因子 0.3：格子空荡荡，碰撞少，快。
  • 负载因子 0.9：格子快挤满了，碰撞一堆，链表变长，开始变慢。

所以哈希表不会等"塞满"才管，而是负载因子一超过阈值（比如 0.75），就自动扩容——格子翻倍，把所有数据重新哈希、重新摆放（这叫 rehash）。

这就是为什么我们说哈希表的 O(1) 是摊还（amortized）的：绝大多数时候插入 O(1)，偶尔扩容那一次是 O(n)，但把成本平摊到每次操作上，仍是 O(1)。

这个"用空间换时间 + 动态扩容"的思路，是理解一切高性能缓存的钥匙。

六、Python 里的哈希表：dict 和 set

好消息：Python 已经把哈希表做好了，你直接用就行。

字典 dict——键值对

d = {}                 # 空字典
d["name"] = "张三"      # 插入，O(1)
d["age"] = 20
print(d["name"])       # 查找，O(1)

"name" in d            # 判断键是否存在，O(1)
d["name"] = "李四"      # 覆盖（更新），O(1)
del d["age"]           # 删除，O(1)

核心性质：字典的键必须是可哈希（hashable）的——字符串、数字、元组可以；列表、字典不行（因为它们可变，一变 hash 值就乱套了）。

# 会报错：列表不可哈希
# {[1, 2]: "x"}   # TypeError: unhashable type: 'list'
{("a", "b"): "元组可以"}   # 元组不可变，可以当键

集合 set——自动去重 + 成员判断

s = {1, 2, 3, 3, 3}    # 自动去重
print(s)               # {1, 2, 3}

2 in s                 # O(1) 成员判断
s.add(4)               # O(1) 插入
s.remove(2)            # O(1) 删除

集合和字典是一对孪生兄弟：集合可以理解成"没有 value 的字典"，底层同样用哈希表。

七、哈希表的两大杀招（面试高频）

杀招一：把"查找"从 O(n) 砍到 O(1)

最经典的题——两数之和（Two Sum）：

给一个数组 nums 和一个目标值 target，找出两个数，使它们的和等于 target，返回它们的下标。

笨办法（双重循环）：O(n²)。

哈希表解法：遍历一遍，每遇到一个数 x，先问"target - x 在不在表里？"在就找到了，不在就把 x 记进表里。一遍搞定，O(n)：

def two_sum(nums, target):
    seen = {}                      # 值 -> 下标
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:           # O(1) 查找
            return [seen[need], i]
        seen[x] = i                # 记住"这个值在第几个位置"
    return None

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

你看，核心就一句 need in seen——因为 seen 是字典，这"在不在"是 O(1)。如果 seen 是列表，这题又退回 O(n²) 了。

杀招二：O(1) 去重 + 计数

# 去重
nums = [1, 2, 2, 3, 3, 3]
print(list(set(nums)))            # [1, 2, 3]

# 统计每个词出现次数
from collections import Counter
words = "a b a c b a".split()
print(Counter(words))             # Counter({'a': 3, 'b': 2, 'c': 1})

Counter 底层就是字典，计数这件事同样是 O(1) 一次。

杀招三：LRU Cache——哈希表 + 双向链表的黄金组合

LRU = Least Recently Used，中文叫「最近最少使用」。场景：缓存（cache）容量有限，塞满之后，就把最久没被用到的那条踢出去，给新数据腾地方。

这是面试最经典的题之一，难在要同时满足两件事，而且都得是 O(1)：

  1. 快速判断某个 key 在不在 → 哈希表负责
  2. 快速把「刚用过的」挪到最新、「最久没用的」挪去被踢 → 链表负责（改指针就行，O(1)）

为什么不能只用其中一种结构？

结构查找挪动/删除
数组按下标 O(1)挪位置要「搬家」O(n)
单向链表找不到（得从头扫）改指针 O(1)
哈希表 + 双向链表O(1)O(1)

关键在「双向」：删除一个节点时，要能同时够到它的前一个和后一个，单向链表做不到 O(1) 删，双向才行。

Python 的偷懒写法：OrderedDict 天生「记住插入顺序」，move_to_end 把它挪到末尾，popitem(last=False) 踢掉最前面（最久没用）的：

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)      # 刚用过，挪到末尾 = 最新
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)   # 踢掉最久没用的（最前面）

c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
print(c.get(1))    # 1（顺便把 1 挪到最新）
c.put(3, 3)        # 满了，踢掉最久没用的 2
print(c.get(2))    # -1（2 已经被踢了）
print(c.get(3))    # 3

面试手写版（原理版）：如果面试官不让用 OrderedDict，就手写双向链表：

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}              # key -> Node（哈希表负责快速找）
        self.head = Node()           # 哨兵头
        self.tail = Node()           # 哨兵尾
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):         # 从链表里摘下
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_tail(self, node):    # 插到尾部 = 最新
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_tail(node)      # 刚用过，挪到最新
        return node.value

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_tail(node)
        if len(self.cache) > self.cap:
            old = self.head.next     # 头部就是最久没用的
            self._remove(old)
            del self.cache[old.key]

一句话记牢：哈希表管「找得快」，双向链表管「挪得快」，两个一合，就是 LRU。

八、延伸：布隆过滤器——用一点点内存，判重海量数据

哈希表能 O(1) 判断"在不在"，但它有个隐藏代价：键本身得存下来。你想判重 1 亿个 URL，就得把这 1 亿个 URL 全放进内存——直接爆掉。

有没有一种结构，能用极小的内存回答"这个元素在不在"，哪怕偶尔判断错？

有，它就是布隆过滤器（Bloom Filter）。

思路：一个位数组 + 多个哈希

布隆过滤器不存元素本身，只存一个位数组（一堆 0/1）和多个哈希函数：

  • 加入：把一个元素用 k 个哈希函数算出 k 个位置，把这 k 个位置都置 1。
  • 查询：同样算出 k 个位置，如果全为 1，就说"可能在"；只要有一个不是 1，就一定不在。
class Bloom:
    def __init__(self, size=100):
        self.bits = [0] * size
    def _hs(self, s):                      # 3 个简单哈希
        h1 = sum(ord(c) * (i + 1) for i, c in enumerate(s)) % 100
        h2 = sum(ord(c) * 7 for c in s) % 100
        h3 = (sum(ord(c) ** 2 for c in s) + len(s)) % 100
        return h1, h2, h3
    def add(self, s):
        for h in self._hs(s):
            self.bits[h] = 1
    def maybe(self, s):
        return all(self.bits[h] for h in self._hs(s))

bf = Bloom()
bf.add("apple")
bf.add("banana")
print(bf.maybe("apple"))   # True（加过）
print(bf.maybe("cherry"))  # False（没加过）

关键性质：只会"误报"，不会"漏报"

  • 一定不在：某位是 0 → 这个元素绝对没被加入过（可信）。
  • 可能在：所有位都是 1 → 可能真加过，也可能恰好撞车（别的元素把这几位置 1 了），这是误报（false positive）。

布隆过滤器永远不会漏掉真正加过的元素，只可能把"没加过的"误判成"在"。这个误报率可以通过"位数组越大、哈希函数越多"压到任意低。

用在哪儿

场景用法
缓存穿透先问布隆"这个 key 存在吗"，不在就直接拒，不查数据库
爬虫去重记下爬过的 URL，新 URL 先查布隆
垃圾邮件快速判断是不是已知垃圾地址
数据库（LSM 树）判断 key 是否可能存在，避免无谓的磁盘查找

记住：布隆过滤器 = 哈希思想的极致工程化——用"位 + 多哈希"把 O(1) 查找的内存成本压到极致，代价是允许极小的误报率。

九、动手时间 🎯

实验 1：亲眼看看哈希表有多快

同样是"查 10 万个数里有没有某个数"，对比列表（O(n)）和集合（O(1)）：

import time

n = 100000
nums_list = list(range(n))     # 列表：按顺序存
nums_set  = set(range(n))      # 集合：哈希表存
target = n - 1                 # 查最后一个（对列表是最坏情况）

start = time.time()
for _ in range(10000):
    target in nums_list        # 每次都要从头扫到底
print("列表查找 1 万次:", round(time.time() - start, 3), "秒")

start = time.time()
for _ in range(10000):
    target in nums_set         # 每次 O(1)
print("集合查找 1 万次:", round(time.time() - start, 3), "秒")

你大概率会看到：集合比列表快几百上千倍。 这就是哈希表"查找 O(1)"的威力。

实验 2：用字典做"电话本"

phone = {}
while True:
    name = input("输入名字（输入 q 退出）：")
    if name == "q":
        break
    if name in phone:
        print(f"{name} 的电话是 {phone[name]}")
    else:
        num = input(f"没有 {name} 的记录，输入电话存起来：")
        phone[name] = num
        print("已保存")

实验 3：统计一篇文章的词频 Top 3

from collections import Counter

text = "the cat and the dog and the bird"
words = text.split()
c = Counter(words)
print(c.most_common(3))     # [('the', 3), ('and', 2), ('cat', 1)]

most_common() 内部就是"计数 + 排序"，是数据处理的日常操作。

十、小结

  1. 哈希表 = 数组 + 哈希函数，靠"键算下标"把查找/插入/删除都做到平均 O(1)。
  2. 碰撞躲不掉，但要处理好——链地址法"一格挂一串"，开放定址法"没位往后挪"；负载因子一高就扩容（rehash），这是"摊还 O(1)"的真相。
  3. Python 的 dict 和 set 就是现成的哈希表，遇到"查找、去重、计数"先想到它们，能把 O(n) 砍成 O(1)。

先别急着往后翻，把「两数之和」和「列表 vs 集合测速」敲熟，哈希表的"手感"就长在你脑子里了。

标签: none

添加新评论