【C++】布隆过滤器的概念与特点解析

 

🌈 个人主页：谁在夜里看海.

🔥 个人专栏：《C++系列》《Linux系列》

⛰️ 天高地阔，欲往观之。

目录

00.引入

01.布隆过滤器的概念

特点1：极低的内存消耗

特点2：快速查询

特点3：假阳性误判（禁止删除）

02.布隆过滤器的底层实现

00.引入

上一篇博客介绍了位图这一数据结构，它可以在大量整数中快速查找某一数据是否存在，并且内存占用率很低（例如，查找40亿个整数只需0.5G空间）。博客链接跳转->

那么问题来了，如果我要查找的数据类型是字符串或其他类型，位图还能用吗？

分析：

位图本质上是一种哈希结构，哈希结构在存储元素时是根据元素的哈希值进行存储的，整数在位图中进行存储时，哈希值就是它本身，因此也不会产生哈希冲突；如果字符串想要用位图进行存储的话，需要计算出对应的哈希值，就要通过哈希函数来实现。

但是有一个问题，那就是哈希冲突：

最优秀的哈希函数也只能减少产生冲突的可能性，而不能完全避免冲突，那么在位图中，哈希冲突会造成什么后果呢？

例如：字符串“AaAaA”与“BBBBB”通过某哈希函数计算所得的哈希值都是5，事实上，“AaAaA”是存在的元素，而“BBBBB”并不存在，将所有元素存入位图后，bit位5的bool值为1（因为“AaAaA”的哈希值为5）此时就会对“BBBBB”产生误判，即“BBBBB”不存在但是通过位图会判断其存在。

当然了，为了应对哈希冲突，我们可以对位图进行扩容（通常是二倍扩容），并更新哈希函数重新计算哈希值来化解冲突，但是这种扩容的方式背离了位图的初衷：高效的内存利用。频繁的扩容必然导致内存的浪费，那么面对字符串的存储问题，该怎么解决呢？下面就要介绍布隆过滤器了。

01.布隆过滤器的概念

哈希冲突的产生原理就是，不同的元素有相同的哈希值，一般来说，一个元素对应一个哈希值，但是布隆（Burton Howard Bloom）告诉你，一个元素可以有多个哈希值：

一个元素经过多个不同哈希函数得到多个哈希值，将这些哈希值都作为该元素的映射，这样就大大减小了哈希冲突的可能性。两个不同的元素要想发生冲突，它们每个哈希值都得相同，并且可以通过增加哈希函数的办法，让这种可能性继续降低。

这是某位大佬总结出来的哈希函数的个数与误判率的关系：

说到底，布隆过滤器还是没办法完全解决哈希冲突的问题，还是会导致误判，但是布隆过滤器的以下特点使其具有重要意义：

特点1：极低的内存消耗

布隆过滤器拥有和位图一样的底层结构，使其使用极少的内存空间就可以支持大量数据的“存在性”查询。

特点2：快速查询

布隆过滤器通过简单的位运算就可以完成元素的“存在性”判断，速度非常之快，这种高效性在实时性要求高的场景（如网络请求过滤、黑名单检测）中尤为有用。

特点3：假阳性误判（禁止删除）

布隆过滤器虽然存在误判，但是可以将误判率控制在一个可以接受的范围内，并且布隆过滤器的误判是假阳性误判，不会存在假阴性误判，解释：

假阳性误判就是，将不存在的元素误判为存在，例如：由于A和B的哈希值全部相同，A存在就会导致B被误判

而假阴性误判就是，将存在的元素误判为不存在，查询某一元素是否存在，就要看它对应的比特位bool值是否都为1，只要该位置的bool值不被修改，就不会造成假阴性误判。元素的插入不会造成修改，但是元素的删除会造成修改。

A与B有一个哈希值7相同，B的删除会使7的bool值置0，这就会导致A被误判为不存在，即假阴性误判，为了避免这种情况发生，布隆过滤器不允许删除元素。

为什么布隆过滤器允许假阳性误判但不允许假阴性误判的产生呢，来看下面这一个场景：

为了方便用户之间的搜索，某应用不允许用户的id重复，现在用布隆过滤器存储着所有用户id的存储情况，用户注册时如果预输入id已存在，则要求更换id（可能预输入id并不存在，但是发生假阳性误判），由于假阴性误判的杜绝，用户的id一定不会相同（已存在的id肯定不会被误判为不存在，而被新用户注册）

02.布隆过滤器的底层实现

布隆过滤器的底层结构与位图相同，只不过前者用多个哈希值表示1个元素，而且后者只用1个哈希值对应1个元素

 // 将which比特位置1
 void set(size_t which)
 {
	 if (which > _bitCount)
	 	return;
	 size_t index = (which >> 5);
	 size_t pos = which % 32;
	 _bit[index] |= (1 << pos); // 将对应bit位改为1
 }
 // 将which比特位置0
 
 void Set(const K& key)
 {
     size_t len = X*N;
     size_t index1 = HashFunc1()(key) % len;
     size_t index2 = HashFunc2()(key) % len;
     size_t index3 = HashFunc3()(key) % len;

     _bs.set(index1);
     _bs.set(index2);
     _bs.set(index3);
 }

哈希函数参考：

struct BKDRHash
{
    size_t operator()(const string& s)
    {
        // BKDR
        size_t value = 0;
        for (auto ch : s)
        {
            value *= 31;
            value += ch;
        }
        return value;
    }
};
struct APHash
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (long 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 DJBHash
{
    size_t operator()(const string& s)
    {
        size_t hash = 5381;
        for (auto ch : s)
        {
            hash += (hash << 5) + ch;
        }
        return hash;
    }
};

以上就是对布隆过滤器的详细介绍与说明，欢迎指正~

码文不易，还请多多关注支持，这是我持续创作的最大动力！