哈希表

1. 概述与学习目标

1.1 什么是哈希表

哈希表（Hash Table，又称散列表）是一种通过哈希函数将键（key）映射到数组下标，从而实现 $O(1)$ 平均时间复杂度的插入、查找、删除的关联数组（associative array）数据结构。

核心思想：用一个数组 T[0..m-1] 存储元素，通过哈希函数 $h: U \to \{0, 1, \ldots, m-1\}$ 将键 $k$ 映射到下标 $h(k)$，使得大部分情况下元素可直接定位。当不同键映射到同一槽位（冲突）时，通过链地址法或开放寻址法处理。

一句话定义：哈希表 = 数组 + 哈希函数 + 冲突处理，平均 $O(1)$ 查找/插入/删除，最坏 $O(n)$，是空间换时间的极致实现。

1.2 学习目标

完成本文档学习后，你将能够：

1. 记忆哈希表作为直接寻址表空间优化方案的形式化定义，复述链地址法与开放寻址法在查找成功/查找失败场景下的平均探测次数公式；
2. 理解 Hans Peter Luhn 1953 IBM 首次提出哈希、Knuth TAOCP Vol.3 §6.4 系统化理论、Carter-Wegman 1979 全域哈希、Bloom 1970 布隆过滤器、Pagh-Rodler 2004 布谷鸟哈希的历史脉络，说明哈希表为何在键值查找场景下不可替代；
3. 应用除法哈希、乘法哈希（Knuth 黄金分割比）、多项式滚动哈希（Rabin-Karp）、链地址法、开放寻址法（线性探测/二次探测/双重哈希）编写可运行的 Python/C++/Java 代码；
4. 分析简单均匀哈希假设下链地址法 $\text{ASL} = 1 + \alpha/2$ 与均匀哈希假设下开放寻址法 $\text{ASL} = \frac{1}{\alpha}\ln\frac{1}{1-\alpha}$ 的推导过程，论证负载因子 $\alpha$ 对性能的影响；
5. 评估哈希表相对于平衡树、有序数组、跳跃表在”键值查找”问题维度上的优劣，识别 LRU/LFU 缓存、计数器、字典编码、数据库索引中的哈希选型动机；
6. 对比链地址法、线性探测、二次探测、双重哈希、布谷鸟哈希在聚集现象、缓存友好性、删除复杂度、负载因子上限维度的差异；
7. 创造性设计基于哈希表的开源项目解决方案，如 LRU 缓存、词频统计器、URL 短链系统、数据库去重索引、Bloom Filter 海量数据判重。

1.3 直接寻址表 vs 哈希表

直接寻址表（Direct-Address Table）：当键域 $U$ 较小时，用数组 T[k] 直接存储键 $k$ 对应的值。查找 $O(1)$，但空间 $O(|U|)$。

键域 U = {0, 1, 2, ..., 999}
直接寻址表 T[0..999]：每个键 k 直接存到 T[k]
查找：T[k] 即为结果，O(1)
空间：O(|U|) = O(1000)

哈希表（Hash Table）：当键域 $U$ 很大（如全部 64 位整数，$|U| = 2^{64}$）但实际键数 $n$ 远小于 $|U|$ 时，用哈希函数 $h(k)$ 将键映射到 $m$ 个槽位中，空间仅需 $O(m)$。

键域 U = 全部 64 位整数（|U| = 2^64）
实际键数 n = 1000
槽位数 m = 2048（取 2 倍冗余）
哈希函数 h(k) = k mod 2048
查找：计算 h(k) 后定位槽位，平均 O(1)
空间：O(m) = O(2048)

代价：不同键可能映射到同一槽位（冲突），需要冲突处理策略。这是哈希表的核心权衡。

1.4 核心指标

1.5 哈希表 vs 其他查找结构

跨模块引用：哈希查找的搜索框架参见 搜索算法；BST 和红黑树参见 树；跳跃表作为概率平衡结构参见 跳跃表；链表作为链地址法底层存储参见 链表。

1.6 适用场景与不适用场景

教学提示：哈希表的”魔法”在于哈希函数将”任意键”压缩为”固定大小下标”，但代价是冲突。理解哈希表的关键是抓住”哈希函数均匀性 + 冲突处理代价”的权衡。

2. 历史动机与演进

2.1 前哈希时代：线性查找与对数查找

1950 年代初期，计算机内存稀少且昂贵，程序员主要使用有序数组 + 二分查找或线性查找存储与检索数据。这两种方案存在三大根本性缺陷：

1. 二分查找要求有序：插入新元素需 $O(n)$ 移动，无法支持动态数据集；
2. 线性查找代价高：$O(n)$ 查找在数据量增大时无法接受；
3. 平衡树尚未出现：AVL 树 1962 年才由 Adelson-Velsky-Landis 提出，且实现复杂、常数大。

IBM 科学家 Hans Peter Luhn 在为 IBM 701 计算机设计信息检索系统时，遇到”对大量文献关键词快速定位”的需求，传统的索引方案无法满足。

2.2 Hans Peter Luhn 1953：哈希表的诞生

1953 年，Hans Peter Luhn 在 IBM 内部备忘录中首次提出哈希表的概念：用一个函数将键”打散”（hash）后映射到固定大小的数组下标，实现 $O(1)$ 平均查找。

Luhn 最初使用”scrambling function”称呼这个函数，意为”将输入打乱”。后来 IBM 同事借鉴德语 hachieren（切碎）与法语 hacher（剁碎），将这种”将输入切碎后取摘要”的函数命名为 hash function。Luhn 还观察到：

• 不同键可能映射到同一地址（冲突）；
• 冲突可通过”开放寻址”或”链式存储”处理；
• 当槽位足够稀疏时，冲突概率很低，查找接近 $O(1)$。

Luhn 的工作未公开发表，但通过 IBM 内部传播影响了 Arnold Dumey、Gene Amdahl 等人。Dumey 1956 年在 Computers and Automation 杂志首次将哈希表写入公开文献，称其为”scrambled file”。

教学提示：Hans Peter Luhn 还在 1957 年提出了 KWIC（KeyWord In Context）索引，1960 年代提出 Luhn 哈希（用于信息检索）。他被 IBM 誉为”信息检索之父”。

2.3 Knuth 1968-1973：系统化理论

1968 年，Donald E. Knuth 出版《The Art of Computer Programming, Volume 3: Sorting and Searching》（实际 1973 年完稿），在 Section 6.4 Hashing 系统化哈希表理论：

• 形式化定义哈希函数、冲突、负载因子；
• 分析除法哈希、乘法哈希（Knuth 黄金分割比 $A = (\sqrt{5}-1)/2$）；
• 系统总结链地址法、开放寻址法（线性探测/二次探测/双重哈希）；
• 推导均匀哈希假设下的 ASL 公式；
• 讨论 Bob Morris 1968 年提出的”删除标记”问题。

TAOCP Vol.3 成为哈希表教学的金标准，后续教材（CLRS、Sedgewick）均沿用其框架。Knuth 还指出：哈希表是”计算机科学中最优雅的折衷案例之一”，用空间换时间、用随机性换确定性。

2.4 Carter-Wegman 1979：全域哈希

1970 年代，研究人员发现最坏情况攻击问题：如果对手知道用户使用的哈希函数（如固定除数 $m$），可以构造大量冲突键使哈希表退化为 $O(n)$ 链表。这在 1970 年代的批处理系统中尚可忍受，但在 1980 年代的交互式系统与网络服务中成为严重安全漏洞。

1977 年 STOC 会议上，IBM 沃森研究中心 Larry Carter 与 Mark Wegman 提交论文《Universal classes of hash functions》，1979 年正式发表于 Journal of Computer and System Sciences 18(2): 143-154。论文引入全域哈希族概念：

定义（Carter-Wegman 全域）：哈希函数族 $H$ 是全域的，若对任意两个不同键 $x, y \in U$：

$\Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{m}$

关键意义：在执行前随机选择 $h \in H$，对手无法预先构造冲突键，期望 ASL 仍为 $O(1 + \alpha)$。Carter-Wegman 给出具体构造：

$h_{a,b}(k) = ((a \cdot k + b) \mod p) \mod m$

其中 $p$ 为大于 $|U|$ 的质数，$a \in \{1, \ldots, p-1\}$、$b \in \{0, \ldots, p-1\}$ 随机选取。该构造是后续密码学哈希、完美哈希、最小完美哈希的理论基石。

2.5 Bloom 1970：布隆过滤器

1970 年，Burton H. Bloom 在 Communications of the ACM 13(7): 422-426 发表论文《Space/time trade-offs in hash coding with allowable errors》，提出布隆过滤器（Bloom Filter）：用 $k$ 个独立哈希函数 + 位图，在允许少量假阳性的前提下，将判重空间从 $O(n \cdot \text{key\_size})$ 压缩到 $O(n)$ 比特。

Bloom Filter 是哈希思想”用概率换空间”的极致应用，成为后续 HyperLogLog、Count-Min Sketch、Cuckoo Filter 等概率数据结构的鼻祖。

2.6 Pagh-Rodler 2004：布谷鸟哈希

2001 年丹麦奥尔胡斯大学 Rasmus Pagh 与 Flemming Friche Rodler 在 ESA 会议提出布谷鸟哈希（Cuckoo Hashing），2004 年正式发表于 Journal of Algorithms 51(2): 122-144。灵感源自布谷鸟将蛋放入其他鸟巢后，幼鸟将原蛋挤出的行为：

• 每个键使用两个哈希函数 $h_1, h_2$，可放入两个槽位之一；
• 插入时若两槽均被占，踢出原元素并重新哈希（rehash）；
• 核心优势：查找最坏 $O(1)$（仅查两个槽位），删除 $O(1)$。

布谷鸟哈希是开放寻址法的革命性变体，被广泛应用于网络路由表、内存数据库、Cuckoo Filter。

2.7 工业实现演进

2.8 演进时间线

timeline
    title 哈希表演进时间线
    1953 : Luhn 在 IBM 提出哈希表概念 (internal memo)
    1956 : Dumey 在 Computers and Automation 公开介绍
    1968 : Knuth TAOCP Vol.3 §6.4 系统化理论
    1970 : Bloom 提出 Bloom Filter (CACM)
    1974 : Unix DBM 首个工业级哈希数据库
    1979 : Carter-Wegman 全域哈希 (JCSS)
    1986 : Perl 1.0 内置 hash 类型
    1995 : Java HashMap 1.0 (链地址法)
    2003 : Python 2.3 dict 改用开放寻址
    2004 : Pagh-Rodler 布谷鸟哈希 (J. Algorithms)
    2012 : Python PEP 412 紧凑字典
    2014 : Java HashMap 1.8 链表转红黑树
    2017 : Python 3.7 dict 保证插入顺序

2.9 关键设计决策

哈希表演进过程中有六个关键设计决策：

1. 数组而非链表作为底层：数组支持 $O(1)$ 随机访问，是哈希”魔法”的前提；
2. 哈希函数不必可逆：与加密哈希不同，哈希表的哈希函数仅需均匀分布，无需抗碰撞；
3. 冲突不可避免但可控：选择合适负载因子 $\alpha$ + 良好冲突处理策略，可将冲突影响降至 $O(1)$；
4. 随机化防御最坏攻击：全域哈希族使对手无法预构造冲突键；
5. 扩容是渐进的而非一次性：Redis 渐进式 rehash 避免大规模停顿；
6. 概率换空间：Bloom Filter、Count-Min Sketch 等用少量假阳性换取数量级的空间节省。

教学提示：理解哈希表演进的关键是抓住”随机性 + 概率 + 摊还”三重思想。这与跳跃表用概率换平衡、并查集用摊还换复杂度一脉相承。

3. 形式化定义

3.1 哈希函数

定义 3.1（哈希函数）：哈希函数是从键域 $U$ 到槽位集合 $\{0, 1, \ldots, m-1\}$ 的映射：

$h: U \to \{0, 1, \ldots, m-1\}$

其中 $m$ 为哈希表大小，$|U|$ 通常远大于 $m$。

好哈希函数的三条性质：

1. 确定性：对同一键 $k$，$h(k)$ 恒定不变；
2. 均匀性：对任意槽位 $j$，$\Pr[h(k) = j] \approx 1/m$；
3. 高效性：计算 $h(k)$ 的时间为 $O(1)$。

3.2 冲突与负载因子

定义 3.2（冲突）：若两个不同键 $k_1 \neq k_2$ 满足 $h(k_1) = h(k_2)$，则称冲突。由鸽巢原理，当 $|U| > m$ 时冲突不可避免。

定义 3.3（负载因子）：负载因子 $\alpha$ 定义为元素数 $n$ 与槽位数 $m$ 之比：

$\alpha = \frac{n}{m}$

• 链地址法：$\alpha$ 可大于 1（每个槽位挂链表）；
• 开放寻址法：$\alpha < 1$ 严格成立（所有元素占槽）。

3.3 简单均匀哈希假设

定义 3.4（简单均匀哈希假设，SUHA）：每个键 $k$ 等概率地哈希到任一槽位，且与其他键的哈希位置独立：

$\Pr[h(k) = j] = \frac{1}{m}, \quad \forall k \in U, j \in \{0, \ldots, m-1\}$

SUHA 是理想化假设，实际中通过全域哈希族近似实现。

3.4 全域哈希族

定义 3.5（全域哈希族，Carter-Wegman 1979）：哈希函数族 $H$ 是全域的，若对任意两个不同键 $x \neq y \in U$：

$|\{h \in H : h(x) = h(y)\}| \leq \frac{|H|}{m}$

等价地，随机选取 $h \in H$ 时：

$\Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{m}$

Carter-Wegman 构造：

$h_{a,b}(k) = ((a \cdot k + b) \mod p) \mod m$

其中：

• $p$ 为大于 $|U|$ 的质数；
• $a \in \{1, 2, \ldots, p-1\}$ 均匀随机；
• $b \in \{0, 1, \ldots, p-1\}$ 均匀随机；
• 共 $|H| = p(p-1)$ 个函数。

关键推论：在全域哈希族下，链地址法的期望链表长度为 $\alpha = n/m$，期望 ASL 为 $O(1 + \alpha)$。

3.5 哈希表抽象数据类型

哈希表 ADT 支持以下操作：

教学提示：哈希表 ADT 看似简单，但工程实现需要考虑：扩容策略、并发安全、迭代顺序、内存布局、缓存友好性等多重维度。后续章节将逐一展开。

4. 哈希函数设计

4.1 好哈希函数的标准

1. 确定性：同一键始终映射到同一槽位；
2. 均匀性：键均匀分布在所有槽位上，减少冲突；
3. 高效性：计算速度快，理想 $O(1)$；
4. 雪崩效应：输入微小变化导致输出大幅变化；
5. 抗碰撞：难以构造大量冲突键（安全场景）。

4.2 除法哈希

除法哈希：$h(k) = k \mod m$

选择 $m$ 的准则：

• $m$ 应为质数，且远离 2 的幂次；
• 若 $m = 2^p$，则 $h(k)$ 只依赖 $k$ 的最低 $p$ 位，对低规律性输入不友好；
• 推荐选择不接近 2 的幂次的质数，如 $m = 701, 1009, 10007, 100003$。

def division_hash(key: int, m: int) -> int:
    """除法哈希：h(k) = k mod m。

    Args:
        key: 整数键
        m: 槽位数，应为远离 2 的幂次的质数

    Returns:
        哈希值 [0, m-1]
    """
    return key % m

// 除法哈希：C++ 实现
int divisionHash(int key, int m) {
    // m 应为质数且远离 2 的幂次
    return key % m;
}

// 除法哈希：Java 实现
public static int divisionHash(int key, int m) {
    // 处理负数：先取绝对值再模
    return Math.abs(key) % m;
}

陷阱：Java 中 Integer.MIN_VALUE 的绝对值仍是负数（溢出），导致 Math.abs(key) % m 可能为负。应使用 (key & 0x7FFFFFFF) % m 或 Math.floorMod(key, m)。

4.3 乘法哈希

乘法哈希：

$h(k) = \lfloor m \cdot (k \cdot A \mod 1) \rfloor$

其中 $0 < A < 1$ 为常数。Knuth TAOCP Vol.3 §6.4 建议 $A = (\sqrt{5} - 1) / 2 \approx 0.6180339887$（黄金分割比），对 $m$ 的选择不敏感。

优势：

• $m$ 可取 2 的幂次（如 $m = 2^p$），用位运算加速；
• 对键的低规律性不敏感。

def multiplication_hash(key: int, m: int = 1 << 16, A: float = 0.6180339887) -> int:
    """乘法哈希：h(k) = floor(m * (k * A mod 1))。

    Args:
        key: 整数键
        m: 槽位数，推荐 2 的幂次
        A: 乘数，Knuth 建议黄金分割比 (sqrt(5)-1)/2

    Returns:
        哈希值 [0, m-1]
    """
    return int(m * ((key * A) % 1.0))

// 乘法哈希：C++ 实现（使用 32 位定点数加速）
int multiplicationHash(uint32_t key, int p = 16) {
    // A = (sqrt(5)-1)/2 的 32 位定点表示
    const uint32_t A_FIX = 2654435769;  // floor(2^32 * (sqrt(5)-1)/2)
    return (key * A_FIX) >> (32 - p);
}

4.4 全域哈希

全域哈希（Carter-Wegman 1979）：随机选择哈希函数，使得对任意两个不同的键，冲突概率不超过 $1/m$。

$h_{a,b}(k) = ((a \cdot k + b) \mod p) \mod m$

其中 $p$ 为大于 $|U|$ 的质数，$a \in \{1, \ldots, p-1\}$、$b \in \{0, \ldots, p-1\}$ 随机选取。

import random


class UniversalHash:
    """Carter-Wegman 全域哈希函数族。

    H = { h_{a,b}(k) = ((a*k + b) mod p) mod m | a in [1,p-1], b in [0,p-1] }
    """

    def __init__(self, m: int, p: int = 2147483647):
        """初始化哈希函数族。

        Args:
            m: 槽位数
            p: 大于 |U| 的质数，默认 2^31-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: int) -> int:
        """计算哈希值。"""
        return ((self.a * k + self.b) % self.p) % self.m

// 全域哈希：C++ 实现
class UniversalHash {
    uint64_t a, b, p, m;
    std::mt19937_64 rng;

public:
    UniversalHash(uint64_t m, uint64_t p = 2147483647ULL)
        : m(m), p(p), rng(std::random_device{}()) {
        std::uniform_int_distribution<uint64_t> dist_a(1, p - 1);
        std::uniform_int_distribution<uint64_t> dist_b(0, p - 1);
        a = dist_a(rng);
        b = dist_b(rng);
    }

    uint64_t operator()(uint64_t k) const {
        return ((a * k + b) % p) % m;
    }
};

4.5 字符串哈希

4.5.1 多项式滚动哈希

多项式滚动哈希：

$H(s) = s[0] \cdot b^{n-1} + s[1] \cdot b^{n-2} + \cdots + s[n-1] \mod M$

常用基数 $b = 31, 131, 13331$ 等（经验值，减少冲突），模数 $M = 10^9 + 7, 10^9 + 9, 2^{64}$ 等。

def polynomial_hash(s: str, base: int = 31, mod: int = 10**9 + 7) -> int:
    """多项式滚动哈希：H(s) = sum(s[i] * base^(n-1-i)) mod mod。

    Args:
        s: 输入字符串
        base: 基数，推荐 31, 131, 13331
        mod: 模数，推荐 10^9+7, 10^9+9

    Returns:
        哈希值
    """
    h = 0
    for ch in s:
        h = (h * base + ord(ch)) % mod
    return h


def rolling_hash(s: str, window: int, base: int = 31, mod: int = 10**9 + 7) -> list:
    """滑动窗口哈希：在 O(1) 时间内更新窗口哈希值。

    Args:
        s: 输入字符串
        window: 窗口大小
        base: 基数
        mod: 模数

    Returns:
        所有窗口的哈希值列表
    """
    n = len(s)
    if n < window:
        return []
    power = pow(base, window - 1, mod)
    hashes = []
    h = 0
    # 初始化第一个窗口
    for i in range(window):
        h = (h * base + ord(s[i])) % mod
    hashes.append(h)
    # 滑动窗口
    for i in range(window, n):
        # 移除最左字符，添加新字符
        h = (h - ord(s[i - window]) * power % mod + mod) % mod
        h = (h * base + ord(s[i])) % mod
        hashes.append(h)
    return hashes

// 多项式滚动哈希：C++ 实现
long long polynomialHash(const string& s, long long base = 31, long long mod = 1e9 + 7) {
    long long h = 0;
    for (char c : s) {
        h = (h * base + c) % mod;
    }
    return h;
}

// 滑动窗口哈希：用于 Rabin-Karp 字符串匹配
vector<long long> rollingHash(const string& s, int window,
                              long long base = 31, long long mod = 1e9 + 7) {
    int n = s.size();
    if (n < window) return {};
    long long power = 1;
    for (int i = 0; i < window - 1; ++i) {
        power = power * base % mod;
    }
    vector<long long> hashes;
    long long h = 0;
    for (int i = 0; i < window; ++i) {
        h = (h * base + s[i]) % mod;
    }
    hashes.push_back(h);
    for (int i = window; i < n; ++i) {
        h = ((h - s[i - window] * power % mod + mod) % mod * base % mod + s[i]) % mod;
        hashes.push_back(h);
    }
    return hashes;
}

// 多项式滚动哈希：Java 实现
public static long polynomialHash(String s, long base, long mod) {
    long h = 0;
    for (int i = 0; i < s.length(); i++) {
        h = (h * base + s.charAt(i)) % mod;
    }
    return h;
}

4.5.2 Rabin-Karp 字符串匹配

利用滚动哈希在 $O(n + m)$ 平均时间内匹配模式串：

def rabin_karp(text: str, pattern: str, base: int = 31, mod: int = 10**9 + 7) -> list:
    """Rabin-Karp 字符串匹配：使用滚动哈希加速匹配。

    Args:
        text: 文本串
        pattern: 模式串
        base: 基数
        mod: 模数

    Returns:
        所有匹配起始位置列表
    """
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    pattern_hash = polynomial_hash(pattern, base, mod)
    power = pow(base, m - 1, mod)
    # 计算文本第一个窗口的哈希
    h = 0
    for i in range(m):
        h = (h * base + ord(text[i])) % mod
    positions = []
    for i in range(n - m + 1):
        if h == pattern_hash:
            # 哈希匹配后需验证字符串（避免哈希碰撞误判）
            if text[i:i + m] == pattern:
                positions.append(i)
        if i < n - m:
            h = (h - ord(text[i]) * power % mod + mod) % mod
            h = (h * base + ord(text[i + m])) % mod
    return positions

教学提示：Rabin-Karp 的核心是”用滚动哈希在 $O(1)$ 内更新窗口”，避免每次重新计算。哈希匹配后必须验证字符串，因为不同字符串可能哈希相同（假阳性）。

4.5.3 双哈希防碰撞

竞赛与生产环境中常用双哈希（两个不同模数）降低冲突概率：

def double_hash(s: str) -> tuple:
    """双哈希：使用两个不同模数，冲突概率降至 1/(M1*M2)。"""
    MOD1, MOD2 = 10**9 + 7, 10**9 + 9
    BASE = 131
    h1 = polynomial_hash(s, BASE, MOD1)
    h2 = polynomial_hash(s, BASE, MOD2)
    return (h1, h2)

4.6 哈希函数对比

教学提示：Python 3.4+ 默认使用 SipHash-1-3 防止 HashDoS 攻击。Rust HashMap 同样默认 SipHash。生产环境若键可控（如内部数据），可用更快的 MurmurHash 或 CityHash。

5. 冲突处理：链地址法

5.1 基本原理

链地址法（Separate Chaining）：每个槽位维护一个链表，冲突的元素追加到链表。

槽位数 m=5, 哈希函数 h(k) = k mod 5

插入: 10, 22, 31, 4, 15, 28

槽 0: 10 -> 15
槽 1: 31
槽 2: 22
槽 3: 28
槽 4: 4

查找 15: h(15)=0, 遍历槽 0 链表找到 15
查找 7:  h(7)=2,  遍历槽 2 链表未找到, 返回不存在

5.2 操作复杂度

在简单均匀哈希假设下，每个槽位的期望链表长度为 $\alpha = n/m$：

当 $\alpha = O(1)$（即 $m = \Theta(n)$）时，所有操作均为 $O(1)$。

5.3 Python 实现

from typing import Any, Optional, Iterator


class ChainingHashTable:
    """链地址法哈希表。

    使用 Python list 作为桶内链表，支持自动扩容。

    Attributes:
        capacity: 槽位数
        size: 当前元素数
        buckets: 槽位数组，每个槽位为 [(key, value), ...] 列表
    """

    def __init__(self, capacity: int = 16, load_factor_threshold: float = 0.75):
        """初始化哈希表。

        Args:
            capacity: 初始槽位数，应为 2 的幂次
            load_factor_threshold: 触发扩容的负载因子阈值
        """
        self.capacity = capacity
        self.size = 0
        self.load_factor_threshold = load_factor_threshold
        self.buckets: list[list[tuple]] = [[] for _ in range(capacity)]

    def _hash(self, key: Any) -> int:
        """计算键的哈希值并映射到槽位。

        使用 Python 内置 hash() 并对容量取模。
        """
        return hash(key) % self.capacity

    def put(self, key: Any, value: Any) -> None:
        """插入或更新键值对。

        若键已存在，更新其值；否则追加到桶链表末尾。
        """
        idx = self._hash(key)
        for i, (k, _) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)
                return
        self.buckets[idx].append((key, value))
        self.size += 1
        if self.size > self.capacity * self.load_factor_threshold:
            self._resize()

    def get(self, key: Any) -> Optional[Any]:
        """查找键对应的值，不存在返回 None。"""
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return None

    def remove(self, key: Any) -> bool:
        """删除键值对，返回是否删除成功。"""
        idx = self._hash(key)
        for i, (k, _) in enumerate(self.buckets[idx]):
            if k == key:
                del self.buckets[idx][i]
                self.size -= 1
                return True
        return False

    def contains(self, key: Any) -> bool:
        """判断键是否存在。"""
        return self.get(key) is not None

    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 k, v in bucket:
                self.put(k, v)

    def __len__(self) -> int:
        return self.size

    def __contains__(self, key: Any) -> bool:
        return self.contains(key)

    def __setitem__(self, key: Any, value: Any) -> None:
        self.put(key, value)

    def __getitem__(self, key: Any) -> Any:
        v = self.get(key)
        if v is None:
            raise KeyError(key)
        return v

    def __iter__(self) -> Iterator:
        for bucket in self.buckets:
            for k, _ in bucket:
                yield k

5.4 C++ 实现

// 链地址法哈希表：C++ 模板实现
#include <vector>
#include <list>
#include <utility>
#include <functional>
#include <stdexcept>

template<typename K, typename V>
class ChainingHashTable {
    std::vector<std::list<std::pair<K, V>>> buckets;
    size_t sz;
    double load_factor_threshold = 0.75;

    size_t hashFunc(const K& key) const {
        return std::hash<K>{}(key) % buckets.size();
    }

    void rehash(size_t new_cap) {
        std::vector<std::list<std::pair<K, V>>> old = std::move(buckets);
        buckets.assign(new_cap, std::list<std::pair<K, V>>());
        sz = 0;
        for (auto& bucket : old) {
            for (auto& kv : bucket) {
                put(kv.first, kv.second);
            }
        }
    }

public:
    ChainingHashTable(size_t cap = 16) : buckets(cap), sz(0) {}

    void put(const K& key, const V& value) {
        size_t idx = hashFunc(key);
        for (auto& kv : buckets[idx]) {
            if (kv.first == key) {
                kv.second = value;
                return;
            }
        }
        buckets[idx].push_back({key, value});
        ++sz;
        if (static_cast<double>(sz) / buckets.size() > load_factor_threshold) {
            rehash(buckets.size() * 2);
        }
    }

    V* get(const K& key) {
        size_t idx = hashFunc(key);
        for (auto& kv : buckets[idx]) {
            if (kv.first == key) return &kv.second;
        }
        return nullptr;
    }

    bool remove(const K& key) {
        size_t idx = hashFunc(key);
        auto& bucket = buckets[idx];
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->first == key) {
                bucket.erase(it);
                --sz;
                return true;
            }
        }
        return false;
    }

    bool contains(const K& key) const {
        size_t idx = hashFunc(key);
        for (const auto& kv : buckets[idx]) {
            if (kv.first == key) return true;
        }
        return false;
    }

    size_t size() const { return sz; }
};

5.5 Java 实现

// 链地址法哈希表：Java 实现
import java.util.*;

public class ChainingHashTable<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final double LOAD_FACTOR_THRESHOLD = 0.75;

    private List<Entry<K, V>>[] buckets;
    private int size;

    private static class Entry<K, V> {
        K key;
        V value;
        Entry(K k, V v) { key = k; value = v; }
    }

    @SuppressWarnings("unchecked")
    public ChainingHashTable() {
        buckets = new List[DEFAULT_CAPACITY];
        for (int i = 0; i < DEFAULT_CAPACITY; i++) {
            buckets[i] = new LinkedList<>();
        }
        size = 0;
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7FFFFFFF) % buckets.length;
    }

    public void put(K key, V value) {
        int idx = hash(key);
        for (Entry<K, V> e : buckets[idx]) {
            if (e.key.equals(key)) {
                e.value = value;
                return;
            }
        }
        buckets[idx].add(new Entry<>(key, value));
        size++;
        if ((double) size / buckets.length > LOAD_FACTOR_THRESHOLD) {
            resize();
        }
    }

    public V get(K key) {
        int idx = hash(key);
        for (Entry<K, V> e : buckets[idx]) {
            if (e.key.equals(key)) return e.value;
        }
        return null;
    }

    public boolean remove(K key) {
        int idx = hash(key);
        Iterator<Entry<K, V>> it = buckets[idx].iterator();
        while (it.hasNext()) {
            if (it.next().key.equals(key)) {
                it.remove();
                size--;
                return true;
            }
        }
        return false;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        List<Entry<K, V>>[] old = buckets;
        buckets = new List[old.length * 2];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new LinkedList<>();
        }
        size = 0;
        for (List<Entry<K, V>> bucket : old) {
            for (Entry<K, V> e : bucket) {
                put(e.key, e.value);
            }
        }
    }

    public int size() { return size; }
}

5.6 优势与劣势

优势：

1. 实现简单：每个槽位挂链表，无需删除标记；
2. 删除方便：直接从链表删除节点，$O(1)$（已知节点）；
3. 不受负载因子硬限制：$\alpha$ 可大于 1，仅影响性能；
4. 缓存友好性中等：链表节点离散分配，但槽位数组连续。

劣势：

1. 额外指针开销：每个元素多存一个指针（Python 元组中无显式指针，C++ std::list 每节点 2 个指针）；
2. 缓存不友好：链表节点离散分布，遍历链表时缓存命中率低；
3. 小负载因子时空间浪费：$\alpha$ 小时槽位利用率低。

6. 冲突处理：开放寻址法

6.1 基本原理

开放寻址法（Open Addressing）：所有元素存储在数组本身中，冲突时按探测序列寻找下一个空槽。

探测函数：$h(k, i) = (h'(k) + c(i)) \mod m$

其中 $h'(k)$ 是辅助哈希函数，$c(i)$ 是探测序列第 $i$ 项。

6.2 线性探测

线性探测（Linear Probing）：$h(k, i) = (h'(k) + i) \mod m$

槽位数 m=7, h'(k) = k mod 7

插入: 10, 22, 31, 4

10: h'(10)=3, 槽 3 空 -> 放入槽 3
22: h'(22)=1, 槽 1 空 -> 放入槽 1
31: h'(31)=3, 槽 3 被占 -> 探测槽 4 空 -> 放入槽 4
4:  h'(4)=4,  槽 4 被占 -> 探测槽 5 空 -> 放入槽 5

数组: [_, 22, _, 10, 31, 4, _]

一次聚集（Primary Clustering）：线性探测导致连续占用区域越来越长，新元素落入聚集区需多次探测。聚集区越长，越容易继续增长（“富者愈富”）。

6.3 二次探测

二次探测（Quadratic Probing）：$h(k, i) = (h'(k) + c_1 \cdot i + c_2 \cdot i^2) \mod m$

典型取 $c_1 = c_2 = 1/2$，即 $h(k, i) = (h'(k) + i(i+1)/2) \mod m$。

优势：缓解一次聚集，探测序列跳跃式分布。

劣势：二次聚集（Secondary Clustering）—— 不同初始位置的键共享探测序列。

6.4 双重哈希

双重哈希（Double Hashing）：$h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m$

$h_2(k)$ 必须与 $m$ 互素。常用做法：

• 取 $m = 2^p$，$h_2(k)$ 返回奇数；
• 取 $m$ 为质数，$h_2(k) = 1 + (k \mod (m-1))$。

优势：几乎消除聚集现象，是开放寻址法的最优选择。

6.5 Python 实现

from typing import Any, Optional


class OpenAddressingHashTable:
    """开放寻址法哈希表（线性探测 + 删除标记）。

    Attributes:
        capacity: 槽位数
        size: 当前元素数
        keys: 键数组
        values: 值数组
        deleted: 删除标记（用于区分空槽与已删除槽）
    """

    _DELETED = object()  # 哨兵对象，标记已删除槽位

    def __init__(self, capacity: int = 16, load_factor_threshold: float = 0.7):
        self.capacity = capacity
        self.size = 0
        self.load_factor_threshold = load_factor_threshold
        self.keys: list = [None] * capacity
        self.values: list = [None] * capacity

    def _hash(self, key: Any) -> int:
        return hash(key) % self.capacity

    def _probe(self, key: Any, i: int) -> int:
        """线性探测：h(k, i) = (h'(k) + i) mod m。"""
        return (self._hash(key) + i) % self.capacity

    def _find_slot(self, key: Any) -> int:
        """查找键应插入或所在的位置。

        返回第一个空槽、已删除槽或键已存在的位置。
        """
        i = 0
        first_deleted = -1
        while True:
            idx = self._probe(key, i)
            if self.keys[idx] is None:
                # 找到空槽，返回先前记录的已删除槽（若有）或当前空槽
                return first_deleted if first_deleted != -1 else idx
            if self.keys[idx] is self._DELETED:
                # 记录第一个已删除槽
                if first_deleted == -1:
                    first_deleted = idx
            elif self.keys[idx] == key:
                # 键已存在
                return idx
            i += 1
            if i >= self.capacity:
                # 表已满（仅当无删除槽时发生）
                if first_deleted != -1:
                    return first_deleted
                raise RuntimeError("Hash table is full")

    def _find_existing(self, key: Any) -> Optional[int]:
        """查找键已存在的位置，不存在返回 None。"""
        i = 0
        while True:
            idx = self._probe(key, i)
            if self.keys[idx] is None:
                return None
            if self.keys[idx] is not self._DELETED and self.keys[idx] == key:
                return idx
            i += 1
            if i >= self.capacity:
                return None

    def put(self, key: Any, value: Any) -> None:
        if self.size >= self.capacity * self.load_factor_threshold:
            self._resize()
        idx = self._find_slot(key)
        if self.keys[idx] is None or self.keys[idx] is self._DELETED:
            self.keys[idx] = key
            self.size += 1
        self.values[idx] = value

    def get(self, key: Any) -> Optional[Any]:
        idx = self._find_existing(key)
        return self.values[idx] if idx is not None else None

    def remove(self, key: Any) -> bool:
        idx = self._find_existing(key)
        if idx is None:
            return False
        self.keys[idx] = self._DELETED
        self.values[idx] = None
        self.size -= 1
        return True

    def _resize(self) -> None:
        old_keys, old_values = self.keys, self.values
        self.capacity *= 2
        self.keys = [None] * self.capacity
        self.values = [None] * self.capacity
        self.size = 0
        for k, v in zip(old_keys, old_values):
            if k is not None and k is not self._DELETED:
                self.put(k, v)

6.6 探测序列对比

教学提示：线性探测因缓存友好性被广泛使用（Python dict、Google flat_hash_map）。现代 CPU 缓存预取使连续访问的线性探测在实际中比理论更优。

7. 性能理论分析

7.1 链地址法 ASL 推导

定理 7.1：在简单均匀哈希假设下，链地址法的期望查找代价为：

• 查找成功：$\Theta(1 + \alpha/2)$
• 查找失败：$\Theta(1 + \alpha)$

证明：

设 $n$ 个键均匀分布在 $m$ 个槽位，每个槽位的期望链表长度为 $\alpha = n/m$。

查找失败：对任意键 $k$，$h(k)$ 等概率地映射到任一槽位，需遍历该槽位的整个链表。期望长度为 $\alpha$，加上哈希计算 $O(1)$，总代价 $\Theta(1 + \alpha)$。

查找成功：设键 $k$ 在槽位 $h(k)$ 的链表中第 $i$ 个位置（$i$ 从 1 开始）。链表中 $k$ 之前的元素数等于”在 $k$ 之后插入且哈希到同一槽位”的元素数。由于每个其他键哈希到该槽位的概率为 $1/m$，期望数为 $(n-1)/m \approx \alpha$。但平均而言 $k$ 在链表中部，所以期望比较次数为 $\alpha/2$，总代价 $\Theta(1 + \alpha/2)$。

$\square$

7.2 开放寻址法 ASL 推导

定理 7.2：在均匀哈希假设下，开放寻址法的期望探测次数为：

• 查找成功：$\dfrac{1}{\alpha} \ln \dfrac{1}{1-\alpha}$
• 查找失败：$\dfrac{1}{1-\alpha}$

证明：

均匀哈希假设：每次探测的位置独立均匀分布于 $m$ 个槽位。

查找失败：设探测序列长度为 $X$。第 $i$ 次探测命中空槽的概率为 $\dfrac{m - n - (i-1)}{m - (i-1)}$。在 $n < m$ 时，简化分析得：

$\Pr[X \geq i] \leq \left(\dfrac{n}{m}\right)^{i-1} = \alpha^{i-1}$

期望探测次数：

$E[X] = \sum_{i=1}^{\infty} \Pr[X \geq i] = \sum_{i=0}^{\infty} \alpha^i = \dfrac{1}{1-\alpha}$

查找成功：成功查找的期望探测次数等于插入时的探测次数。对第 $j$ 个插入的元素（此时表中有 $j-1$ 个元素，负载因子 $\alpha_j = (j-1)/m$），期望探测次数为 $\dfrac{1}{1-\alpha_j}$。对 $n$ 次插入取平均：

$\text{ASL}_{\text{success}} = \dfrac{1}{n} \sum_{j=0}^{n-1} \dfrac{1}{1 - j/m} = \dfrac{1}{\alpha} \int_0^{\alpha} \dfrac{dx}{1-x} = \dfrac{1}{\alpha} \ln \dfrac{1}{1-\alpha}$

$\square$

7.3 数值对比

关键观察：

• 链地址法在 $\alpha = 1$ 时仍可接受（ASL $\approx 2$）；
• 开放寻址法在 $\alpha > 0.7$ 时性能急剧下降；
• 生产环境推荐：链地址法 $\alpha \leq 0.75$，开放寻址法 $\alpha \leq 0.7$。

7.4 摊还分析

定理 7.3：扩容采用容量翻倍策略时，put 操作的摊还代价为 $O(1)$。

证明（聚合法数）：

设容量从 $m$ 扩容到 $2m$，扩容代价 $O(m)$（重哈希 $m$ 个元素）。两次扩容之间至少有 $m/2$ 次 put 操作（从 $\alpha = 0.5$ 到 $\alpha = 1$）。总代价：

$\text{总代价} = \underbrace{m/2 \cdot O(1)}_{\text{插入代价}} + \underbrace{O(m)}_{\text{扩容代价}} = O(m)$

平均每次 put：

$\text{摊还代价} = \dfrac{O(m)}{m/2} = O(1)$

$\square$

8. 扩容与再哈希

8.1 扩容触发条件

当负载因子超过阈值时触发扩容：

8.2 一次性扩容

一次性扩容（One-shot Resize）：分配新数组，遍历旧表所有元素重哈希到新表，释放旧表。

def _resize(self):
    """一次性扩容：阻塞直至完成。"""
    old_buckets = self.buckets
    self.capacity *= 2
    self.buckets = [[] for _ in range(self.capacity)]
    self.size = 0
    for bucket in old_buckets:
        for k, v in bucket:
            self.put(k, v)

问题：扩容瞬间阻塞，对延迟敏感场景不可接受（如 Redis 单线程模型）。

8.3 渐进式扩容

渐进式扩容（Incremental Rehashing）：Redis dict.c 的核心创新，将扩容分摊到多次操作中：

1. 触发扩容：分配新表 ht[1]，旧表保留为 ht[0]；
2. 渐进迁移：每次 put/get/delete 操作迁移少量（如 1 个）槽位；
3. 查找策略：先查 ht[1]，再查 ht[0]；
4. 完成释放：所有槽位迁移完成后，释放 ht[0]，ht[1] 成为 ht[0]。

class RedisLikeDict:
    """Redis 风格渐进式扩容哈希表（简化版）。"""

    def __init__(self, capacity: int = 16):
        self.ht = [{}, {}]  # ht[0] 旧表, ht[1] 新表
        self.ht[0] = {i: [] for i in range(capacity)}
        self.capacity = [capacity, 0]
        self.size = [0, 0]
        self.rehash_idx = -1  # -1 表示未在扩容

    def _is_rehashing(self) -> bool:
        return self.rehash_idx != -1

    def _trigger_rehash(self) -> None:
        """触发扩容：分配新表。"""
        new_cap = self.capacity[0] * 2
        self.ht[1] = {i: [] for i in range(new_cap)}
        self.capacity[1] = new_cap
        self.rehash_idx = 0

    def _rehash_step(self) -> None:
        """执行一次渐进式迁移：迁移旧表一个槽位。"""
        if not self._is_rehashing():
            return
        # 跳过空槽
        while self.rehash_idx < self.capacity[0] and not self.ht[0][self.rehash_idx]:
            self.rehash_idx += 1
        if self.rehash_idx < self.capacity[0]:
            for k, v in self.ht[0][self.rehash_idx]:
                idx = hash(k) % self.capacity[1]
                self.ht[1][idx].append((k, v))
                self.size[1] += 1
            self.ht[0][self.rehash_idx] = []
            self.rehash_idx += 1
        # 检查是否完成
        if self.rehash_idx >= self.capacity[0]:
            self.ht[0] = self.ht[1]
            self.capacity[0] = self.capacity[1]
            self.size[0] = self.size[1]
            self.ht[1] = {}
            self.capacity[1] = 0
            self.size[1] = 0
            self.rehash_idx = -1

    def put(self, key, value):
        if self._is_rehashing():
            idx = hash(key) % self.capacity[1]
            for i, (k, _) in enumerate(self.ht[1][idx]):
                if k == key:
                    self.ht[1][idx][i] = (key, value)
                    return
            self.ht[1][idx].append((key, value))
            self.size[1] += 1
        else:
            idx = hash(key) % self.capacity[0]
            for i, (k, _) in enumerate(self.ht[0][idx]):
                if k == key:
                    self.ht[0][idx][i] = (key, value)
                    return
            self.ht[0][idx].append((key, value))
            self.size[0] += 1
            if self.size[0] > self.capacity[0]:
                self._trigger_rehash()
        # 每次操作执行一次渐进迁移
        self._rehash_step()

    def get(self, key):
        if self._is_rehashing():
            idx = hash(key) % self.capacity[1]
            for k, v in self.ht[1][idx]:
                if k == key:
                    return v
        idx = hash(key) % self.capacity[0]
        for k, v in self.ht[0][idx]:
            if k == key:
                return v
        return None

教学提示：Redis 渐进式 rehash 是单线程模型下避免阻塞的典范。每次 CRUD 操作迁移 1 个槽位，加上定时任务每次迁移 100 个槽位，保证扩容过程对用户透明。

9. 一致性哈希

9.1 问题背景

分布式缓存场景：$N$ 台缓存服务器，需要将 $K$ 个键均匀分布。传统方案：

$\text{server} = h(\text{key}) \mod N$

问题：当 $N$ 变化（增减节点）时，几乎所有键都需要重新映射，缓存失效雪崩。

9.2 一致性哈希方案

一致性哈希（Consistent Hashing，Karger et al. 1997）：将哈希值空间组织为环（$0 \sim 2^{32}-1$），每个节点和键都映射到环上。键由顺时针方向最近的节点负责。

哈希环 (m = 2^32):

         Node A (v1)
        /            \
   Key1              Node B (v1)
      |                  |
   Node C (v1)       Key2
        \            /
         Node A (v2)

Key1 -> Node A (顺时针最近)
Key2 -> Node B (顺时针最近)

9.3 虚拟节点

虚拟节点（Virtual Node）：为每个物理节点分配多个虚拟节点（如 200 个），使数据分布更均匀。

import hashlib
import bisect


class ConsistentHashRing:
    """一致性哈希环（带虚拟节点）。

    Attributes:
        ring: 排序的哈希值列表
        ring_map: 哈希值到节点的映射
        vnodes: 每个物理节点的虚拟节点数
    """

    def __init__(self, vnodes: int = 200):
        self.ring: list[int] = []
        self.ring_map: dict[int, str] = {}
        self.vnodes = vnodes

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node: str) -> None:
        """添加节点：将 vnodes 个虚拟节点加入环。"""
        for i in range(self.vnodes):
            vname = f"{node}#{i}"
            h = self._hash(vname)
            self.ring_map[h] = node
            bisect.insort(self.ring, h)

    def remove_node(self, node: str) -> None:
        """移除节点：删除该节点的所有虚拟节点。"""
        for i in range(self.vnodes):
            vname = f"{node}#{i}"
            h = self._hash(vname)
            if h in self.ring_map:
                del self.ring_map[h]
                idx = bisect.bisect_left(self.ring, h)
                if idx < len(self.ring) and self.ring[idx] == h:
                    self.ring.pop(idx)

    def get_node(self, key: str) -> str:
        """查找键对应的节点。"""
        if not self.ring:
            raise RuntimeError("No nodes in ring")
        h = self._hash(key)
        idx = bisect.bisect_right(self.ring, h)
        if idx == len(self.ring):
            idx = 0
        return self.ring_map[self.ring[idx]]

9.4 节点增减的影响

节点增加：只影响新节点到前一个节点之间的键，迁移量为 $O(K/N)$。

节点减少：只影响被删节点到前一个节点之间的键，迁移到下一个节点。

跨模块引用：一致性哈希是分布式系统的基础原语，参见 分布式系统。

10. 变体与扩展

10.1 布隆过滤器

布隆过滤器（Bloom Filter，Bloom 1970）：用 $k$ 个独立哈希函数 + 位图判重，允许少量假阳性，不假阴性。

结构：

• 位数组 bit[0..m-1]，初始全 0；
• $k$ 个独立哈希函数 $h_1, h_2, \ldots, h_k$。

插入：对元素 $x$，将 bit[h_i(x)] = 1 对所有 $i$ 置位。

查询：若所有 bit[h_i(x)] == 1，则”可能存在”（假阳性）；若任一为 0，则”一定不存在”。

假阳性率：

$P_{\text{fp}} \approx \left(1 - e^{-kn/m}\right)^k$

其中 $n$ 为元素数，$m$ 为位数，$k$ 为哈希函数数。最优 $k = (m/n) \ln 2$。

import mmh3  # MurmurHash3
from typing import Iterable


class BloomFilter:
    """布隆过滤器：支持 O(1) 判重，允许假阳性。"""

    def __init__(self, capacity: int, error_rate: float = 0.001):
        """初始化布隆过滤器。

        Args:
            capacity: 预期元素数 n
            error_rate: 可接受假阳性率 p
        """
        # 计算最优 m 和 k
        import math
        self.m = int(-capacity * math.log(error_rate) / (math.log(2) ** 2))
        self.k = int(self.m / capacity * math.log(2))
        self.bit_array = [False] * self.m

    def add(self, item: str) -> None:
        """添加元素到布隆过滤器。"""
        for i in range(self.k):
            idx = mmh3.hash(item, i) % self.m
            self.bit_array[idx] = True

    def contains(self, item: str) -> bool:
        """判断元素是否可能存在（可能假阳性）。"""
        for i in range(self.k):
            idx = mmh3.hash(item, i) % self.m
            if not self.bit_array[idx]:
                return False
        return True