数据结构：哈希表

发表于 | 更新于 | 分类于 | 阅读 次
以 CPython 为准介绍哈希表：dict 紧凑插入序、可哈希约束、set / defaultdict / Counter；冲突、装载因子与不可当键的类型。

Python 的「按键查找」默认就是 dict：一张 哈希表（hash table）。3.7 起插入序是语言规范，不只是 CPython 实现细节。set 是没有值的同一套散列；不是有序集合。

段末注释：哈希表用哈希函数把键拍到槽位，期望读写 (O(1))。CPython 3.6+ 把「槽位下标」和「按插入排列的条目」拆开，所以能保序且更省内存。

图 1　先算柜号（散列），再沿插入顺序排队（紧凑表）

1. 一句话定位

维度 内容
ADT 按键增删改查；3.7+ 遍历按插入序
实现 稀疏索引层 + 稠密条目层（紧凑表）
装载 可用分数约 (2/3)，超了扩容（容量取 2 的幂）
该用 计数、分组、去重、当稀疏数组、当图的邻接表
不该用 需要按「键的大小」排序遍历（那是树 / bisect / sortedcontainers）

2. 底层：两层表

1
2
3
4
索引层（稀疏，长度 8, 16, 32, …）
  hash(key) → 探测到一个下标 i
条目层（稠密，按插入排列）
  entries[i] = (hash, key, value)

查找：算 hash(key)，在索引层开放寻址，落到条目。
迭代：只扫条目层，所以 插入序，且比老式「扫一整张稀疏表」省。

删除会在索引层留墓碑，条目层压缩发生在下次重建。不要依赖「删了之后容量立刻变小」。

字符串哈希使用随机种子（PYTHONHASHSEED）：同一进程内稳定，跨进程 / 下次启动 的 hash("a") 可以不同。不要把 hash() 结果写进文件当主键。

3. 什么能当键

键必须 可哈希（hashable）：实现 __hash__ 与 __eq__，且相等的对象哈希必须相等；生命周期内哈希值不能变。

能当键 不能当键
None、int、float（nan 慎用）、str、bytes list、dict、set
元素均可哈希的 tuple / frozenset 含 list 的 tuple
自定义类（默认按 id，或你自己实现且保证不变） 用可变字段参与 __hash__ 的对象 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Point:
    """不可变二维点，用作 dict 键。

    输入：构造 x, y 为可哈希数。
    输出：实例；hash/eq 按坐标，不按 id。
    处理：字段只在 __init__ 写入，之后不改。
    """

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)

改了已入表对象的字段，会把表搞丢（找不回、也删不掉）。这是哈希表最危险的用法。

4. 操作与复杂度

操作 代码 期望 最坏
读 / 写 / 删 d[k] / d[k]=v / del d[k] (O(1)) (O(n))（哈希塌缩）
判断在否 k in d (O(1)) (O(n))
遍历 for k, v in d.items() (O(n)) 按插入序
setdefault d.setdefault(k, []) (O(1)) 键不存在才写入默认值
get d.get(k, default) (O(1)) 不写回

最坏 (O(n)) 在正常 int/str 键上几乎碰不到；自定义 __hash__ 恒返回常数会故意退化。

5. set 与 collections 三件套

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import defaultdict, Counter, ChainMap

def group_by(rows, keyfn):
    """按键分组。

    输入：rows 可迭代，keyfn(row) → 可哈希键。
    输出：dict[键, list]。
    处理：defaultdict(list) 省掉 if key not in。
    """
    g = defaultdict(list)
    for row in rows:
        g[keyfn(row)].append(row)
    return g


def top_k(words, k):
    """词频前 k。

    输入：words 字符串序列，k 正整数。
    输出：[(词, 次数), …] 按次数降序。
    处理：Counter 计数，most_common(k) 内部用堆。
    """
    return Counter(words).most_common(k)
类型 角色
set / frozenset 去重、成员测试、集合运算 | & - ^
defaultdict 缺键时自动工厂（list/int/set）
Counter 多重集合；most_common、加减
ChainMap 叠多层 dict 查找（局部覆盖全局），不拷贝

set 不保证顺序（实现细节随版本，不要当有序用）。要「有序去重」：list(dict.fromkeys(xs))。

6. 常见模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 1) 两数之和：值 → 下标
def two_sum(nums, target):
    """返回两个下标使之和为 target。

    输入：nums 整数列表，target 整数。
    输出：(i, j) 或 None。
    处理：一边扫一边把「还差多少」放进 dict。
    """
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None


# 2) 计数后过滤
# 3) 图的邻接表：g[u].append(v)  （见「图」专篇）
# 4) 稀疏矩阵：{(i, j): value}

7. 踩坑

  1. 遍历时增删键：RuntimeError: dictionary changed size。先 list(d) 再改，或建新 dict。
  2. 用 list 当键：改成 tuple。
  3. d.get(k, expensive())：默认值会先算出来。该用 setdefault 或 if k not in。
  4. Counter 当普通 dict 用完忘了它会为缺键返回 0，if c[k]: 与 if k in c: 不是一回事（后者对 0 计数也是 True）。
  5. 浮点当键：-0.0 与 0.0 哈希相同；nan 不等于自己，当键会疯。
  6. 并发写同一 dict：CPython 靠 GIL 碰巧不崩也不等于安全。跨线程加锁或别共享。

8. 自检

  1. 为什么 3.7+ 可以依赖 dict 插入序，却仍不能假设 set 有序？
  2. 画紧凑表的两层：索引层做什么，条目层做什么。
  3. 哪些内置类型不能当键？自定义类怎样才能当键？
  4. setdefault、defaultdict、Counter 各解决哪一句啰嗦代码？

9. 社区口径与风险

口径：PEP 468 / 3.7 语言规范 + CPython Objects/dictobject.c（USABLE_FRACTION ≈ 2/3）。布隆过滤器标准库没有，社区有 pybloom-live 等；风险是假阳性必须业务可接受，且实现质量参差。需要「按键排序的映射」不要硬用 dict + sorted 充日常结构，见树与堆专篇的 bisect / sortedcontainers。

-------------本文结束感谢您的阅读-------------