腾讯面试：如何实现10亿数据判重？
共 3476字，需浏览 7分钟
·
2024-06-01 11:52
当数据量比较大时，使用常规的方式来判重就不行了。
例如，使用 MySQL 数据库判重，或使用 List.contains() 或 Set.contains() 判重就不可行，因为 MySQL 在数据量大时查询就会非常慢，而数据库又是及其珍贵的全局数据库资源。
《阿里巴巴Java开发手册》上也说了，如果单表数据量超过 500 万或 2GB 时就建议分库分表了，如下图所示：
所以数据库去重显然是不行的。而使用集合也是不合适的，因为数据量太大，使用集合会导致内存不够用或内存溢出和 Full GC 频繁等问题，所以此时我们的解决方案通常是采用布隆过滤器来实现判重，布隆过滤器的详情请访问：如何实现布隆过滤器？
知识扩展
除了布隆过滤器之外，我们还可以使用 BitMap（位图）的数据类型来实现判重。
位图（BitMap）是一种数据结构，用于表示一个特定范围内的元素是否存在或者某种状态，通常用二进制位来表示。在位图中，每一个位只能是 0 或 1，分别表示元素不存在或存在。位图通常用一个 bit 数组来实现，每个 bit 位对应一个元素，如下图所示：
其中，上图中的 1 表示有值，上面 BitMap 描述的值是 1,3,5。
BitMap 优点分析
位图的优势包括：
-
空间效率优势：位图极大地节省了存储空间。对于大量稀疏数据，特别是当元素数量远大于实际存在的项时，相比于使用传统的列表、集合等数据结构，位图占用的空间极小。 -
查询速度：由于内存访问是按字节或字进行的，因此对单个元素的存在性检查时间复杂度为 O(1)，即常量时间，非常快速。 -
批量操作高效：对于批量插入、删除和查询操作，尤其是统计某一范围内元素的数量，位图表现出优秀的性能。
BitMap VS int
以 Java 中的 int 为例，来对比观察 BitMap 的优势，在 Java 中，int 类型通常需要 32 位（4 字节*8），而 BitMap 使用 1 位就可以来标识此元素是否存在，所以可以认为 BitMap 占用的空间大小，只有 int 类型的 1/32，所以有大数据量判重时，使用 BitMap 也可以实现。
PS：布隆过滤器的底层就是基于 BitMap 数据结构实现的。
BitMap 在 Java 中的使用
BitMap 在 Java 中的具体实现是 java.util 中的 BitSet，BitSet 是一个可变大小的位向量，能够动态增长以容纳更多的位数据，以下是 BitSet 基本使用示例：
import java.util.BitSet;
public class BitmapExample {
public static void main(String[] args) {
// 创建一个BitSet实例
BitSet bitmap = new BitSet();
// 设置第5个位置为1，表示第5个元素存在
bitmap.set(5);
// 检查第5个位置是否已设置
boolean exists = bitmap.get(5);
System.out.println("Element at position 5 exists: " + exists); // 输出: Element at position 5 exists: true
// 设置从索引10到20的所有位置为1
bitmap.set(10, 21); // 参数是包含起始点和不包含终点的区间
// 计算bitset中所有值为1的位的数量，相当于计算设置了的元素个数
int count = bitmap.cardinality();
System.out.println("Number of set bits: " + count);
// 清除第5个位置
bitmap.clear(5);
// 判断位图是否为空
boolean isEmpty = bitmap.isEmpty();
System.out.println("Is the bitset empty after clearing some bits? " + isEmpty);
}
}
课后思考
除了布隆过滤器和 BitMap 之外，还有哪些大数据量判重的实现方案呢？布隆过滤器实现判重的原理又是啥呢？
特殊说明
以上内容来自我的《Java 面试突击训练营》，这门课程是有着 14 年工作经验（前 360 开发工程师），9 年面试官经验的我，花费 4 年时间打磨完成的一门视频面试课。
整个课程从 Java 基础到微服务 Spring Cloud、从实际开发问题到场景题应有尽有，包含模块如下：
全程通过视频直播 + 录播的方式，把 Java 常见的面试题系统的过一遍，遇到一个问题，把这个问题相关的内容都给大家讲明白，并且视频支持永久更新和观看。
上完训练营的课程之后，基本可以应对目前市面上绝大部分公司的面试了，想要了解详情，加我微信：GG_Stone【备注：训练营】