第15章 哈希表理论
学习目标
- 掌握哈希表的形式化定义与数学基础
- 理解哈希函数的设计原理与性质
- 深入分析冲突解决策略的理论基础
- 掌握通用哈希与完美哈希理论
- 理解Python字典的CPython实现机制
15.1 哈希表的形式化定义
15.1.1 基本概念
定义 15.1（哈希函数） 设 $U$ 为全键域，$M = {0, 1, \ldots, m-1}$ 为地址空间。哈希函数 $h: U \rightarrow M$ 将任意键映射到有限地址空间。
定义 15.2（哈希表） 哈希表是一个三元组 $HT = (h, T, \sigma)$，其中：
- $h: U \rightarrow M$ 是哈希函数
- $T = (T_0, T_1, \ldots, T_{m-1})$ 是桶数组
- $\sigma: M \rightarrow \text{Strategy}$ 是冲突解决策略
定义 15.3（冲突） 对于键 $k_1, k_2 \in U$，若 $k_1 \neq k_2$ 且 $h(k_1) = h(k_2)$，则称 $k_1$ 与 $k_2$ 发生冲突。
15.1.2 哈希函数的性质
定义 15.4（理想哈希函数） 哈希函数 $h$ 称为理想的，当且仅当：
$$P(h(k) = i) = \frac{1}{m}, \quad \forall k \in U, \forall i \in M$$
定义 15.5（简单均匀哈希假设） 简单均匀哈希假设（SUHA）断言：每个键等概率地独立映射到任意桶。
定理 15.1（冲突概率下界） 在SUHA下，向容量为 $m$ 的哈希表插入 $n$ 个键后，至少发生一次冲突的概率为：
$$P(\text{collision}) = 1 - \frac{m!}{m^n \cdot (m-n)!} \geq 1 - e^{-n(n-1)/(2m)}$$
证明：计算不发生冲突的概率。第一个键可放入任意桶，概率为 $1$。第二个键需放入剩余 $m-1$ 个桶，概率为 $(m-1)/m$。依此类推：
$$P(\text{no collision}) = \prod_{i=0}^{n-1} \frac{m-i}{m} = \frac{m!}{m^n(m-n)!}$$
利用不等式 $1-x \leq e^{-x}$：
$$P(\text{no collision}) = \prod_{i=0}^{n-1} \left(1 - \frac{i}{m}\right) \leq \prod_{i=0}^{n-1} e^{-i/m} = e^{-\sum_{i=0}^{n-1} i/m} = e^{-n(n-1)/(2m)}$$
因此 $P(\text{collision}) = 1 - P(\text{no collision}) \geq 1 - e^{-n(n-1)/(2m)}$。 ∎
推论 15.1（生日悖论） 当 $n \approx \sqrt{2m \ln 2} \approx 1.177\sqrt{m}$ 时，冲突概率超过 $50%$。对于 $m = 365$，$n \approx 23$。
15.2 哈希函数设计理论
15.2.1 哈希函数的评估准则
定义 15.6（雪崩效应） 哈希函数 $h$ 满足雪崩效应，若输入的微小变化导致输出的显著变化：
$$\forall k, k': \text{Ham}(k, k') = 1 \Rightarrow E[\text{Ham}(h(k), h(k'))] \approx \frac{m}{2}$$
其中 $\text{Ham}$ 表示汉明距离。
定义 15.7（扩散性） 哈希函数 $h$ 具有良好扩散性，若：
$$\forall i \in M: |h^{-1}(i)| \approx \frac{|U|}{m}$$
15.2.2 除法哈希法
定义 15.8（除法哈希） 除法哈希函数定义为：
$$h(k) = k \mod m$$
定理 15.2 当 $m$ 为质数且远离 $2^p$ 的幂时，除法哈希具有较好的分布特性。
证明：设 $m = 2^p$，则 $h(k)$ 仅取决于 $k$ 的低 $p$ 位。若键具有周期性模式，将导致聚集。选择质数可避免此问题。 ∎
15.2.3 乘法哈希法
定义 15.9（乘法哈希） 乘法哈希函数定义为：
$$h(k) = \lfloor m \cdot (k \cdot A \mod 1) \rfloor$$
其中 $A \in (0, 1)$ 为常数，Knuth建议 $A = (\sqrt{5}-1)/2 \approx 0.6180339887$。
定理 15.3（黄金分割最优性） 当 $A = \phi^{-1} = (\sqrt{5}-1)/2$ 时，乘法哈希对连续键序列具有最优扩散性。
证明：黄金分割比 $\phi = (1+\sqrt{5})/2$ 满足 $\phi^2 = \phi + 1$。对于连续键 $k, k+1, \ldots$，哈希值序列形成低差异序列，最大化空间填充效率。 ∎
15.2.4 多项式滚动哈希
定义 15.10（多项式哈希） 对于字符串 $s = s_0 s_1 \ldots s_{n-1}$：
$$h(s) = \sum_{i=0}^{n-1} s_i \cdot p^{n-1-i} \mod m$$
其中 $p$ 为基数（通常取质数如 $31, 37, 53$）。
def polynomial_hash(s: str, base: int = 31, mod: int = 2**61 - 1) -> int:
h = 0
for c in s:
h = (h * base + ord(c)) % mod
return h15.3 冲突解决策略理论
15.3.1 链地址法
定义 15.11（链地址法） 每个桶存储一个链表（或其他容器），所有哈希到同一桶的元素存入该链表。
定理 15.4（链地址法期望复杂度） 在SUHA下，负载因子为 $\alpha = n/m$ 时：
- 成功查找期望比较次数：$1 + \alpha/2$
- 失败查找期望比较次数：$\alpha$
- 插入期望比较次数：$\alpha$
证明：设 $n_j$ 为桶 $j$ 的元素数。成功查找键 $k$ 时，需遍历桶 $h(k)$ 中的元素。期望比较次数为：
$$E[C_{\text{success}}] = \frac{1}{n}\sum_{k \in HT} \text{position}(k) = \frac{1}{n}\sum_{j=0}^{m-1} \frac{n_j(n_j+1)}{2}$$
由SUHA，$E[n_j] = \alpha$，故：
$$E[C_{\text{success}}] = 1 + \frac{\alpha}{2}$$
失败查找需遍历整个桶，期望长度为 $\alpha$。 ∎
定义 15.12（负载因子） 负载因子定义为：
$$\alpha = \frac{n}{m}$$
其中 $n$ 为元素数，$m$ 为桶数。
15.3.2 开放寻址法
定义 15.13（开放寻址法） 所有元素直接存储在桶数组中。冲突时按探查序列寻找空桶。
定义 15.14（探查序列） 探查序列是函数 $p: U \times {0, 1, \ldots, m-1} \rightarrow M$，满足：
- $p(k, 0), p(k, 1), \ldots, p(k, m-1)$ 是 $0, 1, \ldots, m-1$ 的排列
- $p(k, i)$ 表示键 $k$ 的第 $i$ 次探查位置
线性探查：
$$p(k, i) = (h(k) + i) \mod m$$
二次探查：
$$p(k, i) = (h(k) + c_1 i + c_2 i^2) \mod m$$
双重哈希：
$$p(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m$$
定理 15.5（线性探查聚集效应） 线性探查导致主聚集，连续被占桶形成"块"，期望块长度随负载因子指数增长。
证明：设 $q_i$ 为从位置 $i$ 开始的连续被占桶数。当插入新元素时，若哈希到块内任意位置，都将延长该块。块的"吸引力"与其长度成正比，形成正反馈。 ∎
定理 15.6（开放寻址期望探查次数） 在均匀哈希假设下，负载因子 $\alpha = n/m < 1$ 时：
- 失败查找期望探查次数：$\frac{1}{1-\alpha}$
- 成功查找期望探查次数：$\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$
证明：失败查找时，每次探查成功的概率为 $(1-\alpha)$。期望探查次数服从几何分布：
$$E[\text{probes}] = \sum_{i=1}^{\infty} i \cdot \alpha^{i-1}(1-\alpha) = \frac{1}{1-\alpha}$$
成功查找时，需考虑元素插入时的表状态。设元素在第 $j$ 次插入，当时负载因子为 $j/m$：
$$E[\text{probes}] = \frac{1}{n}\sum_{j=0}^{n-1} \frac{1}{1-j/m} \approx \frac{1}{\alpha}\ln\frac{1}{1-\alpha}$$
∎
15.4 通用哈希理论
15.4.1 通用哈希函数族
定义 15.15（通用哈希函数族） 哈希函数族 $\mathcal{H} \subseteq {h: U \rightarrow M}$ 称为通用的，若：
$$\forall k_1 \neq k_2 \in U: |{h \in \mathcal{H}: h(k_1) = h(k_2)}| \leq \frac{|\mathcal{H}|}{m}$$
定理 15.7（通用哈希冲突概率） 从通用哈希函数族中随机选取 $h$，对于任意 $k_1 \neq k_2$：
$$P(h(k_1) = h(k_2)) \leq \frac{1}{m}$$
证明：由定义15.15：
$$P(h(k_1) = h(k_2)) = \frac{|{h \in \mathcal{H}: h(k_1) = h(k_2)}|}{|\mathcal{H}|} \leq \frac{1}{m}$$
∎
15.4.2 构造通用哈希函数族
定理 15.8（Carter-Wegman构造） 设 $p$ 为质数，$p \geq |U|$。定义：
$$\mathcal{H} = {h_{a,b}: h_{a,b}(k) = ((ak + b) \mod p) \mod m, ; a \in {1, \ldots, p-1}, b \in {0, \ldots, p-1}}$$
则 $\mathcal{H}$ 是通用哈希函数族。
证明：对于 $k_1 \neq k_2$，设 $r = (ak_1 + b) \mod p$，$s = (ak_2 + b) \mod p$。
由于 $a \neq 0$ 且 $k_1 \neq k_2$，有 $r \neq s$。
对于固定的 $k_1, k_2$，当 $a, b$ 均匀选取时，$(r, s)$ 在 ${(x, y) \in \mathbb{Z}_p^2 : x \neq y}$ 上均匀分布。
冲突条件为 $r \equiv s \pmod{m}$，即 $r - s \equiv 0 \pmod{m}$。
满足此条件的 $(r, s)$ 对数为 $p(p-1)/m$，故冲突概率为：
$$\frac{p(p-1)/m}{p(p-1)} = \frac{1}{m}$$
∎
import random
from typing import Callable, TypeVar
K = TypeVar('K')
class UniversalHash:
def __init__(self, m: int, p: int = 2**61 - 1):
self.m = m
self.p = p
self.a = random.randint(1, p - 1)
self.b = random.randint(0, p - 1)
def __call__(self, k: K) -> int:
return ((self.a * hash(k) + self.b) % self.p) % self.m
@staticmethod
def create_family(m: int, p: int = 2**61 - 1) -> Callable[[], 'UniversalHash']:
return lambda: UniversalHash(m, p)15.4.3 强通用哈希
定义 15.16（强通用哈希函数族） 哈希函数族 $\mathcal{H}$ 称为强通用（2-通用）的，若：
$$\forall k_1 \neq k_2, \forall i, j \in M: P(h(k_1) = i \land h(k_2) = j) = \frac{1}{m^2}$$
定理 15.9 强通用哈希函数族满足成对独立性：任意两个不同键的哈希值独立。
15.5 完美哈希
15.5.1 静态完美哈希
定义 15.17（完美哈希函数） 哈希函数 $h: S \rightarrow M$ 称为完美的，若 $|S| = |M|$ 且 $h$ 在 $S$ 上无冲突。
定理 15.10（Fredman-Komlós-Szemerédi定理） 对于任意 $n$ 元键集 $S$，存在 $O(n)$ 空间、$O(1)$ 最坏情况查询时间的完美哈希方案，构造时间为 $O(n)$ 期望。
FKS方案：
- 第一层：使用通用哈希 $h_1: S \rightarrow {0, \ldots, m_1-1}$，$m_1 = O(n)$
- 第二层：对每个桶 $i$，若桶大小为 $n_i$，使用完美哈希 $h_{2,i}$ 映射到 $m_{2,i} = O(n_i^2)$ 空间
定理 15.11（FKS空间复杂度） FKS方案期望空间为 $O(n)$。
证明：第二层总空间为：
$$E\left[\sum_{i=0}^{m_1-1} m_{2,i}\right] = E\left[\sum_{i=0}^{m_1-1} c \cdot n_i^2\right] = c \cdot E\left[\sum_{i=0}^{m_1-1} n_i^2\right]$$
由通用哈希性质：
$$E\left[\sum_{i=0}^{m_1-1} n_i^2\right] = n + \sum_{k_1 \neq k_2} P(h_1(k_1) = h_1(k_2)) \leq n + \binom{n}{2} \cdot \frac{1}{m_1} = O(n)$$
当 $m_1 = n$ 时，期望空间为 $O(n)$。 ∎
15.5.2 最小完美哈希
定义 15.18（最小完美哈希） 完美哈希函数 $h: S \rightarrow {0, 1, \ldots, n-1}$ 称为最小的，若值域恰好为 $n$。
from typing import List, Dict, Optional
import random
class MinimalPerfectHash:
def __init__(self, keys: List[str]):
self.n = len(keys)
self._build(keys)
def _build(self, keys: List[str]) -> None:
m1 = max(self.n, 1)
while True:
self.h1 = self._pick_hash(m1)
buckets: Dict[int, List[str]] = {}
for k in keys:
b = self.h1(k)
if b not in buckets:
buckets[b] = []
buckets[b].append(k)
self.h2 = {}
self.g = {}
used = set()
success = True
for b in sorted(buckets.keys(), key=lambda x: -len(buckets[x])):
bucket_keys = buckets[b]
m2 = len(bucket_keys) ** 2
found = False
for _ in range(100):
h2_func = self._pick_hash(m2)
slots = [h2_func(k) for k in bucket_keys]
if all((b * m2 + s) % self.n not in used for s in slots):
self.h2[b] = h2_func
for k, s in zip(bucket_keys, slots):
self.g[k] = (b, s)
used.add((b * m2 + s) % self.n)
found = True
break
if not found:
success = False
break
if success:
break
def _pick_hash(self, m: int) -> callable:
a = random.randint(1, 2**31 - 1)
b = random.randint(0, 2**31 - 1)
return lambda k: ((a * hash(k) + b) % (2**31 - 1)) % m
def __call__(self, key: str) -> int:
b, s = self.g.get(key, (0, 0))
h2_func = self.h2.get(b, lambda k: 0)
return (b * len(self.h2.get(b, [key]))**2 + h2_func(key)) % self.n15.6 Cuckoo哈希
15.6.1 基本原理
定义 15.19（Cuckoo哈希） 使用两个哈希函数 $h_1, h_2$，每个键可存储在 $h_1(k)$ 或 $h_2(k)$ 两个位置之一。查询最多检查两个位置。
定理 15.12（Cuckoo哈希查询复杂度） Cuckoo哈希的最坏情况查询时间为 $O(1)$，仅需两次探查。
定义 15.20（Cuckoo图） 对于键集 $S$，Cuckoo图 $G = (V, E)$ 定义为：
- $V = {0, 1, \ldots, 2m-1}$（两个表的桶）
- $E = {(h_1(k), h_2(k)) : k \in S}$
定理 15.13（Cuckoo哈希可行性） 当且仅当Cuckoo图无环时，存在有效放置方案。
证明：若Cuckoo图有环，则环上的键无法同时满足各自的位置约束。若Cuckoo图无环（森林），可通过拓扑排序确定放置顺序。 ∎
15.6.2 插入操作
from typing import Generic, TypeVar, Optional, List, Tuple
import random
K = TypeVar('K')
V = TypeVar('V')
class CuckooHashMap(Generic[K, V]):
def __init__(self, capacity: int = 16, max_displacements: int = 500):
self._capacity = capacity
self._size = 0
self._table1: List[Optional[Tuple[K, V]]] = [None] * capacity
self._table2: List[Optional[Tuple[K, V]]] = [None] * capacity
self._max_displacements = max_displacements
self._seed1 = random.randint(1, 2**31 - 1)
self._seed2 = random.randint(1, 2**31 - 1)
def _h1(self, key: K) -> int:
return hash((key, self._seed1)) % self._capacity
def _h2(self, key: K) -> int:
return hash((key, self._seed2)) % self._capacity
def get(self, key: K) -> Optional[V]:
i1 = self._h1(key)
if self._table1[i1] and self._table1[i1][0] == key:
return self._table1[i1][1]
i2 = self._h2(key)
if self._table2[i2] and self._table2[i2][0] == key:
return self._table2[i2][1]
return None
def put(self, key: K, value: V) -> bool:
if self.get(key) is not None:
i1 = self._h1(key)
if self._table1[i1] and self._table1[i1][0] == key:
self._table1[i1] = (key, value)
else:
i2 = self._h2(key)
self._table2[i2] = (key, value)
return True
return self._insert((key, value), 0)
def _insert(self, pair: Tuple[K, V], table: int) -> bool:
for _ in range(self._max_displacements):
if table == 0:
idx = self._h1(pair[0])
else:
idx = self._h2(pair[0])
if table == 0:
if self._table1[idx] is None:
self._table1[idx] = pair
self._size += 1
return True
evicted = self._table1[idx]
self._table1[idx] = pair
else:
if self._table2[idx] is None:
self._table2[idx] = pair
self._size += 1
return True
evicted = self._table2[idx]
self._table2[idx] = pair
pair = evicted
table = 1 - table
self._rehash()
return self._insert(pair, 0)
def _rehash(self) -> None:
old_table1 = self._table1
old_table2 = self._table2
self._capacity *= 2
self._table1 = [None] * self._capacity
self._table2 = [None] * self._capacity
self._seed1 = random.randint(1, 2**31 - 1)
self._seed2 = random.randint(1, 2**31 - 1)
self._size = 0
for pair in old_table1:
if pair:
self.put(pair[0], pair[1])
for pair in old_table2:
if pair:
self.put(pair[0], pair[1])
def remove(self, key: K) -> bool:
i1 = self._h1(key)
if self._table1[i1] and self._table1[i1][0] == key:
self._table1[i1] = None
self._size -= 1
return True
i2 = self._h2(key)
if self._table2[i2] and self._table2[i2][0] == key:
self._table2[i2] = None
self._size -= 1
return True
return False15.7 哈希表ADT规范
15.7.1 代数规范
ADT HashMap[K, V]
imports Boolean, Integer, K, V, List[Pair[K, V]]
sorts HashMap
operations
empty : → HashMap
put : HashMap × K × V → HashMap
get : HashMap × K → V ∪ {None}
remove : HashMap × K → HashMap
contains : HashMap × K → Boolean
size : HashMap → Integer
keys : HashMap → Set[K]
values : HashMap → List[V]
axioms
∀ m: HashMap, k, k': K, v, v': V
[G1] get(empty, k) = None
[G2] get(put(m, k, v), k) = v
[G3] k ≠ k' ⇒ get(put(m, k, v), k') = get(m, k')
[G4] put(put(m, k, v), k, v') = put(m, k, v')
[R1] remove(empty, k) = empty
[R2] remove(put(m, k, v), k) = remove(m, k)
[R3] k ≠ k' ⇒ remove(put(m, k, v), k') = put(remove(m, k'), k, v)
[C1] contains(empty, k) = false
[C2] contains(put(m, k, v), k) = true
[C3] k ≠ k' ⇒ contains(put(m, k, v), k') = contains(m, k')
[S1] size(empty) = 0
[S2] contains(m, k) ⇒ size(put(m, k, v)) = size(m)
[S3] ¬contains(m, k) ⇒ size(put(m, k, v)) = size(m) + 1
end ADT15.8 完整哈希表实现
15.8.1 基于链地址法的哈希表
from typing import TypeVar, Generic, Optional, List, Tuple, Iterator, Set
from collections import defaultdict
import math
K = TypeVar('K')
V = TypeVar('V')
class HashMap(Generic[K, V]):
def __init__(self, capacity: int = 16, load_factor: float = 0.75):
self._capacity = self._next_power_of_two(capacity)
self._size = 0
self._buckets: List[List[Tuple[K, V]]] = [[] for _ in range(self._capacity)]
self._load_factor = load_factor
self._mod_count = 0
@staticmethod
def _next_power_of_two(n: int) -> int:
if n <= 0:
return 1
return 1 << (n - 1).bit_length()
def _hash(self, key: K) -> int:
h = hash(key)
h ^= (h >> 16)
return h & (self._capacity - 1)
def _resize(self) -> None:
old_buckets = self._buckets
self._capacity *= 2
self._buckets = [[] for _ in range(self._capacity)]
self._size = 0
for bucket in old_buckets:
for key, value in bucket:
self._put_internal(key, value)
self._mod_count += 1
def _put_internal(self, key: K, value: V) -> bool:
index = self._hash(key)
bucket = self._buckets[index]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return False
bucket.append((key, value))
self._size += 1
return True
def put(self, key: K, value: V) -> Optional[V]:
if self._size >= self._capacity * self._load_factor:
self._resize()
index = self._hash(key)
bucket = self._buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
old_value = v
bucket[i] = (key, value)
return old_value
bucket.append((key, value))
self._size += 1
self._mod_count += 1
return None
def get(self, key: K, default: Optional[V] = None) -> Optional[V]:
index = self._hash(key)
bucket = self._buckets[index]
for k, v in bucket:
if k == key:
return v
return default
def remove(self, key: K) -> Optional[V]:
index = self._hash(key)
bucket = self._buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
self._size -= 1
self._mod_count += 1
return v
return None
def contains(self, key: K) -> bool:
return self.get(key) is not None
def __getitem__(self, key: K) -> V:
result = self.get(key)
if result is None:
raise KeyError(key)
return result
def __setitem__(self, key: K, value: V) -> None:
self.put(key, value)
def __delitem__(self, key: K) -> None:
if self.remove(key) is None:
raise KeyError(key)
def __contains__(self, key: K) -> bool:
return self.contains(key)
def __len__(self) -> int:
return self._size
def __iter__(self) -> Iterator[K]:
for bucket in self._buckets:
for key, _ in bucket:
yield key
def items(self) -> Iterator[Tuple[K, V]]:
for bucket in self._buckets:
for pair in bucket:
yield pair
def keys(self) -> Set[K]:
return set(self)
def values(self) -> List[V]:
return [v for _, v in self.items()]
def clear(self) -> None:
self._buckets = [[] for _ in range(self._capacity)]
self._size = 0
self._mod_count += 1
@property
def load_factor(self) -> float:
return self._size / self._capacity
def statistics(self) -> dict:
lengths = [len(b) for b in self._buckets]
non_empty = [l for l in lengths if l > 0]
return {
'capacity': self._capacity,
'size': self._size,
'load_factor': self.load_factor,
'empty_buckets': lengths.count(0),
'max_chain_length': max(lengths) if lengths else 0,
'avg_chain_length': sum(non_empty) / len(non_empty) if non_empty else 0,
}15.8.2 基于开放寻址法的哈希表
from typing import TypeVar, Generic, Optional, List, Tuple, Iterator
from enum import Enum, auto
K = TypeVar('K')
V = TypeVar('V')
class EntryState(Enum):
EMPTY = auto()
OCCUPIED = auto()
DELETED = auto()
class OpenAddressingHashMap(Generic[K, V]):
def __init__(self, capacity: int = 16, load_factor: float = 0.5):
self._capacity = self._next_power_of_two(capacity)
self._size = 0
self._deleted = 0
self._entries: List[Tuple[Optional[K], Optional[V], EntryState]] = [
(None, None, EntryState.EMPTY) for _ in range(self._capacity)
]
self._load_factor = load_factor
@staticmethod
def _next_power_of_two(n: int) -> int:
if n <= 0:
return 1
return 1 << (n - 1).bit_length()
def _hash(self, key: K) -> int:
h = hash(key)
h ^= (h >> 16)
return h & (self._capacity - 1)
def _probe(self, key: K, i: int) -> int:
return (self._hash(key) + i) & (self._capacity - 1)
def _find_slot(self, key: K) -> Tuple[int, bool]:
first_deleted = -1
for i in range(self._capacity):
index = self._probe(key, i)
entry = self._entries[index]
if entry[2] == EntryState.EMPTY:
if first_deleted >= 0:
return first_deleted, False
return index, False
if entry[2] == EntryState.DELETED:
if first_deleted < 0:
first_deleted = index
elif entry[0] == key:
return index, True
if first_deleted >= 0:
return first_deleted, False
raise RuntimeError("Hash table is full")
def _resize(self) -> None:
old_entries = self._entries
self._capacity *= 2
self._entries = [(None, None, EntryState.EMPTY) for _ in range(self._capacity)]
self._size = 0
self._deleted = 0
for key, value, state in old_entries:
if state == EntryState.OCCUPIED:
self.put(key, value)
def put(self, key: K, value: V) -> Optional[V]:
if (self._size + self._deleted) >= self._capacity * self._load_factor:
self._resize()
index, found = self._find_slot(key)
if found:
old_value = self._entries[index][1]
self._entries[index] = (key, value, EntryState.OCCUPIED)
return old_value
if self._entries[index][2] == EntryState.DELETED:
self._deleted -= 1
self._entries[index] = (key, value, EntryState.OCCUPIED)
self._size += 1
return None
def get(self, key: K, default: Optional[V] = None) -> Optional[V]:
for i in range(self._capacity):
index = self._probe(key, i)
entry = self._entries[index]
if entry[2] == EntryState.EMPTY:
return default
if entry[2] == EntryState.OCCUPIED and entry[0] == key:
return entry[1]
return default
def remove(self, key: K) -> Optional[V]:
for i in range(self._capacity):
index = self._probe(key, i)
entry = self._entries[index]
if entry[2] == EntryState.EMPTY:
return None
if entry[2] == EntryState.OCCUPIED and entry[0] == key:
value = entry[1]
self._entries[index] = (None, None, EntryState.DELETED)
self._size -= 1
self._deleted += 1
return value
return None
def __len__(self) -> int:
return self._size
def __contains__(self, key: K) -> bool:
return self.get(key) is not None
def __getitem__(self, key: K) -> V:
result = self.get(key)
if result is None:
raise KeyError(key)
return result
def __setitem__(self, key: K, value: V) -> None:
self.put(key, value)15.9 Python字典内部实现
15.9.1 CPython字典结构
CPython使用开放寻址法与伪随机探查。字典条目结构：
typedef struct {
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictKeyEntry;探查序列：
$$p(i) = p(0) + i \cdot \text{perturb} \mod 2^k$$
其中 $\text{perturb}$ 初始为哈希值，每次迭代右移5位：
def cpython_probe(hash_value: int, capacity: int) -> Iterator[int]:
mask = capacity - 1
perturb = hash_value
i = hash_value & mask
while True:
yield i
i = (i * 5 + perturb + 1) & mask
perturb >>= 515.9.2 字典扩容策略
定理 15.14（CPython字典扩容） CPython字典在以下情况扩容：
- 插入新键时，若使用率超过 $2/3$
- 删除大量键后，若使用率低于 $1/6$
扩容时容量增长约2倍，选择最近的 $2^n$。
15.10 复杂度分析总结
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 插入 | $O(1)$ | $O(n)$ |
| 查找 | $O(1)$ | $O(n)$ |
| 删除 | $O(1)$ | $O(n)$ |
| 遍历 | $O(n)$ | $O(n)$ |
定理 15.15（哈希表摊还复杂度） 在SUHA下，哈希表操作的摊还时间复杂度为 $O(1)$。
证明：使用势能法。设势能函数 $\Phi = 2n - m$（$n$ 元素数，$m$ 桶数）。
- 插入：若不扩容，实际代价 $O(1)$，势能增加 $2$，摊还代价 $O(1)$
- 扩容：实际代价 $O(n)$，但势能从正变负，摊还代价 $O(1)$
因此所有操作摊还代价 $O(1)$。 ∎
15.11 本章小结
本章系统介绍了哈希表理论：
- 形式化基础：哈希函数、冲突概率的数学分析
- 哈希函数设计：除法哈希、乘法哈希、多项式哈希
- 冲突解决策略：链地址法、开放寻址法的理论分析
- 高级技术：通用哈希、完美哈希、Cuckoo哈希
- 实现技术：ADT规范、完整实现、CPython内部机制
参考文献
- Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
- Cormen, T. H., et al. (2009). Introduction to Algorithms, 3rd ed. MIT Press.
- Carter, J. L., & Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences, 18(2), 143-154.
- Fredman, M. L., Komlós, J., & Szemerédi, E. (1984). Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(3), 538-544.
- Pagh, R., & Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2), 122-144.
下一章：第16章 图基础