八股收录:如何实现10亿数据判重?

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

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

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

alt

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

知识扩展

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

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

alt

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

参考 & 鸣谢

《阿里巴巴Java开发手册》

javacn.site

#八股文##java学习#
Java面试精讲 文章被收录于专栏

Java常见面试题、场景题、企业真题精讲。

全部评论

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:26
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务