面试官:如何实现10亿数据判重?

简介: 面试官:如何实现10亿数据判重?

当数据量比较大时,使用常规的方式来判重就不行了。

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

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

所以数据库去重显然是不行的。而使用集合也是不合适的,因为数据量太大,使用集合会导致内存不够用或内存溢出和 Full GC 频繁等问题,所以此时我们的解决方案通常是采用布隆过滤器来实现判重,布隆过滤器的详情请访问:如何实现布隆过滤器?其中,推荐使用 Redis 中的布隆过滤器来实现大数据量的判重。

知识扩展

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

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

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

BitMap 优点分析

位图的优势包括:

  1. 空间效率优势:位图极大地节省了存储空间。对于大量稀疏数据,特别是当元素数量远大于实际存在的项时,相比于使用传统的列表、集合等数据结构,位图占用的空间极小。
  2. 查询速度:由于内存访问是按字节或字进行的,因此对单个元素的存在性检查时间复杂度为 O(1),即常量时间,非常快速。
  3. 批量操作高效:对于批量插入、删除和查询操作,尤其是统计某一范围内元素的数量,位图表现出优秀的性能。

    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 之外,还有哪些大数据量判重的实现方案呢?布隆过滤器实现判重的原理又是啥呢?

本文已收录到我的面试小站 www.javacn.site,其中包含的内容有:Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、消息队列等模块。

相关文章
|
6月前
|
SQL 分布式计算 监控
Sqoop数据迁移工具使用与优化技巧:面试经验与必备知识点解析
【4月更文挑战第9天】本文深入解析Sqoop的使用、优化及面试策略。内容涵盖Sqoop基础,包括安装配置、命令行操作、与Hadoop生态集成和连接器配置。讨论数据迁移优化技巧,如数据切分、压缩编码、转换过滤及性能监控。此外,还涉及面试中对Sqoop与其他ETL工具的对比、实际项目挑战及未来发展趋势的讨论。通过代码示例展示了从MySQL到HDFS的数据迁移。本文旨在帮助读者在面试中展现Sqoop技术实力。
469 2
|
6月前
|
SQL 缓存 easyexcel
面试官问10W 行级别数据的 Excel 导入如何10秒处理
面试官问10W 行级别数据的 Excel 导入如何10秒处理
267 0
|
6月前
|
编解码 移动开发 前端开发
【面试题】 给你十万条数据,怎么样顺滑的渲染出来?
【面试题】 给你十万条数据,怎么样顺滑的渲染出来?
|
6月前
|
前端开发 JavaScript
【面试题】面试官:如果后端给你 1w 条数据,你如何做展示?
【面试题】面试官:如果后端给你 1w 条数据,你如何做展示?
|
24天前
|
存储 缓存 关系型数据库
滴滴面试:单表可以存200亿数据吗?单表真的只能存2000W,为什么?
40岁老架构师尼恩在其读者交流群中分享了一系列关于InnoDB B+树索引的面试题及解答。这些问题包括B+树的高度、存储容量、千万级大表的优化、单表数据量限制等。尼恩详细解释了InnoDB的存储结构、B+树的磁盘文件格式、索引数据结构、磁盘I/O次数和耗时,以及Buffer Pool缓存机制对性能的影响。他还提供了实际操作步骤,帮助读者通过元数据找到B+树的高度。尼恩强调,通过系统化的学习和准备,可以大幅提升面试表现,实现“offer直提”。相关资料和PDF可在其公众号【技术自由圈】获取。
|
29天前
|
监控 Java easyexcel
面试官:POI大量数据读取内存溢出?如何解决?
【10月更文挑战第14天】 在处理大量数据时,使用Apache POI库读取Excel文件可能会导致内存溢出的问题。这是因为POI在读取Excel文件时,会将整个文档加载到内存中,如果文件过大,就会消耗大量内存。以下是一些解决这一问题的策略:
69 1
|
1月前
|
存储 关系型数据库 MySQL
面试官:MySQL一次到底插入多少条数据合适啊?
本文探讨了数据库插入操作的基础知识、批量插入的优势与挑战,以及如何确定合适的插入数据量。通过面试对话的形式,详细解析了单条插入与批量插入的区别,磁盘I/O、内存使用、事务大小和锁策略等关键因素。最后,结合MyBatis框架,提供了实际应用中的批量插入策略和优化建议。希望读者不仅能掌握技术细节,还能理解背后的原理,从而更好地优化数据库性能。
|
1月前
|
存储 大数据 数据库
Android经典面试题之Intent传递数据大小为什么限制是1M?
在 Android 中,使用 Intent 传递数据时存在约 1MB 的大小限制,这是由于 Binder 机制的事务缓冲区限制、Intent 的设计初衷以及内存消耗和性能问题所致。推荐使用文件存储、SharedPreferences、数据库存储或 ContentProvider 等方式传递大数据。
62 0
|
3月前
|
Java
【Java基础面试五】、 int类型的数据范围是多少?
这篇文章回答了Java中`int`类型数据的范围是-2^31到2^31-1,并提供了其他基本数据类型的内存占用和数值范围信息。
【Java基础面试五】、 int类型的数据范围是多少?
|
4月前
|
canal 缓存 NoSQL
Redis常见面试题(一):Redis使用场景,缓存、分布式锁;缓存穿透、缓存击穿、缓存雪崩;双写一致,Canal,Redis持久化,数据过期策略,数据淘汰策略
Redis使用场景,缓存、分布式锁;缓存穿透、缓存击穿、缓存雪崩;先删除缓存还是先修改数据库,双写一致,Canal,Redis持久化,数据过期策略,数据淘汰策略
Redis常见面试题(一):Redis使用场景,缓存、分布式锁;缓存穿透、缓存击穿、缓存雪崩;双写一致,Canal,Redis持久化,数据过期策略,数据淘汰策略