位图

位图：使用比特位来表示某种状态。比特位为0表示不存在，为1表示存在。
适用于大量的数据且数据没有重复的情况。通常用来判断某个数据存不存在。

位图的实现

namespace xty
{
	// N代表一共有多少个数据	
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			//开n/8 + 1个字节，数据初始化为0
			_bits.resize(N / 8 + 1, 0);
		}
		void set(size_t x)
		{
			size_t i = x / 8;        //表示第几个字节
			size_t j = x % 8;        //表示第几个比特位
			_bits[i] |= (1 << j);    //把位置设为1

		}


		void reset(size_t x)
		{
			size_t i = x / 8;//表示第几个字节
			size_t j = x % 8;//表示第几个比特位
			_bits[i] &= (~(1 << j));  //把位置设为0
		}

		bool tset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;

			return _bits[i] & (1 << j);
		}

	private:
		vector<char> _bits;
	};



//测试代码
	void bitmaptest()
	{
		bitset<10> bs;
		int a[] = { 1,2, 3,4, 5, 6, 7, 8, 9 };
		for (auto e : a)
		{
			bs.set(e);
		}
		cout << bs.tset(10) << endl;
		int x = 0;
	}

}	

位图优缺点

优点：

• 速度快，节省空间

缺点：

• 只能映射整形，其他类型：浮点数、string等等不能存储映射。

关于位图的题目

1. 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？
   10亿个字节大约是1GB，40亿个整数大约是16GB。把40亿个数全存到内存中是不现实的。
   如果我们使用位图的概念，每个比特位表示一个数，那么只需要40亿个bit（约为512MB）大小的内存即可。大大节省了空间占用。出现的数比特位置为1，不存在的置为0，就可以查找了。

位图的应用

1. 给定100亿个整数，设计算法，找到只出现一次的整数？
   使用双位图的概念。00表示未出现过，01表示出现过一次，10表示出现过两次。
   实现如下：

	template<size_t N>
	class doubleset
	{
	public:

		void set(size_t x)
		{
			//00->01
			if (_bs1.tset(x) == false
				&& _bs2.tset(x) == false)
			{
				_bs2.set(x);
			}
			// 01->10
			else if (_bs1.tset(x) == false
				&& _bs2.tset(x) == true)
			{
				_bs1.set(x);
				_bs2.reset(x);
			}
		}


		void print()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (_bs2.tset(i))
				{
					cout << i << endl;
				}
			}
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};

	//测试代码
	void double_bit()
	{
		int a[] = { 3, 45, 53, 32, 32, 43, 3, 2, 5, 2, 32, 55, 5, 53,43,9,8,7,8 };
		doubleset<100> bs;
		for (auto e : a)
		{
			bs.set(e);
		}

		bs.print();
	}

2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
   解法1：将其中一个文件的值读到内存的一个位图中；再读取另外一个文件，判断在不在上面的位图中，在就是交集！！但是会有重复的值，需要再次去重才可以。
   解法2：
   
   法1适合数据量小的场景，因为判断在不在的时候读的是数据量的个数。
   而法2适合大数据量，不管多少数据只读2^31次方次。并且可以解决多个文件。

3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数？
   跟问题1，完全一样，稍微变一下即可。
   

布隆过滤器

参考来源

提出原因

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

1. 用哈希表存储用户记录， 缺点：浪费空间
2. 用位图存储用户记录，缺点：位图一般处理整形，如果内容编号是字符串，就无法处理了。
3. 将位图与哈希结合，就是布隆过滤器

布隆过滤器概念

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

操作

插入

将一个关键字使用不同的哈希函数，映射到多个位置，如上图：baidu的插入使用3个哈希函数，映射到三个位置。

查找

bloom判定为不在，是准的。
因为如果不在，三个比特位一定有0。
1有可能是被其他关键字哈希到的，所以说不能判断一定存在。

删除

bloom不支持删除操作。因为在删除一个元素时，可能会影响到其他元素。
比如：“baidu”和“zijie”都映射到了2这个位置。删了其中一个就要把该比特位置0.这会影响到另一个元素的判断。因此，bloom不支持删除。

一种支持删除的方法：将bloom的每个比特位扩展成一个小计数器，每映射一个，给该比特位加1。删除时，给k个比特位减1。通过多开空间，来实现删除功能。

缺点：

缺陷：

1. 无法确认元素是否真正在布隆过滤器中
2. 存在计数回绕

bloom优缺点

优点：

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

缺点：

1. 有误判率，即假阳性（补救方法：再建立一个白名单，存储可能会误判的数据）
2. 不能获取元素本身
3. 一般情况下，不能从bloom删除元素
4. 如果采用计数方式删除，可能会存在数据回绕。

关于bloom的题目

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集? 分别给出精确算法和近似算法
   近似算法：第一个文件放入布隆过滤器+第二个文件查询。
   精确算法：使用哈希切分，分别进入每个小文件里面找交集。

因为不是平均切分，所以可能会出现有些文件过大的情况。如何解决呢？
情况1：单个文件中，有某个大量重复的query
情况2：单个文件中，有大量不同的query

2. 如何扩展BloomFilter使得它支持删除元素的操作？
   扩充比特位进行计数。

实现

	template<size_t N, class K,
	class Hash1,
	class Hash2,
	class Hash3>
	class BloomFilter
	{
	public:
		void set(const K& key)
		{
			size_t hash1 = Hash1()(key) % N;   //用到了匿名对象的知识
			_bs.set(hash1);
			size_t hash2 = Hash2()(key) % N;   //用到了匿名对象的知识
			_bs.set(hash2);
			size_t hash3 = Hash3()(key) % N;   //用到了匿名对象的知识
			_bs.set(hash3);
		}


		//在不在
		bool test(const K& key)
		{
			//不在是准的
			size_t hash1 = Hash1()(key) % N;   //用到了匿名对象的知识
			size_t hash2 = Hash2()(key) % N;   //用到了匿名对象的知识
			size_t hash3 = Hash3()(key) % N;   //用到了匿名对象的知识
			if (_bs.test(hash1) == false || _bs.test(hash2) == false
				|| _bs.test(hash3) == false)
			{
				//有一个是假，就说明不在
				return false;
			}


			return true;  //存在误判，
			
		}

	private:
		static const size_t _X = 4;//设置开空间的倍数
		bitset<N* _X> _bs;    //三个哈希函数，开4倍的空间
	};

哈希切割问题

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

• 将文件用哈希切成500个小文件（相同的ip一定进入同一个文件，读取单个文件，就可以统计处ip出现的次数）。
• 依次处理每个小文件，使用一个unordered_map统计次数。
• 如果：统计过程中，出现抛内存异常，则说明单个文件过大，冲突太多，需要重新换哈希函数，再次切分这个小文件
• 如果没有抛异常，则正常统计。统计完一个小文件，记录最大的。clear再统计下一个小文件。

建立K个小根堆，统计。