哈希的应用（位图，布隆过滤器）-ag真人游戏

位图（整型）

1.面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数 中。【腾讯】

1. 遍历，时间复杂度o(n)
2. 排序(o(nlogn))，利用二分查找: logn
3. 位图解决 数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比 特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

位图概念
所谓位图，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

#pragma once
#include
#include
using namespace std;
class bitset
{ 
public:
	bitset(size_t bitnum)
		:_bitnum(bitnum)
	{ 
		_bits.resize((bitnum >> 8)  1, 0);
	}
	void set(size_t x)//把那个位设置成1，代表存在
	{ 
		//size_t index = x / 8;
		size_t index = x >> 3;
		size_t num = x % 8;
		_bits[index] |= (1 << num);
	}
	void reset(size_t x)//把那个位设置成0，代表不存在
	{ 
		//size_t index = x / 8;
		size_t index = x >> 3;
		size_t num = x % 8;
		_bits[index] &= (~(1 << num));
	}
	bool test(size_t x)//存在返回1，不存在返回0
	{ 
		size_t index = x >> 3;
		size_t num = x % 8;
		return _bits[index] & (1 << num);
	}
private:
	vector<char> _bits;//一个char，8个bite
	size_t _bitnum;
};
void testbitset()
{ 
	bitset bs(10000);
	bs.set(9999);
	bs.set(999);
	bs.set(99);
	bs.set(9);
	cout << bs.test(9999) << endl;
	cout << bs.test(999) << endl;
	cout << bs.test(99) << endl;
	cout << bs.test(9) << endl;
}
int main()
{ 
	testbitset();
	system("pause");
	return 0;
}

布隆过滤器（任意类型）

优点：节省空间，快（直接找到那个位）

缺点：容易误判，判断在一定是准确的，判断不在不一定准确

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看 过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记 录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查 找呢？

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

概念

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

emplate<class k, class hashfunc1, class hashfunc2, class hashfunc3>//一个值映射三个位置
class bloomfilter
{ 
public:
	void set(const k& key)//不支持reset，因为布隆过滤器映射了很多个位，把冲突的位置为零，会影响其他冲突的映射
	{ 
		size_t index1 = hashfunc1()(key);
		size_t index2 = hashfunc2()(key);
		size_t index3 = hashfunc3()(key);
		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	void test(const k& key)//只要有一个位不在，就能判断他不在
	{ 
		size_t index1 = hashfunc1()(key);
		if (_bs.test(index1) == false)
		{ 
			return false;
		}
		size_t index2 = hashfunc2()(key);
		if (_bs.test(index1) == false)
		{ 
			return false;
		}
		size_t index3 = hashfunc3()(key);
		if (_bs.test(index1) == false)
		{ 
			return false;
		}
		return true;//存在误判
	}
private:
	bitset _bs;
};
int main()
{ 
	system("pause");
	return 0;
}