布隆过滤器

布隆过滤器地提出：

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉
那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用
户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那
些已经存在的记录。 如何快速查找呢？
1. 用 哈希表存储用户记录 ，缺点： 浪费空间
2. 用位图存储用户记录，缺点： 位图一般只能处理整形 ， 如果内容编号是字符串，就无法处理
了 。
3. 将 哈希与位图结合 ，即 布隆过滤器

布隆过滤器的概念：

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

位图的实现（布隆过滤器是基于位图的基础上实现的）：

template<size_t bitCount>
class Bitset
{
public:
	Bitset(size_t bitCount=10)
		:_bitCount(bitCount)
		, _bit((bitCount >> 5) + 1,0)
	{

	}
	//设置which比特位为1
	void set(size_t which)
	{
		if (which > _bitCount)
		{
			return;
		}
		size_t index = which / 32;
		size_t pos = which % 32;

		_bit[index] |= (1 << pos);//"|"有一则是一 
	}
	//检测which比特位为1
	bool test(size_t which)
	{
		if (which > _bitCount)
		{
			return false;
		}
		size_t index = which / 32;
		size_t pos = which % 32;
		return _bit[index] & (1 << pos);//有0则为0 并没有改变原有的数据
	}
	//将which比特位设置为0
	void reset(size_t which)
	{
		if (which > _bitCount)
		{
			return;
		}
		size_t index = which / 32;
		size_t pos = which % 32;
		
		_bit[index] &= ~(1 << pos);
	}
	//获取位图中的比特位总数
	size_t size()const
	{
		return _bitCount;
	}


private:
	vector<int> _bit;
	size_t _bitCount;
};

布隆过滤器的实现：

//哈希函数 将原始数据通过哈希函数的转换形成特定的整形进行存储
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;
	}
};

template<size_t N,
	class K=string,
	class Hash1= BKDRHash,
	class Hash2= APHash,
	class Hash3= DJBHash>
class BloomFilter
{
public:
	//BloomFilter(){}
	void set(const K& key)
	{
		size_t len = N;
		size_t x1 = Hash1()(key) % len;
		size_t x2 = Hash2()(key) % len;
		size_t x3 = Hash3()(key) % len;
		_bs.set(x1);
		_bs.set(x2);
		_bs.set(x3);
	}
	//检查存不存在
	bool Test(const K& key)
	{
		size_t len = N;
		size_t x1 = Hash1()(key) % len;
		if (_bs.test(x1)==false)
			return false;
		size_t x2 = Hash2()(key) % len;
		if (_bs.test(x2) == false)
			return false;
		size_t x3 = Hash3()(key) % len;
		if (_bs.test(x3) == false)
			return false;

		return true;//存在误判 布隆过滤器的特点 不存在是肯定的
	}
	//不支持删除 可能会影响其他值
	//void Reset(const K& key);
private:
	Bitset<N> _bs;
};

布隆过滤器的测试：

void TestBF1()
{
	BloomFilter<100> bf;
	bf.set("猪八戒");
	bf.set("沙悟净");
	bf.set("孙悟空");
	bf.set("二郎神");

	cout << bf.Test("猪八戒") << endl;
	cout << bf.Test("沙悟净") << endl;
	cout << bf.Test("孙悟空") << endl;
	cout << bf.Test("二郎神") << endl;
	cout << bf.Test("二郎神1") << endl;
	cout << bf.Test("二郎神2") << endl;
	cout << bf.Test("二郎神 ") << endl;
	cout << bf.Test("太白晶星") << endl;
}
void TestBF2()
{
	srand(time(0));
	const size_t N = 100000;
	BloomFilter<N * 10> bf;

	std::vector<std::string> v1;
	//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
	std::string url = "猪八戒";

	for (size_t i = 0; i < N; ++i)
	{
		v1.push_back(url + std::to_string(i));
	}

	for (auto& str : v1)
	{
		bf.set(str);
	}

	// v2跟v1是相似字符串集（前缀一样），但是不一样
	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string urlstr = url;
		urlstr += std::to_string(9999999 + i);
		v2.push_back(urlstr);
	}

	size_t n2 = 0;
	for (auto& str : v2)
	{
		if (bf.Test(str)) // 误判
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	// 不相似字符串集
	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		//string url = "zhihu.com";
		string url = "孙悟空";
		url += std::to_string(i + rand());
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

布隆过滤器的优点：

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

布隆过滤器的缺陷：

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

布隆过滤器的应用：

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出
精确算法和近似算法
2. 如何扩展BloomFilter使得它支持删除元素的操作

哈希切割：

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

位图的应用：

1. 给定100亿个整数，设计算法找到只出现一次的整数？
2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整
数