处理大数据运算的利器 — 布隆过滤器原理以及设计

太过爱你忘了你带给我的痛 2022-06-05 03:53 115阅读 0赞

# 布隆过滤器 #

说到布隆过滤器千万别想到英雄联盟里面的布隆大叔. 我们今天认识的布隆过滤器是一个处理大数据问题的利器. 它可以进行粗略估计

一个数据是否存 在 在该集合当中.如果想判断一个元素是不是在一个集合当中，一般想到的是将所有元素保存起来，然后通过比较确定.

链表，树等等结构都是这种思 路. 但是随着集合中元素的增多，我们需要的存储空间越来越大.检索的速度也越来越慢. 效果不错的就 是

我们的哈希表，当然我们的布隆过滤器其实也 是使 用了我们的hash映射思想. 我们可以通过一个Hash函数将一个元素映射到一个位图当

中，如果这个点被置为1，那么集合当中就是有她的.反之则没 有.这 就是布隆过滤器的基本思想.

布隆过滤器用于字符串去重复，比如网络爬虫抓取时url去重，邮件提供商反垃圾黑名单Email地址去重，等等，用哈希表也可以用于元素

去重，但是占用空间比较大，而且空间使用率只有50%，布隆过滤器只占哈希表的1/8和1/4的空间复杂度，就能解决同样的问题，但是存在

误判，而且不能够删除已经有的元素，元素越多，误报率越大，但是不会漏报. 对于还需要删除的布隆过滤器，还有Counter Bloom

Filter ，这个是布隆过滤器的变体，可以删除元素.

但是我们都知道的哈希表是有哈希冲突的. 况且你是使用位处理的那么也就不存在Hash开链法这种优化方式了. 那么当你好几个数据同

时映射到一个位 怎 么办?? 那你就映射呗 我对于映射真的没有办法改变? 但是布隆过滤器不会坐以待毙，如果这样我可不可以使用好 几

个Hash算法，然后让你映射不 同的 位置当你过来检验的时候，必须这几个位都被置为1，那样你才能认定这个数字是存在的. 当然这里都

是 有数学建模的基础的，然而我又不是很理 解...  我就找到网上的一个图过来瞧瞧~

下图是布隆过滤器假正列概率p与位数大小m和集合中插入数据个数n的关系图. 假定Hash函数个数选取最优数目: K = (M/N)In

![20171117150009385][]

我们也看到了布隆过滤器是有缺陷的，他不够准确当数值足够大的时候误判率就会越来越大. 所以布隆过滤器只能够作为一个粗略的判

断.我们目前为 止已经大概的了解到它的基本原理. 我们可以发现布隆过滤器的判断存在是不准确的. 但是它判断不存在一定是准确的.

好了我们来缕一下布隆过滤器 的优缺点.

优点:相比于其他的数据结构，布隆过滤器在空间和时间方面都有巨大的优势.布隆过滤器存储空间和插入/查询时间都是常数.另外，

Hash函数相互之间 没有关系，方便由硬件并行实现. 布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势. 布

隆过滤器可以表示所有类型的数据， 其他任何数 据结构都不能.

缺点: 首先误判率是一定要提出来的，如果存入的元素数量增加，误判率就会增加. 但是如果元素数量过少，那还不如使用Hash表呢

还有，布隆过滤器当中不能随便删除元素. 因为同一个位有可能有好几个数据标记了它, 如果涉及一个引用计数却又太复杂啦.

现在我们理解清楚布隆过滤器的原理，那么我们尝试实现一个最简单的布隆过滤器试一试！

代码实现：

#include"BitMap.h"
    #include<string>
    
    
    template<class K>
    struct __HashFunc1
    {
    	static size_t BKDRHash(const char * str)
    	{
    		unsigned int seed = 131; // 31 131 1313 13131 131313
    		unsigned int hash = 0;
    		while (*str)
    		{
    			hash = hash * seed + (*str++);
    		}
    		return (hash & 0x7FFFFFFF);
    	}
    
    	size_t operator()(const K& key)
    	{
    		return  BKDRHash(key.c_str());
    	}
    };
    
    
    template<class K>
    struct __HashFunc2
    {
    	size_t SDBMHash(const char *str)
    	{
    		register size_t hash = 0;
    		while (size_t ch = (size_t)*str++)
    		{
    			hash = 65599 * hash + ch;
    			//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
    		}
    		return hash;
    	}
    
    	size_t operator()(const K& key)
    	{
    		return  SDBMHash(key.c_str());
    	}
    };
    
    
    template<class K>
    struct __HashFunc3
    {
    	size_t APHash(const char *str)
    	{
    		register size_t hash = 0;
    		size_t ch;
    		for (long i = 0; ch = (size_t)*str++; i++)
    		{
    			if ((i & 1) == 0)
    			{
    				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
    			}
    			else
    			{
    				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
    			}
    		}
    		return hash;
    	}
    
    	size_t operator()(const K& key)
    	{
    		return  APHash(key.c_str());
    	}
    };
    
    
    template<class K = string, class HashFunc1 = __HashFunc1<K>, class HashFunc2 = __HashFunc2<K>, class HashFunc3 = __HashFunc3<K>>
    class BloomFilter
    {
    public:
    
    	BloomFilter(size_t num)
    		:_bm(num * 5)
    		, _bitSize(num * 5)
    	{}
    
    	void Set(const K& key)
    	{
    		size_t index1 = HashFunc1()(key);
    		_bm.SetBit(index1);
    
    		size_t index2 = HashFunc2()(key);
    		_bm.SetBit(index2);
    
    		size_t index3 = HashFunc3()(key);
    		_bm.SetBit(index3);
    	}
    
    	bool Test(const K& key)
    	{
    		size_t index1 = HashFunc1()(key);
    		if (_bm.TestBit(index1) == false)
    		{
    			return false;
    		}
    
    		size_t index2 = HashFunc2()(key);
    		if (_bm.TestBit(index2) == false)
    		{
    			return false;
    		}
    
    		size_t index3 = HashFunc3()(key);
    		if (_bm.TestBit(index3) == false)
    		{
    			return false;
    		}
    
    		//所有位置都为真. 但是它是不准确的.
    		return true;
    	}
    
    private:
    	BitMap _bm;
    	size_t _bitSize;
    };
    
    void Test()
    {
    	BloomFilter<> T(4000000000);
    
    	T.Set("12312312411231215151251251252151251");
    	T.Set("12312312411231215151251251252151252");
    	T.Set("12312312411231215151251251252151253");
    	T.Set("12312312411231215151251251252151254");
    	T.Set("12312312411231215151251251252151255");
    	T.Set("12312312411231215151251251252151256");
    	T.Set("12312312411231215151251251252151257");
    
    	cout << T.Test("12312312411231215151251251252151251") << endl;
    	cout << T.Test("12312312411231215151251251252151252") << endl;
    	cout << T.Test("12312312411231215151251251252151253") << endl;
    	cout << T.Test("12312312411231215151251251252151254") << endl;
    	cout << T.Test("12312312411231215151251251252151255") << endl;
    	cout << T.Test("12312312411231215151251251252151256") << endl;
    	cout << T.Test("12312312411231215151251251252151257") << endl;
    
    	system("pause");
    
    }

用到的位图的代码在我的另外一个博客当中: [位图的原理以及设计][Link 1]

[20171117150009385]: /images/20220605/3d36ab20a731474d878ea92e25dff79b.png
[Link 1]: http://blog.csdn.net/dawn_sf/article/details/78544612