数据结构：位图、布隆过滤器以及海量数据面试题

1.位图

1.1概念

1. 引入
   给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
   （1）遍历： 时间复杂度O(N)
   （2）排序加二分：时间复杂度O(N*logN)
   其中 方法(2)是行不通的，因为内存很难装下这么多数据(40亿整数大概为16G)。
   方法(1)可行，但如果需要多次查询很耗时。
   
   （3）位图：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：
   
   方法（3）的优势的建立起这个位图后，查找任一数据在不在时间复杂度均为O(1)，而且只需要 16G / 32 = 0.5G(存储整形需要16G，现在一个比特位就可代表，一个整形有32个比特位)，空间占用很小。
2. 概念
   所谓位图，就是用比特位来存放某种状态(哈希思想的体现)，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

1.2实现

namespace mystd
{
	//叫bitset只是单纯和库里面统一而已，接口命名也是
	//库里面bitset使用基本也是这几个接口
	template<size_t N>  //N表示要表示整数的范围，即比特位个数
	class bitset  
	{
	public:
		bitset() 
		{
			//初始化这里，可能存在浪费，但几个比特位而已
			_bits.resize(N / 32 + 1, 0);
		}

		void set(size_t x)  //设置标记，表示x存在
		{
			//给你x，计算出x属于第几个整数，整数中的第几个比特位
			int i = x / 32;  //第几个
			int j = x % 32;  //第几个比特位
			//把对应的_bits[i]的第[j]位修改为1即可，方法是将1左移j位，或运算即可
			_bits[i] |= (1 << j);
		}

		void reset(size_t x)  //去标记，表示x不存在
		{
			int i = x / 32;
			int j = x % 32;
			//把对应的_bits[i]的第[j]位修改为0即可，方法(1)是将1左移j位 (2)取反(j位置为0，其它位置为1) (3)进行与运算
			_bits[i] &= ~(1 << j);
		}

		bool test(size_t x)  //看x在不在
		{
			int i = x / 32;
			int j = x % 32;
			//取到_bits[i]的第j位即可
			return _bits[i] & (1 << j);  //非0即真，0即假
		}
	private:
		vector<int> _bits;
	};
}

1.3位图应用

1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等

代码：

#include<iostream>
#include<bitset>
using namespace std;
//位图的应用
//快速查找某个数据是否在一个集合中
void test1()
{
	vector<int> a = { 0, 1, 2, 3, 4, 8, 99, 100, 150 };
	bitset<151> bit_set;
	for (auto e : a)
	{
		bit_set.set(e);
	}
	int x = 0;
	while (cin >> x)
	{
		if (bit_set.test(x))
		{
			cout << x << "存在" << endl;
		}
		else
		{
			cout << x << "不存在" << endl;
		}
	}
}


//排序 + 去重
void test2()
{
	int a[] = {0, 1, 2, 3, 4, 8, 99, 99, 100, 100, 150};
	bitset<151> bit_set;
	vector<int> result;
	for (auto e : a)
	{
		bit_set.set(e);
	}
	//实际中应该在建立位图的过程中找出最大最小值，这里就不写了
	//min = 0， max = 150;
	for (int i = 0; i <= 150; i++)   
	{
		if (bit_set.test(i))
		{
			result.push_back(i);
		}
	}
	for (auto e : result)  cout << e << " ";
	cout << endl;
}


//求两个集合的交集、并集等
void test3()
{
	int a1[] = { 0, 1, 2, 3 };
	int a2[] = { 0, 2, 2, 4, 5, 6 };
	//交集
	bitset<7> bit_set1;
	bitset<7> bit_set2;
	for (auto e : a1)  bit_set1.set(e);
	cout << "交集为：";
	for (auto e : a2)
	{
		if (bit_set1.test(e) && bit_set2.test(e) == false)
		{
			bit_set2.set(e);  //过滤掉多次出现的数据
			cout << e << " ";
		}
	}
	cout << endl;

	//并集
	cout << "并集为：";
	bitset<7> bit_set3;  //去掉a1中重复的部分
	for (auto e : a1)
	{
		if (bit_set3.test(e) == false)
		{
			cout << e << " ";
			bit_set3.set(e);
		}
	}
	for (auto e : a2)
	{
		if (bit_set3.test(e) == false)  //把a2特有的提取出来
		{
			cout << e << " ";
		}
	}
	cout << endl;
}

2.布隆过滤器

2.1布隆过滤器的提出

想要判断某个数据在不在：

1. 哈希表，空间消耗大。
2. 位图，空间消耗小，只适用于整形。
3. 哈希位图相结合，即布隆过滤器。可适用各种复杂数据，只要能通过哈希函数转化出关键值即可。

2.2布隆过滤器的概念

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

图解：

2.3布隆过滤器的查找

结合前面可知，布隆过滤器的查找需要对多个位置进行判断，都为1才认为存在，有一个为0认为不存在。

1. 布隆过滤器判断存在，判断不准确。
   
   
2. 布隆过滤器判断不在，结果准确。

布隆过滤器存在误判，为什么还要使用？

以用户注册为例，用户名等信息存储在服务器数据库，每次注册新用户都要遍历所有数据，消耗太大。这个时候可以考虑使用布隆过滤器，对于判断不在的情况，是准确的，可以允许注册；对于判断在的情况就需要去遍历数据。实际当中可以过滤掉大量的请求，提高效率。

2.4布隆过滤器的实现

//三个字符串哈希函数
struct BKDRHash
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

struct APHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			char ch = key[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};


//布隆过滤器一般都是解决字符串
//关于布隆过滤器的长度，len = N * x，一般x取三以上，至于具体大小依据场景进行衡量
//（1）x过大，空间浪费
//（2）x过小，误判较多（不在判断为在），过滤效果不好
template<size_t N, size_t x = 5, class K = string, class HashFun1 = BKDRHash, class HashFun2 = APHash, class HashFun3 = DJBHash>
class BloomFilter
{
	void set(const K& key)
	{
		//一次标记3个位置，要让数值落在范围内部
		size_t len = N * x;
		size_t hash1 = HashFun1()(key) % len;
		size_t hash2 = HashFun2()(key) % len;
		size_t hash3 = HashFun3()(key) % len;
		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}

	bool test(const K& key)
	{
		//看三个位置，有一个为0就返回false
		size_t len = N * x;
		size_t hash1 = HashFun1()(key) % len;
		if (_bs.test(hash1) == false)  return false;
		size_t hash2 = HashFun2()(key) % len;
		if (_bs.test(hash2) == false)  return false;
		size_t hash3 = HashFun3()(key) % len;
		if (_bs.test(hash3) == false)  return false;
		return true;
	}
private:
	bitset<N * x> _bs;
};

2.5布隆过滤器的删除

布隆过滤器一般不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

比如：删除上图中"腾讯"元素，如果直接将该元素所对应的二进制比特位置0，“百度”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

（了解）一定要支持删除的话，可以采用引用计数的方法：
将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

2.6布隆过滤器的优点

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

2.7布隆过滤器的缺点

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

3.海量数据面试题

3.1哈希切分

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

1. 100G过大，无法直接在内存中处理，可以先切割成100个小文件。先将IP转化为整形key，然后key %= 100，相同IP会分到一样的小文件。
2. 依此读取这100个文件，找每个文件中出现次数最多，然后找出最大的那个。
3. 利用哈希切分可能存在冲突，如果某个小文件极大，可以更换哈希函数，对这个小文件再进行切分。

3.2位图应用

1. 给定100亿个整数，设计算法找到只出现一次的整数？
   解法一：整形范围为40多亿，位图需要的空间为0.5G，存在出现多次的情况，即三种状态，故一个比特位不够，可以增加一位，即用两个位图实现。当结果为00时代表没有出现、为01时代表出现了一次、为11时代表出现了多次。
   解法二：哈希切分，相同的数字一定会分到同个文件，对每个文件做统计即可。
2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
   （1）先哈希切分，key %= 500，文件一分出A0、A1、A2……A499，文件二分出B0、B1、B2……B499。其中相同的部分（交集）会被分到相同标号的文件，只需要A0对B0、A1对B1……A499对B499的两两找交集就行。
   （2）小文件过大的情况，更换哈希，再次切分即可。
3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
   （1）分析状态：一、出现0次。二、出现1次。三、出现2次。四、出现2次以上。
   （2）有四种状态，用两个比特位即可表示，即使用两个位图。当结果为00、01、10时都属于没超过2次，当结果为11时代表结果超过了两次。

3.3布隆过滤器

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
   （1）近似算法，先读取文件一，建立布隆过滤器。然后读取文件二，依次判断是否在布隆过滤器中，近似算法存在误判。
   （2）精确算法，对两个大文件进行哈希切分，两两小文件找交集即可。
2. 如何扩展BloomFilter使得它支持删除元素的操作
   （1）数据量不大，可以用几个位图实现。
   （2）数据量大，一个哈希值对应的就不是一比特位了，而是一个整形。