【C++】布隆过滤器

布隆过滤器提出

我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容

问题来了,新闻客户端推荐系统如何实现推送去重的？

答:用服务器记录了用户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那些已经存在的记录

那问题又来了,如何快速查找呢？

1. 用哈希表存储用户记录,缺点：浪费空间
2. 用位图存储用户记录,缺点：不能处理哈希冲突
3. 将哈希与位图结合,即布隆过滤器

---

布隆过滤器概念

位图:节省空间,效率高 ,但是有局限性:只能处理整数 但是布隆过滤器可以处理字符串,自定义类型

---

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

例子:

布隆过滤器中一个值通过多个哈希函数,在位图中有多个映射位置,即使一个位置发生冲突了,还有另外的映射的值,降低了冲突的概率,由于映射多个位置,因此可能不同的值,处于同一个位置,虽然不能保证这个值一定存在,但是可以保证一个值一定不存在,因为只要有一个映射的位置为0,就说明该值不存在

---

问题:布隆过滤器会误判存在还是会误判不存在?

• 存在可能会误判！ 因为会产生哈希冲突,不同的字符串可能会映射在同一个位置, 一个字符串不存在但是可能会被误判成存在
• 为了减少减少误判,通常采用多个哈希函数来映射多个位置 即一个值映射多个位置

是一定会有哈希冲突的！！！因为整数是有限的,字符串是无限的

---

布隆过滤器应用场景

布隆过滤器会存在误判,所以通常应用在允许误判的场景之中

一般应用场景:数据量大,节省空间,允许误判

• 黑名单校验
  发现存在黑名单中的,就执行特定操作,比如：识别垃圾邮件,只要是邮箱在黑名单中的邮件,就识别为垃圾邮件,假设黑名单的数量是数以亿计的,存放起来就是非常耗费存储空间的,布隆过滤器则是一个较好的解决方案,把所有黑名单都放在布隆过滤器中,再收到邮件时,判断邮件地址是否在布隆过滤器中即可,

• 身份验证：
  大门口的身份验证,如果不是小区里面的人,直接就拒绝进入(不在是确定的),如果通过了布隆过滤器的判断,再去数据库中对比一次,这样通过一层布隆过滤器可以提高这个查找系统的效率

• 检测手机号是否注册过

  系统所有用户的电话号码都存储再数据库的用户表 . 如果这个手机号不在布隆过滤器就肯定没有注册过, 如果在布隆过滤器,那么这里可能存在误判,再查一次数据库复核一下

---

设计思路:

首先我们需要确定位图开辟多大的空间

假设k为3, 则->位图的大小大致应该为: m = 4.2*n

---

先准备几个哈希函数用于将字符串转为整形

//BKDR算法
struct BKDRHash
{size_t operator()(const string& s){// BKDRsize_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;}
};

---

template<size_t N>	非类型模板参数,共插入多少个值
size_t X = 4,	//X值越大,产生冲突的概率越低, N*X表示位图开辟多少个比特位空间,利用公式计算X
class K = string,
class HashFunc1 = BKDRHash,//一个字符串想映射几个比特位就给几个HashFunc仿函数计算哈希地址
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>class BloomFilter
{
public:
private:bitset<X*N> _bs;
};

---

布隆过滤器的插入

将值对应的每个哈希函数计算出的位置都置为1

//将key所映射的位置设为1
void Set(const K& key)
{size_t len = N * X;//总长度 //计算映射的哈希地址 HashFunc()是匿名对象size_t index1 = HashFunc1()(key) % len;size_t index2 = HashFunc2()(key) % len;size_t index3 = HashFunc3()(key) % len;//将对应的映射位置标志为1_bs.set(index1);_bs.set(index2);_bs.set(index3);
}

---

布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中 因此被映射到的位置的比特位一定为1,所以可以按照以下方式进行查找：

• 分别计算每个哈希值对应的比特位置存储的是否为0, 只要有一个映射位置为0代表该元素一定不在哈希表中
• 否则可能在哈希表中(因为存在误判)

//判断key是否在布隆过滤器中
bool Test(const K& key)
{//三个映射为都是1才在(可能存在误判),其中一个不是1就不在size_t len = N * X;size_t index1 = HashFunc1()(key) % len;size_t index2 = HashFunc2()(key) % len;size_t index3 = HashFunc3()(key) % len;if ( (!_bs.test(index1)) || (!_bs.test(index2)) || (!_bs.test(index3))){return false;}return true;//可能存在误判	
}

注意：布隆过滤器如果说某个元素不存在时,该元素一定不存在, 如果**该元素存在时,该元素可能存在也可能不存在.**因为有些哈希函数存在一定的误判

---

布隆过滤器删除

布隆过滤器不能直接支持删除工作, 因为在删除一个元素时可能会影响其他元素,因为不确定当前位置,是自己的,还是发生了哈希冲突其它的值映射过来的

如何支持修改呢? ->存储引用计数(有几个值映射在当前位置)

将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一, 删除元素时给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作

但是这种方法不太好, 因为计数器的大小不易确定,如果给小了,发生冲突会导致溢出(计数回绕:即最大值溢出变为 最小值) 如果给大了浪费空间,脱离了布隆过滤器的本质思想,

缺陷：

1. 无法确认元素是否真正在布隆过滤器中
2. 存在计数回绕

BloomFilter.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once//BKDR算法
struct BKDRHash
{size_t operator()(const string& s){// BKDRsize_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;}
};template<size_t N,	非类型模板参数,共插入多少个值
size_t X = 4,	//X值越大,产生冲突的概率越低, N*X表示位图开辟多少个比特位空间
class K = string,// 假设布隆过滤器中元素类型为K,默认为string类型
//每个元素对应3个哈希函数
class HashFunc1 = BKDRHash,//一个字符串想映射几个比特位就给几个HashFunc仿函数计算哈希地址
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>
class BloomFilter
{
public://将key所在的三个映射位设为1void Set(const K& key){size_t len = N * X;//总长度 //计算映射的哈希地址 HashFunc()是匿名对象size_t index1 = HashFunc1()(key) % len;size_t index2 = HashFunc2()(key) % len;size_t index3 = HashFunc3()(key) % len;//将对应的映射位置标志为1_bs.set(index1);_bs.set(index2);_bs.set(index3);}//判断key是否在布隆过滤器中bool Test(const K& key){//三个映射为都是1才在(可能存在误判),其中一个不是1就不在size_t len = N * X;size_t index1 = HashFunc1()(key) % len;size_t index2 = HashFunc2()(key) % len;size_t index3 = HashFunc3()(key) % len;if ( (!_bs.test(index1)) || (!_bs.test(index2)) || (!_bs.test(index3))){return false;}return true;//可能存在误判	}
// 不支持删除,删除可能会影响其他值,
// 一般情况不支持删除,why?->多个值可能会标记一个位,删除可能会影响其他key
// 如果非要支持删除的话,标记不再使用一个比特位,可以使用多个比特位,进行计数多少个值映射的这个比特位
// 但是这种方法是杀敌一千,自损八百的做法,因为消耗的更多的空间void Reset(const K& key);
private://此时k为3 则此时位图的大小大致应该为: m = 4.2*n 即X = 4bitset<N*X> _bs;
};
void TestBloomFilter()
{BloomFilter<100> bf;//最多存100个值 -》开辟100*4个比特位srand(time(0));size_t N = 100;std::vector<std::string> v2;for (size_t i = 0; i < N; ++i){std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";url += std::to_string(6789 + i);v2.push_back(url);}size_t n2 = 0;for (auto& str : v2){if (bf.Test(str)){++n2;}}cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
}

---

布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关

2. 哈希函数相互之间没有关系,方便硬件并行运算

3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势

4. 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势

5. 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

---

布隆过滤器缺陷

1. 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法：再建立一个白名单,存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除,可能会存在计数回绕问题

---