一、位图
1. 位图的引入
我们先来看一道面试题：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
首先，这到底乍一看去可以用以下两种方式解决：
- 遍历，时间复杂度O(N)
- 排序(O(NlogN))，利用二分查找: logN
但是在这里这两种方法都行不通，因为数据量太大了，在内存中放不下。
1G = 1024MB = 1024*1024KB = 1024*1024*1024Byte 约等于 10亿Byte，这里有40亿个整数，每个整数4个Byte，一共就是160亿Byte，换算过来大约为16G，而我们的内存空间一般是4G，如果我们使用排序+二分的方式，就必须开一个16G大小的整形数组，这显然是做不到的。那么哈希表就更做不到了，因为哈希表的每个哈希桶中还要存放一个指针来指向下一个节点，空间消耗会更大。
在这里因为题目只要求我们判断一个数在不在，并没有别的要求，所以我们不必将这些数存储下来，只需要对他们进行标记即可，而要标记一个数只需要一个比特位，如果二进制比特位为1，代表存在，为0表示不存在。
因此，位图就是用比特位来存放某种状态，适用于在海量数据中判断某一个数据是否存在的场景。实际上位图是哈希表直接映射的一种变形。
2. 位图的实现
💕 set——将对应的比特位置设为1
💕 reset——将对应的比特位置设为0
💕 test——查看x在或不在
代码实现：
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1, 0);
}
void set(size_t x) //将某一位bit位置为1
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_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;
};
这里的模板参数 N 是给定的 数据的范围 (特别注意这里N不是数据的个数)，因为C++中最小的数据类型是 char，占一个字节的空间，而一个字节中有8个比特位，可以标识8个元素，所以在构造函数中我们将 vector resize 到 N/8+1 即可，这里加1是因为 C++ 中的除法是整数除法，即直接舍弃余数，所以我们需要多开辟一个字节的空间。
对于 set、reset 和 reset 函数，目标值 x/8 可以得到 x 应该被映射到哪个下标，即第几个 char，x%8 可以得到 x 应该被映射到该下标的第几个比特位，然后再将对应下标的对应比特位置1或置0即可。
测试用例：
void test_bits1()
{
int arr[] = { 10, 1000, 20, 9999, 1883948, 23884 };
bitset<-1> bs;
for (auto e : arr)
bs.set(e);
bs.reset(10);
bs.reset(20);
for (auto e : arr)
cout << bs.test(e) << " ";
cout << endl;
}
有了位图之后，我们就可以解决上面的面试题了 – 由于题目中只说明了数据是无符号整数，而并没有给出具体的数据范围，所以我们可以将 N 定义为 -1 (有符号的 -1 等于无符号的最大值，参考 string 的 npos)，然后我们只需要将这 40 亿个元素依次进行 set，最后对目标元素进行 test 即可。
注：无符号数的最大值大约等于42亿9千万，也就是说一共需要这么多个比特位来进行标记，换算过来大约5亿字节，而1G内存大约有10亿字节，所以位图最多占用512M左右的内存，这是现在的一般计算机能够做到的。
C++库中的——bitset
C++ 中其实也提供了类似于位图这样的东西，只是 C++ 把它叫做位的集合 – bitset，它的功能比我们自己模拟实现的要更加丰富，不过主要功能比如 set、reset 和 test 都是一样的。
3. 位图的应用
- 快速查找某个数据是否在一个集合中
- 排序和去重
- 求两个集合的交集、并集
- 操作系统中磁盘块标记
- 例1
给定100亿个整数，设计算法找出只出现一次的整数？
当我们使用传统的位图时，只能表示在或不在，并不能表示某个数出现了几次。而位图只能表示灾祸不在是因为位图中一个数据只用一个比特位表示，而一个比特位只能标识两种状态，那么我们就可以将两个位图合并在一起，使用两个比特位来标识一个数据，而两个比特位一共可以标识四种状态，我们取三种即可：
00：不在01：出现了一次10：出现了两次及两次以上
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);
}
// 10
}
void Print()
{
for (size_t i = 0; i < N; ++i)
{
if (_bs2.test(i))
{
cout << i << endl;
}
}
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};
- 例2
一个文件有100亿个int，1G内存，设计算法找出出现次数不超过2次的所有整数？
这道题和上面那道题目的思路是一样的，无非就是我们需要将出现次数为0次、1次、2次、3次以及以上的都标识出来而已，所以需要将状态11利用起来，这里就不给出代码实现了，大家可以自己尝试实现一下。
- 例3
给定两个文件，分别有100亿个整数，只有1G的内存，如何找到两个文件的交集？
方法1： 将其中一个文件的值，读到内存的一个位图中去。再读取另一个文件，判断在不在上面的位图中，在就是交集，在这里需要注意的是，每次找到交集值的时候，都将上面位图对应的值设置为0，这样可以解决所有交集有重复值的问题。
方法2： 将文件1中的数据映射到位图1，将文件2中的数据映射到位图2，然后遍历取出某一个位图中的数据与另一个位图进行 && test。
操作系统中磁盘块标记
对于操作系统磁盘块标记来说，在操作系统中的文件系统中，文件系统会将磁盘上的空间划分为一个个固定大小的块，每个块都有一个对应的位图位；位图中为0的位表示该块是空闲的，为1的位表示该块已经被分配给某个文件或目录；
当文件系统需要分配一个新的块时，可以在位图中查找第一个为0的位，将其设置为1，并将该块分配给文件；当文件系统需要释放一个块时，可以将该块对应的位图位设置为0，表示该块变为了空闲块，可以被重新分配给其他文件或目录。
4. 哈希切割
给一个超过100G大小的log file，log中存着IP地址，设计算法找出出现次数最多的IP地址？
这道题目不能使用位图来解决，因为我们不知道相同IP最多会出现多少次，所以无法确定使用多少个比特位来标识一个数据。
那么既然100G太大内存放不下，我们能不能将这个文件平均分成100份小文件，这样每个文件只有1G大小，此时再依次放进 map 中进行统计呢？答案是也不行，因为再统计下一个小文件之前我们需要将前一个文件的统计结果即 map 中的数据情况，否则还是有可能因为 map 中存放的数据过多导致内存不足，但这样就会导致统计的次数不准，因为我们不能保证相同的IP全部被划分到同一个子文件中去；
这道题目正确的解法是进行哈希切割，先使用字符串哈希函数将IP转换成整型，然后再使用除留余数法将100G文件中的IP地址划分到不同的小文件中。
size_t Ai = HashFunc(IP) % 100;
经过哈希切割后，相同的IP一定会被划分到同一个小文件中，因为相同IP结果字符串哈希函数转换得到的整数时相同的。那么模出来的小标位置也是相同的。但是不同的IP也可能会被划分到同一文件中，因为会发生哈希冲突
- 子文件中有多种不同的IP地址，但是子文件大小在1G左右，说明这些IP地址出现的次数不多，此时我们可以直接使用 map 统计出这些IP地址的数量；(所有相同的IP地址一定会出现在同一个子文件中)
- 子文件中有多种不同的IP地址，但是子文件非常大，说明这些IP地址中的某一个/某几个IP地址出现次数非常多，此时 map 统计不下，我们可以换一种字符串哈希函数继续对这个子文件进行哈希切割，即递归子问题解决。
最终出现次数最多的那个IP地址会被全部映射到某一个子文件中，我们对该子文件使用 map 进行统计可以得到其出现的次数。
二、布隆过滤器
1. 布隆过滤器的引入
上面我们已经学习了位图，但是位图是有它的缺点的：
- 位图只适用于数据范围集中的情况，当数据比较分散时，存在空间的浪费。
- 位图只能针对整形，对于非整形数据它不能处理。
当然了，对于位图只能针对整形这一缺陷我们可以有解决的办法，比如针对某一特定类型定义一个HashFunc函数，将其转换为整形。例如：当数据类型是字符串string类型的时候，我们可以使用字符串哈希算法将字符串转换为整型，然后再将这个整形映射到位图中。
但是这种方法存在一个缺陷——不同的自负床通过同一个HashFunc函数转换出来的值可能是一样的，也就是会发生哈希冲突，这种情况会造成的问题：
- 位图中该字符串存在是不准确的，因为该比特位可能原本是0，但是和其它字符冲突，发生了误判，导致该比特位变为了1.
- 位图中字符串不存在是准确的，因为该比特位为0说明该字符串以及可能与该字符串发生冲突的其它字符串都没有插入过，当然前提是不考虑删除的情况。
注意： 由于通过字符串哈希函数转换出来的值得范围是不确定的，因此我们一般都会对结果进行取模，但是取模又会增加哈希冲突的概率，因为不同的整形取模后得到的结果可能是一样的。
布隆过滤器的提出
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，其特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
因此，布隆过滤器通过多噶哈希函数的方法来降低误判率，即让同一个元素映射多个下标位置，在查询的时候只有当这些位置都为1时才能表示该元素存在，而同一元素通过不同哈希函数映射出的不同下标同时被误判的概率肯定是比一个下标位置被误判的概率要低得多。
💕 哈希函数个数的选择
当然，也不是映射的下标位置越多越好，因为一个元素映射的下标位置越多，那么浪费的空间也就越多。详情可以参考：详解布隆过滤器的原理
这儿有哈希长度、布隆过滤器长度、插入元素个数与误判率的关系图：
- k == 3 时，m ≈ 4.3 n；即一个元素要消耗四个左右的比特位；
- k == 5 时，m ≈ 7.2 n；即一个元素要消耗七个左右的比特位；
- k == 8 时，m ≈ 11.6 n；即一个元素要消耗12个左右的比特位；
由此我们可以看出，哈希函数的个数选择3~5个是比较合适的。
2. 布隆过滤器的实现
在这里插入代码片
第一个模板参数N为数据的范围，第二个X为每一个数据最多占用多少个比特位，它与哈希函数的个数有关，由于我们实现的版本中默认使用的是三个哈希函数，所以X的缺省值为5，但我们也可以显示传递X的值来增加/减少哈希冲突的概率，最后三个模板参数分别为三个哈希函数，这里我们使用的字符串哈希算法分别为BKDRHash、APHash 和 DJBHash；
简单测试：
当我们加大测试用例，并分别构造相似的字符串集 和 不相似字符串集来分别测试其误判率时，测试代码如下：
void test_bloomfilter2()
{
srand(time(0));
const size_t N = 10000;
BloomFilter<N> bf;
std::vector<std::string> v1;
std::string url = "https:///-clq/archive/2012/05/31/2528153.html";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.set(str);
}
// v2跟v1是相似字符串集，但是不一样
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string url = "https:///-clq/archive/2012/05/31/2528153.html";
url += std::to_string(999999 + i);
v2.push_back(url);
}
size_t n2 = 0;
for (auto& str : v2)
{
if (bf.test(str))
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
// 不相似字符串集
std::vector<std::string> v3;
for (size_t i = 0; i < N; ++i)
{
string url = "";
//string url = "https:///m/statistics/live/16845432622875";
url += std::to_string(i + rand());
v3.push_back(url);
}
size_t n3 = 0;
for (auto& str : v3)
{
if (bf.test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}
这里我们可以发现布隆过滤器的误判率是可控的 – 我们可以根据具体的应用场景来测试调整哈希函数的个数以及布隆过滤器的长度，最终实现出最符合当前应用场景的布隆过滤器。
布隆过滤器的删除： 布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素；但是我们也可以使用计数的方式强行让其支持删除操作，即使用多个位图来标记某一个元素出现的次数，其思路和 位图 中查找出现一次或两次的元素的思路一样，不过这里还存在一个问题 – 我们不知道元素最多的出现次数为几，所以无法确定要使用几个位图来标记一个元素；所以如果不是在某些特殊场景下布隆过滤器是不支持删除操作的。
3. 布隆过滤器的应用
在实际开发中布隆过滤器的应用场景还有许多，比如网站黑名单的设计等；所以布隆过滤器在实际开发中是比较重要的，在面试时被考察的也比较多，大家需要理解它的原理，特别是布隆过滤器到底是在是正确的还是不在是准确的，大家必须要能够正确回答并且清晰阐释这个问题。
4. 布隆过滤器的总结
解决位图只能处理整形和数据范围集中的缺陷 – 哈希函数和取模，但这样会导致哈希冲突从而发生误判，为了降低误判率我们需要合理选择哈希函数的个数以及布隆过滤器的长度。
布隆过滤器的优点：
- 增加和查询元素的时间复杂度为 O(K)，与数据量大小无关；(K为哈希函数的个数，一般都不会超过10)
- 不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势；\n在允许一定误判率的场景中，具有很大的空间优势和时间优势；
- 数据量很大时，布隆过滤器可以表示全集；
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算，从而实现计数功能。
布隆过滤器的缺点：
- 有一定的误判率，即存在假阳性，不能准确判断元素是否在集合中，但误判率是可控的；(补救方法：建立一个白名单，其中存储可能会误判的数据）
- 不能获取元素本身；
- 一般情况下不能从布隆过滤器中删除元素；
- 如果采用计数方式进行删除，会存在空间浪费，还可能会存在计数回绕问题。(计数回绕是指在计数的过程中，当计数器达到其最大值之后，继续累加将导致计数器值回到零)
布隆过滤器相关的面试题：
给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。
这道题和上一节 位图 中求IP地址个数那道题一样，都是考察哈希切割 – 使用相同的哈希函数分别对这两个文件进行切割，切割结果为 A0 ~ Ai，B0 ~Bi，因为哈希函数相同，所以 Ai 和 Bi 中相同的 query 及发生冲突的 query 都在同一个小文件中，此时我们只需要分别求出 Ai 和 Bi 相同下标小文件中的交集即可，需要注意的是，如果小文件很大，说明某一个或某几个 query 有大量重复，此时换一个哈希函数再分别对 Ai 和 Bi 小文件递归子问题进行哈希切割即可；
对于精确算法来说，我们需要先将 Ai 号小文件中的元素全部存入 set/map 中，再依次取 Bi 号小文件中的数据到 set/map 中查询即可得到交集，注意结果需要去重；
对于近似算法来说，我们可以先将 Ai 号小文件中的元素全部映射到一个布隆过滤器中，然后再依次取 Bi 号小文件中的数据到布隆过滤器中查询即可得到交集，注意结果也需要去重。
