腾讯面试：有40亿整数，如何 判断一个 int 是在其中，越快越好 ？
本文 的 原文 地址本文 的 原文 地址
尼恩说在前面：
在40岁老架构师 尼恩的读者交流群(50+)中，最近有小伙伴拿到了一线互联网企业如腾讯、得物、阿里、滴滴、极兔、有赞、shein 希音、shopee、百度、网易的面试资格，遇到很多很重要的海量数据处理 相关面试题：
[*]给 40亿个不重复的无符号整数， 没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中 ？
[*]给定100亿个整数，设计算法找到只出现一次的整数？
[*]阿里面试：全国14亿人，统计出重名最多的前100个姓名?
[*]如何判断一个数是否在40亿个整数中？
前几天 小伙伴面试 腾讯，遇到了这个问题。但是由于 没有回答好，导致面试挂了。
小伙伴面试完了之后，来求助尼恩。那么，遇到 这个问题，该如何才能回答得很漂亮，才能 让面试官刮目相看、口水直流。
所以，尼恩给大家做一下系统化、体系化的梳理，使得大家内力猛增，可以充分展示一下大家雄厚的 “技术肌肉”，让面试官爱到 “不能自已、口水直流”，然后实现”offer直提”。
当然，这道面试题，以及参考答案，也会收入咱们的 《尼恩Java面试宝典》V145版本PDF集群，供后面的小伙伴参考，提升大家的 3高 架构、设计、开发水平。
最新《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请关注本公众号【技术自由圈】获取，后台回复：领电子书
原始的 面试问题：
下面是小伙伴面试腾讯，遇到的 完整问题：
给 40亿个不重复的无符号整数， 没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中 ？
常规的思路
下面内容从这道面试题开始引入，这道面试题，怎么回答 好呢？
容易想到的做法：
[*]直接遍历：比如set，map存储，然后直接遍历时间复杂度o(n)
[*]二分查找，比如array存储，先排序o(nlogn)，二分查找o(logn)，二分查找时间复杂度o(nlogn) + o(logn)
如果面试被问到类似的这种问题，上面两种回答绝对是挂了的。 那么我们该用什么方法来解决这个问题?
尼恩团队告诉大家，一定要讲到 下面的三种方案， 越全面越好。
第1种方案：位图
为什么要用位图？
首先我们对40亿个无符号整数算一下，它到底是多少G呢？
40亿个整数大概是40亿*4个字节=160亿个字节 ，4G=2^32byte，大概为42亿九千万字节，所以1G大概就是10亿字节 ，所以40亿个整数大概就是16G。
那这么大数据放到内存中，一般是放不下的，怎么办呢？ 可以首先考虑二分查找，比如map，set等等。
但是，map、set 还有额外的消耗，这更不可能完成了。
于是我们可以 用另一个 更加高效率 的结构：位图！
什么是位图？
位图本质：是一种直接定址法的哈希，因此效率很高，用O(1)就可以探测到对应位是0还是1，效率非常高，因此可以快速判断。
判断数据是否在给定的 整形集合中，结果是在或者不在，刚好是两种状态。
那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0 代表不存在。
利用每一个比特位的0或1的情况，来判断数在不在，所以40亿不重复的数，开辟2^32-1个比特位，转化为G，也就512m，从 16G到512M， 效能提升了 32倍。
位图的操作方法：
[*]设置位（set）：将某一位置上的位设为 1，表示该位置对应的元素存在。
[*]清除位（reset）：将某一位置上的位设为 0，表示该位置对应的元素不存在。
[*]检查位（test）：检查某一位置上的位是 1 还是 0，以判断该元素是否存在。
位图存储的案例：
通过位图判断数组元素是否存在，如下图
位图解决方案分析
1、确定位图大小
举例说明：
位图所给的大小取决于给的数的范围值，最大数是23，所以我们只需要开23个比特位就可以。
但是，内存是无法按比特位来分配，所以我们可以使用byte（或者int）来分配位图，byte相对于int粒度更细。
接下来的任务就是找到数在位图中的位置，然后置1
2、怎么算数在位图中那个位？
这里内存中的位图以byte为例，参考后面代码实现
[*]第一步，计算在哪一个 byte或者 int（这个案例是byte）。每个数我们可以先num/8，算出他在第几个byte里，比如：3 / 8 = 0，在第1个byte；
[*]第二步，计算在byte里边的 哪一位。 然后再num%8算出在哪一位，比如3 % 8=3，在第4位上面。
3、置位操作（set）
如何把任意一位置1，且不改变其他位？
<ul>第一步，先把目标位置设置为1（移位运算）。 就是 把“1” （这个是一个干净的1 ）左移 n位，就是 向高位移动 ，移动上面计算的位数（即其他位是0，只有要改变那一位是1），比如num=3 ，先算 1 > 3) + 1 long bytesNeeded = (maxBits >> 3) + 1; //左移3位就相当于/8，效率更快一些，但要注意运算符的优先级 bits = new byte[(int) bytesNeeded]; } // 设置第 x 位为 1 public void set(long x) { int i = (int) (x >> 3);// 字节索引（等价于 x / 8） int j = (int) (x & 7); // 位偏移（等价于 x % 8） bits |= (1 > 3); int j = (int) (x & 7); bits &= ~(1 > 3); int j = (int) (x & 7); return (bits & (1 > 5); // 等价于 x / 32 int offset = (int) (x & 0x1F);// 等价于 x % 32 bits |= (1 > 5); int offset = (int) (x & 0x1F); bits &= ~(1 > 5); int offset = (int) (x & 0x1F); return (bits & (1 = 0) { bitmap.set((int) num); // 标记存在位 } } } return bitmap.get((int) target); } /** * 简易哈希函数（实际生产环境建议用MurmurHash等） */ private static long hash(long key) { key = (~key) + (key >> 24); key = (key + (key > 14); } public static void main(String[] args) throws IOException { // 示例用法 partitionData("bigdata.txt");// 先分桶处理原始数据 System.out.println(checkExistence(123456789L)); // 检查数值是否存在 }}通过哈希切分结合位图的方式，可高效解决40亿级数据的存在性检测问题，兼顾内存限制与查询性能 。
还有没有其他方法呢？
讲到这里， 再回顾一下咱们的问题：
给 40亿个不重复的无符号整数， 没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中（腾讯面试题）
到此为止，用位图、 哈希表+位图就可以解决了。
哈希表+位图 需要占用磁盘空间。那么， 还有没有其他的 不用占用磁盘空间的方法呢。
可以。下一种就是 布隆过滤器。这是一种牺牲 准确度，换取 内存 的方法。
第3种方案：布隆过滤器
在讲布隆过滤器之前，我们要说一说位图结构的缺点是什么？
最大的缺点就是：
[*]开空间得看数据范围，一般要求范围集中，分散的话空间消耗就会上升
[*]只能针对整型 如果给了一堆字符串，可不可以使用位图判断是否存在呢？ 当然可以，可以使用哈希函数，将字符串转化为整型，再去映射到位图中。
当针对字符串来判断是否存在时，位图+多次哈希其实就是布隆过滤器了。
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的 概率型数据结构。
布隆（Burton Howard Bloom） 特点是 高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。
布隆（Burton Howard Bloom）不仅可以提升查询效率，也可以节省大量的内存空间。
话不多说，上例子来理解这段话：
当不同的字符串通过哈希函数转化为整型映射到位图中时，就会发生哈希碰撞！
比如find通过哈希函数可能和insert映射到同一位置，那么当find不存在时，但是他的位置的确已经被置为1，所以这就导致了：
[*]判断存在是不准确的
[*]判断不存在一定是准确的，因为位置是0，那一定不存在
于是，我们就要想一些办法，让他的误判率低一些：
可以增加不同的哈希函数，转化为不同的哈希值，去映射到多个位置，降低误判率
这样的话，我们可以看到，只有当一个字符串映射的全部位置都置为1时，这个数才可能存在，说的是可能存在，因为也可能存在哈希碰撞。但降低了哈希碰撞的概率，降低了误判率。
那还有问题就是：一个字符串映射多个位图的位置，那位图应该开多大呢？ 或者说如何选择哈希函数个数和布隆过滤器长度？
大佬研究出来的一个公式：
k为哈希函数个数，m 为布隆过滤器长度，n为插入的元素个数，p 为误报率
布隆过滤器长度计算公式：
public class CustomBitSet {
private byte[] bits;
// 构造函数：初始化 bitset，最大支持 maxBits 个无符号整数
public CustomBitSet(long maxBits) {
//通过加上 7 再进行 / 8 运算，可以实现向上取整的效果，确保即使有余数也能分配足够的字节数
// long bytesNeeded = (maxBits + 7) / 8;// 等价于 (maxBits >> 3) + 1
long bytesNeeded = (maxBits >> 3) + 1; //左移3位就相当于/8，效率更快一些，但要注意运算符的优先级
bits = new byte[(int) bytesNeeded];
}
// 设置第 x 位为 1
public void set(long x) {
int i = (int) (x >> 3);// 字节索引（等价于 x / 8）
int j = (int) (x & 7); // 位偏移（等价于 x % 8）
bits |= (1 << j); //将 bits 的第 j 位设为 1，其余位保持不变。
}
// 将第 x 位重置为 0
public void reset(long x) {
int i = (int) (x >> 3);
int j = (int) (x & 7);
bits &= ~(1 << j); //将 bits 的第 j 位设为 0，其余位保持不变。
}
// 判断第 x 位是否为 1
public boolean test(long x) {
int i = (int) (x >> 3);
int j = (int) (x & 7);
return (bits & (1 << j)) != 0; // 判断 bits 的第 j 位是否为 1
}
public static void main(String[] args) {
CustomBitSet bitSet = new CustomBitSet(4294967295L); // 40亿个数
bitSet.set(123456L);
bitSet.set(789012L);
System.out.println(bitSet.test(123456L)); // true
System.out.println(bitSet.test(999999L)); // false
}
}哈希函数个数计算公式：
public class XnyBitSet {
private int[] bits;
// 构造函数：初始化 bitset，最大支持 maxBits 个无符号整数
public XnyBitSet(long maxBits) {
// 计算数组大小：(maxBits + 31) / 32，确保向上取整
int size = (int) ((maxBits + 31) / 32); // 向上取整
bits = new int;
}
// 设置第 x 位为 1
public void set(long x) {
int index = (int) (x >> 5); // 等价于 x / 32
int offset = (int) (x & 0x1F);// 等价于 x % 32
bits |= (1 << offset); //在 bits 中设置对应位
}
// 将第 x 位重置为 0
public void reset(long x) {
int index = (int) (x >> 5);
int offset = (int) (x & 0x1F);
bits &= ~(1 << offset); // 清除对应位
}
// 判断第 x 位是否为 1
public boolean test(long x) {
int index = (int) (x >> 5);
int offset = (int) (x & 0x1F);
return (bits & (1 << offset)) != 0; // 判断 bits 的第 offset 位是否为 1
}
public static void main(String[] args) {
XnyBitSet bitSet = new XnyBitSet(4294967295L); // 42.9 亿个数
bitSet.set(123456L);
bitSet.set(789012L);
System.out.println(bitSet.test(123456L)); // true
System.out.println(bitSet.test(999999L)); // false
}
}现在来实现布隆过滤器：
[*]假设k==3，m=4.2n
[*]假设k==4，m=5.7n
布隆过滤器参考实现：
// 位图示例（假设数据类型为无符号整数）
Bitmap bitmap(MAX_VALUE); // MAX_VALUE为桶内最大值
for (auto num : bucket_data) {
bitmap.set(num); // 标记存在性
}当然也可以采用java 中的 现成的布隆过滤器实现方案， 常见的有：
[*]Apache Commons Collections，提供基础版布隆过滤器实现
[*]Guava库实现，基于内存，适合单机环境：
[*]Redisson分布式实现，基于Redis的分布式布隆过滤器，适合集群环境
那布隆过滤器支持删除吗？
no，当然不支持！
没有reset（不可以删除）的原因是：因为存在哈希冲突，修改一个数的哈希值映射位置的值，会影响到其他的数，导致结果不准确。
硬要有reset，就需要计数，通过计数（--)来控制，那就需要成倍的位图来表示个数，严重浪费内存空间。
如上图所示这样实现
海量数据处理 相关面试题
如果上面的题目不过瘾，再来几个 海量数据处理面试题
面试题2： 给定100亿个整数，设计算法找到只出现一次的整数？
这是一个位图 相关面试题。
给定100亿个整数，设计算法找到只出现一次的整数？
这个面试题，不仅仅是判存在，而是统计次数的话。
那么，就需要通过多状态位图（两个位图）。
[*]00：未出现。第一个 位图 上 对应位置的值 0，第一个 位图 上 对应位置 的值 0， 表示 一次都没有出现。
[*]01：出现一次。第一个 位图上 对应位置 的值 0，第一个 位图上 对应位置 的值 1， 表示出现一次。
[*]10：出现两次。第一个 位图 上 对应位置的值 1，第一个 位图 上 对应位置 的值 0， 表示出现两次。
[*]11：出现三次及以上。第一个 位图 上 对应位置的值 0，第一个 位图 上 对应位置 的值 0， 表示出现三次及以上。
我们可以在1GB内存中高效处理100亿个整数，找出只出现一次的值。该方法利用位图的紧凑存储和位运算的快速操作，解决了海量数据下的内存瓶颈问题。
如果 内存大点， 位图可以扩展。
以此内推，其实可以用三个位图， 统计8 次以内的次数。分别是 000/001/....等。
以此内推，其实可以用四个位图， 统计16 次以内的次数。分别是 0000/0001/....等。
一个使用多状态位图案例：
直接上代码：
import java.io.*;
import java.util.BitSet;
import java.util.HashMap;
public class HashPartitionDetector {
private static final int BUCKET_COUNT = 1000; // 分桶数量
private static final String BUCKET_PREFIX = "bucket_"; // 桶文件前缀
/**
* 分桶阶段：将数据根据哈希值分散到不同文件
* @param dataFile 原始数据文件路径
*/
public static void partitionData(String dataFile) throws IOException {
BufferedWriter[] buckets = new BufferedWriter;
// 初始化桶文件写入器
for (int i = 0; i < BUCKET_COUNT; i++) {
buckets = new BufferedWriter(new FileWriter(BUCKET_PREFIX + i + ".txt"));
}
try (BufferedReader br = new BufferedReader(new FileReader(dataFile))) {
String line;
while ((line = br.readLine()) != null) {
long num = Long.parseLong(line.trim());
int bucketId = (int) (hash(num) % BUCKET_COUNT);
buckets.write(line + "\n"); // 写入对应桶文件
}
}
// 关闭所有文件写入器
for (BufferedWriter writer : buckets) {
writer.close();
}
}
/**
* 检测阶段：检查目标值是否存在
* @param target 待检测数值
* @return 是否存在
*/
public static boolean checkExistence(long target) throws IOException {
int bucketId = (int) (hash(target) % BUCKET_COUNT);
String bucketFile = BUCKET_PREFIX + bucketId + ".txt";
// 使用BitSet存储桶内数据（适用于整数）
BitSet bitmap = new BitSet();
try (BufferedReader br = new BufferedReader(new FileReader(bucketFile))) {
String line;
while ((line = br.readLine()) != null) {
long num = Long.parseLong(line.trim());
if (num >= 0) {
bitmap.set((int) num); // 标记存在位
}
}
}
return bitmap.get((int) target);
}
/**
* 简易哈希函数（实际生产环境建议用MurmurHash等）
*/
private static long hash(long key) {
key = (~key) + (key << 21);
key = key ^ (key >>> 24);
key = (key + (key << 3)) + (key << 8);
return key ^ (key >>> 14);
}
public static void main(String[] args) throws IOException {
// 示例用法
partitionData("bigdata.txt");// 先分桶处理原始数据
System.out.println(checkExistence(123456789L)); // 检查数值是否存在
}
}set方法逻辑：
[*]一个数如果在两个位图中的同一位置都是0，那么说明就是0次 ，
[*]再进来的数就要将00第二位set为01，表示出现一次，
[*]后面同理可得。其他状态不用处理
printOnce方法逻辑：
[*]遍历元素，判断是01，则输出
面试题3： 1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
这是一个位图 相关面试题。
首先我们知道，整数的范围最大是42亿多，所以100亿个整数中，一定存在许多重复的整数。
所以将文件中的数据都放入位图中，只看 存在或者不存在两种状态，占用内存很少。
通过两个位图来表示次数，00（0次），01（1次），10（2次），11（3次及以上），然后控制条件（只找01，10）输出结果，和上一个问题其实是一样的。
代码如下：
m = k * n / 0.7面试题4：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
这是一个位图 相关面试题。
思路一：
将其中一个文件的所有值映射到一个位图，然后去遍历另一个文件中的数据去判断在不在。
这种思路存在一个缺陷，得到的交集中可能出现重复值的情况，而正常情况下交集中是不应该出现重复值，因此在前面求得交集后，还需要用 set 进行去重。
这里可能会出现重复的数据过多的情况，去使用 set 可能会超过 1G 内存。
思路二：
将两个文件中的整数分别映射到两个位图中，然后再将两个位图按位与一下，值为 1 的比特位对应的整数就是交集。
代码实现：
k = m / n * ln2面试题5：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
这是一个哈希切分相关面试题。
为什么不用位图？
由前面所学，我们可能会想到位图，但是行不通，要统计次数就要开辟多个位图，
成倍的开辟位图来表示次数的话，会占用大量的内存空间，内存也存不下。
哈希切分怎么做？
我们用的是map记录，但是在用map之前，要把大文件处理：
那我们就可以利用哈希的思想来把100G的文件分成100个小文件，每个1G，那么不就可以进内存了吗？
那怎么分？？？
[*]平均分？那当然不行，平均分对于分散的ip地址，都不在同一个小文件中，进入内存用map统计时，结果是不正确的。
[*]需要哈希切分，让相同的IP进入同一个分区小文件。
哈希切分示意图
我们可以对100G大文件中的ip进行哈希切分，利用哈希表的思想，将哈希值相同的放入同一个小文件中，然后通过一个一个的小文件进入内存读取并统计个数，搞完一个clear掉，记录再进下一个。
实现步骤：
1、哈希切分：
[*]使用 IP 的哈希值对分区数取模，将 IP 分配到不同的小文件中。
[*]保证相同 IP 始终被分配到同一个文件，从而保证统计正确。
2、递归处理：
[*]如果某个小文件超过内存限制（如 1GB），递归切分该文件为更小的子文件。
[*]使用不同的分区数（如每次乘以 10），确保最终每个文件都能被内存处理。
3、内存统计：
[*]每个小文件在内存中使用 HashMap 统计 IP 出现次数。
[*]记录每个小文件中出现次数最多的 IP，最后合并所有结果。
特性说明哈希切分使用 IP 哈希值 % 分区数，保证相同 IP 总在同一个文件中。递归处理若某小文件过大，继续切分，直到文件大小在内存限制内。统计效率每个小文件使用 HashMap 统计，时间复杂度 O(N)，空间复杂度 O(K)。适用性适用于大文件日志分析、IP 统计、TopK 等任务。参考实现
import java.util.BitSet;
/**
* 布隆过滤器Java实现
* @param <K> 键类型，默认为String
*/
public class BloomFilter<K> {
private final BitSet bitSet; // 位数组
private final int size; // 位数组大小(N*M)
private final HashFunction<K> hash1;
private final HashFunction<K> hash2;
private final HashFunction<K> hash3;
/**
* 构造函数
* @param n 预期元素数量因子
* @param m 每个元素占用的位数因子
* @param hash1 第一个哈希函数实现
* @param hash2 第二个哈希函数实现
* @param hash3 第三个哈希函数实现
*/
public BloomFilter(int n, int m,
HashFunction<K> hash1,
HashFunction<K> hash2,
HashFunction<K> hash3) {
this.size = n * m;
this.bitSet = new BitSet(size);
this.hash1 = hash1;
this.hash2 = hash2;
this.hash3 = hash3;
}
/**
* 添加元素到布隆过滤器
* @param key 要添加的键
*/
public void set(K key) {
// 计算三个哈希位置
int i = Math.abs(hash1.hash(key) % size);
int j = Math.abs(hash2.hash(key) % size);
int k = Math.abs(hash3.hash(key) % size);
// 设置对应位为1
bitSet.set(i);
bitSet.set(j);
bitSet.set(k);
}
/**
* 检查元素是否存在（可能有误判）
* @param key 要检查的键
* @return false表示一定不存在，true表示可能存在
*/
public boolean test(K key) {
// 检查第一个哈希位
int i = Math.abs(hash1.hash(key) % size);
if (!bitSet.get(i)) return false;
// 检查第二个哈希位
int j = Math.abs(hash2.hash(key) % size);
if (!bitSet.get(j)) return false;
// 检查第三个哈希位
int k = Math.abs(hash3.hash(key) % size);
if (!bitSet.get(k)) return false;
return true; // 所有位都为1，元素可能存在
}
/**
* 哈希函数接口
* @param <T> 键类型
*/
public interface HashFunction<T> {
int hash(T key);
}
// 示例哈希函数实现（BKDRHash）
public static class BKDRHash implements HashFunction<String> {
@Override
public int hash(String key) {
int seed = 131; // 31/131/1313等质数
int hash = 0;
for (char c : key.toCharArray()) {
hash = hash * seed + c;
}
return hash & 0x7FFFFFFF; // 确保为正数
}
}
}
public class BloomFilterTest {
public static void main(String[] args) {
// 创建布隆过滤器（预期100万元素，每个元素5位）
BloomFilter<String> filter = new BloomFilter<>(1_000_000, 5);
// 添加元素
filter.set("google.com");
filter.set("baidu.com");
// 测试存在性
System.out.println(filter.test("google.com")); // true（可能存在）
System.out.println(filter.test("baidu.com"));// true
System.out.println(filter.test("twitter.com")); // false（一定不存在）
}
}日志文件示例（ip_log.txt）
public class TwoBitSet {
private final XnyBitSet _bs1;
private final XnyBitSet _bs2;
private final long n;
// 构造函数：初始化两个位图，最大支持 n 个无符号整数
public TwoBitSet(long n) {
this.n = n;
this._bs1 = new XnyBitSet(n);
this._bs2 = new XnyBitSet(n);
}
// 设置整数 x 的出现次数
public void set(long x) {
if (!_bs1.test(x) && !_bs2.test(x)) { // 如果 x 不在两个位图中，则将其设置为 01
// 00 -> 01（第一次出现）
_bs2.set(x);
} else if (!_bs1.test(x) && _bs2.test(x)) { // 如果 x 在 _bs1 中，则将其设置为 10
// 01 -> 10（第二次出现）
_bs1.set(x);
_bs2.reset(x);
}
// 其他状态（如 10 或 11）不处理
}
// 打印只出现一次的整数
public void printOnce() {
for (long i = 0; i < n; ++i) {
if (!_bs1.test(i) && _bs2.test(i)) { // 如果 01，则输出 x
System.out.println(i);
}
}
System.out.println();
}
public static void main(String[] args) {
TwoBitSet twoBitSet = new TwoBitSet(100); // 最大支持 100 个整数
twoBitSet.set(10);
twoBitSet.set(20);
twoBitSet.set(30);
twoBitSet.set(10); // 重复出现
twoBitSet.set(20); // 重复出现
twoBitSet.set(20); // 再次出现
twoBitSet.printOnce(); // 输出：10, 30
}
}输出结果
public class TwoBitSet2 {
private final XnyBitSet bits1;
private final XnyBitSet bits2;
private final long maxBits;
// 构造函数：初始化两个位图，最大支持 maxBits 个无符号整数
public TwoBitSet2(long maxBits) {
this.maxBits = maxBits;
this.bits1 = new XnyBitSet(maxBits);
this.bits2 = new XnyBitSet(maxBits);
}
// 设置整数 num 的出现次数状态
public void set(long num) {
// 00 -> 01（第一次出现）
if (!bits1.test(num) && !bits2.test(num)) {
bits2.set(num);
}
// 01 -> 10（第二次出现）
else if (!bits1.test(num) && bits2.test(num)) {
bits1.set(num);
bits2.reset(num);
}
// 10 -> 11（第三次及以上出现）
else if (bits1.test(num) && !bits2.test(num)) {
bits2.set(num);
}
// 11 表示出现超过两次，无需处理
}
// 判断整数 num 是否出现超过两次
public boolean overTwice(long num) {
return bits1.test(num) && bits2.test(num); // bits1 和 bits2 都为 1 表示出现超过两次
}
// 判断整数 num 是否未出现过
public boolean empty(long num) {
return !bits1.test(num) && !bits2.test(num); // bits1 和 bits2 都为 0 表示未出现过
}
public static void main(String[] args) {
// 定义数组
int[] nums = {1, 2, 3, 4, 4, 5, 3, 2, 5, 6, 7, 5, 4};
// 初始化双位图，最大支持 10 个无符号整数（0 ~ 9）
TwoBitSet2 twoBitSet = new TwoBitSet2(10);
// 将 nums 中的数字设置到位图中
for (int num : nums) {
twoBitSet.set(num);
}
// 查询每个数字的出现状态
for (int i = 0; i < 10; ++i) {
if (!twoBitSet.empty(i) && !twoBitSet.overTwice(i)) {
System.out.println(i + " 出现不超过两次");
}
}
}
}面试题4：给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出 精确算法和近似算法。
这是一个 布隆过滤相关面试题。
query-般是查询指令，比如可能是一个网络请求，是一个数据库sq|语句 假设平均每个query是50byte, 100亿个query合计多少内存? -- 500G
当看到这个题目时，可能就会想到位图来解决，但是100亿个字符串都是不相同的，100亿个字符串已经超过了1G,不可行。
可以有两种方案：
[*]精确算法：交集中一定是准确的（哈希切分）
[*]近似算法：那么一定是允许有误判的情况（有误差），那么就可以使用布隆过滤器。
精确算法：
利用哈希函数，将100亿个query是500G，因为要到内存中比较两个文件，所以需要分为1000个小文件，每个小文件占用0.5G，那么两个小文件就可以都进内存中比较了。
如图所示：
当然也会出现哈希冲突超过0.5G的情况，若是重复数较多，但是我们是找交集，所以用位图来存或不在时，0.5G的小文件中数据个数占的内存一定小于0.5G，然后两个位图相与即可。
但如果是都不重复，就需要递归继续分割。用位图找交集
近似算法：
使用位数组和多个哈希函数，以概率方式判断元素是否存在
[*]预处理阶段：将文件A所有query存入布隆过滤器（需约1GB内存）
[*]检测阶段：遍历文件B的query，若布隆过滤器返回存在则视为交集
遇到问题，找老架构师取经
借助此文的问题 套路 ，大家可以 放手一试，保证 offer直接到手，还有可能会 涨薪100%-200%。
后面，尼恩java面试宝典回录成视频， 给大家打造一套进大厂的塔尖视频。
在面试之前，建议大家系统化的刷一波 5000页《尼恩Java面试宝典PDF》，里边有大量的大厂真题、面试难题、架构难题。
很多小伙伴刷完后， 吊打面试官， 大厂横着走。
在刷题过程中，如果有啥问题，大家可以来 找 40岁老架构师尼恩交流。
另外，如果没有面试机会，可以找尼恩来改简历、做帮扶。
遇到职业难题，找老架构取经， 可以省去太多的折腾，省去太多的弯路。
尼恩指导了大量的小伙伴上岸，前段时间，刚指导 32岁 高中生，冲大厂成功。特批 成为 架构师，年薪 50W，逆天改命 ！！！。
狠狠卷，实现 “offer自由” 很容易的， 前段时间一个武汉的跟着尼恩卷了2年的小伙伴， 在极度严寒/痛苦被裁的环境下， offer拿到手软， 实现真正的 “offer自由” 。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]