第4章 字典与哈希表理论

本章导读

字典是Python中实现键值映射的核心数据结构，其底层实现为哈希表。本章从算法理论角度深入分析哈希表的数学基础，包括哈希函数设计、冲突解决策略、负载因子分析、扩容策略的形式化证明，以及CPython紧凑字典的实现细节。

学习目标

完成本章学习后，读者将能够：

• 掌握哈希表的数学定义与ADT规范
• 理解哈希函数的设计原则与均匀性分析
• 分析开放寻址法的期望探测次数
• 掌握负载因子与性能的理论关系
• 理解CPython紧凑字典的实现原理

---

4.1 哈希表的形式化理论

4.1.1 映射ADT规范

定义 4.1（映射） 映射（Map）是从键集合 $K$ 到值集合 $V$ 的函数关系，每个键最多关联一个值。

ADT 4.1（Map）

ADT Map[K, V]
  Types: Map[K, V]
  
  Operations:
    empty: → Map[K, V]
    size: Map[K, V] → ℕ
    get: Map[K, V] × K → V ∪ {error}
    put: Map[K, V] × K × V → Map[K, V]
    remove: Map[K, V] × K → Map[K, V]
    contains: Map[K, V] × K → Boolean
    keys: Map[K, V] → Set[K]
    values: Map[K, V] → MultiSet[V]
  
  Axioms:
    ∀m: Map[K, V], ∀k: K, ∀v: V
    (A1) size(empty) = 0
    (A2) get(empty, k) = error
    (A3) get(put(m, k, v), k) = v
    (A4) k' ≠ k → get(put(m, k, v), k') = get(m, k')
    (A5) contains(empty, k) = false
    (A6) contains(put(m, k, v), k) = true
    (A7) k' ≠ k → contains(put(m, k, v), k') = contains(m, k')
    (A8) size(put(m, k, v)) = size(m) + 1  (当 ¬contains(m, k))
    (A9) size(put(m, k, v)) = size(m)       (当 contains(m, k))
    (A10) remove(empty, k) = empty
    (A11) remove(put(m, k, v), k) = m
    (A12) k' ≠ k → remove(put(m, k, v), k') = put(remove(m, k'), k, v)

定理 4.1（映射ADT一致性） 映射ADT的公理系统是一致的。

证明：构造函数模型。设映射为部分函数 $f: K \rightharpoonup V$。

• $empty = \emptyset$（空函数）
• $get(f, k) = f(k)$ 若 $k \in dom(f)$，否则 $error$
• $put(f, k, v) = f \cup {(k, v)}$
• $remove(f, k) = f|_{K \setminus {k}}$
• $contains(f, k) = (k \in dom(f))$

可直接验证所有公理成立。∎

4.1.2 哈希表的数学模型

定义 4.2（哈希表） 哈希表是实现映射的数据结构，使用哈希函数 $h: K \to {0, 1, \ldots, m-1}$ 将键映射到数组索引。

定义 4.3（完美哈希） 哈希函数 $h$ 对于键集 $S \subseteq K$ 是完美的，当且仅当：

$$\forall k_1, k_2 \in S, k_1 \neq k_2 \Rightarrow h(k_1) \neq h(k_2)$$

定义 4.4（最小完美哈希） 完美哈希 $h$ 是最小的，当且仅当 $|range(h)| = |S|$。

定理 4.2（完美哈希存在性） 对于任意有限键集 $S$，存在完美哈希函数。

证明：设 $S = {k_1, \ldots, k_n}$。定义 $h(k_i) = i$。显然 $h$ 是完美的。∎

注：实际中，构造最小完美哈希是NP完全问题，通常使用启发式算法。

4.1.3 哈希函数的性质

定义 4.5（均匀哈希假设） 哈希函数 $h$ 满足均匀哈希假设，当且仅当对于任意键序列 $k_1, \ldots, k_n$，哈希值 $h(k_1), \ldots, h(k_n)$ 独立且均匀分布在 ${0, \ldots, m-1}$ 上。

定义 4.6（简单均匀哈希） 简单均匀哈希假设：每个键等概率地哈希到任意槽位，与其他键的哈希位置独立。

定理 4.3（通用哈希） 设 $\mathcal{H}$ 为哈希函数族。若对于任意不同的 $k_1, k_2 \in K$：

$$|{h \in \mathcal{H} : h(k_1) = h(k_2)}| \leq \frac{|\mathcal{H}|}{m}$$

则从 $\mathcal{H}$ 中随机选取的哈希函数满足：$P(h(k_1) = h(k_2)) \leq \frac{1}{m}$。

证明：由定义，满足 $h(k_1) = h(k_2)$ 的哈希函数数量不超过 $|\mathcal{H}|/m$。随机选取时：

$$P(h(k_1) = h(k_2)) = \frac{|{h : h(k_1) = h(k_2)}|}{|\mathcal{H}|} \leq \frac{1}{m}$$

∎

---

4.2 冲突解决理论

4.2.1 冲突的数学定义

定义 4.7（哈希冲突） 当 $k_1 \neq k_2$ 但 $h(k_1) = h(k_2)$ 时，发生哈希冲突。

定理 4.4（生日悖论） 在均匀哈希假设下，当 $n$ 个键哈希到 $m$ 个槽位时，至少发生一次冲突的概率为：

$$P_{collision} = 1 - \frac{m!}{m^n(m-n)!} \approx 1 - e^{-n^2/(2m)}$$

当 $n \approx \sqrt{2m \ln 2}$ 时，冲突概率约为 $50%$。

证明：无冲突的概率为：

$$P_{no_collision} = \frac{m}{m} \cdot \frac{m-1}{m} \cdot \frac{m-2}{m} \cdots \frac{m-n+1}{m} = \frac{m!}{m^n(m-n)!}$$

使用近似 $\frac{m-i}{m} \approx e^{-i/m}$：

$$P_{no_collision} \approx e^{-\sum_{i=0}^{n-1} i/m} = e^{-n(n-1)/(2m)} \approx e^{-n^2/(2m)}$$

因此 $P_{collision} = 1 - P_{no_collision}$。∎

推论 4.1 当 $m = 365$（生日问题），$n \approx 23$ 时冲突概率达 $50%$。

4.2.2 开放寻址法分析

定义 4.8（开放寻址） 开放寻址法将所有条目存储在哈希表本身，通过探测序列查找空槽。

探测序列定义为：$h(k, i)$，其中 $i = 0, 1, 2, \ldots$ 为探测次数。

定义 4.9（探测策略）

1. 线性探测：$h(k, i) = (h'(k) + i) \mod m$
2. 二次探测：$h(k, i) = (h'(k) + c_1 i + c_2 i^2) \mod m$
3. 双重哈希：$h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m$

定理 4.5（线性探测的期望探测次数） 在均匀哈希假设下，设负载因子 $\alpha = n/m < 1$，线性探测的成功查找期望探测次数为：

$$E[\text{probes}_{success}] \approx \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$$

不成功查找期望探测次数为：

$$E[\text{probes}_{failure}] \approx \frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$$

证明概要：分析连续被占用槽位的分布。设 $p_i$ 为第 $i$ 个槽被占用的概率。在稳态下，探测序列的期望长度满足递推关系，解得上述公式。∎

定理 4.6（双重哈希的期望探测次数） 双重哈希在均匀假设下的期望探测次数：

$$E[\text{probes}_{success}] \approx \frac{1}{\alpha}\ln\frac{1}{1-\alpha}$$

$$E[\text{probes}_{failure}] \approx \frac{1}{1-\alpha}$$

证明：双重哈希产生近似均匀的探测序列，分析为几何分布。设成功概率为 $1-\alpha$，期望探测次数为 $1/(1-\alpha)$。成功查找需平均已存储元素的探测次数一半。∎

4.2.3 负载因子分析

定义 4.10（负载因子） 负载因子 $\alpha = n/m$，其中 $n$ 为元素数，$m$ 为表大小。

定理 4.7（负载因子与性能） 哈希表操作期望时间 $T$ 与负载因子的关系：

负载因子 $\alpha$	不成功查找探测数	成功查找探测数
0.5	2.0	1.5
0.75	4.0	2.5
0.9	10.0	5.5

推论 4.2 为保持 $O(1)$ 期望时间，应保持 $\alpha \leq 0.75$。

---

4.3 CPython字典实现

4.3.1 紧凑字典结构

Python 3.7+采用紧凑字典（Compact Dict）设计：

CPython 紧凑字典结构
┌─────────────────────────────────────────────────────────────┐
│  PyDictObject                                                │
├─────────────────────────────────────────────────────────────┤
│  ma_used: Py_ssize_t          │ 已使用条目数                │
│  ma_version_tag: uint64_t     │ 版本号（迭代器有效性）      │
│  ma_keys: PyDictKeysObject*   │ 键表指针                    │
│  ma_values: PyObject**        │ 值数组指针（分离存储）      │
└─────────────────────────────────────────────────────────────┘
                    │
                    ▼
┌─────────────────────────────────────────────────────────────┐
│  PyDictKeysObject                                            │
├─────────────────────────────────────────────────────────────┤
│  dk_refcnt: Py_ssize_t        │ 引用计数                    │
│  dk_size: Py_ssize_t          │ 哈希表大小（2的幂）          │
│  dk_lookup: lookup_func       │ 查找函数指针                │
│  dk_usable: Py_ssize_t        │ 可用条目数                  │
│  dk_nentries: Py_ssize_t      │ 已填充条目数                │
│  dk_indices: int8_t[]         │ 哈希索引数组（变长）        │
│  dk_entries: PyDictKeyEntry[] │ 键值条目数组                │
└─────────────────────────────────────────────────────────────┘

查找流程:
key → hash(key) → idx = hash & (dk_size - 1)
    → dk_indices[idx] → entry_index → dk_entries[entry_index]
    → 比较 key == entry.key

4.3.2 探测序列实现

CPython使用改进的二次探测：

def cpython_probe(hash_value: int, table_size: int) -> Iterator[int]:
    """
    CPython探测序列生成器
    
    探测公式：perturb >>= 5, i = (i * 5 + perturb + 1) & mask
    """
    mask = table_size - 1
    i = hash_value & mask
    perturb = hash_value
    
    yield i
    
    while True:
        perturb >>= 5
        i = (i * 5 + perturb + 1) & mask
        yield i

定理 4.8（CPython探测的覆盖性） CPython探测序列保证访问表中所有槽位。

证明：探测公式 $i_{n+1} = 5i_n + perturb_n + 1 \mod m$，其中 $perturb_n = hash \gg (5n)$。

当 $m = 2^k$ 时，乘数 $5$ 与 $m$ 互质（$gcd(5, 2^k) = 1$），因此序列在完整周期内覆盖所有槽位。∎

4.3.3 扩容策略分析

定理 4.9（CPython扩容阈值） CPython字典在负载因子达到约 $2/3$ 时扩容。

证明：设 dk_usable 初始为 dk_size * 2 / 3。当 dk_nentries 达到 dk_size - dk_usable 时触发扩容。

新大小计算：new_size = (old_nentries * 2) rounded up to power of 2

这保证了扩容后负载因子约为 $1/3$。∎

4.3.4 性能基准测试

import sys
import timeit
from typing import Dict, Any

def analyze_dict_memory():
    """分析字典内存占用"""
    print("=== 字典内存占用 ===")
    for n in [0, 1, 5, 10, 100, 1000]:
        d = {i: i for i in range(n)}
        print(f"  {n}元素: {sys.getsizeof(d)}字节, 每元素{sys.getsizeof(d)/max(n,1):.1f}字节")

def benchmark_dict_operations():
    """字典操作性能基准测试"""
    n = 100000
    
    print("\n=== 操作性能 ===")
    
    insert_time = timeit.timeit(
        'd[i] = i',
        setup='d = {}; i = 0',
        number=n
    )
    print(f"  插入: {insert_time:.4f}秒 ({n}次)")
    
    d = {i: i for i in range(n)}
    
    lookup_time = timeit.timeit(
        'd[50000]',
        globals=globals(),
        number=n
    )
    print(f"  查找: {lookup_time:.4f}秒 ({n}次)")
    
    delete_time = timeit.timeit(
        'del d[i]; i += 1',
        setup=f'd = {{i: i for i in range({n})}}; i = 0',
        number=n
    )
    print(f"  删除: {delete_time:.4f}秒 ({n}次)")

def benchmark_collision_performance():
    """冲突对性能的影响"""
    print("\n=== 冲突影响分析 ===")
    
    class BadHash:
        def __init__(self, value):
            self.value = value
        def __hash__(self):
            return 1
        def __eq__(self, other):
            return isinstance(other, BadHash) and self.value == other.value
    
    n = 1000
    
    good_time = timeit.timeit(
        'd[i] = i; d.get(i)',
        setup='d = {}',
        number=n
    )
    
    bad_time = timeit.timeit(
        'd[BadHash(i)] = i; d.get(BadHash(i))',
        setup='from __main__ import BadHash; d = {}',
        number=n
    )
    
    print(f"  好哈希: {good_time:.4f}秒")
    print(f"  坏哈希(全冲突): {bad_time:.4f}秒")
    print(f"  性能下降: {bad_time/good_time:.0f}倍")

if __name__ == '__main__':
    analyze_dict_memory()
    benchmark_dict_operations()
    benchmark_collision_performance()

---

4.4 哈希函数设计

4.4.1 哈希函数设计原则

定义 4.11（好的哈希函数） 好的哈希函数应满足：

1. 确定性：相同输入产生相同输出
2. 均匀性：输出均匀分布在值域内
3. 高效性：计算时间为 $O(|key|)$
4. 雪崩效应：输入微小变化导致输出剧烈变化

定理 4.10（雪崩效应） 若哈希函数满足雪崩效应，则改变输入的 $1$ 位，输出平均改变 $50%$ 的位。

4.4.2 整数哈希

def integer_hash(x: int, m: int) -> int:
    """
    整数哈希函数
    
    使用乘法哈希：h(k) = floor(m * (k * A mod 1))
    其中 A = (√5 - 1) / 2 ≈ 0.618 (黄金比例)
    """
    A = 0.618033988749895
    return int(m * ((x * A) % 1))

def knuth_hash(x: int, m: int) -> int:
    """
    Knuth乘法哈希
    
    h(k) = floor(m * (k * 2654435761 mod 2^32) / 2^32)
    """
    return (x * 2654435761) % m

def wang_hash(key: int) -> int:
    """
    Thomas Wang的整数哈希
    64位整数哈希函数
    """
    key = (~key) + (key << 21)
    key = key ^ (key >> 24)
    key = (key + (key << 3)) + (key << 8)
    key = key ^ (key >> 14)
    key = (key + (key << 2)) + (key << 4)
    key = key ^ (key >> 28)
    key = key + (key << 31)
    return key

4.4.3 字符串哈希

def djb2_hash(s: str) -> int:
    """
    DJB2字符串哈希
    
    h = 0
    for c in s:
        h = 33 * h + c
    """
    h = 5381
    for c in s:
        h = ((h << 5) + h) + ord(c)
    return h

def sdbm_hash(s: str) -> int:
    """
    SDBM字符串哈希
    
    h = 0
    for c in s:
        h = c + (h << 6) + (h << 16) - h
    """
    h = 0
    for c in s:
        h = ord(c) + (h << 6) + (h << 16) - h
    return h

def fnv1a_hash(s: str) -> int:
    """
    FNV-1a字符串哈希
    
    FNV偏移基数: 2166136261
    FNV素数: 16777619
    """
    FNV_OFFSET = 2166136261
    FNV_PRIME = 16777619
    
    h = FNV_OFFSET
    for c in s:
        h ^= ord(c)
        h *= FNV_PRIME
    return h

def murmur3_32(data: bytes, seed: int = 0) -> int:
    """
    MurmurHash3 (32位)
    
    高性能非加密哈希函数
    """
    c1 = 0xcc9e2d51
    c2 = 0x1b873593
    
    h = seed
    length = len(data)
    nblocks = length // 4
    
    for i in range(nblocks):
        k = int.from_bytes(data[i*4:(i+1)*4], 'little')
        k = (k * c1) & 0xFFFFFFFF
        k = ((k << 15) | (k >> 17)) & 0xFFFFFFFF
        k = (k * c2) & 0xFFFFFFFF
        
        h ^= k
        h = ((h << 13) | (h >> 19)) & 0xFFFFFFFF
        h = (h * 5 + 0xe6546b64) & 0xFFFFFFFF
    
    tail = data[nblocks * 4:]
    k = 0
    for i, byte in enumerate(tail):
        k |= byte << (i * 8)
    
    if tail:
        k = (k * c1) & 0xFFFFFFFF
        k = ((k << 15) | (k >> 17)) & 0xFFFFFFFF
        k = (k * c2) & 0xFFFFFFFF
        h ^= k
    
    h ^= length
    h ^= (h >> 16)
    h = (h * 0x85ebca6b) & 0xFFFFFFFF
    h ^= (h >> 13)
    h = (h * 0xc2b2ae35) & 0xFFFFFFFF
    h ^= (h >> 16)
    
    return h

---

4.5 高级字典实现

4.5.1 自定义哈希表

from typing import TypeVar, Generic, Optional, List, Tuple, Iterator
from dataclasses import dataclass
import hashlib

K = TypeVar('K')
V = TypeVar('V')

@dataclass
class Entry(Generic[K, V]):
    key: K
    value: V
    hash: int

class HashMap(Generic[K, V]):
    """
    自定义哈希表实现
    
    特性：
    - 开放寻址法
    - 双重哈希探测
    - 自动扩容
    - 删除标记处理
    """
    
    DEFAULT_CAPACITY = 16
    LOAD_FACTOR = 0.75
    DELETED = object()
    
    def __init__(self, capacity: int = DEFAULT_CAPACITY):
        self._capacity = max(16, self._next_power_of_2(capacity))
        self._table: List[Optional[Entry[K, V] | object]] = [None] * self._capacity
        self._size = 0
        self._deleted_count = 0
    
    @staticmethod
    def _next_power_of_2(n: int) -> int:
        n -= 1
        n |= n >> 1
        n |= n >> 2
        n |= n >> 4
        n |= n >> 8
        n |= n >> 16
        return n + 1
    
    def _hash(self, key: K) -> int:
        if hasattr(key, '__hash__'):
            h = hash(key)
        else:
            h = int(hashlib.md5(str(key).encode()).hexdigest(), 16)
        return h ^ (h >> 16)
    
    def _probe(self, hash_val: int, i: int) -> int:
        """双重哈希探测序列"""
        h2 = 1 + (hash_val % (self._capacity - 1))
        return (hash_val + i * h2) % self._capacity
    
    def _find_slot(self, key: K) -> Tuple[int, bool]:
        """
        查找键的位置
        
        返回: (索引, 是否找到)
        """
        hash_val = self._hash(key)
        first_deleted = -1
        
        for i in range(self._capacity):
            idx = self._probe(hash_val, i)
            entry = self._table[idx]
            
            if entry is None:
                return (first_deleted if first_deleted >= 0 else idx, False)
            
            if entry is self.DELETED:
                if first_deleted < 0:
                    first_deleted = idx
            elif entry.hash == hash_val and entry.key == key:
                return (idx, True)
        
        return (first_deleted, False)
    
    def get(self, key: K, default: Optional[V] = None) -> Optional[V]:
        idx, found = self._find_slot(key)
        if found:
            return self._table[idx].value
        return default
    
    def put(self, key: K, value: V) -> Optional[V]:
        if self._should_resize():
            self._resize()
        
        idx, found = self._find_slot(key)
        old_value = None
        
        if found:
            old_value = self._table[idx].value
            self._table[idx] = Entry(key, value, self._hash(key))
        else:
            if self._table[idx] is self.DELETED:
                self._deleted_count -= 1
            self._table[idx] = Entry(key, value, self._hash(key))
            self._size += 1
        
        return old_value
    
    def remove(self, key: K) -> Optional[V]:
        idx, found = self._find_slot(key)
        if not found:
            return None
        
        value = self._table[idx].value
        self._table[idx] = self.DELETED
        self._size -= 1
        self._deleted_count += 1
        
        return value
    
    def _should_resize(self) -> bool:
        return (self._size + self._deleted_count) >= self._capacity * self.LOAD_FACTOR
    
    def _resize(self) -> None:
        old_table = self._table
        self._capacity *= 2
        self._table = [None] * self._capacity
        self._size = 0
        self._deleted_count = 0
        
        for entry in old_table:
            if entry is not None and entry is not self.DELETED:
                self.put(entry.key, entry.value)
    
    def __getitem__(self, key: K) -> V:
        value = self.get(key)
        if value is None:
            raise KeyError(key)
        return value
    
    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:
        idx, found = self._find_slot(key)
        return found
    
    def __len__(self) -> int:
        return self._size
    
    def __iter__(self) -> Iterator[K]:
        for entry in self._table:
            if entry is not None and entry is not self.DELETED:
                yield entry.key
    
    def items(self) -> Iterator[Tuple[K, V]]:
        for entry in self._table:
            if entry is not None and entry is not self.DELETED:
                yield entry.key, entry.value

4.5.2 LRU缓存实现

from typing import TypeVar, Generic, Optional, Dict
from collections import OrderedDict

K = TypeVar('K')
V = TypeVar('V')

class LRUCache(Generic[K, V]):
    """
    LRU（最近最少使用）缓存
    
    时间复杂度：
    - get: O(1)
    - put: O(1)
    
    空间复杂度：O(capacity)
    """
    
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("Capacity must be positive")
        self._capacity = capacity
        self._cache: OrderedDict[K, V] = OrderedDict()
    
    def get(self, key: K) -> Optional[V]:
        if key not in self._cache:
            return None
        
        value = self._cache.pop(key)
        self._cache[key] = value
        return value
    
    def put(self, key: K, value: V) -> None:
        if key in self._cache:
            self._cache.pop(key)
        elif len(self._cache) >= self._capacity:
            self._cache.popitem(last=False)
        
        self._cache[key] = value
    
    def __contains__(self, key: K) -> bool:
        return key in self._cache
    
    def __len__(self) -> int:
        return len(self._cache)
    
    def clear(self) -> None:
        self._cache.clear()


class LFUCache(Generic[K, V]):
    """
    LFU（最不经常使用）缓存
    
    时间复杂度：
    - get: O(1)
    - put: O(1)
    """
    
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._size = 0
        self._min_freq = 0
        self._key_to_val_freq: Dict[K, Tuple[V, int]] = {}
        self._freq_to_keys: Dict[int, OrderedDict] = {}
    
    def get(self, key: K) -> Optional[V]:
        if key not in self._key_to_val_freq:
            return None
        
        val, freq = self._key_to_val_freq[key]
        
        del self._freq_to_keys[freq][key]
        if not self._freq_to_keys[freq]:
            del self._freq_to_keys[freq]
            if freq == self._min_freq:
                self._min_freq += 1
        
        self._key_to_val_freq[key] = (val, freq + 1)
        if freq + 1 not in self._freq_to_keys:
            self._freq_to_keys[freq + 1] = OrderedDict()
        self._freq_to_keys[freq + 1][key] = None
        
        return val
    
    def put(self, key: K, value: V) -> None:
        if self._capacity <= 0:
            return
        
        if key in self._key_to_val_freq:
            _, freq = self._key_to_val_freq[key]
            self._key_to_val_freq[key] = (value, freq)
            self.get(key)
            return
        
        if self._size >= self._capacity:
            evict_key = self._freq_to_keys[self._min_freq].popitem(last=False)[0]
            del self._key_to_val_freq[evict_key]
            self._size -= 1
        
        self._key_to_val_freq[key] = (value, 1)
        if 1 not in self._freq_to_keys:
            self._freq_to_keys[1] = OrderedDict()
        self._freq_to_keys[1][key] = None
        self._min_freq = 1
        self._size += 1

---

4.6 特殊字典类型

4.6.1 defaultdict分析

from collections import defaultdict
from typing import TypeVar, K, V, Callable, DefaultDict

K = TypeVar('K')
V = TypeVar('V')

class CustomDefaultDict(Generic[K, V]):
    """
    自定义defaultdict实现
    
    特性：
    - 自动初始化缺失键
    - 支持任意工厂函数
    """
    
    def __init__(self, default_factory: Callable[[], V]):
        self._data: Dict[K, V] = {}
        self._default_factory = default_factory
    
    def __getitem__(self, key: K) -> V:
        if key not in self._data:
            self._data[key] = self._default_factory()
        return self._data[key]
    
    def __setitem__(self, key: K, value: V) -> None:
        self._data[key] = value
    
    def __delitem__(self, key: K) -> None:
        del self._data[key]
    
    def __contains__(self, key: K) -> bool:
        return key in self._data
    
    def __len__(self) -> int:
        return len(self._data)
    
    def __iter__(self):
        return iter(self._data)
    
    def get(self, key: K, default: Optional[V] = None) -> Optional[V]:
        return self._data.get(key, default)
    
    def items(self):
        return self._data.items()
    
    def keys(self):
        return self._data.keys()
    
    def values(self):
        return self._data.values()


def demonstrate_defaultdict_patterns():
    """演示defaultdict常用模式"""
    
    print("=== 计数模式 ===")
    counter = defaultdict(int)
    for char in "hello world":
        counter[char] += 1
    print(f"字符计数: {dict(counter)}")
    
    print("\n=== 分组模式 ===")
    grouper = defaultdict(list)
    words = ["apple", "banana", "cherry", "apricot", "blueberry"]
    for word in words:
        grouper[word[0]].append(word)
    print(f"按首字母分组: {dict(grouper)}")
    
    print("\n=== 集合模式 ===")
    sets = defaultdict(set)
    pairs = [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'c')]
    for key, val in pairs:
        sets[key].add(val)
    print(f"集合分组: {dict(sets)}")
    
    print("\n=== 嵌套字典模式 ===")
    nested = defaultdict(lambda: defaultdict(int))
    data = [("A", "X", 1), ("A", "Y", 2), ("B", "X", 3)]
    for k1, k2, v in data:
        nested[k1][k2] = v
    print(f"嵌套字典: {dict((k, dict(v)) for k, v in nested.items())}")


if __name__ == '__main__':
    demonstrate_defaultdict_patterns()

4.6.2 Counter分析

from collections import Counter
from typing import Dict, List, Tuple, Optional

class CustomCounter(Dict):
    """
    自定义Counter实现
    
    特性：
    - 计数统计
    - 算术运算
    - 集合运算
    """
    
    def __init__(self, iterable=None, **kwargs):
        super().__init__()
        if iterable is not None:
            self.update(iterable)
        self.update(kwargs)
    
    def __missing__(self, key):
        return 0
    
    def update(self, iterable=None, **kwargs):
        if iterable is not None:
            if hasattr(iterable, 'items'):
                for elem, count in iterable.items():
                    self[elem] = self.get(elem, 0) + count
            else:
                for elem in iterable:
                    self[elem] = self.get(elem, 0) + 1
        
        for elem, count in kwargs.items():
            self[elem] = self.get(elem, 0) + count
    
    def most_common(self, n: Optional[int] = None) -> List[Tuple]:
        sorted_items = sorted(self.items(), key=lambda x: (-x[1], x[0]))
        if n is None:
            return sorted_items
        return sorted_items[:n]
    
    def elements(self):
        for elem, count in self.items():
            for _ in range(count):
                yield elem
    
    def __add__(self, other: 'CustomCounter') -> 'CustomCounter':
        result = CustomCounter()
        for elem in set(self) | set(other):
            result[elem] = self[elem] + other[elem]
        return result
    
    def __sub__(self, other: 'CustomCounter') -> 'CustomCounter':
        result = CustomCounter()
        for elem in set(self) | set(other):
            new_count = self[elem] - other[elem]
            if new_count > 0:
                result[elem] = new_count
        return result
    
    def __mul__(self, other: int) -> 'CustomCounter':
        result = CustomCounter()
        for elem, count in self.items():
            result[elem] = count * other
        return result
    
    def __and__(self, other: 'CustomCounter') -> 'CustomCounter':
        result = CustomCounter()
        for elem in set(self) & set(other):
            result[elem] = min(self[elem], other[elem])
        return result
    
    def __or__(self, other: 'CustomCounter') -> 'CustomCounter':
        result = CustomCounter()
        for elem in set(self) | set(other):
            result[elem] = max(self[elem], other[elem])
        return result

---

4.7 本章小结

4.7.1 核心定理总结

定理	内容	应用
定理 4.3	通用哈希冲突概率 $\leq 1/m$	哈希函数设计
定理 4.4	生日悖论冲突概率	安全分析
定理 4.5	线性探测期望探测数	性能预估
定理 4.7	负载因子与性能关系	容量规划

4.7.2 时间复杂度汇总

操作	平均情况	最坏情况	说明
d[key]	$O(1)$	$O(n)$	哈希冲突时退化
d[key] = value	$O(1)$	$O(n)$	扩容时更高
del d[key]	$O(1)$	$O(n)$	-
key in d	$O(1)$	$O(n)$	-
d.keys()	$O(1)$	$O(1)$	视图对象
len(d)	$O(1)$	$O(1)$	-

4.7.3 选择指南

场景	推荐类型	原因
通用键值存储	dict	高效、有序
计数统计	Counter	内置统计方法
分组聚合	defaultdict(list)	自动初始化
多层配置	ChainMap	不复制数据
LRU缓存	OrderedDict	move_to_end
类型安全	TypedDict	类型检查

---

4.8 习题

理论题

1. 证明：在均匀哈希假设下，开放寻址法不成功查找的期望探测次数为 $1/(1-\alpha)$。

2. 证明：当负载因子 $\alpha \to 1$ 时，线性探测的性能急剧下降。

3. 分析双重哈希相比线性探测的优势。

4. 证明：通用哈希族的冲突概率上界。

设计题

5. 设计一个支持范围查询的哈希表变体。

6. 实现一个支持并发访问的无锁哈希表。

实现题

7. 实现一个支持动态扩容的哈希表，分析其均摊复杂度。

8. 实现一个布隆过滤器，分析其假阳性率。

---

4.9 参考文献

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press. Chapter 11: Hash Tables.

2. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. Section 6.4: Hashing.

3. Carter, J. L., & Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences, 18(2), 143-154.

4. CPython Source Code. (2024). Objects/dictobject.c. https://github.com/python/cpython/blob/main/Objects/dictobject.c

5. Preshing, J. (2016). Hash Table Animation. https://preshing.com/20160314/leapfrog-hashing/

6. Kwon, J., & Park, J. (2018). Compact Hash Tables on GPUs. IEEE Transactions on Parallel and Distributed Systems, 29(7), 1499-1511.

---

下一章：第5章 集合与位集理论