位图与布隆过滤器

引例

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
思路1：排序+二分查找
思路2：哈希或红黑树
因为40亿个整数要占用16GB
102410241024Byte 约等于10亿Byte=1GB
40亿*4Byte = 16GB
16G太大放不进内存，就算我们用归并排序对文件排序，也无法对文件使用二分查找，如果一段一段的放进内存里面查找的话，还不如在读取的时候就直接把他那个数挨个查找，放在内存，所以用哈希桶和红黑存储就更加不可能了，毕竟红黑树和哈希桶存储还有导致其他的内存开销。

位图

位图就是用数据中的一个位来标识，然后用哈希的直接定址法存储那一个标识bit位来表示某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
逻辑结构图：
问:如何确定我要存储的x值应该存储到哪一个位置？
x/8=x存储在那一个char里面
x%8= x存储在char的那一个位里面
问:如何在第一个char中的第5个字节置为1？
对0x01左移动5位(设为y)，然后再对第一个char(设为x)，x|=y，因为0|或任何数都是该数本身，而1|任何数都是1
注意，这里的为什么是左移而不是右移，要清楚左右移不是指移动的方向，而是指右移一向低地址移动，左移-向高地址移动
问:如何在第一个char中的第5个字节置为0？
对0x01左移动5位（设为y）,在对y取反就会得到 1110 1111, x&=y，因为1&任何数都是该数本身，而0&任何数都是0

位图的作用

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

代码实现：

#pragma once
#include <vector>
using namespace std;template<size_t N>
class bitset
{
public:bitset(){_bits.resize(N / 8 + 1, 0);}//置1void set(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] |= (0x01 << j);//为什么是左移动}//置零void reset(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] &= ~(0x01 << j);}// 查值bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return _bits[i] & (0x01 << j);}private:vector<char> _bits;
};

int main()
{bitset<-1> bitset;return 0;
}

注意这里这个bitset使用了一个非类型的模版参数来传入一个N用来表述，用于在开空间的时候要开多少多大？

非类型模板参数

模板参数分类类型形参与非类型形参。
类型形参即：出现在模板参数列表中，跟在class或者typename之类的参数类型名称。
非类型形参，就是用一个常量作为类(函数)模板的一个参数，在类(函数)模板中可将该参数当成常量来使用。

引例的解决方案

把40亿存到位图中，再用位图的test去查那个无符号整数到底有没有在位图里面

位图的题目：

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

解答：用两个位图来标识出现的状态， 00表示一次都没有出现，01表示出现一次，如果在01状态之后再出现的话就是多次出现

2. 1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

解答：同样用两个位图来标识出现的状态00一次都没有出现 01出现一次 10出现两次 11出现两次以上。

代码实现

#pragma once
#include "bitset.h"template<size_t N>
class TwoBitset
{
public:// 给定100亿个整数，设计算法找到只出现一次的整数？bool Test_OneTime(size_t x) const{if (bit1.test(x) && !bit2.test(x)){return true;}return false;}// 1个文件有100亿个int，1G内存，// 设计算法找到出现次数不超过2次的所有整数bool Test_NoMoreThanTwoTime(size_t x) const{if (bit1.test(x) && bit2.test(x)){return false;}return true;}void set(size_t x){if (!bit1.test(x) && !bit2.test(x)){bit1.set(x);}else if (bit1.test(x) && !bit2.test(x)){bit1.reset(x);bit2.set(x);}else if (!bit1.test(x) && bit2.test(x)){bit1.set(x);}}
private:bitset<N> bit1;bitset<N> bit2;
};

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

解答：用两个位图来存储两个文件，然后再对两个位图进行 &预算，得出的第三个位图就是交集

代码实现

//给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
void intersection()
{int a1[] = { 100,21,21,32,121,123,123,31,32,12,41,213,231,413312,312,213,122 };int a2[] = { -1,-1,100,21,21,21,32,32,121,123,123,31,32,1,12,4321,24,12,412, };bitset<-1> bit1;bitset<-1> bit2;for (auto val : a1){bit1.set(val);}for (auto val : a2){bit2.set(val);}for (size_t i = 0; i < -1; i++){if (bit1.test(i) && bit2.test(i)){cout << i << endl;}}
}

位图的缺点

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

布隆过滤器

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

布隆过滤器就是用位图+多个哈希函数映射来确定字符串在不在的一个key模型，但是布隆过滤器确定一个字符串不在是准确的，在是不准确的，如下图：
我们存放不同名字的时候，会映射三个位置，如果我搜寻这字符串的时候少于三个位置就是不在的，为什么呢？因为我们是映射是通过三个函数去映射三个位置，如果只有二个位置，那么就证明我并没有存进来，这那个位置只不过是存放其他值的时候刚好冲突到该字符串映射的位置而已，而为什么说在是不准的呢？是因为这三个映射位置也有可能是其他值冲突导致碰巧映射到而已。

White是没有映射存放的，但是碰巧他的映射位置被其他字符串冲突了

布隆过滤器实现代码

struct BKDRHash
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}
};struct APHash
{size_t operator()(const string& s){size_t hash = 0;for (long i = 0; i < s.size(); i++){size_t ch = s[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& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}
};// N最多会插入key数据的个数
template<size_t N,
class K = string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash>
class BloomFilter
{
public:void set(const K& key){size_t len = N*_X;size_t hash1 = Hash1()(key) % len;_bs.set(hash1);size_t hash2 = Hash2()(key) % len;_bs.set(hash2);size_t hash3 = Hash3()(key) % len;_bs.set(hash3);//cout << hash1 << " " << hash2 << " " << hash3 << " " << endl << endl;}bool test(const K& key){size_t len = N*_X;size_t hash1 = Hash1()(key) % len;if (!_bs.test(hash1)){return false;}size_t hash2 = Hash2()(key) % len;if (!_bs.test(hash2)){return false;}size_t hash3 = Hash3()(key) % len;if (!_bs.test(hash3)){return false;}// 在      不准确的，存在误判// 不在    准确的return true;}
private:static const size_t _X = 6;bitset<N*_X> _bs;
};

布隆过滤器的场景

能容忍误判的场景。比如:注册时，快速判断昵称是否使用过，假设现在要实现注册表单去判断有没有人用过昵称，就可以用到布隆过滤器，因为布隆过滤器对于不在这个结果是准确的。所以可以把昵称存放在布隆过滤器中快速过滤

哈希切分

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

首先，估算一下文件大小，100亿个query大概需要占用多少空间? 假设单个query，平均50byte，100亿个query是5000亿byte大概估算占用500G
用哈希函数把文件映射成小文件

为什么哈希切分只需要找A、B中对应i号的文件即可？
因为在哈希切分的时候，query字符串经过哈希函数的切分，会把冲突的字符串放在同一个桶里，只需要桶对桶之间进行交集计算即可

问题:因为不是平均切分，可能会出现冲突多，每个Ai，Bi小文件过大。…假设两个都是4-5G
所以要分类处理，
直接使用一个unordered set/set，依次读取文件query，插入set中
1、如果读取整个小文件query，都可以成功插入set，那么说明单个文件有大量重复的query
2、如果读取整个小文件query，插入过程中抛异常，则是单个文件有大量不同的query，换其他哈希函数，再次分割，再求交集。说明:set插入key，如果已经有了，返回false;如果没有内存，会抛bad alloc异常，剩下的都会成功。