C++ 布隆过滤器

这里我们可以发现插入“baidu”和“tencent”这两个生产出的哈希值都存在4，所以不同的值通过哈希函数求出来的哈希值是会冲突的，当插入的值多了之后，比如我们又插入一个“bit”，假设bit的3个映射位为1，4，8，这三个位置的位置上面都置为1，所以就会存在误判，布隆过滤器是降低误判概率，而不是没有误判，所以对于一个元素的映射的位置如果都为1，我们只能说它可能存在，如果映射的位置有一个不为1，

虾..

656人浏览 · 2025-11-12 18:59:31

虾.. · 2025-11-12 18:59:31 发布

1.布隆过滤器的提出

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉
那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？用服务器记录了用
户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那
些已经存在的记录。如何快速查找呢？

1. 用哈希表存储用户记录，缺点：浪费空间

2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理
了。

3. 将哈希与位图结合，使用位图的数据结构加上多个哈希函数来实现一个元素的多个位置的映射，即布隆过滤器

所以一般整型使用位图来解决，字符串使用位图来解决。

2.概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存
在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也
可以节省大量的内存空间。

3.实现原理

布隆过滤器的数据结构底层就是一张位图。

3.1 数据结构

向布隆过滤器插入“baidu”，我们使用多个不同的哈希算法来生成多个哈希值，映射到不同的位置上面。

将不同哈希函数生成的哈希值映射上去的位置置为1，就表示这个位置也就被添加进行了，我们再插入一个“tencent”

ps：存在不一定是真的，不存在一定是真的。

3.2 哈希函数

struct BKDRHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (auto ch : str)
        {
            hash = hash * 131 + ch;
        }

        //cout <<"BKDRHash:" << hash << endl;
        return hash;
    }
};

struct APHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (size_t i = 0; i < str.size(); i++)
        {
            size_t ch = str[i];
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }

        //cout << "APHash:" << hash << endl;
        return hash;
    }
};

struct DJBHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 5381;
        for (auto ch : str)
        {
            hash += (hash << 5) + ch;
        }

        //cout << "DJBHash:" << hash << endl;
        return hash;
    }
};

要实现多个映射位，那么就需要多个哈希函数来映射出多个位置的值，这里我们通过仿函数来提供三个哈希函数，这三个哈希函数都是误判率很低的三个字符串哈希算法。

3.3 插入

插入也就是把三个哈希函数求出来的哈希值映射到位图的相应位置，将相应位置改为1。

void Set(const K& key)
{
    size_t hash1 = Hash1()(key) % N;
    _bs.set(hash1);

    size_t hash2 = Hash2()(key) % N;
    _bs.set(hash2);

    size_t hash3 = Hash3()(key) % N;
    _bs.set(hash3);

     cout << hash1 << endl;
     cout << hash2 << endl;
     cout << hash3 << endl << endl;
}

3.4 查找

查找时，需要判断它每一个的哈希值是否都存在，如果有一个不存在那么就是不存在的。

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

     size_t hash2 = Hash2()(key) % N;
     if (_bs.test(hash2) == false)
         return false;

     size_t hash3 = Hash3()(key) % N;
     if (_bs.test(hash3) == false)
         return false;

     return true; 
 }

这里还是要注意，查找出来的值不一定存在，都是不存在一定是真的，布隆过滤器只是降低了误判率。

3.5 删除

布隆过滤器是不支持删除的，删除了一个元素对应的映射值，会影响到对于其他元素的判断。

当我们删除腾讯的时候，把1，6，7位置都设为0，百度也有映射为1的位置，那么再查找百度的时候就会判断百度也不存在。

如果硬要支持删除的话，就需要把比特位扩展为一个个的计数器，插入元素的时候给这计数器++，删除的时候把这个计数器--，对于0时才认为这个映射的这个位置是没有的，那么就不能1个比特位来表示一个映射的位置，就需要给每一个映射的位置多准备几个比特位来表示当前位置被映射的数量，比如使用2个比特位，00表示不存在，01，表示映射一次，10表示2次，11表示3次。

都是这样子也有缺陷：

1.需要多个比特位，浪费空间。

2.无法保证某个元素是否真的存在于布隆过滤器中，如果我们把一个元素的映射的位置--，如果那几个位置的映射值都不为0，去查询的时候，不是还是认为它是存在的吗？

3.存在计数回绕。

4.哈希函数个数和过滤器长度的选择

很明显，长度过小和哈希函数的个数都会影响误判率，哈希函数个数越少，误判率越高，长度过小，一个位置被多次映射的概越高，误判率越高。那么要如何选择哈希函数个数和过滤器长度呢？

k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率。

如何选择合适的k和m值呢？

k 次哈希函数某一 bit 位未被置为 1 的概率为：

5. 简单测试

void TestBloomFilter()
{
	BloomFilter<11> bf;
	bf.Set("孙悟空");
	bf.Set("猪八戒");
	bf.Set("牛魔王");
	bf.Set("二郎神");

	cout << bf.Test("孙悟空") << endl;
	cout << bf.Test("猪八戒") << endl;
	cout << bf.Test("沙悟净") << endl;
}
int main()
{
	TestBloomFilter();
	return 0;
}

运行结果：

这边把映射的位置的值也打印了出来，可以看到出现了误判，把沙悟净也认为存在了，所以经过布隆过滤器的值只可以认为是可能。

6.小结

应用场景：

因为布隆过滤器是有误判的可能的，所以它一般并不会作为把结果作为直接返回值，而是一种手段，比如我们打游戏时都要取自己的昵称，难道我们直接把这个数据直接放到数据库里面去一个一个比较吗，肯定不是的，所以可以先借助布隆过滤器去筛除一下，如果布隆过滤器里面不存在，那么肯定不存在，可以使用，如果存在，再去数据库里面比较。

所以可以应用于快速判断是否存在的场景。

优点：

1.时间复杂度低，增加和查询元素的时间复杂为O(N)，（N为哈希函数的个数，通常情况比较小）

2.保密性强，布隆过滤器不存储元素本身

3.存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）

缺点：

1.有点一定的误判率，但是可以通过调整参数来降低

2.无法获取元素本身

3.很难删除元素

7.哈希切割问题

问题一：

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

query 指查询语句，比如网络请求、SQL 语句等，假设一个 query 语句占 30 Byte，单个文件中的 100 亿个 query 占 3000亿Byte 的空间（约等于300GB）

近似算法：

借用布隆过滤器，先存储其中一个文件的query语句，假设给一个query准备4个比特位来映射的话，100亿个就约占1GB的内存，可以存下，存储完毕后，再从另外一个文件读取query语句，一个一个判断是否存在于布隆过滤器中，“存在”的话就是交集，这里也会存在像位图一样的问题也就是文件一{1，2}和文件二{2，2，2}，所以最后的结果还需要去重。

精确算法：

对于这么多的数据我们可以使用哈希切割，把单个文件（300GB）先切成1000个小文件，一个小文件也就是300MB，我们读取两个文件进行操作也就是600MB，够用，这里面有两种切法，一种是平均切，可以保证每个文件的大小都是一样的，但是这个样子的话的每一个小文件都要跟另一个文件的每一个小文件比较一下，确认是否存在交集。

这样子效率实在实在是太慢了。

所以我们这边应该使用哈希切分的方法，来保证每一个相同的元素会报存到同一个文件里面。

i = HashFunc(query) % 1000

不同的 query 语句会得到不同的下标 i，这个下标 i 决定着这条 query 语句会被存入哪个小文件中，显然，一样的 query 语句计算出一样的下标，也就意味着它们会进入下标相同的小文件中，经过 哈希切割 后，只需要将大文件 A 中的小文件 A0 与大文件 B 中的小文件 B0 进行求交集的操作就行了，这样能大大提高效率。但是这样子操作的话，也会有问题，如果说很多相同的query语句或者相同的query语句映射的值是相同的话，就会出现一些小文件超过了1GB，就无法被加载到内存里面。