位图、布隆过滤器、海量数据处理

正文开始前给大家推荐个网站，前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。

位图

概念：所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。但是位图只能判断正整数的在不在问题。
我们用一个比特位的0/1代表这个数的在不在。

我们可以看到，我们直接开最大数个比特位+1就可以把所有的数在不在映射到位图中，我们可以用char的数组也可以用int的数组，但是用位图的情况数据一般都比较大，我们综合考虑，用int的数组，一个位置可以表示32个比特位。实现比较简单。
代码有注释。

template <size_t N>
class bitset
{
public:
	bitset()
	{
		//N表示几个比特位，所以开空间需要/32,+1是为了方式向下取整导致空间少开
		_bits.resize(N / 32 + 1);
	}
	void set(const int& x)
	{
		// /32计算在数组中的第几个位置
		int i = x / 32;
		// %32计算在第几个比特位
		int j = x % 32;
		//将数组第i个元素的第j个比特位置为1
		_bits[i] |= (1 << j);
	}

	void reset(const int& x)
	{
		int i = x / 32;
		int j = x % 32;
		//将数组第i个元素的第j个比特位置为0
		_bits[i] &= ~(1 << j);
	}

	bool test(const int& x)
	{
		int i = x / 32;
		int j = x % 32;
		//将数组第i个元素的第j个比特位置为0就返回fasle，非0就返回true
		return _bits[i] & (1 << j);
	}
private:
	vector<int> _bits;
};

位图的应用

1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记

布隆过滤器

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

查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，也有可能不存在，因为有些哈希函数存在一定的误判。
比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
想要支持删除的话就需要使用引用计数，将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

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

布隆过滤器的实现
我们会用到位图这个结构来封装布隆过滤器。

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,
	size_t X = 5,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;
		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	bool Test(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		if (_bs.test(index1) == false)
			return false;
		size_t index2 = HashFunc2()(key) % len;
		if (_bs.test(index2) == false)
			return false;
		size_t index3 = HashFunc3()(key) % len;
		if (_bs.test(index3) == false)
			return false;
		return true; // 存在误判的
	}
	// 不支持删除，删除可能会影响其他值。
	void Reset(const K& key);
private:
	bitset<X* N> _bs;
};

优点

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

缺点

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

海量数据处理

海量数据一般数据都比较到，直接放内存肯定是放不下的，所以我们就要使用位图或者布隆过滤器来尝试着解决一下。

位图应用

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

这两个题的思路都是一样的，只使用一个位图是没法解决的，我们需要用位图的变形，使用两个位图，即一个数据映射两个位置，在不同的位图中,两个比特位可以标识4中不同的状态，出现0次(00),出现1次(01)出现2次(10)还有其他(11).

template <size_t N>
class two_bitset
{
public:
	void set(const int& x)
	{
		//00->01
		if (_b1.test(x) == false && _b2.test(x) == false)
		{
			_b2.set(x);
		}
		else
		{
			//01->10
			if (_b1.test(x) == false && _b2.test(x) == true)
			{
				_b1.set(x);
				_b2.reset(x);
			}
			else
			{
				//10->11
				if (_b1.test(x) == true && _b2.test(x) == false)
				{
					_b2.set(x);
				}
			}
		}
	}

	void print()
	{
		for (size_t i = 0; i < N; i++)
		{
			if (_b1.test(i) == false && _b2.test(i) == true)
			{
				cout << "1->" << i << endl;
			}

			if (_b1.test(i) == true && _b2.test(i) == false)
			{
				cout << "2->" << i << endl;
			}
		}
	}
private:
	bitset<N> _b1;
	bitset<N> _b2;
};

3. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

我们同样可以使用2个位图，每个文件映射一个位图，然后两个位图都是1的位就是交集。虽然有100亿个数据，我们还是只开42亿多个就可以了，因为在计算机中能表示的整数只有42亿多个，直接开bitset<-1>就可以，因为-1会被转化为size_t类型的。

布隆过滤器

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

近似算法就是直接使用布隆过滤器映射一个文件，然后读取另一个文件判断是否在布隆过滤器中。
精确算法的话，还是需要先把一个文件映射到布隆过滤器，然后读取另一个文件，判断该值在过滤器中的情况，如果不在，就说明一定不定交集，但是如果判断在的话，我们不能确定到底是在还是不在，所以需要遍历文件，得到准确情况。也可以使用哈希分割的思想，使用同一个哈希函数对文件A和文件B的元素操作，将两个大文件分切切分成相等份的小文件，然后在内存中找交集。

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

只有一个文件要要求出现次数最多的，光凭位图或者布隆过滤器时无法解决的。
由于文件log file的大小超过100GB，考虑使用相同的Hash函数将文件log file切分成200个小文件。使得每个小文件能够以合适的大小（不影响效率）加载到内存中,因为使用的是相同的Hash函数，所以相同的IP地址一定会被分到同一个文件，依次将每个小文件加载到内存中， 然后用map容器统计出每个小文件中各个 IP 地址出现的次数，然后比对各个小文件中出现次数最多的 IP 地址，最后能得到出现次数最多的IP。