高级数据结构-02：布隆过滤器

预备知识

集合类

集合（Set）抽象数据类型对应数学中的集合概念。集合由互异值组成，元素之间没有固定顺序。

集合名称	数学表示与内容枚举	集合内涵描述
digits	$\{0,1,2,3,4,5,6,7,8,9\}$	十进制基础数字集合
evens	$\{0,2,4,6,8\}$	10 以内的正偶数集合
odds	$\{1,3,5,7,9\}$	10 以内的正奇数集合
primes	$\{2,3,5,7\}$	10 以内的素数集合
squares	$\{0,1,4,9\}$	10 以内的完全平方数集合
colors	$\{\text{red}, \text{yellow}, \text{green}, \text{cyan}, \text{blue}, \text{magenta}\}$	基础颜色域
primary	$\{\text{red}, \text{green}, \text{blue}\}$	光学三原色集合
secondary	$\{\text{yellow}, \text{cyan}, \text{magenta}\}$	次级混合色集合
$R$	$\{x \mid x \text{ is a real number}\}$	实数域连续集合
$Z$	$\{x \mid x \text{ is an integer}\}$	整数域离散集合
$N$	$\{x \mid x \text{ is an integer and } x \ge 0\}$	自然数（非负整数）集合
$\emptyset$	$\text{Empty Set}$	不包含任何元素的空集

集合类通常支持添加元素、移除元素、成员测试，以及并集、交集、差集、子集判断、相等性测试等集合运算。

集合关系运算

判断两个集合是否相等，充分必要条件是二者互为子集。

/*
 * 运算符: ==
 * 用法: set1 == set2
 * 逻辑: 如果 set1 和 set2 包含完全相同的元素，则返回 true。
 * 备注: 函数签名末尾的 const 关键字承诺该操作不会修改调用方（set1）的内部状态。
 */
// 参数 set2 是右操作数；返回值表示两个集合的成员资格是否完全一致。
bool operator==(const Set & set2) const;

/*
 * 运算符: !=
 * 用法: set1 != set2
 * 逻辑: 返回 true 如果 set1 和 set2 在元素构成上存在任何差异。
 */
// 通常可实现为 !(*this == set2)，同样不修改当前集合。
bool operator!=(const Set & set2) const;

集合相等不取决于底层内存表示，而取决于成员资格是否一致。即使两个集合分别由树和哈希表实现，只要任意元素对二者的 contains 结果一致，它们在抽象数据类型层面就是同一个集合。因此，用“互为子集”实现相等判断，本质上是在检查是否存在遗漏或多余元素。

集合代数运算

并集用于合并两个集合并消除重复项；交集用于保留共同元素；差集用于保留只属于左侧集合的元素。

/*
 * 运算符: + (并集 Union)
 * 用法: set1 + set2 或 set1 + element
 * 逻辑: 返回一个全新的集合，包含至少出现在两个运算集合之一中的所有元素。
 *       针对重载的第二个版本，右侧操作数可为单一值类型，表示向集合中追加单一元素并返回新集合。
 */
// 集合并集：返回新集合，不修改当前集合或 set2。
Set operator+(const Set & set2) const;
// 元素插入式并集：返回包含 element 的新集合，不修改当前集合。
Set operator+(const ValueType & element) const;

/*
 * 运算符: += (原地并集)
 * 用法: set1 += set2; 或 set1 += value;
 * 逻辑: 将 set2 中的所有元素（或单一的 value）直接合并进入 set1 中，修改 set1 的内部状态。
 */
// 原地合并 set2，并返回当前集合引用以支持链式调用。
Set & operator+=(const Set & set2);
// 原地插入单个元素，并返回当前集合引用。
Set & operator+=(const ValueType & value);

/*
 * 运算符: * 与 *= (交集 Intersection)
 * 用法: set1 * set2; set1 *= set2;
 * 逻辑: 返回或原地修改为同时存在于两个集合中的元素集合。
 *       *= 操作会移除 set1 中所有未在 set2 中出现的元素。
 */
// 返回交集副本，不修改参与运算的两个集合。
Set operator*(const Set & set2) const;
// 将当前集合原地收缩为与 set2 的交集。
Set & operator*=(const Set & set2);

/*
 * 运算符: - 与 -= (差集 Set Difference)
 * 用法: set1 - set2; set1 -= set2;
 * 逻辑: 返回或原地修改为出现在 set1 中，但绝对不包含在 set2 中的元素集合。
 */
// 返回当前集合相对 set2 的差集副本。
Set operator-(const Set & set2) const;
// 返回删除 element 后的集合副本。
Set operator-(const ValueType & element) const;
// 原地删除 set2 中出现的所有元素。
Set & operator-=(const Set & set2);

指针与泛型排序

实现集合时，系统必须能够比较值类型元素。对于整数、字符串等内置类型，内置的 == 与 < 运算符通常足够；对于用户自定义的复合类型，关系运算符未必已经重载，因此接口需要允许客户端在构造集合时传入自定义比较函数。

冯·诺伊曼架构提出了存储程序模型。在这一模型中，指令代码与数据统一存储在内存中。函数的机器指令在进程地址空间中有确定的入口地址，因此可以用指针变量保存该地址，并在运行时调用对应函数。

以下声明方式展示了指针与不同类型函数的结合：

声明语法	语义解析
int n;	声明 n 为一个普通整型变量。
int *pn;	声明 pn 为一个指向整型数据的指针。
int f();	声明 f 为一个没有参数且返回整型结果的函数。
int *g();	声明 g 为一个没有参数且返回整型指针的函数。
int (*fn)();	声明 fn 为一个指向函数的指针，该函数无参数且返回整型。
int (*cmp)(int, int);	声明 cmp 为一个指向函数的指针，该函数接受两个整型参数并返回一个整型结果。

可以基于模板构建泛型排序函数。下面的实现采用选择排序，并通过函数指针 cmp 决定元素的相对顺序：

/*
 * 泛型排序函数 (支持自定义比较逻辑)
 * 参数 vec: 待排序的泛型向量引用
 * 参数 cmp: 函数指针，接受两个 ValueType，返回负数(小于), 0(等于), 正数(大于)
 */
// ValueType 由调用点推导，使同一份排序逻辑适用于不同元素类型。
template <typename ValueType>
void sort(Vector<ValueType> & vec, int (*cmp)(ValueType, ValueType)) {
    // lh 是当前要填入最小元素的位置。
    for (int lh = 0; lh < vec.size() - 1; lh++) {
        // rh 保存未排序区间中当前已知最小元素的索引。
        int rh = lh;
        // 扫描 lh 右侧的未排序区间。
        for (int i = lh + 1; i < vec.size(); i++) {
            // cmp < 0 表示 vec[i] 应排在 vec[rh] 之前。
            if (cmp(vec[i], vec[rh]) < 0) {
                // 更新当前最小元素位置。
                rh = i;
            }
        }
        // 将未排序区间的最小元素交换到 lh 位置。
        ValueType temp = vec[lh];
        vec[lh] = vec[rh];
        vec[rh] = temp;
    }
}

如果客户端希望按照字符串长度排序，可以定义如下比较函数并将其作为参数传入：

int lengthCompare(string s1, string s2) {
    // s1 较短时返回负数，表示 s1 应排在 s2 前面。
    if (s1.length() < s2.length()) return -1;
    // s1 较长时返回正数，表示 s1 应排在 s2 后面。
    if (s1.length() > s2.length()) return 1;
    // 长度相等时返回 0，排序算法可视为二者等价。
    return 0;
}

// 将函数名作为函数指针传入，排序逻辑将按字符串长度比较。
sort(strvec, lengthCompare);

接口层通常提供默认模板文件 cmpfn.h。其中的 operatorCmp 函数默认使用基础类型的 == 与 < 运算符进行判定，使集合框架可直接用于常见类型。

集合数据结构

实现集合时，常见底层结构有两类：

1. 哈希表： 利用哈希函数将元素映射到桶中。其优势是元素添加与成员测试的平均时间复杂度为 $O(1)$；缺点是哈希映射破坏了元素的内在顺序，难以支持按值有序迭代。
2. 平衡二叉树： 红黑树、AVL 树等结构可以提供最坏情况下的 $O(\log N)$ 性能。虽然单次操作的渐进复杂度高于哈希表，但它保留了节点偏序关系，适合实现有序迭代器。

基于 Map 构建 Set

集合（Set）可以视为只有键（Key）而没有有效值（Value）的字典（Map），因此可以将 Set 的底层私有成员定义为一个 Map 实例。为了降低占位开销，映射的值类型可以选取 C++ 中较小的内置类型 char，并在逻辑中忽略该字符的具体内容。

头文件 setpriv.h 中的私有成员声明如下：

// 底层使用 Map 保存集合元素；ValueType 是真实元素类型。
// char 只用于满足 Map 的 key-value 接口，不承载集合语义。
Map<ValueType, char> map;

这里的 Map<ValueType, char> 可以看作“用字典模拟集合”。ValueType 是实际集合元素，char 只用于满足 Map 的键值对接口要求。只要某个键存在于 map 中，就代表对应元素属于集合；占位字符的具体取值不参与集合语义。

在 setimpl.cpp 中，基础集合操作可以直接代理给内部 map 对象：

// 构造函数接收元素比较函数，并直接传递给底层 map。
template <typename ValueType>
Set<ValueType>::Set(int (*cmp)(ValueType, ValueType)) : map(cmp) {
    // 函数体为空，因为 map 已在初始化列表中完成构造。
}

// 集合大小等于底层 map 中键的数量。
template <typename ValueType>
int Set<ValueType>::size() const {
    return map.size();
}

// 添加元素时只关心键是否存在，value 位置写入占位字符。
template <typename ValueType>
void Set<ValueType>::add(ValueType element) {
    map.put(element, '\0');
}

集合相等可以通过子集关系实现：只有当集合 A 是集合 B 的子集，同时集合 B 也是集合 A 的子集时，二者才相等。

// 两个集合相等当且仅当二者互为子集。
template <typename ValueType>
bool Set<ValueType>::operator==(const Set & s2) const {
    return isSubsetOf(s2) && s2.isSubsetOf(*this);
}

// 判断当前集合是否为 s2 的子集。
template <typename ValueType>
bool Set<ValueType>::isSubsetOf(const Set & s2) const {
    // 遍历当前集合的每个元素。
    foreach (ValueType value in *this) {
        // 只要存在一个元素不属于 s2，子集关系立即失败。
        if (!s2.contains(value)) return false;
    }
    // 所有元素都能在 s2 中找到，子集关系成立。
    return true;
}

集合并集（operator+）同样依赖底层迭代机制。若两个集合的比较函数指针不一致，则它们不具备可比性，需要抛出运行时错误。实现时先复制当前集合，再迭代合并目标集合元素，最后返回合并后的结果。获取集合首元素（first()）时，直接调用底层迭代器的初始位置 begin() 并解引用。

// 返回当前集合与 set2 的并集副本。
template <typename ValueType>
Set<ValueType> Set<ValueType>::operator+(const Set & set2) const {
    // 比较函数不同会导致元素顺序和等价关系不一致，因此拒绝合并。
    if (cmpFn != set2.cmpFn) {
        error("Sets have different comparison functions");
    }
    // 先复制当前集合，避免修改左操作数。
    Set<ValueType> set = *this;
    // 逐个插入 set2 的元素；集合语义会自动去重。
    foreach (ValueType value in set2) {
        set.add(value);
    }
    // 返回合并后的新集合。
    return set;
}

// 返回集合中的第一个元素。
template <typename ValueType>
ValueType Set<ValueType>::first() {
    // 空集合没有可返回元素，直接报错。
    if (isEmpty()) error("first: set is empty");
    // begin() 指向底层有序结构中的首个元素，解引用得到元素值。
    return *begin();
}

特征向量与字符集合

在编译器设计或词法扫描器中，经常需要定义由定界符组成的字符集合（Set<char>）。这类集合的值域有限，可以使用专用表示减少通用容器带来的开销。

对于值域有限的数据类型，例如仅有 256 个状态的 ASCII 字符集，树结构或哈希表会产生较高的对象管理开销。常见做法是采用特征向量，也称位向量。

特征向量的思想是：对于小整数或字符集，用一个位（Bit）表示一个元素的存在状态。状态 1 表示包含，状态 0 表示不包含。由于每个 ASCII 码都可以映射为 0 到 255 的偏移量，一个字符集合可以压缩进一段 256 位的连续内存区域。

CPU 可以将位序列载入寄存器，并通过按位运算执行集合代数计算。这样，并、交、差等操作可以由少量机器指令完成。

运算符	描述与位级操作行为	在特征向量集合代数中的映射意义
&	按位与： 对齐的两操作数对应位同为 1，结果位才为 1，否则为 0。	集合交集： 只有同时属于两个集合的元素，其特征位才会保留为 1。该技术在底层常被称为掩码（Masking）截取。
|	按位或： 对齐的两操作数对应位只要有一个为 1，结果位即为 1。	集合并集： 合并两个特征向量，使得出现在任一集合中的元素均被标记。
^	按位异或： 对齐的两操作数对应位的值不相同，结果位即为 1。	集合对称差： 提取属于集合 A 或属于集合 B，但不同时属于二者的元素。
~	按位非： 单操作数取反，0 变为 1，1 变为 0。	集合的补集： 标记所有未被当前集合涵盖的全集元素。
<<	左移： 所有位整体向左移动，低位补 0。	用于快速定位和生成特定元素的特征掩码（如 1 << charValue）。
>>	右移： 所有位整体向右移动（无符号数执行逻辑移位）。	用于快速扫描或状态降维。

结合上述运算符，可以组合出复杂集合操作。例如，集合 $A$ 与集合 $B$ 的差集，即出现在 $A$ 中但不属于 $B$ 的元素，可以通过 A & (~B) 实现。先用 ~B 得到不属于 $B$ 的元素标记，再与 $A$ 做 & 运算，结果即为差集。

特征向量的关键是把“元素是否存在”从一次对象查找压缩成一次位判断。例如字符 c 的 ASCII 码为 99，就把第 99 位看作 c 的存在标记。集合运算于是变成了整段机器字上的并行位运算：CPU 一次 & 或 | 处理的不是一个元素，而是一组元素的存在状态。

布隆过滤器

特征向量通过限制值域换取了较高性能。但当全集规模很大时，直接建立特征向量会消耗大量内存；若使用哈希表等传统结构存储原始数据，内存成本也可能过高。

布隆过滤器用少量准确性损失换取大规模数据集成员测试中的空间压缩能力。

容许的错误率 (P)	哈希区域大小 N (Bits)	避免的不必要磁盘访问百分比
1/2	72,800	45.0%
1/4	145,600	67.5%
1/8	218,400	78.7%
1/16	291,200	84.4%
1/32	364,000	87.2%

定义

布隆过滤器由一条初始状态全为 0 的位数组构成，数组长度为 $m$。同时定义 $k$ 个相互独立的哈希函数 $h_1, h_2, \dots, h_k$。这些函数应具有较好的离散性，将输入元素尽量均匀地映射到 $\{0, 1, \dots, m-1\}$。

• 插入： 将元素 $x$ 分别输入 $k$ 个哈希函数，得到 $k$ 个索引，并将位数组中对应位置全部置为 1。由于系统不记录具体元素与比特位之间的来源关系，不同元素可能将同一位重复置为 1。

• 查询： 检验未知元素 $y$ 是否属于集合时，按相同规则对 $y$ 进行 $k$ 次哈希映射。

  • 确定排除： 如果 $k$ 个目标索引位置中任意一位为 0，则元素 $y$ 一定不在集合中。若它曾被插入，这些位置都应已被置为 1。这就是布隆过滤器的无假阴性。
  • 概率存在： 如果 $k$ 个目标位均为 1，系统只能判断元素 $y$ 可能在集合中。因为这些位置可能由其他元素在历史插入中覆盖。这种将非成员误判为成员的情况称为假阳性。

  布隆过滤器的查询结果只有两种语义：“一定不存在”和“可能存在”。它不会把已经插入过的元素误判为不存在，因为插入只会把位从 0 改成 1，不会反向清空；但它可能把没插入过的元素误判为存在，因为多个元素的哈希足迹可能刚好把相关位置都覆盖成 1。参数 $m$ 控制位数组空间，$n$ 控制已插入规模，$k$ 控制每个元素留下多少个哈希足迹，三者共同决定误报率。

假阳性率

假设所有哈希函数相互独立，且索引分布足够均匀，可以得到如下规律：

1. 单次映射后的空闲概率： 执行一次哈希操作时，某个特定位被命中并置为 1 的概率是 $\frac{1}{m}$。相反，该位保持 0 的概率为：

   $$1 - \frac{1}{m}$$

2. 单个元素插入后的空闲概率： 插入一个元素会触发 $k$ 次独立哈希，该特定位仍保持 0 的概率为：

   $$\left(1 - \frac{1}{m}\right)^k$$

3. n 个元素插入后的空闲概率极限： 插入 $n$ 个不同元素后，共执行 $kn$ 次映射。该位始终未被置为 1 的精确概率是：

   $$\left(1 - \frac{1}{m}\right)^{kn}$$

   当 $m$ 较大时，由 $\lim_{x \to \infty} (1 - \frac{1}{x})^{-x} = e$，可以近似为：

   $$\left(1 - \frac{1}{m}\right)^{kn} = \left[ \left( 1 - \frac{1}{m} \right)^{-m} \right]^{-\frac{kn}{m}} \approx e^{-\frac{kn}{m}}$$

   因此，插入全部 $n$ 个元素后，任意比特位为 1 的期望概率 $p_{\text{set}}$ 可表示为：

   $$p_{\text{set}} \approx 1 - e^{-\frac{kn}{m}}$$

对未插入元素 $y$ 进行查询时，发生假阳性的条件是：$y$ 经 $k$ 个哈希函数映射后，指向的 $k$ 个比特位都已经为 1。若近似认为这 $k$ 个位状态相互独立，假阳性概率 $f$ 为：

$$f = (p_{\text{set}})^k \approx \left( 1 - e^{-\frac{kn}{m}} \right)^k$$

由公式可知，位数组 $m$ 越长，哈希空间越稀疏，错误率越低；插入规模 $n$ 越大，数组越拥挤，错误率越高。哈希函数数量 $k$ 同时影响位数组填充率和查询时需要匹配的位数，因此存在理论最优值。

最优 k 选取

给定 $m$ 与 $n$ 时，需要选择使假阳性概率 $f$ 最小的 $k$。

令位为 1 的概率 $p = 1 - e^{-\frac{kn}{m}}$，则误报率为：

$$f = p^k$$

对等式两侧同时取自然对数：

$$\ln(f) = k \ln(p)$$

由 $1 - p = e^{-\frac{kn}{m}}$ 可得 $k = -\frac{m}{n} \ln(1 - p)$。将该表达式代回目标函数，得到仅关于 $p$ 的函数 $g(p)$。最小化 $g(p)$ 等价于最小化误报率 $\ln(f)$：

$$g(p) = -\frac{m}{n} \ln(1 - p) \ln(p)$$

由于系数为负，极小化 $g(p)$ 等价于极大化 $H(p) = \ln(p) \ln(1 - p)$。函数 $\ln(p)$ 与 $\ln(1 - p)$ 关于 $p = \frac{1}{2}$ 对称。求解一阶导数 $\frac{d}{dp}[\ln(p)\ln(1-p)] = \frac{\ln(1-p)}{p} - \frac{\ln(p)}{1-p} = 0$，可得驻点 $p = \frac{1}{2}$。

将 $p = \frac{1}{2}$ 代回到我们对 $k$ 的关系式中：

$$1 - e^{-\frac{kn}{m}} = \frac{1}{2} \implies e^{-\frac{kn}{m}} = \frac{1}{2}$$

两边取对数，得到最优哈希函数个数：

$$-\frac{kn}{m} = \ln\left(\frac{1}{2}\right) = -\ln 2 \implies k = \frac{m}{n} \ln 2 \approx 0.693 \frac{m}{n}$$

结论 $p = 1/2$ 表示：当哈希函数数量取理论最优值时，布隆过滤器的位数组中约有一半比特为 0，一半比特为 1。此时位数组的信息熵较高，空间利用率较充分。

将最优 $k$ 代入最初的误差公式，可以得到最小假阳性率：

$$f_{\text{min}} = \left( \frac{1}{2} \right)^k \approx (0.6185)^{\frac{m}{n}}$$

这表明，在独立均匀哈希的近似假设下，只要系统能够保证每个插入对象平均分配到 $m/n \approx 9.6$ 位的存储空间，就能将误报率控制在 $1\%$ 以下；分配 $14.4$ 位时，误报率可降至千分之一级别。

以下数据展示了 $k$ 逼近最优理论值时误报率的趋势：

每元素分配位数 (m/n)	理论最优 k 估值	k=2 假阳性率	k=3 假阳性率	k=4 假阳性率	k=5 假阳性率	k=6 假阳性率	k=8 假阳性率
4	2.77	0.155	0.147	0.160	-	-	-
6	4.16	0.0804	0.0609	0.0561	0.0578	0.0638	-
8	5.55	0.0489	0.0306	0.0240	0.0217	0.0216	0.0229
10	6.93	0.0329	0.0174	0.0118	0.00943	0.00844	0.00846
12	8.32	0.0236	0.0108	0.00646	0.00459	0.00371	0.00314