布隆过滤器：基于哈希函数的原理、应用解析

一、引言

1、布隆过滤器的概念简介

**布隆过滤器（Bloom Filter）**是一种空间效率极高的概率型数据结构，它利用位图和哈希函数来快速判断一个元素是否属于某个集合。布隆过滤器不是传统意义上的过滤器，它不能完整地存储数据，而是以一种紧凑的方式表示数据可能存在的集合。

2、布隆过滤器是基于哈希函数的强大工具

布隆过滤器的核心机制是基于哈希函数的映射和位图将哈希与位图结合。哈希函数能够将输入数据均匀地映射到一个固定大小的范围内，而位图则提供了一种紧凑的数据表示方式。在布隆过滤器中，多个哈希函数被用于将数据映射到位图的不同位置上，并设置相应的位为1来表示数据可能存在。在查询时，只需通过同样的哈希函数计算并检查位图中对应位置的值即可判断数据是否存在。这种基于哈希函数的映射方式不仅实现了空间的高效利用，还保证了查询的快速性。

---

二、布隆过滤器基础知识

1、布隆过滤器的工作原理

• 位图与哈希函数的结合

布隆过滤器主要由两部分组成：一个很长的二进制向量（即位图）和一系列随机映射函数（即哈希函数）。二进制向量中的每一位初始时都设置为0。当添加一个新元素时，该元素会经过k个哈希函数的计算，得到k个哈希值。这k个哈希值对应到位图中的k个位置，并将这些位置上的值设置为1。因此，布隆过滤器利用位图和哈希函数的结合，实现了对元素的添加操作。

下图中假设 x，y，z 通过三个不同的哈希函数映射在不同的位置上，集合元素x、y、z分别被映射到位图的某些位置，并且这些位置被标记为1。这表明这些位置在布隆过滤器中已经被设置为1，表示这些元素可能存在于集合中。

元素w不在集合{x, y, z}中，因为它哈希到了一个包含0的位图位置。

哈希函数的选择对布隆过滤器的性能至关重要。好的哈希函数应该具有均匀性、一致性和冲突最小化等特点，以确保布隆过滤器的误报率尽可能低。同时，哈希函数的计算速度也直接影响到布隆过滤器的查询性能。因此，在实际应用中，需要根据具体场景选择合适的哈希函数来构建高效的布隆过滤器。

• 元素添加与查询过程

添加元素到布隆过滤器中的过程相对简单。首先，将要添加的元素通过k个哈希函数进行计算，得到k个哈希值。然后，根据这些哈希值在位图中找到对应的k个位置，并将这些位置上的值设置为1。如果某些位置上的值已经是1，则不需要进行任何操作。

由于哈希函数的特性，布隆过滤器在处理数据时具有一定的概率性。这意味着它可能会存在误报（false positive）的情况，即判断某个元素属于集合但实际上并不属于。然而，通过合理选择哈希函数和调整位图的大小，可以降低误报率，使得布隆过滤器在实际应用中仍然具有非常高的实用价值。

{ A，B，C }通过哈希函数映射在不同的位置。此时我们查找元素 X，通过哈希函数得到的三个下标上的元素均为1，但是元素 X 不存在于集合中。

查询一个元素是否存在于布隆过滤器中的过程也相对直接。同样地，将要查询的元素通过k个哈希函数进行计算，得到k个哈希值。然后，检查这些哈希值对应到位图上的位置，如果所有位置上的值都是1，则认为该元素可能存在于集合中。然而，需要注意的是，由于哈希冲突的存在，即使所有位置上的值都是1，也不能确定该元素一定存在于集合中，因此布隆过滤器的查询结果具有概率性。

• 误报率（False Positive Rate）的解释

误报率表示的是当一个元素查询结果为存在时，但实际上该元素并不存在的概率。由于布隆过滤器是通过哈希函数将元素映射到位图上的，因此存在哈希冲突的可能性。当两个不同的元素经过哈希函数计算后得到相同的哈希值时，就会发生哈希冲突。在这种情况下，如果一个元素被错误地标记为存在（即其对应的位图位置上的值为1），就会导致误报。误报率与布隆过滤器的位图大小、哈希函数的个数以及集合中元素的个数有关。通常情况下，通过增加位图的大小和哈希函数的个数，可以降低误报率，但也会增加空间和时间开销。

⚠️总结来说，布隆过滤器通过位图和哈希函数的结合，实现了高效的元素添加和查询操作。然而，由于其基于哈希函数的特性，布隆过滤器的查询结果具有概率性，存在误报的可能性。因此，在使用布隆过滤器，要注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

• 删除布隆过滤器中的元素

布隆过滤器的一个主要限制是它不支持删除操作。这是因为布隆过滤器是基于位图和哈希函数实现的，当一个元素被添加到过滤器中时，它会被哈希到多个位上并将这些位设置为1。然而，当尝试删除一个元素时，我们无法简单地将其对应的位重置为0，因为这可能会影响到其他已经添加的元素。

具体来说，如果我们将某个元素对应的位重置为0，那么可能会破坏掉其他已经添加到过滤器中的元素的哈希表示。因为多个元素可能哈希到同一个位上，而这个位被某个元素“占用”时，我们不能确定它是否只被这一个元素所使用。

因此，一旦一个元素被添加到布隆过滤器中，它就不能被直接删除。这是布隆过滤器的一个固有特性，也是它与其他数据结构（如哈希表或集合）相比的一个主要区别。

⭕️ 但是我们可以通过将布隆过滤器中的每个比特位扩展成一个小的计数器（通常称为计数布隆过滤器或Counting Bloom Filter），可以实现对元素的删除操作。这种方法通过牺牲更多的存储空间来换取删除功能。

在计数布隆过滤器中，每个位不再是一个简单的0或1，而是一个可以递增和递减的计数器。当插入一个元素时，通过k个哈希函数计算出的k个哈希地址，将对应的k个计数器加一。当需要删除一个元素时，同样通过这k个哈希函数找到对应的计数器，并将它们减一。

通过这种方法，可以准确地跟踪每个位置上的元素计数，从而支持删除操作。然而，需要注意的是，计数布隆过滤器仍然无法完全避免误报（False Positive）的情况。即使某个元素的计数器被正确减至零，由于哈希冲突的存在，其他元素可能仍然会导致该位置上的计数器非零，从而产生误报。

此外，计数布隆过滤器还需要考虑计数器溢出的问题。如果计数器的值超过了其能够表示的范围，就会导致数据丢失和误操作。因此，在选择计数器的位数时需要根据实际应用场景进行权衡。

2、布隆过滤器的空间效率分析

布隆过滤器的空间效率分析主要体现在其相对于其他数据结构的空间占用优势上。布隆过滤器通过使用位图和哈希函数，实现了对元素存在性的高效判断，同时显著降低了空间占用。

• 与其他数据结构的空间对比

与常见的数据结构如list、set、map等相比，布隆过滤器在空间效率上具有显著优势。这些传统数据结构通常需要存储元素的完整信息，而布隆过滤器只存储位图中的位信息，且每一位只占用极少的空间（通常是1比特）。因此，在存储相同数量的元素时，布隆过滤器所需的存储空间远小于其他数据结构。

• 影响空间效率的关键因素

1. 位图的大小：位图是布隆过滤器存储元素信息的主要数据结构。位图的大小直接决定了布隆过滤器能够存储的元素数量以及误报率的高低。通常情况下，位图越大，能够存储的元素数量越多，同时误报率也会相应降低。
2. 哈希函数的个数和性质：哈希函数在布隆过滤器中起到了将元素映射到位图的关键作用。哈希函数的个数和性质直接影响到布隆过滤器的空间效率和误报率。一般来说，使用更多的哈希函数可以降低误报率，但同时也会增加计算开销和空间占用。此外，哈希函数的均匀性和分散性也对布隆过滤器的性能有重要影响。
3. 元素的数量：存储的元素数量越多，布隆过滤器所需的位图空间就越大。这是因为每个元素都需要通过哈希函数映射到位图中的多个位置，并设置相应的位为1。
4. 误报率的设定：误报率是布隆过滤器的一个重要指标，它表示了当查询一个不存在的元素时错误地返回存在的概率。误报率的设定会直接影响到布隆过滤器的空间占用。通常情况下，误报率越低，所需的位图空间就越大。

3、布隆过滤器的性能特点

插入和查询的时间复杂度都是O(k)，这意味着无论集合中元素的数量如何增加，插入和查询的时间都将保持稳定，不会随着元素数量的增长而显著增长。这是因为布隆过滤器使用位图和哈希函数来表示集合，查询和插入操作只涉及到位图的访问和更新，而无需遍历整个集合。

其次，哈希函数的选择对布隆过滤器的性能具有重要影响。一个好的哈希函数能够近似等概率地将字符串映射到各个位上，从而减少哈希冲突的可能性，提高布隆过滤器的准确性和性能。哈希函数的个数k也是影响性能的关键因素，k值的选择需要根据实际情况进行权衡。过多的哈希函数会增加计算复杂度，而过少的哈希函数则可能导致较高的误报率。

总的来说，布隆过滤器以其高效的插入和查询操作以及灵活的哈希函数选择，成为了处理大规模数据集合的理想选择。然而，需要注意的是，布隆过滤器存在误报的可能性，即可能会错误地判断一个不存在的元素为存在。因此，在使用布隆过滤器时，需要根据具体的应用场景和需求来选择合适的参数配置，以达到最优的性能和准确性。

---

三、布隆过滤器的应用场景

1、数据库查询优化

• 过滤不存在的记录，减少磁盘I/O

布隆过滤器可以有效地过滤不存在的记录，从而避免不必要的磁盘I/O操作。那么，当一个新的查询请求到达时，首先通过布隆过滤器检查该记录是否可能存在于数据库中。如果布隆过滤器返回结果为“不存在”，则可以直接拒绝该查询请求，无需进一步访问数据库。这样可以显著减少磁盘I/O操作，提高查询效率。

在实际应用中，布隆过滤器可以与数据库查询语句结合使用。例如，在执行查询操作之前，可以先将查询条件通过布隆过滤器进行过滤，只保留可能存在于数据库中的记录，然后再执行实际的查询操作。这样可以确保查询操作只针对可能存在的记录进行，避免了对大量不存在记录的无效查询。

2、例子

假设给了两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法？

假设一个 query 平均是50byte，1G约等于10亿字节。那么100亿个query是500G。

精确算法

由于内存限制，我们不能一次性加载所有query到内存中。因此，需要采用分块处理的策略。

1. 哈希分块：
   • 使用哈希函数将两个文件分别分成多个小块，每个块的大小适中，使得可以加载到内存中。
   • 对每个块进行排序，以便后续快速查找交集。
2. 逐块对比：
   • 逐块比较两个文件中的query。对于每一对块，将其中一个块加载到内存中，另一个块则使用外部排序的方法（如多路归并排序）进行遍历。
   • 在内存中执行二分查找或使用哈希表来查找交集。
3. 合并结果：
   • 将所有找到的交集合并到一个输出文件中。
4. 去重：
   • 由于可能存在重复的交集，在写入输出文件之前，需要对结果进行去重处理。可以使用 map、set等容器。

这个算法虽然精确，但可能非常耗时，因为它涉及到多次磁盘I/O操作和排序操作。该文中也有涉猎 -> 深入探索位图技术：原理及应用

近似算法

为了在处理大数据集时提高效率，可以采用近似算法来找到交集的近似解。

1. 布隆过滤器：

   • 使用布隆过滤器来存储一个文件中的所有query。布隆过滤器允许快速检查一个元素是否可能存在于集合中，但可能会产生误报（即，将不存在的元素错误地识别为存在）。
   • 加载第一个文件的query到布隆过滤器中。由于布隆过滤器的内存占用相对较小，因此可以在有限的内存中存储大量的query。

2. 检查交集：

   • 遍历第二个文件的query，使用布隆过滤器检查每个query是否可能存在于第一个文件中。
   • 将布隆过滤器识别为可能存在的query作为交集的近似结果输出。

请注意，由于布隆过滤器的误报性质，这种算法只能给出交集的近似解，而不是精确解。误报率取决于布隆过滤器的大小和哈希函数的数量。通过调整这些参数，可以在一定程度上控制误报率，但无法完全消除它。

---

四、布隆过滤器的实现与优化

1、常见的布隆过滤器库

• 开源库
  • Google Guava：Java语言的开源库，提供了布隆过滤器的实现。
  • RedisBloom：针对Redis的布隆过滤器模块，提供丰富的布隆过滤器功能。
  • pybloom：Python语言的布隆过滤器库。
  • bloomfilter-cpp：C++语言的布隆过滤器库

2、自定义布隆过滤器的实现步骤

struct HashFunc1 {
	//BKDR
	size_t operator()(const string& s){
		size_t hash = 0;
		for (auto ch : s)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};
struct HashFunc2 {
	// AP
	size_t operator()(const string& s){
		size_t hash = 0;
		for (size_t i = 0; i < s.size(); i++){
			if ((i & 1) == 0) // 偶数位字符
				hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
			else              // 奇数位字符
				hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
		}

		return hash;
	}
};
struct HashFunc3 {
	// DJB
	size_t operator()(const string& s){
		size_t hash = 5381;
		for (auto ch : s)
			hash = hash * 33 ^ ch;
		return hash;
	}
};
template<size_t N, class K = string,
	class Hash1 = HashFunc1,
	class Hash2 = HashFunc2,
	class Hash3 = HashFunc3>
class BloomFilter {
public:
    void Set(const K& key) {
        size_t hash1 = Hash1()(key) % M;
        size_t hash2 = Hash2()(key) % M;
        size_t hash3 = Hash3()(key) % M;

        _bs->set(hash1);
        _bs->set(hash2);
        _bs->set(hash3);


    }

    bool Test(const K& key) {
        size_t hash1 = Hash1()(key) % M;
        if (_bs->test(hash1) == false)
            return false;

        size_t hash2 = Hash2()(key) % M;
        if (_bs->test(hash2) == false)
            return false;

        size_t hash3 = Hash3()(key) % M;
        if (_bs->test(hash3) == false)
            return false;

        // 存在误判(有可能3个位都是跟别人冲突的，所以误判)
        return true;
    }
private:
    static const size_t M = 5 * N;
    std::bitset<M>* _bs = new std::bitset<M>;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

1. Set方法：用于将元素添加到布隆过滤器中。它计算元素的三个哈希值，并将对应位置上的位设置为1。
2. Test方法：用于检查元素是否可能存在于布隆过滤器中。它同样计算元素的三个哈希值，并检查对应位置上的位是否都为1。如果有任何一位为0，则确定元素一定不存在；如果所有位都为1，则返回true，但存在误报的可能。

3、降低误报率的策略

• 增加位图长度

布隆过滤器的误报率与其使用的位图（bit array）大小直接相关。位图越长，能提供的唯一标识就越多，从而减少了哈希冲突的可能性。因此，增加位图长度可以有效降低误报率。但需要注意的是，位图长度的增加也会导致空间需求的增加，所以需要在误报率和空间使用之间找到平衡。

• 使用多个独立的哈希函数

布隆过滤器通常使用多个哈希函数将元素映射到位图的不同位置。使用更多的哈希函数可以增加元素在位图中的覆盖面积，进一步减少哈希冲突的可能性。然而，这也增加了计算复杂性和哈希函数的选择难度。因此，在选择哈希函数数量时，需要权衡误报率和计算效率。

• 动态调整布隆过滤器大小

在某些情况下，可以根据实际需求动态调整布隆过滤器的大小。例如，当检测到误报率较高时，可以扩大位图长度或增加哈希函数数量来降低误报率。同样地，当空间资源紧张时，也可以适当缩小位图长度或减少哈希函数数量以节省空间。这种动态调整策略需要根据实际应用场景进行灵活配置。

需要注意的是，虽然这些策略可以降低误报率，但它们并不能完全消除误报。布隆过滤器是一种概率数据结构，其设计本身就允许存在一定的误报率。因此，在使用布隆过滤器时，需要充分考虑其特性并根据实际需求进行权衡和配置。