【【哈希应用】位图/布隆过滤器】

位图/布隆过滤器

位图
- 位图概念
- 位图的使用
- 位图模拟实现
布隆过滤器
- 布隆过滤器概念
- 布隆过滤器的使用
- 布隆过滤器模拟实现
位图/布隆过滤器应用：海量数据处理
- 哈希切分

位图

位图概念

计算机中通常以位bit为数据最小存储单位，只有0、1两种二进制状态，这决定了位可以用来保存某一项条件yes/no的信息，且这种方式是占用系统内存最小的方式。因此，C++中标准库提供bitset类，以位bit为最小单位，存储数据，主要用于提供位级别的操作。

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

位图的使用

初始化bitset,初始化同时给定bit的个数n 在这里插入图片描述

bitset<16> foo;
bitset<16> bar(0xfa2);
bitset<16> baz("0101111001"); //从右往左读取，如果字符串长度小于n位数，补0
foo: 0000000000000000
bar: 0000111110100010
baz: 0000000101111001

bitset操作汇总
在这里插入图片描述

位图模拟实现

template<size_t N>
class bitset {bitset(){_bt.resize(N / 8 + 1,0);}//将x位设位1void set(size_t x){size_t i = x / 8;size_t j = x % 8;_bt[i] |= (1 << j);}//将x位设位0void reset(size_t x){size_t i = x / 8;size_t j = x % 8;_bt[i] &= ~(1 << j);}//查询x在不在bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return _bt[i] & (1 << j);}
private:vector<char> _bt;
};

//海量数据处理时
void BitSetTest()
{// 开出42亿9千万个比特位bitset<-1> bs1;	bitset<0xffffffff> bs2;
}

布隆过滤器

布隆过滤器概念

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

与位图的区别：
布隆过滤器：布隆过滤器主要用于快速地判断一个元素是否可能存在于数据集合中。可能存在一定的误判率
位图：位图主要用于精确地判断一个整数是否存在于集合中。它可以不会出现误判。

在这里插入图片描述

布隆过滤器的使用

初始化
布隆过滤器使用一个长度为m的位图，并初始化所有位为0。同时，需要选择k个不同的哈希函数。

插入
当要将一个元素加入到布隆过滤器时，对该元素进行k次哈希计算，得到k个哈希值（通常是整数）。然后将位数组中对应的k个位置设置为1。
在这里插入图片描述

查询
布隆过滤器进行k次哈希计算，得到k个哈希值。
若其中有任何一个位置为0，则可以确定该元素一定不存在于布隆过滤器中；否则，可能存在（这里存在着一定的误判率，因不同的元素可能存在相同的哈希值，导致位图中相同位置表示了不同的元素存在情况）
在这里插入图片描述
删除
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
优化：将布隆过滤器中的每个bit位扩展成一个小的计数器，插入元素时，哈希函数计算后为k个位置，给该位置的计数器+1，删除元素时，元素相应位置计数器-1，通过多占用几倍存储空间的代价来增加删除操作。

注意事项：

哈希函数的选择：哈希函数应该能够均匀地分布哈希值，以最大程度减少冲突的可能性。
位数组的大小：位数组的长度m和哈希函数的个数k会直接影响布隆过滤器的误判率。通常情况下，m的大小与预期存储元素数量和容忍的误判率有关。
误判率：布隆过滤器存在一定的误判率，即可能判断某个元素存在于布隆过滤器中，但实际上并不存在。这是由于不同元素在位数组上可能发生冲突的原因。

布隆过滤器模拟实现

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.给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
解答：
1G=2^30=10亿bytes
40亿个int=160亿bytes=16G
数据量非常大，占用内存空间高，用位图可以减少占用内存空间
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

2.给定100亿个整数，设计算法找到只出现一次的整数？
用两个位图表示，可以表示的组合有：

组合	出现次数
00	0
01	1
10	2
11	3次以上

统计位图中存的是01的数即为所求

求两个集合的交集、并集

3.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
初始思路：一个文件所有值映射，读取另一个文件，判断在不在
问题：文件中可能存在多个相同的元素，得出的交集需要去重，耗费时间。
优化：两个文件两个位图，对应位置&运算，结果为1的该位置代表的元素是交集

操作系统中磁盘块标记

布隆过滤器应用
在这里插入图片描述
给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？给出精确算法
精确算法：
假设每个query占30个字节，则上面每个文件有3000亿字节==300G，文件很大，我们可以先将它们分成若干小文件，每个小文件之间找交集。
我们使用哈希切割来分割文件。
在这里插入图片描述
这样，相同的query一定进入标号相同的小文件。我们只需分别求两个标号相同小文件的交集。接下来，用set找交集，读出Ai，放到set，读Bi看在不在set，不在则删去。