面试官:如何实现 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 优点分析
位图的优势包括:
空间效率优势:位图极大地节省了存储空间。对于大量稀疏数据,特别是当元素数量远大于实际存在的项时,相比于使用传统的列表、集合等数据结构,位图占用的空间极小。
查询速度:由于内存访问是按字节或字进行的,因此对单个元素的存在性检查时间复杂度为 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 基本使用示例:
课后思考
除了布隆过滤器和 BitMap 之外,还有哪些大数据量判重的实现方案呢?布隆过滤器实现判重的原理又是啥呢?
本文已收录到我的面试小站 www.javacn.site,其中包含的内容有:Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、消息队列等模块。
评论