哈希扩展：位图与布隆过滤器

1. 位图

1.1 位图引入

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

很经典的判断在不在的模型，那么可以使用set吗？答案是不可以的，40亿个整数大概需要16G的内存空间来进行存储，一般而言操作系统是不能也无法开辟这么大的空间，因此这种数据量大且仅需判断在不在的场景可以使用位图来解决。

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

一个整形能表示数的个数为2的32次方，因此就需要这么多个比特位来表示，换算成字节为2的29次方也就是500MB左右，500MB系统是可以开出来的。

若有负数的情况，需要做一次相对映射，让其加上一个数变成正数，其余所有数字都需要加上这个数，然后判断某个值是否存在则需要再减去这个数得到它的真实值即可

1.2 位图概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

1.3 位图的模拟实现

//位图的模板参数为非类型模板参数
//用来表示数的总范围
template<size_t N>
class bitset
{
public:
	bitset()
	{
		// 先开辟空间
		_a.resize(N / 32 + 1);
	}

	//三个主要成员函数：

	// 第x个比特位标记成1
	void set(size_t x)
	{
		//先找到是在第几个整数中
		size_t i = x / 32;
		//再找到是在这个整数的第几个比特位
		size_t j = x % 32;
		_a[i] |= (1 << j);
	}

	// 第x个比特位个标记成0
	void reset(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		_a[i] &= (~(1 << j));
	}
	// 检测第x个比特位是0还是1
	bool test(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		return _a[i] & (1 << j);
	}
private:
	// 由于要用到移位运算符，因此参数类型必须是整形家族的
	//若使用char则上面所有/或%32的位置都要改成8
	//因为char占8个比特位
	vector<int> _a;
};

1.4 位图相关问题

1. 给定100亿个整数，设计算法找到只出现一次的整数？

一个比特位只能表示两种状态，即在不在，无法统计对应数字的出现次数，而两个比特位则可以表示出四种状态，00 01 10和11，因此可以使用两个比特位即两个位图来统计次数，规定00代表没有出现，01代表出现一次，10代表两次及以上。

代码实现：

template<size_t N>
class twoBt {
public:
	void set(size_t x) {
		//如果是00则置为01，表示出现一次
		if (!b1.test(x) && !b2.test(x)) {
			b2.set(x);
		}
		//如果是01则置为10，表示出现次数≥2次
		else if (!b1.test(x) && b2.test(x)) {
			b1.set(x);
			b2.reset(x);
		}
		//其它情况均表示大于2次无需出口i
	}

	//判断是否出现一次，即为01
	bool isOnce(size_t x) {
		return !b1.test(x) && b2.test();
	}

private:
	//使用两个位图
	bitset<N> b1;
	bitset<N> b2;
};

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

一种方法是建立一个位图，然后将一个文件中的数据依次set到对应的位置，然后再依次检测另一个文件中的数据，看该数据对应要set的位置是否为1，若为1说明前面一个文件中出现了和当前相同的元素，就是交集，此时需要把该位置的值reset一下即置成0，因为可能会出现重复的值，但是交集没有重复，相当于去重。
另一种方法是建立两个位图，把两个文件中的数据依次set到对应位图中，然后遍历两个位图，若两个位图中的同一个位置都为1说明是交集，使用两个位图天然就完成了去重操作。

代码实现：

//使用第二种方法：
int main() {
	int a1[] = { 1,1,2,2,3,4,5,5,6 };
	int a2[] = { 3,5,7,9 };

	bit::bitset<10> b1;
	bit::bitset<10> b2;

	for (int x : a1) {
		b1.set(x);
	}
	for (int x : a2) {
		b2.set(x);
	}

	for (int i = 0; i < 10; ++i) {
		if (b1.test(i) && b2.test(i)) {
			cout << i << ' ';
		}
	}
	cout << endl;
	return 0;
}

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

和第一问非常类似，直接上代码：

template<size_t N>
class twoBt {
public:
	void set(size_t x) {
		//如果是00则置为01，表示出现一次
		if (!b1.test(x) && !b2.test(x)) {
			b2.set(x);
		}
		//如果是01则置为10，表示出现两次
		else if (!b1.test(x) && b2.test(x)) {
			b1.set(x);
			b2.reset(x);
		}
		//如果是10则置成11，表示出现三次及以上
		else {
			b1.set(x);
			b2.set(x);
		}
	}
	
	//判断出现0、1和2次
	//00、01和10
	bool isValid(size_t x) {
		return (!b1.test(x) && !b2.test(x)) || (!b1.test(x) && b2.test(x)) || (b1.test(x) && !b2.test(x));
	}
private:
	bitset<N> b1;
	bitset<N> b2;
};

1.5 位图的应用

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

2. 布隆过滤器

位图一般应用在判断整形数据是否存在的场景，得到的结果一定准确，若为字符串(或其它自定义)类型则得到的结果就不一定准确了，会存在误判的可能性，因为不同的字符串通过哈希函数得到的映射位置可能是一样的，这样便导致了冲突造成误判，如何有效缓解误判问题呢？

2.1 布隆过滤器概念

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

将哈希与位图结合，即布隆过滤器

需要注意的是，即使是布隆过滤器也无法完全杜绝误判的存在，只能降低误判率。

2.2 模拟实现

#include <iostream>
#include <bitset>
using namespace std;
struct BKDRHash {
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (auto ch : str)
            hash = hash * 131 + ch;
        return hash;
    }
};

struct APHash {
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (size_t i = 0; i < str.size(); i++) {
            size_t ch = str[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& str) {
        size_t hash = 5381;
        for (auto ch : str)
        {
            hash += (hash << 5) + ch;
        }
        return hash;
    }
};

namespace bit {
	template<size_t N,
			 class K = string,
			 class hashFunc1 = BKDRHash,
			 class hashFunc2 = APHash,
		     class hashFunc3 = DJBHash>
        class BloomFilter {
        public:
            void set(const K& key) {
                size_t hashi1 = hashFunc1()(key) % N;
                _bs.set(hashi1);

                size_t hashi2 = hashFunc2()(key) % N;
                _bs.set(hashi2);

                size_t hashi3 = hashFunc3()(key) % N;
                _bs.set(hashi3);
            }

            bool test(const K& key) {
                //计算出对应存储位置
                //只要有一个位置是0就是不存在
                size_t hashi1 = hashFunc1()(key) % N;
                if (!_bs.test(hashi1))
                    return false;

                size_t hashi2 = hashFunc2()(key) % N;
                if (!_bs.test(hashi2))
                    return false;

                size_t hashi3 = hashFunc3()(key) % N;
                if (!_bs.test(hashi3))
                    return false;

                //依旧是存在误判
                //不存在的值可能会返回true
                return true;           
            }

        private:
            bitset<N> _bs;
    };
}

一般而言，布隆过滤器是不支持删除的，因为简单的把某个位置置成0有可能会影响其它值的判定，比如x和y都映射到了1位置，若删除x，把1位置置成0则会影响到y的判定，y存在但是查找y会得到不存在的结果。

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

布隆过滤器的优势之一就是空间损耗小，若像上述支持删除功能的话就相当于把这个优势给抹掉了，需要酌情考虑

2.3 布隆过滤器相关问题

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

设两个大文件的名称分别为A文件和B文件。

近似算法：把A文件中的数据全部放进布隆过滤器，然后逐个检测B文件中的数据是否在过滤器中，如果不在那一定不是交集，如果在，很有可能就是交集，因为还存在小概率误判。

精确算法：可以将其分别平均分割成N份小文件(每个文件大小为几百兆即可)，然后把A文件中数据依次放入每个小文件中，然后依次拿A的每个小文件中的数据与B的每个小文件中的数据依次比对，相同就是交集，但是这种比对的效率很低，如果要提高效率则需要用到哈希切分。

2.3.1 哈希切分

同样是将其分割成N份小文件(无需平均分割)，编号为0~N，把A和B文件中的query依次通过哈希函数计算出一个位置i，然后将该query数据放入编号为Ai(或者Bi)的小文件中，由于使用的是相同的哈希函数，因此A和B文件中相同的query数据必然分别会存放到对应相同编号的小文件中(但也可能包含冲突的query)。

这里与哈希桶非常相似，每个相同的数据必然进入同一个桶，但是桶中不一定都是相同的数据，还可能包含不同但冲突的数据

切分完毕后，找交集，只需要把Ai文件中的数据依次放入哈希表中，然后再用Bi中的数据依次检测是否存在，在就是交集再把其从表中删除(防止重复)，这种做法极大的提高了比对效率，那还有什么问题没？

问题是每个小文件并不是平均切分的，因此可能某个小文件相同的或者冲突的query过多导致文件过大，该怎么办？

解决方案如下：先把该文件中的数据读出来放入一个set中，若set报错抛异常(bad_alloc)，那么说明该文件数据的冲突太多，set放不下了，这种情况则需要换个哈希函数继续对其进行切分，重新对数据进行映射。
若能够全部放进set中，则说明该文件中有大量相同的数据，这种情况直接进行比对即可。

还有一个与其类似的问题：
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？与上题条件相同，如何找到top K的IP？

同样使用哈希切分，切分成若干份小文件，把每个IP地址数据通过哈希函数计算出一个编号i，将其存进对应编号的小文件中，然后使用哈希表依次统计每个小文件中每个数据的出现次数，并且每统计一个文件都要更新出现次数最多的那个IP地址数据，全部文件统计完成后即可找到出现次数最多的那个IP地址。

而统计topK则需要再加个小堆结构来处理。

同样会出现某个小文件过大的问题，但是解决方法是一样的