【C++篇】哈希扩展：位图和布隆过滤器+哈希切割

常用接口：

面试题

面试题： 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在 这40亿个数中。【腾讯】

常规查找方法可以吗？ 比如：

1. 用set解决？
2. 排序+二分查找？

答案是不行！ 我们来算算如果用常规的整数去处理，需要多少空间？

40亿个整数大概占160亿比特位，也就是16个G左右，非常的夸张。

位图解决

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

将数据集{1, 3, 7,4,12, 16, 19, 13, 22, 18}映射到位图（本质上是一个vector<char>的一个对象）中:

最后判断一个数在不在，看其映射的byte位的值即可。

模拟实现位图

对于比特位数据的操作，无非就是0和1直接修改或判断。因此，位图的实现的核心思想是位运算。

本文我们用vector<int>，作为载体，实现位图：

代码语言：javascript

AI代码解释

template<size_t N> class Bitset { public: Bitset() { _a.resize(N / 32 + 1);//开好空间，默认初始空间位32位 } //………… private: vector<int> _a; };

1. set

具体逻辑：

1. 查找该比特位在哪个整数中i = x%32
2. 查找该比特位在整数的第几位j = x/32
3. 将该整数与对应比特位为1且其余为0的整数按位或_a[i] |= 1<<j