布隆过滤器：

目录

1.布隆过滤器的引出

2.布隆过滤器的概念

3.布隆过滤器的模拟实现

布隆过滤器的删除

4.布隆过滤器优点

5.布隆过滤器缺陷

---

1.布隆过滤器的引出

我们在上一篇介绍海量数据处理的文章中在解决问题：给两个文件，分别有100亿个query（字符串），我们只有1G内存，如何找到两个文件交集？这一题中提出了布隆过滤器。没有看的可以看我上一篇文章对海量数据处理分析的那篇文章。对于这一问题的解决我们提出了两种方式。一种是精确的算法就是哈希分割，但是无疑哈希为了避免哈希冲突，那么就要给出足够多的空间来存储数据，本质就是以空间换取时间，我们又给出了位图的方式来解决问题，但是位图却无法解决哈希冲突，会导致处理结果不准确，那么我们是否可以找到一种即节省空间又可以高效快速查找数据的方式呢？你别说还真有，那就是布隆过滤器。海量数据处理文章链接奉上。http://t.csdn.cn/HUjt8http://t.csdn.cn/HUjt8

2.布隆过滤器的概念

• 布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的（紧凑型的是指用位图进行实现）、比较巧妙的概率型（概率是指他不是一定准确的这一点我们在下面对其详细介绍中会提到）数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

  

3.布隆过滤器的模拟实现

boomfilter.hpp
 
#pragma once
#include<iostream>
#include<string>
#include<vector>
#include"my_bitset.hpp"
#include"common.h"
//布隆过滤器就是通过多个哈希函数映射到位图中，将相应的位图位置置为1
//当我们对布隆过滤器中一个数据进行查询的时候用映射的时候的所有哈希函数
//计算出来每个比特位然后查看所有对应比特位是否为1，如为1那么次元素就存在
//可以保证的是元素在布隆过滤器中一定不存在，但是无法保证查询的结果一定存在
//于布隆过滤器中，因为通过哈希函数计算出来的映射到位图中的结果可能和其他元素
//在位图中的位置一样。
template<class K, size_t N = 100, class DTOK1 = DATOK1
								, class DTOK2 = DATOK2
								, class DTOK3 = DATOK3
								, class DTOK4 = DATOK4
								, class DTOK5 = DATOK5>
class bloomfilter
{
public:
	bloomfilter()
		:_con(),_count(0)
	{}
	void insert(const K key)
	{
		//通过字符串转化函数计算出字符串代表的元素
		DTOK1 fun1;
		size_t addr=fun1(key)%(5*N);
		_con.set(addr);	
		cout << key << ":" << addr << " ";
		DTOK2 fun2;
		 addr = fun2(key) % (5 * N);
		_con.set(addr);
		cout << addr << " ";
		DTOK3 fun3;
		 addr = fun3(key) % (5 * N);
		_con.set(addr);	
		cout << addr << " ";
 
		DTOK4 fun4;
		 addr = fun4(key) % (5 * N);
		_con.set(addr);
		cout << addr << " ";
 
		DTOK5 fun5;
		 addr = fun5(key) % (5 * N);
		_con.set(addr);
		cout << addr << " ";
		cout << endl;
		_count++;
	}
	bool test(const K key)
	{
		DTOK1 fun1;
		size_t addr = fun1(key) % (5 * N);
		cout << key << ":" << addr << " ";
 
		if (!_con.test(addr))
		{
			return false;
		}
		DTOK2 fun2;
		addr = fun2(key) % (5 * N);
		cout << addr << " ";
 
		if (!_con.test(addr))
		{
			return false;
		}
		DTOK3 fun3;
		addr = fun3(key) % (5 * N);
		cout << addr << " ";
 
		if (!_con.test(addr))
		{
			return false;
		}
		DTOK4 fun4;
		addr = fun4(key) % (5 * N);
		cout << addr << " ";
 
		if (!_con.test(addr))
		{
			return false;
		}
		DTOK5 fun5;
		addr = fun5(key) % (5 * N);
		cout << addr << " ";
 
		if (!_con.test(addr))
		{
			return false;
		}
		cout << endl;
 
		return true;
	}
	size_t size()
	{
		return N;
	}
	size_t count()
	{
		return _count;
	}
private:
	//这里因为我们要用五个比特位来映射一个元素所以我们开辟位图比特位的位数要乘五
	wbx::bitset<N*5> _con;
	size_t _count;
};
 
void test_boomfilter()
{
	bloomfilter<string> b;
	b.insert("张飞");
	b.insert("关羽");
	b.insert("刘备");
	b.insert("马超");
	b.insert("赵云");
	b.insert("曹操");
	b.insert("cba");
	b.insert("abc");
	if (b.test("马超"))
	{
		cout << "三国" << endl;
	}
	else
	{
		cout << "没有" << endl;
	}
	if (b.test("李逵"))
	{
		cout << "三国" << endl;
	}
	else
	{
		cout << "没有" << endl;
	}
}

common.h
 
#pragma once
#include<string>
//字符串哈希函数：
 
class DATOK1
{
public:
	size_t operator()(const string str)
	{
		return BKDRHash(str.c_str());
	}
private:
	size_t BKDRHash(const char *str)
	{
		register size_t hash = 0;
		while (size_t ch = (size_t)*str++)
		{
			hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..  
			// 有人说将乘法分解为位运算及加减法可以提高效率，如将上式表达为：hash = hash << 7 + hash << 1 + hash + ch;  
			// 但其实在Intel平台上，CPU内部对二者的处理效率都是差不多的，  
			// 我分别进行了100亿次的上述两种运算，发现二者时间差距基本为0（如果是Debug版，分解成位运算后的耗时还要高1/3）；  
			// 在ARM这类RISC系统上没有测试过，由于ARM内部使用Booth's Algorithm来模拟32位整数乘法运算，它的效率与乘数有关：  
			// 当乘数8-31位都为1或0时，需要1个时钟周期  
			// 当乘数16-31位都为1或0时，需要2个时钟周期  
			// 当乘数24-31位都为1或0时，需要3个时钟周期  
			// 否则，需要4个时钟周期  
			// 因此，虽然我没有实际测试，但是我依然认为二者效率上差别不大          
		}
		return hash;
	}
 
};
 
class DATOK2
{
public:
	size_t operator()(const string str)
	{
		return SDBMHash(str.c_str());
	}
private:
	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;
	}
	
};
class DATOK3
{
public:
	size_t operator()(const string str)
	{
		return RSHash(str.c_str());
	}
private:
	size_t RSHash(const char *str)
	{
		register size_t hash = 0;
		size_t magic = 63689;
		while (size_t ch = (size_t)*str++)
		{
			hash = hash * magic + ch;
			magic *= 378551;
		}
		return hash;
	}
 
};
 
class DATOK4
{
public:
	size_t operator()(const string str)
	{
		return APHash(str.c_str());
	}
private:
	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;
	}
 
};
 
 
class DATOK5
{
public:
	size_t operator()(const string str)
	{
		return JSHash(str.c_str());
	}
private:
	
	size_t JSHash(const char *str)
	{
		if (!*str)        // 这是由本人添加，以保证空字符串返回哈希值0  
			return 0;
		register size_t hash = 1315423911;
		while (size_t ch = (size_t)*str++)
		{
			hash ^= ((hash << 5) + ch + (hash >> 2));
		}
		return hash;
	}
 
};

布隆过滤器的删除

我们可以看到上面没有给出布隆过滤器的删除，这是因为用位图的方式实现布隆过滤器将删除布隆过滤器当中的元素是无法删除的。如果我们将一个元素的所有映射关系都置为0那么可能会影响其他元素的存在。

但是我们可以用另一种方式来实现布隆过滤器即可实现删除操作。用数组实现布隆过滤器。

4.布隆过滤器优点

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

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

3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。因为布隆过滤器保存的是元素存在与否的信息。

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

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

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

5.布隆过滤器缺陷

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)

2. 不能获取元素本身

3. 一般情况下不能从布隆过滤器中删除元素

4. 如果采用计数方式删除，可能会存在计数回绕问题