腾讯面试：有40亿整数，如何判断一个 int 是在其中，越快越好？

垢峒 · 2025-5-30 13:35:41

本文的原文地址

本文的原文地址
尼恩说在前面：

在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[index] |= (1 > 5);       int offset = (int) (x & 0x1F);       bits[index] &= ~(1 > 5);       int offset = (int) (x & 0x1F);       return (bits[index] & (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)); // 检查数值是否存在 }}[/code]通过哈希切分结合位图的方式，可高效解决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[i] |= (1 << j); //  将 bits[i] 的第 j 位设为 1，其余位保持不变。
}
// 将第 x 位重置为 0
public void reset(long x) {
      int i = (int) (x >> 3);
      int j = (int) (x & 7);
      bits[i] &= ~(1 << j); //将 bits[i] 的第 j 位设为 0，其余位保持不变。
}
// 判断第 x 位是否为 1
public boolean test(long x) {
      int i = (int) (x >> 3);
      int j = (int) (x & 7);
      return (bits[i] & (1 << j)) != 0; // 判断 bits[i] 的第 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[size];
}
// 设置第 x 位为 1
public void set(long x) {
      int index = (int) (x >> 5);    // 等价于 x / 32
      int offset = (int) (x & 0x1F);  // 等价于 x % 32
      bits[index] |= (1 << offset); //  在 bits[index] 中设置对应位
}
// 将第 x 位重置为 0
public void reset(long x) {
      int index = (int) (x >> 5);
      int offset = (int) (x & 0x1F);
      bits[index] &= ~(1 << offset);    // 清除对应位
}
// 判断第 x 位是否为 1
public boolean test(long x) {
      int index = (int) (x >> 5);
      int offset = (int) (x & 0x1F);
      return (bits[index] & (1 << offset)) != 0; // 判断 bits[index] 的第 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[BUCKET_COUNT];

      // 初始化桶文件写入器
      for (int i = 0; i < BUCKET_COUNT; i++) {
         buckets[i] = 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[bucketId].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自由” 。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

腾讯面试：有40亿整数，如何 判断一个 int 是在其中，越快越好 ？

签约作者

腾讯面试：有40亿整数，如何判断一个 int 是在其中，越快越好？