目录
布隆过滤器的提出
布隆过滤器的概念
布隆过滤器的实现
布隆过滤器的插入
布隆过滤器的查找
布隆过滤器的删除
布隆过滤器的优点
布隆过滤器的缺点
布隆过滤器的使用场景
布隆过滤器的提出
在注册账号设置昵称的时候,为了保证每个用户的昵称唯一性,系统必须检测你输入昵称是否被使用过,这本质就是一个key模型,我们只需要判断这个昵称被使用过还是没被使用过.
- 方法一:用红黑树或哈希表将所有使用过的昵称存储起来,当需要判断一个昵称是否被使用过时,直接判断该昵称是否在红黑树或哈希表中即可,但红黑树和哈希表最大的问题就是空间浪费,当昵称数量非常多的时候内存当作根本无法存储该昵称
- 方法二:用位图将所有使用过的昵称存储起来,虽然位图只能存储整型数据类型数据,但我们可以通过哈希函数将字符串转成整型,比如BKDR哈希算法.当需要判断一个昵称是否被使用过时,直接判断位图中该昵称对应的比特位是否被设置即可.
位图虽然能够大大节省空间,但由于字符串的组合形式太多了,一个字符串的取值有256种,而一个数字的取值只有10种,因此无论通过何种算法将字符串转成整型都无法避免哈希冲突.
这里的哈希冲突就是不同的昵称最终被转换成了相同的整型,此时就可能会引发误判,即某个昵称明明没有被使用过,却被系统判定位使用过,于是就出现了布隆过滤器.
布隆过滤器的概念
布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的一种紧凑型的,比较巧妙的概率型数据结构,特点是高效的插入和查询.
- 布隆过滤器其实就是位图的一个变型延申,虽然无法避免存在哈希冲突,但我们可以想办法降低误判率.
- 当一个数据映射到位图中时,布隆过滤器会用多个哈希函数将其映射到多个比特位,当判断一个数据是否存在位图当中时,需要分别根据这些哈希函数计算出对应的比特位,如果这些比特位都被设置位1则判定存在,否则判定不存在.
- 布隆过滤器使用多个哈希函数进行映射,目的就在于降低哈希冲突,一个哈希函数产生的哈希冲突的概率比较大,但多个哈希函数产生冲突的概率就没那么大了.
假设布隆过滤器使用三个哈希函数进行映射,那么"张三:这个昵称被使用后位图中会有三个比特位会被设置成1,当有人有使用"李四"这个昵称时,就算前两个哈希函数计算出来的位置都产生冲突,但由于第三个哈希函数计算出来的比特位的值是0,此时系统会判定:"李四"这个昵称没有被使用.
但是随着位图中添加的数据不断增多,位图中1的个数也在不断增多,此时就会导致误判率增加.
你如"张三"和"李四"都添加到位图中后,当有人要使用"王五"这个昵称时.虽然王五计算出来的三个位置即不和张三完全一样,也不和李四完全一样,但王五计算出来的三个位置分别被"张三"和李四占用了,此时系统也会误判为:王五:这个昵称已经使用过了.
布隆过滤器的特点:
- 当布隆过滤器判断一个数据存在可能时不准确的,因为这个数据对应的比特位可能被其他一个数据或多个数据占用了.
- 当布隆过滤器判断一个数不存在是准确的,因为如果该数据对应的比特位都因该被设置成一了.
如何控制误判率:
- 很显然,过小的布隆过滤器很快所有的比特位都会被设置成一,此时布隆过滤器的误判率就会变得很高,因此布隆过滤器得长度会直接影响误判率,布隆过滤器得长度越长,其误判率越小.
- 此外,哈希函数得个数也需要权衡,哈希函数得个数越多布隆过滤器中比特位被设置成一得速度越快,并且布隆过滤器得效率越低,当如果哈希函数的个数太少,也会导致误判率变高.
那因该如何选择哈希函数的个数和布隆过滤器的长度呢,有人通过计算后得出了一下关系:
其中k位哈希函数个数,m位布隆过滤器的长度,n位插入的元素个数,p为误判率.
我们这里可以大概的估算一下,如果使用3个哈希函数,即k的值为3,ln2的值我们取0.7,那么m和n的关系大概是m=4*n,也就是布隆过滤器的长度因该是插入元素的4倍.
布隆过滤器的实现
首先,布隆过滤器可以实现为一个模板类,因为插入布隆过滤器的元素不仅仅是字符串,也可以是其他数据类型,只有调用者能够通过对应的哈希函数将该数据类型转换成该类型对应的整型数据即可,但一般情况下布隆过滤器都是用来处理字符串类的.所以这里可以将模板参数k的缺省值类型设置为string.
布隆过滤器中的成员一般也就是一个位图,我们可以在布隆过滤器这里设置一个非类型的模板参数,由于指定位图的长度.
template<size_t N,class K = string,class Hash1 = BKDRHash,class Hash2 = APHash,class Hash3 = DJBHash>
class BloomFilter
{
public:
private:
bitset<N> _bs;
};示例化布隆过滤器是需要提供三个哈希函数,由于布隆过滤器一般处理字符串的数据类型,因此这里我们默认提供几个将字符串转换成整型的哈希函数.
- 这里选取将字符串转换成整型的哈希函数,是经过测试后者评分最高的BKFRHash APHash和DJBHash,这三种哈希算法在多种场景下产生的哈希冲突的概率是最小的.
代码如下:
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;
}
};布隆过滤器的插入
布隆过滤器当中需要提供一个Set接口,用于插入元素到布隆过滤器当中,插入元素是,需要通三个哈希函数分别计算出该元素对应的比特位,然后将位图中这三个比特位设置位1即可.
代码如下:
size_t i1 = Hash1()(key) % N;
size_t i2 = Hash2()(key) % N;
size_t i3 = Hash3()(key) % N;
_bs.set(i1);
_bs.set(i2);
_bs.set(i3);
}布隆过滤器的查找
布隆过滤器当中还需要提供一个Test接口,用于检测某个元素是否在布隆过滤器当中,检测时通过三个哈希函数分别计算出该元素对应的三个比特位.然后判断位图中这三个比特位是否倍设置成1.
- 只要这三个比特位中有一个未被设置成1则说明该元素一定 不存在.
- 如果这三个比特位全部被设置,则返回true表示该元素存在(可能存在误判).
bool Test(cosnt K& key)
{
size_t i1 = Hash1()(key) % N;
size_t i2 = Hash2()(key) % N;
size_t i3 = Hash3()(key) % N;
if (_bs.test(i1) == false)
return false;
if (_bs.test(i2) == false)
return false;
if (_bs.test(i3) == false)
return false;
return true;
}布隆过滤器的删除
布隆过滤器一般不支持删除操作,原因如下:
- 因为布隆过滤器判断一个元素存在时可能存在误判,因此无法保证要删除的元素确实存在在布隆过滤器当中,此时位图中对应的比特位清0会影响其他元素.
- 此外,就算要删除的元素确实存在在布隆过滤器当中,也可能该元素映射的多个比特位当中有些比特位是于其他元素共用的,此时将这些比特位清0也会影响其他元素.
如何让布隆过滤器支持删除?
要让布隆过滤器支持删除,必须要做到一下两点:
- 保证删除的元素在布隆过滤器中存在,比如刚才举的昵称例子,如果通过调用Test函数得知要删除的昵称可能存在布隆过滤器当中后,可以进一步遍历存储昵称的文件,确认该昵称是否存在.
- 保证删除后不会影响到其他元素.可以位图中的每个比特位设置一个对应的计数器,当插入元素映射到该比特位是将该比特位对应的计数器值++,当删除元素时将该元素对应比特位计数值--即可.
可是布隆过滤器最终还是没有提供删除接口,因为使用布隆过滤器本来就是要节省空间和提高效率.在删除时需要遍历文件或磁盘确认待删除元素确实存在,而文件IO和磁盘IO的速度相对比较慢,并且位图中的每个比特位额外设置一个计数器,就需要多余原位图几倍的内存空间,这个代价还是不小的.
布隆过滤器的优点
- 增加和查询元素的时间复杂度位O(K)(K为哈希元素的个数,一般比较小),与数据量无关.
- 哈希函数相互之间没有关系,方便硬件并行运算.
- 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势.
- 在能够承受一定误判时,布隆过滤器比其他数据结构有着很大的空间优势
- 数据量很大时,布隆过滤器可以表示全集,而其他数据结构不能
- 使用同一组哈希函数的布隆过滤器可以进行交,并,差运算.
布隆过滤器的缺点
- 有误判率,即存在假阳性,即不能正确判断元素是否在结合中
- 不能获取元素本身
- 一般情况下不能从布隆过滤器中删除元素
布隆过滤器的使用场景
使用布隆过滤器的前提是,布隆过滤器的误判不会对业务逻辑造成影响.
比如当我们首次访问某个网站时需要手机号注册账号,而用户的各种数据实际上都是存储在数据库当中,也就是磁盘上面.
- 当我们用手机号注册时,系统就需要判断你填入的手机号是否已经注册过,如果注册过则会提示注册失败.
- 但这种情况下系统不可能直接去磁盘当中遍历用户数据,判断该手机号是否注册过,因为磁盘Io时是很慢的,这会降低用户体验,
- 这种情况下就可以使用布隆过滤器,将所有注册过的手机号全部添加到布隆过滤器当中,当我们使用手机号进行注册账号时,就可以直接去布隆过滤器当中查找.
- 如果在布隆过滤器中查找后发现该手机号不存在,则说明该手机号没有被注册过,此时就可以让用户进行注册避免了磁盘IO.
- 如果在布隆过滤器中查找后发现该手机号存在,此时还需进一步访问磁盘进行复核,确认该手机号是否真的被注册过,因为布隆过滤器在判断元素时存在误判.
由于大部分情况下用户用一个手机号注册账号时,都知道自己没有用该手机号注册过账号的,因此布隆过滤器中查找后都是找不到的,此时即避免了进行磁盘IO.而只有布隆过滤器误判或用户忘记自己用该手机号注册过账号的情况下,才需要访问磁盘.
