引言
🍔在上一篇文章位图中，我们了解了C++中位图的概念和实现。位图是一种用于表示和操作大量二进制位的数据结构，它在解决需要高效存储和操作布尔类型数据的问题上具有重要作用。而在本篇文章中，我们将继续探讨另一个在C++中常用的数据结构——布隆过滤器。布隆过滤器是一种概率型数据结构，它可以高效地判断一个元素是否存在于一个集合中，同时具备较小的内存占用和快速查询的特点。通过对比位图和布隆过滤器的实现原理和应用场景，我们可以更全面地了解不同数据结构在C++中的应用。接下来，让我们深入探索布隆过滤器的奥秘吧！坐稳扶好咱们要开车了😍
一、布隆过滤器提出
🍪在我们日常生活中我们一定会收到不少的垃圾邮件所以我们有时候会开启自动过滤垃圾邮件，垃圾邮件过滤中，布隆过滤器可以快速判断一个邮件发送者是否为垃圾邮件发送者，从而减少用户收到垃圾邮件的数量。要想实现上面的功能我们需要从数据库中寻找出来并判断是不是垃圾邮件经常发送者。那么如何快速查找呢？
- 用哈希表存储用户记录，缺点：浪费空间
- 用位图存储发送者的信息，缺点：位图一般只能处理整形，如果发送者信息是字符串，就无法处理了。
- 将哈希与位图结合，即布隆过滤器
二、布隆过滤器的概念
🍁布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种概率型数据结构，用于快速判断一个元素是否存在于一个集合中。它通过使用多个哈希函数和位数组来实现，具有较小的内存占用和快速查询的特点。由于其高效的元素存在性判断能力，布隆过滤器在各种应用场景中得到了广泛的应用。
🍁然而，布隆过滤器也存在一定的缺点。首先，它是一个概率型数据结构，存在一定的误判率。即使一个元素不存在于集合中，也有可能被误判为存在。其次，布隆过滤器不支持删除操作，因为删除一个元素会影响到其他元素的判断结果。最后，由于使用了多个哈希函数和位数组，布隆过滤器的构建和查询操作需要一定的计算资源。
🍁在实际应用中，我们可以根据具体的需求和数据特点来选择合适的布隆过滤器参数，如位数组长度、哈希函数数量等，以达到较低的误判率和较高的性能。同时，我们需要注意布隆过滤器的误判率与插入元素数量、位数组长度和哈希函数数量等因素相关，需要合理权衡这些参数，以满足实际应用的需求。 
三、布隆过滤器的实现
1. 插入
布隆过滤器是一种快速判断某个元素是否存在于一个集合中的数据结构，它通过哈希函数将元素映射到位数组中的多个位置，并将这些位置标记为1。
void set(const K& key) { size_t len = N * _X; size_t hash1 = Hash1()(key) % len; _bs.set(hash1); size_t hash2 = Hash2()(key) % len; _bs.set(hash2); size_t hash3 = Hash3()(key) % len; _bs.set(hash3); }
具体来说，set函数接受一个键值key作为参数，将其哈希后的值映射到位数组中的多个位置，并将这些位置标记为1。这里使用了三个不同的哈希函数Hash1、Hash2和Hash3，它们的返回值被分别对位数组的大小（即N * _X）取模，得到三个不同的哈希值hash1、hash2和hash3。这样可以使得每个元素在位数组中的位置更加分散，减少冲突的可能性。
最后，使用bitset的set函数将对应的位设置为1，表示该元素存在于集合中。
2. 查找
在C++中，布隆过滤器的查找操作可以通过以下方式实现：
bool contains(const K& key) const { size_t len = N * _X; size_t hash1 = Hash1()(key) % len; size_t hash2 = Hash2()(key) % len; size_t hash3 = Hash3()(key) % len; // 判断位数组中对应位置的值是否都为1 if (_bs.test(hash1) && _bs.test(hash2) && _bs.test(hash3)) { return true; // 可能存在于集合中 } return false; // 一定不存在于集合中 }
在上述代码中，contains函数接受一个键值key作为参数，通过哈希函数将其映射到位数组中的多个位置。然后，使用bitset的test函数判断位数组中对应位置的值是否都为1。如果所有对应的位都是1，则返回true，表示该元素可能存在于集合中；否则，返回false，表示该元素一定不存在于集合中。
需要注意的是，由于布隆过滤器存在一定的误判率，即有可能将一个不存在的元素误判为存在，因此在使用contains函数进行查询时，可能会出现误判的情况。因此，布隆过滤器更适合用于快速判断元素不存在的情况，而不能完全依赖它来判断元素是否存在。
3. 删除（不支持）
🚨🚨布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素
💧布隆过滤器使用多个哈希函数将元素映射到位数组中的多个位置，并将这些位置的位设置为1。在查询操作时，如果所有位置的位都为1，则判断该元素可能存在于集合中。然而，当我们想要删除一个元素时，如果直接将对应位置的位设置为0，那么其他元素可能会受到影响。
💧考虑这样一种情况：假设有两个元素A和B，它们经过多个哈希函数映射后，分别在位数组的位置1、2、3上都设置了1。现在我们想要删除元素A，将位置1、2、3上的位设置为0。但是，这样一来，当查询元素B时，由于位置1、2、3上的位都为0，系统会错误地判断元素B不存在于集合中，即产生了误判。
💧因此，为了避免删除操作对其他元素的判断造成干扰，布隆过滤器通常被设计为只能进行插入和查询操作，不支持删除操作。如果需要删除某个元素，通常的做法是重新构建一个新的布隆过滤器，将需要删除的元素排除在外。
C++模拟实现布隆过滤器
#include <vector> #include <string> #include <time.h> using namespace std; //位图 template<size_t N> class bitset { public: bitset() { _bits.resize(N / 8 + 1, 0); } void set(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] |= (1 << j); } void reset(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] &= ~(1 << j); } bool test(size_t x) { size_t i = x / 8; size_t j = x % 8; return _bits[i] & (1 << j); } private: vector<char> _bits; }; struct BKDRHash { size_t operator()(const string& s) { size_t hash = 0; for (auto ch : s) { hash += ch; hash *= 31; } return hash; } }; struct APHash { size_t operator()(const string& s) { size_t hash = 0; for (long i = 0; i < s.size(); i++) { size_t ch = s[i]; if ((i & 1) == 0) { hash ^= ((hash << 7) ^ ch ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ ch ^ (hash >> 5))); } } return hash; } }; struct DJBHash { size_t operator()(const string& s) { size_t hash = 5381; for (auto ch : s) { hash += (hash << 5) + ch; } return hash; } }; // N最多会插入key数据的个数 template<size_t N, class K = string, class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash> class BloomFilter //布隆过滤器 { public: void set(const K& key) { size_t len = N * _X; size_t hash1 = Hash1()(key) % len; _bs.set(hash1); size_t hash2 = Hash2()(key) % len; _bs.set(hash2); size_t hash3 = Hash3()(key) % len; _bs.set(hash3); //cout << hash1 << " " << hash2 << " " << hash3 << " " << endl << endl; } bool test(const K& key) { size_t len = N * _X; size_t hash1 = Hash1()(key) % len; if (!_bs.test(hash1)) { return false; } size_t hash2 = Hash2()(key) % len; if (!_bs.test(hash2)) { return false; } size_t hash3 = Hash3()(key) % len; if (!_bs.test(hash3)) { return false; } // 在 不准确的，存在误判 // 不在 准确的 return true; } private: static const size_t _X = 6; bitset<N* _X> _bs; };
四、布隆过滤器的优缺点
✅优点
- 快速查询：布隆过滤器可以在常数时间内进行元素的插入和查询操作，不受数据规模的影响。这是因为布隆过滤器使用位数组和多个哈希函数，可以快速计算出元素对应的位数组位置，并进行位操作。
- 空间效率高：相比于其他数据结构，布隆过滤器占用的空间很小。它通过位数组来表示元素的存在与否，并且可以通过调整位数组大小和哈希函数个数来控制空间占用和误判率之间的平衡。
- 高效的哈希函数：布隆过滤器使用多个哈希函数将元素映射到位数组中的多个位置，这样可以减少冲突的可能性，提高查询的准确性。
✅缺点
- 误判率：布隆过滤器存在一定的误判率，即有可能将一个不存在的元素误判为存在。这是由于位数组中的某些位置可能被多个元素映射到，导致多个元素的位都被设置为1。因此，在实际使用中，需要根据需求和误判率的可接受范围来选择合适的位数组大小和哈希函数个数。
- 不支持删除操作：布隆过滤器的设计初衷是用于快速判断元素是否存在，而不支持删除操作。因为删除一个元素可能会影响其他元素的判断结果。如果需要支持删除操作，可以考虑使用其他数据结构或者扩展布隆过滤器的设计。
- 无法存储额外信息：布隆过滤器只能判断元素是否存在，无法存储额外的信息。如果需要存储额外的信息，可以考虑使用其他数据结构，如哈希表或数据库。
