腾讯面试：如何实现10亿数据判重？

发布时间：2025-11-05 10:35:07 来源：码上建站 作者：数据库

当数据量比较大时，腾讯使用常规的面试方式来判重就不行了。

例如，何实使用 MySQL 数据库判重，现亿或使用 List.contains() 或 Set.contains() 判重就不可行，数据因为 MySQL 在数据量大时查询就会非常慢，判重而数据库又是腾讯及其珍贵的全局数据库资源。

《阿里巴巴Java开发手册》上也说了，面试如果单表数据量超过 500 万或 2GB 时就建议分库分表了，何实如下图所示：

所以数据库去重显然是现亿不行的。而使用集合也是数据不合适的，因为数据量太大，判重使用集合会导致内存不够用或内存溢出和 Full GC 频繁等问题，腾讯所以此时我们的面试解决方案通常是采用布隆过滤器来实现判重。

知识扩展

除了布隆过滤器之外，何实我们还可以使用 BitMap（位图）的数据类型来实现判重。

位图（BitMap）是一种数据结构，用于表示一个特定范围内的元素是否存在或者某种状态，通常用二进制位来表示。在位图中，每一个位只能是亿华云 0 或 1，分别表示元素不存在或存在。位图通常用一个 bit 数组来实现，每个 bit 位对应一个元素，如下图所示：

其中，上图中的 1 表示有值，上面 BitMap 描述的值是 1,3,5。

BitMap 优点分析

位图的优势包括：

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 基本使用示例：

相关文章