布隆过滤器

1. 布隆过滤器概念

在日常生活中，我们在使用新闻客户端看新闻时，它会给我们不断推荐新的内容，每次推荐时它都需要去重，去掉那些已经看过的内容.

那么，新闻客户端系统如何去实现推送的呢？

用服务器记录了那些用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录，如何快速的进行查找呢？

先来看看这样几种做法：

1. 用哈希表存储用户记录；缺点:浪费空间
2. 用位图存储用户记录，缺点：位图一般只能处理整型，如果内容编号是字符串，就无法处理了

上面两种方法都不能采取：

第三种方法：将哈希表与位图结合：布隆过滤器

布隆过滤器概念：

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

那么，布隆过滤器是怎样设计的呢？

假如现在我们有这样的一个场景：

有10亿个ip的文件，快速判断一个ip在这个文件中

2. 布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1，所以可以按照下列方式进行查找：分别计算每个哈希值对应的比特位存储的是否为0，只要有一个0，则该元素一定不在哈希表中，否则可能在哈希表中.

重点：布隆过滤器中如果查找某个元素不在时，则该元素一定不存在，如果该元素存在时，该元素可能存在，因此对于存在可能有误判.

比如：在布隆过滤器中查找"abcd"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的

3. 布隆过滤器的删除

布隆过滤器不能直接支持删除，因为在删除一个元素时，可能会影响其他元素.

所以，简单的将要删除的数的比特位置1，是不行的.所以，我们可以试着采用存计数的方式去来支持删除元素，

所以，布隆过滤器一般是不支持删除操作的.

4. 布隆过滤器的优点

1. 增加和查询相关元素的时间复杂度为O(K)，K为哈希函数的个数，一般比较小，与数据量的的大小无关
2. 哈希函数相互之间没有关系，方便硬件并行计算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构具有很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

5. 布隆过滤器的缺陷

1. 有误判率，即存在假阳性（False Position），即不能准确判断元素是否在集合中
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素

6. 布隆过滤器的应用

1. 注册账号

   布隆过滤器可以帮助我们快速判断一个昵称是否被使用过，如果在布隆过滤器中查找没有这个昵称，则它一定没有使用过（不存在误判），如果在，可以再去数据库中去查询一遍（可能有误判）.

2. 黑名单

   比如我们在浏览网站的时候，如果系统发现一个网站不在黑名单中，那它一定不在，就可以浏览，如果在，那可能误判，可以再去白名单中查找一遍

3. 在数据系统的上层设置一个过滤层，当要查找的关键字不在数据系统中时，效率提高

   

7. 布隆过滤器的实现

对于布隆过滤器哈希函数个数和布隆过滤器长度的选取：

布隆过滤器实现：

#pragma once
#include
using namespace std;

//一些将字符串转换为整数的哈希算法
template<class K>
struct BKDRHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct BKDRHash<string>
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

template<class K>
struct APHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct APHash<string>
{
	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;
	}
};

template<class K>
struct DJBHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};


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

struct JSHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 1315423911;
		for (auto ch : s)
		{
			hash ^= ((hash << 5) + ch + (hash >> 2));
		}
		return hash;
	}
};

template<size_t N,
class K = string,
size_t x = 5,
class HashFunc1 = BKDRHash<K>, 
class HashFunc2 = APHash<K>, 
class HashFunc3 = DJBHash<K>>
class BloomFilter
{
public:
	void set(const K& val)
	{
		size_t len = x * N;
		size_t index1 = HashFunc1()(val) % len;
		size_t index2 = HashFunc2()(val) % len;
		size_t index3 = HashFunc3()(val) % len;

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

	bool test(const K& val)
	{
		size_t len = x * N;
		size_t index1 = HashFunc1()(val) % len;
		size_t index2 = HashFunc2()(val) % len;
		size_t index3 = HashFunc3()(val) % len;

		return _bs.test(index1) && _bs.test(index2) && _bs.test(index3);
	}

private:
	bitset<x*N> _bs;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131