C++进阶--哈希的应用之位图和布隆过滤器

哈希的应用之位图和布隆过滤器

一、位图
- 1.1 位图（bitset）的提出
- 1.2 位图的概念
- 1.3 位图的模拟实现
- - 1.3.1 位图的底层结构
  - 1.3.2 位图的成员函数
  - - 1.3.2.1 位图的构造
    - 1.3.2.2 位图的插入：set
    - 1.3.2.3 位图的删除：reset
    - 1.3.2.4 位图的查找：test
  - 1.3.3 位图的优缺点
- 1.4 位图的应用
二、布隆过滤器
- 2.1 布隆过滤器（BloomFilter）的提出
- 2.2 BloomFilter的概念
- 2.3 BloomFilter的优缺点
- - 2.3.1 BloomFilter的优点
  - 2.3.2 BloomFilter的缺点
- 2.4 BloomFilter的模拟实现
- - 2.4.1 BloomFilter的底层结构
  - 2.4.2 BloomFilter的插入：set
  - 2.4.3 BloomFilter的查找：test
  - 2.4.4 测试BloomFilter的误判率
- 2.5 BloomFilter的应用场景
三、海量数据处理
- 3.1 哈希切割
- 3.2 位图（只能处理整数）
- 3.3 布隆过滤器
四、完整代码
- 4.1 bitset.h
- 4.2 boomfilter.h
- 4.3 test.cpp

一、位图

1.1 位图（bitset）的提出

哈希是一种映射的思想。
先来看一道题：给40亿个不重复的无符号整数，没排序过。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
首先想到的解法可能有这几种：

解法1：遍历40亿个数，O（N）
解法2：先排序，快排O（ $Nlog_2N$ ），再利用二分查找O（ $log_2N$ ）
解法3：40亿个数放进set/unordered_set中，然后查找key在不在

思考：上面的解法看似可行，实际上有很大的问题，内存消耗太大。

40亿个整数要占用多少空间？大约16GB

1GB=102410241024= $2^{10}*2^{10}*2^{10}$ = $2^{30}$ （大约是10亿byte）
4GB=4* $2^{30}$ = $2^{32}$ byte（大约是42亿9千多万byte）
40亿个unsigned int整数=40亿4字节=160亿字节=1610亿字节≈16GB

这40亿个数据是放在文件中的，要对这40亿个整数进行排序：

难道在内存中开一个16GB空间的数组存放这些数据吗？显然不太现实，内存消耗太大，玩不起。
虽然归并排序可以对文件中的数据做外排序，但是效率很低，磁盘读写速度是很慢的，即使在文件中对40亿个数据排完了序，但是很难去算数据的下标位置，不能进行二分查找，那意义也不大了。
但是很难去算数据的下标位置，不能进行二分查找，那意义也不大了。
解法三，把数据放进set/unordered_set中，因为其底层是链式结构，除了存数据，还要存指针，所以附带的内存消耗更大，需要的空间比16GB还要大很多，更不可行。

所以我们一定要从节省内存的角度出发去思考，才能更好的解决问题。同时题目要求是：快速判断。
这里是判断一个数在不在数据集中，仔细想一想，也并不需要把这个数存起来，只需要有个标记去标记某个数在不在就行了。（就好比统计数组中数字的出现次数，我们用数的数值作为下标，在该下标处存储出现的次数，也并没有把数存下来）
标记一个数在不在，最小的标记单位是比特位（0/1），我们用一个比特位标记一个数，这样就节省空间了。
解法4：位图
某个数是否在给定的数据集中，有两种结果：存在或不存在，刚好是两种状态，那么可以使用一个二进制比特位来代表某个数是否存在的信息，比如二进制比特位为1代表存在，为0代表不存在。
我们把数据集的所有数用直接定址法映射到一张二进制表中，并用二进制值（1/0）标记其是否存在，这样每个数都有唯一的映射位置，不会出现哈希冲突。如果要判断某个数在不在数据集中，只需要找到这个数映射到表中的位置，然后查看该位置的比特位为1还是0。
我们是用每个无符号整数unsigned int的值来映射其哈希位置（比如25，就映射到第25个二进制位）：

因为unsigned int 的取值范围是0~ $2^{32}$ -1，所以一个无符号整数最小值为0，最大值为 $2^{32}$ -1（4,294,967,295，42亿9千多万）。
所以我们要开有 $2^{32}$ 个二进制位的表，才能映射完所有的无符号整数，但实际上只能开到有 $2^{32}$ -1个二进制位的表（因为size_t最大为0xffffffff），也就是开（ $2^{32}$ -1）/8个字节≈5亿多个字节≈0.5GB=512MB的内存空间。

一个bit位标记一个unsigned int值，512GB的内存就可以标记完42亿9千多万个整数的存在状态了，极大的节省了内存。
注意：位图并没有把整个数据集存储起来，而是将所有数映射到哈希表中，在映射的哈希位置上标记这个数在不在。
在这里插入图片描述

1.2 位图的概念

面对判断一个数在不在海量数据中的问题，红黑树和哈希表查找效率是挺高的，但是我们光把海量数据存起来够呛，同时红黑树和哈希表附带的内存消耗，所需空间更大，基于这样的原因，提出了位图这种数据结构。

template <size_t N>
class bitset
{
public:
//...
private:
	vector<char> _bits;
};

位图（bitset）是一种常见的数据结构，在给一个很大范围的数，判断其中的一个数是不是在其中。在索引、数据压缩方面有很大的应用。
位图是用数组实现的，数组的每一个元素的每一个二进制位都表示一个数据，0表示该数据不存在，1表示该数据存在。
位图最大的特点就是：快、节省空间，因为它不需要存储数据集，只要标记某个数在不在这个数据集中。

1.3 位图的模拟实现

1.3.1 位图的底层结构

如图，我们开一个数组，数组的每个元素是一个char（8个bit位），当然，是一个int（32个bit位）也可以，只是计算数据映射的比特位的方法略有差别。

在这里插入图片描述
思考：如何计算这个数据映射在数组中第几个char（字节）中的第几个比特位上：

字节位置=数据/8，得出x映射在第几个char中
位位置=数据%8，得出x映射在这个char中的第几个比特位上
注意：如果数组的每个元素是一个int，改成除以32就好了

比如数据x=10，则：

字节位置=10/8=1，说明10映射在第1个char（字节）中
位位置=10%8=2，说明10映射在第1个char（字节）中的第2个比特位上

1.3.2 位图的成员函数

1.3.2.1 位图的构造

默认构造函数：

bitset()
{
	_bits.resize(N / 8 + 1, 0);
}

1.3.2.2 位图的插入：set

set函数：
修改数据映射的比特位位置。位位置从最右边的位开始计数，即从0位置开始计数

void set(size_t x)
{
	size_t i = x / 8;  
	size_t j = x % 8;

	_bits[i] |= (1 << j);
}

1.3.2.3 位图的删除：reset

reset函数：
修改数据映射的比特位位置，位位置从最右边的位开始计数，即从0位置开始计数

void reset(size_t x)
{
	size_t i = x / 8;  //计算x映射的位在第i个char数组位置
	size_t j = x % 8;  //计算x映射的位在这个char的第j个比特位

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

1.3.2.4 位图的查找：test

test函数：检测数据x映射的比特位是否为1，即数据x是否存在

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

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

1.3.3 位图的优缺点

优点：
1、速度快、节省空间
缺点：
1、只能映射整形，其他类型如：浮点数、string等等不能存储映射

1.4 位图的应用

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

二、布隆过滤器

2.1 布隆过滤器（BloomFilter）的提出

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何快速查找到已经存在的记录呢？
判断一个元素是不是在一个集合里，这是一个典型的key模型。
思路1：用哈希表存储用户记录，缺点：浪费空间。
思路2：用位图存储用户记录，缺点：不能处理哈希冲突
思路3：将哈希与位图结合，即布隆过滤器。

场景一：现在有1亿个IP地址（字符串），给你一个IP，需要快速判断这个IP在不在其中，如何处理？
思路1：哈希切分。太慢了，还有没有更快的办法呢？
思路2：用一个字符串哈希算法，把IP地址转换成可以取模的整形（size_t），然后映射到位图的某一个比特位中，进行标记，0表示这个IP不存在，1表示这个IP存在。
问题是：如果不同的IP地址映射的是同一个比特位，会发生哈希冲突，可能存在误判：

判断一个值是否在，就是判断其映射的比特位是否为1。判断结果是不准确的，可能存在误判。
判断一个值是否不在，就是判断其映射的比特位是否为0。判断结果一定是准确的。（因为如果这个值在，其映射的比特位一定是1）
那该怎么办呢？布隆左思右想，发现想要判断一个值是否在，变得一定是准确得，几乎是不可能得。
因为总会存在哈希冲突。
虽然无法解决冲突，但是可以缓解冲突。
解决思路2的改进：
一个IP映射位图中的一个比特位，冲突概率大，误判概率大。
那么我们对同一个IP使用不同的哈希算法，让其映射多个比特位，缓解冲突，降低误判的概率。
虽然还存在一定的误判，但至少节省了空间。

场景二：判断一个人是不是这个学校的学生：

思路1：用[姓名]作为标识，来表示一个人，万一同姓名的人比较多，就会导致误判
思路2：用[姓名]、[性别]、[出生年月]作为标识，来表示一个人，同姓名的人比较多容易导致误判，而同姓名同性别同出生年月的人，可能有，但没有那么多，这样就缓解了冲突，降低误判概率。
核心思想：一个值映射多个位

2.2 BloomFilter的概念

布隆过滤器是由布隆在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，它的实现是一个很长的二进制向量（位数组）和一系列哈希函数
可以用来快速判断”一个元素一定不存在或者可能存在一个集合中“，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

优点：是空间效率和查询时间O（1）都比一般的算法要好的多。
缺点：是有一定的误识别率和删除困难。

核心思想：一个值映射多个位。

先思考：
1.哈希函数的个数需要权衡一下，映射的位越多，冲突的概率也越低，但是消耗的空间也越大；但是映射的位少，误判率就会变高，那映射多少位是合理的呢？
2.布隆过滤器的底层就是一个位数组，一次性开Oxffffffff个位空间也没必要，很浪费，那如何控制开多少个位是合理的呢？
如何选择哈希函数个数和布隆过滤器的长度

在这里插入图片描述
比如：规定哈希函数个数k=3，布隆过滤器长度m=（k/ln2）n≈4.2n（大约是插入元素个数的4.2倍）

2.3 BloomFilter的优缺点

2.3.1 BloomFilter的优点

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

2.3.2 BloomFilter的缺点

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

2.4 BloomFilter的模拟实现

2.4.1 BloomFilter的底层结构

布隆过滤器的插入元素可能是字符串，也可能是其他类型，只要提供对应的哈希函数将该类型的数据转换成整形就可以了。
一般情况下布隆过滤器都是用来处理字符串的，所以布隆过滤器可以实现为一个模板类，将模板参数T的缺省类型设置为string
这里布隆过滤器提供三个哈希函数，由于布隆过滤器一般处理的时字符串类型的数据，所以我们默认提供几个将字符串转换成整形的哈希函数：选取综合评分最高的BKDRHash、APHash和DJBhash这三个哈希算法：

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:
//...
private:
	static const size_t _X = 4;
	bitset <N*_X> _bs;
};

2.4.2 BloomFilter的插入：set

布隆过滤器复用bitset的set接口用于插入元素，插入元素时，我们通过上面的三个哈希函数分别计算出该元素对应的三个比特位，然后在位图中设置位1即可：

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;
	}

2.4.3 BloomFilter的查找：test

通过三个哈希函数分别算出对应元素的三个哈希地址，得到对应的比特位，然后去判断这三个比特位是否都被设置成了1。
如果出现一个比特位未被设置成1说明该元素一定不存在，也就是如果一个比特位为0就是false；而如果三个比特位全部都被设置，则return true表示该元素已经存在（注：可能会出现误判）

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;
	}

2.4.4 测试BloomFilter的误判率

相似字符串的误判率：测试发现，哈希函数个数和插入元素个数确定情况下，布隆过滤器长度越长，误判率越低。

void test_bloomfilter2()
{
    BloomFilter<100> bf; // 最多向布隆过滤器中插入100个元素

    // 1、构造100个不同的字符串，存放到 v1 中
    vector<string> v1;
    for (size_t i = 0; i < 100; i++)
    {
        string url = "https://www.bilibili.com/";
        url += std::to_string(123 + i); // 构造出100个不同的字符串

        v1.push_back(url);
    }

    // 把100个不同的字符串插入到布隆过滤器中
    for (const auto& e : v1) bf.set(e);
    
    /*--------------------------------------------------------*/

    // 2、构造100个不同的相似字符串，存放到 v2 中
    vector<string> v2;
    for (size_t i = 0; i < 100; i++)
    {
        string url = "https://www.bilibili.com/"; // 用了相同的网址
        url += std::to_string(456 + i); // 构造出100个不同的相似字符串

        v2.push_back(url);
    }

    // 检测这100个不同的相似字符串是否在布隆过滤器中（按理来说应该不在）
    size_t count1 = 0;
    for (const auto& e : v2)
    {
        if (bf.test(e)) count1++; // 如果判断在，说明误判了
        // 统计出有多少个字符串误判了
    }

    cout << "相似字符串的误判率：" << (double)count1 / (double)100 << endl;
}

2.5 BloomFilter的应用场景

布隆过滤器一般没有删除，因为布隆过滤器判断一个元素是会存在误判，此时无法保证要删除的元素在布隆过滤器中，如果此时将位图中对应的比特位清0，就会影响到其他元素了。这时候我们只需要在每个比特位加一个计数器，当存在插入操作时，在计数器里面进行++，删除后对该位置进行- -即可。但是布隆过滤器的本来目的就是为了提高效率和节省空间，在每个比特位增加额外的计数器，空间消耗那就更多了。

场景一：假设这里有一个网站，注册的时候需要每个用户取一个昵称，要求昵称不能重复。用户在注册的时候，输入一个昵称，系统需要判断一下这个昵称是否已被注册。
1.用户输入昵称点击提交后，先到后台数据库中去查，再返回判断这个昵称是否存在的结果。这种方式太麻烦了。
2.思考：那能不能当用户刚输入完昵称后，还没有点提交，切换到下一个输入框，这个时候就会提示用户，该昵称是否被占用。
解决思路
我们可以使用一个布隆过滤器，标记所有使用过的昵称，就能快速判断一个昵称是否被使用过。
这里虽然会存在误判，但在这种场景下，误判的影响并不大（因为判断一个昵称没被使用过，一定是准确的。判断一个昵称被使用过，可能存在误判，但没啥影响，大不了不用这个昵称了呗）

场景二：如果要求判断在或不在的结果都要是准确的，能否使用布隆过滤器呢？
也是可以的，比如验证一个手机号是否在系统中注册过，要求验证结果是准确的。
解决思路：使用一个布隆过滤器，标记所有注册过的手机号，判断这个手机号在不在布隆过滤器中：
1.如果不在，直接返回结果：未注册。
2.如果在，因为可能存在误判，所以再去服务器的数据库中查询，然后返回查询结果：未注册/已注册。
虽然查询效率降低了，但比起每次判断都去访问数据库，还是要高效不少。
有些服务器就会采用这种方式，来提高效率。

场景三：比如判断垃圾邮箱，垃圾邮箱的地址都会被标记映射到一个黑名单（布隆过滤器）中，当有人给你发邮件时，系统会快速判断出这个是否是垃圾邮件，然后进行拦截或分类。

系统判断这个邮件不在黑名单中，一定不会被拦截。
系统判断这个邮件在黑名单中，但这个邮件实际上可能不在黑名单中，误判了，把正常邮件拦截了，但影响不大，在垃圾箱还是能够找到这封正常邮件。

三、海量数据处理

3.1 哈希切割

1.给一个超过100G大小的log file（日志文件），log中存着IP地址，设计算法找到出现次数最多的IP地址？与上面的条件相同，如何找到topK的IP？如何直接用Linux系统命令实现？

解决思路：
此题不能用位图来处理了，因为位图处理的是整数，而IP地址是字符串（比如：192.0.0.1）
这里就需要用到[哈希切分]，大文件我们处理不了，就想办法把他切分小文件处理。
假设我们有4G内存，我们就把这个大文件平均切分成500份小文件，每份200M，但是这种平均切分实际上是不行的，因为同一个IP可能进入了多份小文件中，想要统计出每个IP最终出现的次数都是非常麻烦的，更别说找到出现次数最多的那个IP地址了
那怎么办呢？使用哈希切分
在这里插入图片描述
切分操作：

先创建500个小文件，分别叫0、1、…、500
然后读取100G log file，依次获取每个IP地址，用字符串哈希算法，把IP地址转换成可以取模的整数（size_t），比如使用BKDR算法：

size_t num=BKDRHash(IP)%100
然后这个IP地址就放入（映射到）第num号小文件。依次对所有IP进行处理，进入（映射到）对应的小文件。

如果运气好一点，平均下来差不多每个小文件就是1G左右；如果运气不好，可能有些小文件是512MB，有些小文件是2G，但至少是相对可控的。

思考：如果最小的小文件num还是过大该怎么办呢？
我们可以限制一个大小，在处理操作之前，先检测一下当前小文件的大小，如果超过2G，就换一个哈希算法把当前小文件再切小一些。

处理操作：

依次读取每个小文件，比如先读取文件0中所有的IP，用map<string, int>统计所有IP出现的次数，这里统计的IP出现次数，就是这个IP最终出现的次数。我们记录下文件0中出现次数最多的IP

思考：这里为什么用了map呢？因为是小文件，内存消耗不大。

然后再clear()掉map中的元素，再读取文件1中所有的IP，继续统计所有IP出现的次数，不断走下去。

问题一：我们要找到出现次数最多的IP地址，在最开始记录下当前小文件中出现次数最多的IP地址，然后再读取后面小文件的过程中，不断更新这个IP地址，当最后一个小文件读取完，就找到出现次数最多的IP地址了。
问题二：如果要找到topK的IP地址，建立K个小数的小堆即可。

这里采用哈希切分的关键是：

相同的IP地址，一定会进入编号相同的小文件。
因为用字符串哈希算法，同一个IP地址转换出来的哈希位置一定是相同的。

可以理解为这里就是100个存着文件指针的哈希桶。

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

3.2 位图（只能处理整数）

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

前面的题目是

在没排过序的海量数据中快速判断一个数在不在其中，是一个典型的key模型。
所以我们只需要用位图标记2中状态：存在或不存在，用一个比特位1/0来标记。

而这里是，在海量数据中找到只出现一次的数，不仅要判断这个数在不在，还要知道这个数的出现次数。
错误思路：

显然是不能把这100亿个整数存储在map/unordered_map（红黑树/哈希表）中
正确思路：
我们需要标记3种状态：不存在或出现一次或出现多次，则要用两个比特位来标记。
因为两个比特位有4种表现形式00/01/10/11
00：表示这个数不存在，01：表示这个数只出现一次，10：表示这个数出现多次
然后遍历位图，找到所有01标记的位置，此位置映射的就是只出现一次的整数。

那这里需要消耗多少空间呢？
这里要注意：虽然有100亿个整数，但并不是开100亿个比特位的表。
这100亿个unsigned int整数的取值范围都是0~ $2^{32}$ -1（大约是42亿9千多万个整数），如果每个整数映射一个比特位，需要消耗（ $2^{32}$ -1）/8个字节≈5亿多个字节≈0.5GB的空间，则每个整数映射两个比特位，需要消耗1GB的空间。
具体做法：
方法一：用一个位图，用2个连续的比特位标识一个数
需要修改2个不同位置的比特的值，不方便
方法二：封装两个位图，用两个位图的同一个位置的2个比特位来标识一个数
所以修改两个位图的同一个位置的比特位的值就好了，还可以复用之前写的位图代码。

template<size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		//00 -> 01
		if (_bs1.test(x) == false
			&& _bs2.test(x) == false)
		{
			_bs2.set(x);
		}
		else if (_bs1.test(x) == false
			&& _bs2.test(x) == true)
		{
			//01 -> 10
			_bs1.set(x);
			_bs2.reset(x);
		}

	}

	void Print()
	{
		for (size_t i = 0; i < N; ++i)
		{
			if (_bs2.test(i))
			{
				cout << i << endl;
			}
		}
	}


public:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

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

分析问题：找到两个文件的交集，只需要判断这个数是否分别在两个文件中，是一个典型的key模型
解决思路：定义两个位图

位图1标识第一个文件中所有数的存在状态（1存在、0不存在）
位图2标识第二个文件中所有数的存在状态（1存在、0不存在）
遍历位图中的N个比特位，检测两个位图的同一个位置的比特位的值是否都为1，如果都为1，说明此位置映射的这个数就是交集。

在这里插入图片描述
需要消耗的内存：
因为unsigned int 整数的取值范围是0~ $2^{32}$ -1（大约是42亿9千多万个整数），每个整数映射一个比特位，需要消耗（ $2^{32}$ -1）/8个字节≈5亿多个字节≈0.5GB的空间，这里开了两个位图，需要消耗1GB的空间。

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

和问题一类似
解决思路：封装两个位图，用两个位图的同一个位置的2个比特位来标识一个数。
我们需要标记4种状态：不存在或出现一次或出现两次或出现多次
因为两个比特位有4种表现形式00/01/10//11，所以：

00 - 表示这个数不存在
01 - 表示这个数只出现1次
10 - 表示这个数出现2次
11 - 表示这个数出现2次及以上
然后遍历位图，找到所有不是11标记的位置，此位置映射的就是出现次数不超过2次的整数。

3.3 布隆过滤器

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

近似算法：把第一个文件中的100亿个查询插入布隆过滤器，再读取第二个文件，看当前查询在不在布隆过滤器中。如果不在，说明一定不是交集；如果在，说明可能是交集（因为存在误判）
精确算法：[哈希切分]
假设一个query平均50字节，则100亿个query大约是5000亿字节，则文件大约是占500G

第一步:
先创建999个小文件，分别叫A0、A1…A999
先创建999个小文件，分别叫B0、B1…B999

第二步：
依次读取A文件中的query，使用字符串哈希算法转成可以取模的整型：

size_t=Hash(query)%200，把这个query放入到（映射到）第Ai号小文件中
依次读取B文件中的query，使用字符串哈希算法转成可以取模的整型：
size_t=Hash(query)%200，把这个query放入到（映射到）第Bi号小文件中
注意：平均下来，每个小文件是1G左右（可能有些文件大，有些文件小）

第二步结束后，文件中相同的query会分别进入编号相同的小文件，只需要去编号相同的小文件中找交集即可。
在这里插入图片描述

第三步：

在这里插入图片描述

第四步：
i=[0,999]，把Ai读进setA中，Bi读进setB中，setA和setB相同的query就是交集。

核心思想：
源文件太大，存在磁盘中，直接读取去找交集效率太低，先切分成一个一个的小文件，然后再去读取小文件找交集。

产生的问题：因为不是平均切分，可能会出现冲突多，每个Ai，Bi小文件过大，–假设两个都是4-5G

1.单个文件中，有某个大量重复的query
2.单个文件中，有大量不同的query

直接使用一个unordered_set/set，依次读取文件query，插入set中
1.如果读取整个小文件query，都可以成功插入set，那么说明情况1
2.如果读取整个小文件query，插入过程中抛异常，则是情况2，换其他哈希函数，再次分割，再求交集。
说明：set插入key，如果已经有了，返回false；如果没有内存，会抛bad_alloc异常，剩下的都会成功。

四、完整代码

4.1 bitset.h

#pragma once
#include <vector>


template <size_t N>
class bitset
{
public:
	bitset()
	{
		_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);
	}

	void reset(size_t x)
	{
		size_t i = x / 8;  //计算x映射的位在第i个char数组位置
		size_t j = x % 8;  //计算x映射的位在这个char的第j个比特位

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

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

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

private:
	vector<char> _bits;
};



void test_bitset1()
{
	bitset<100> bs;
	bs.set(10);
	bs.set(11);
	bs.set(15);
	cout << bs.test(10) << endl;
	cout << bs.test(15) << endl;

	bs.reset(10);

	cout << bs.test(10) << endl;
	cout << bs.test(15) << endl;

	bs.reset(10);
	bs.reset(15);

	cout << bs.test(10) << endl;
	cout << bs.test(15) << endl;

}


void test_bitset2()
{
	//bitset<-1> bs1;
	bitset<0xFFFFFFFF> bs1;
}




template<size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		//00 -> 01
		if (_bs1.test(x) == false
			&& _bs2.test(x) == false)
		{
			_bs2.set(x);
		}
		else if (_bs1.test(x) == false
			&& _bs2.test(x) == true)
		{
			//01 -> 10
			_bs1.set(x);
			_bs2.reset(x);
		}

	}

	void Print()
	{
		for (size_t i = 0; i < N; ++i)
		{
			if (_bs2.test(i))
			{
				cout << i << endl;
			}
		}
	}

public:
	bitset<N> _bs1;
	bitset<N> _bs2;
};


void test_twobitset()
{
	int a[] = { 3,45,53,32,32,43,3,2,5,2,32,55,5,53,43,9,8,7 };
	twobitset<100> bs;
	for (auto e : a)
	{
		bs.set(e);
	}
	bs.Print();
}

4.2 boomfilter.h

#pragma once
#include <bitset>
#include<string>


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;
	}

	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 = 4;
	bitset <N*_X> _bs;
};


void test_bloomfilter()
{
	BloomFilter<100> bs;
	bs.set("sort");
	bs.set("bloom");
	bs.set("hello world");
	bs.set("test");
	bs.set("etst");
	bs.set("estt");

	cout << bs.test("sort") << endl;
	cout << bs.test("bloom") << endl;
	cout << bs.test("hello world") << endl;
	cout << bs.test("test") << endl;
	cout << bs.test("etst") << endl;
	cout << bs.test("estt") << endl;


	cout << bs.test("ssort") << endl;
	cout << bs.test("tors") << endl;
}

4.3 test.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include<string>
using namespace std;

//#include "bitset.h"
//
//int main()
//{
//	test_bitset1();
//	//test_twobitset();
//
//	return 0;
//}


#include"boomfilter.h"

int main()
{
	test_bloomfilter();
	return 0;
}