您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > JAVA

BitSet处理海量数据

时间:2019-08-16 10:03:21  来源:  作者:
BitSet处理海量数据

 

关于BitSet

BitSet是JAVA.util下包下,JDK1.0中就已经引入这个数据结构。

如果你对数据结构的"位图"比较熟悉,那么BitSet就很好理解了。位图定义了数据的存在性可以用bit位上的1和0来表示,一个bit有两个值,0或1。而BitSet正是因为采用这种数据结构,在判断“数据是否存在”的场景会经常出现。

如果不知道位图,我们看一下JDK API中对BitSet的定义:BitSet类实现了一个按需增长的位向量(位向量就是由一些二进制位组成的向量)。

通俗点说,BitSet就是维护一个long类型数组,每次我们将数set到BitSet中时,BitSet通过位运算找到该数对应的数组下标(>>,右移2^6,),再通过位运算(<< 和 |)来将其对应位定义为1,来表示该数存在(具体可以看下面的BitSet的set源码)。

在Java中,判断某个数是否存在有很多种方法,为什么会选用BitSet呢?其重要的原因是它可以有效的降低内存的使用量。因为BitSet内部定义来long数组,而long在内存中占用8个字节,即64bit,BitSet中每一个bit都可以保存一个int数据(准确的说是用0和1来说明int数据是否存在),那么也就是我们用了8个字节保存了4*64位整数,这个比例就是1:32。

使用BitSet

写这篇文章,也是因为遇到了相关的问题:

我需要获取某一天没有登陆的用户列表

最初我的解决方案:用户活跃数据是存在hive中,通过调用接口返回到List中。然后遍历全部用户,通过list.contains()来进行判断(这可能就是一直没有接触过海量数据造成的),那么效果就不用说了,挺低的。

我简单模拟一下这个操作:假设全部用户100万(线上不止),活跃用户5万,循环中仅做判断,这里不涉及其他操作,我们看一下光判断的耗时

 //全部用户 100万
 List<Integer> list = new ArrayList();
 for (int i = 0; i < 100000; i++) {
 list.add(i);
 }
 //活跃用户 5 万
 List<Integer> list1 = new ArrayList();
 Random ra = new Random();
 for (int i = 0; i < 50000; i++) {
 int val = ra.nextInt(1000000);
 list1.add(val);
 }
 long s = System.currentTimeMillis();
 for (int i : list) {
 if (!list1.contains(i)) {
 //其他操作
 }
 }
 System.out.println(System.currentTimeMillis() - s);

结果运行了4秒多(跟计算机性能也有关系),如果循环里面再加上一些其他操作,简直没法玩(事实上确实没法玩)。

到这里的时候,我就在考虑如何解决这个方案,想到小程序收集的面试题(数据结构篇)有这么一道题(忘记是出自阿里还是百度了):有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来?答案中采用了BitSet的方案。所以这里我也就复习了一下BitSet。实际运用的效果确实也没有让人失望,运行了四五次,每次都不会超过10ms,对于这个速度我这边是可以接受的,代码如下。

 //全部用户 100万
 List<Integer> list = new ArrayList();
 for (int i = 0; i < 100000; i++) {
 list.add(i);
 }
 //活跃用户 5 万
 List<Integer> list1 = new ArrayList();
 Random ra = new Random();
 for (int i = 0; i < 50000; i++) {
 int val = ra.nextInt(1000000);
 list1.add(val);
 }
// long s = System.currentTimeMillis();
// for (int i : list) {
// if (!list1.contains(i)) {
// //记录下来
// }
// }
// System.out.println(System.currentTimeMillis() - s);
 long s1 = System.currentTimeMillis();
 BitSet bitSet = new BitSet();
 for (int i : list1) {
 bitSet.set(i);
 }
 for (int i : list) {
 if (!bitSet.get(i)) {
 //记录下来
 }
 }
 System.out.println(System.currentTimeMillis() - s1);

通过上面的例子我们就会发现,最前面讲的概念可能比较难理解,但是使用却很简单,就是new出来,然后就是get和set操作了,并不复杂。

关于set方法

首先是判断是否是正整数。

然后通过wordIndex获取下标。

expandTo方法就是用来判断数组是否需要扩一下 合并数据,1L << bitIndex之后通过或运算来对响应位置的bit置1

checkInvariants内部就是断言,这里就不说了

 public void set(int bitIndex) {
 //首先是判断是否是正整数。
 if (bitIndex < 0)
 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
 //然后通过wordIndex获取下标。
 int wordIndex = wordIndex(bitIndex);
 //expandTo方法就是用来判断数组是否需要扩一下
 expandTo(wordIndex);
 //合并数据
 words[wordIndex] |= (1L << bitIndex); // Restores invariants
 checkInvariants();
 }

关于wordIndex:

 private static int wordIndex(int bitIndex) {
 return bitIndex >> ADDRESS_BITS_PER_WORD;
 }

这里ADDRESS_BITS_PER_WORD的值是6.因为在Java里Long类型是64位,所以一个Long可以存储64个数,而要计算给定的参数bitIndex应该放在数组(在BitSet里存在word的实例变量里)的哪个long里,只需要计算:bitIndex / 64即可,这里正是使用>>来代替除法(因为位运算要比除法效率高)。而64正好是2的6次幂,所以ADDRESS_BITS_PER_WORD的值是6

关于get方法

public boolean get(int bitIndex) {
 if (bitIndex < 0)
 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
 checkInvariants();
 int wordIndex = wordIndex(bitIndex);
 return (wordIndex < wordsInUse)
 && ((words[wordIndex] & (1L << bitIndex)) != 0);
}

意思就是算出来所给定的bitIndex所对应的位数是否为1即可,如果是1那么说明存在

相关问题

1.BitSet是否是线程安全的?

2.BitSet引发OOM的原因会是什么?

3.为保证某网站订单系统订单ID的连续性,生成订单号的时候如何分配给它一个可用的ID?



Tags:BitSet   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
关于BitSetBitSet是java.util下包下,JDK1.0中就已经引入这个数据结构。如果你对数据结构的"位图"比较熟悉,那么BitSet就很好理解了。位图定义了数据的存在性可以用bit位上的1...【详细内容】
2019-08-16  Tags: BitSet  点击:(222)  评论:(0)  加入收藏
▌简易百科推荐
面向对象的特征之一封装 面向对象的特征之二继承 方法重写(override/overWrite) 方法的重载(overload)和重写(override)的区别: 面向对象特征之三:多态 Instanceof关键字...【详细内容】
2021-12-28  顶顶架构师    Tags:面向对象   点击:(2)  评论:(0)  加入收藏
一、Redis使用过程中一些小的注意点1、不要把Redis当成数据库来使用二、Arrays.asList常见失误需求:把数组转成list集合去处理。方法:Arrays.asList 或者 Java8的stream流式处...【详细内容】
2021-12-27  CF07    Tags:Java   点击:(3)  评论:(0)  加入收藏
文章目录 如何理解面向对象编程? JDK 和 JRE 有什么区别? 如何理解Java中封装,继承、多态特性? 如何理解Java中的字节码对象? 你是如何理解Java中的泛型的? 说说泛型应用...【详细内容】
2021-12-24  Java架构师之路    Tags:JAVA   点击:(5)  评论:(0)  加入收藏
大家好!我是老码农,一个喜欢技术、爱分享的同学,从今天开始和大家持续分享JVM调优方面的经验。JVM调优是个大话题,涉及的知识点很庞大 Java内存模型 垃圾回收机制 各种工具使用 ...【详细内容】
2021-12-23  小码匠和老码农    Tags:JVM调优   点击:(12)  评论:(0)  加入收藏
前言JDBC访问Postgresql的jsonb类型字段当然可以使用Postgresql jdbc驱动中提供的PGobject,但是这样在需要兼容多种数据库的系统开发中显得不那么通用,需要特殊处理。本文介绍...【详细内容】
2021-12-23  dingle    Tags:JDBC   点击:(13)  评论:(0)  加入收藏
Java与Lua相互调用案例比较少,因此项目使用需要做详细的性能测试,本内容只做粗略测试。目前已完成初版Lua-Java调用框架开发,后期有时间准备把框架进行抽象,并开源出来,感兴趣的...【详细内容】
2021-12-23  JAVA小白    Tags:Java   点击:(11)  评论:(0)  加入收藏
Java从版本5开始,在 java.util.concurrent.locks包内给我们提供了除了synchronized关键字以外的几个新的锁功能的实现,ReentrantLock就是其中的一个。但是这并不意味着我们可...【详细内容】
2021-12-17  小西学JAVA    Tags:JAVA并发   点击:(11)  评论:(0)  加入收藏
一、概述final是Java关键字中最常见之一,表示“最终的,不可更改”之意,在Java中也正是这个意思。有final修饰的内容,就会变得与众不同,它们会变成终极存在,其内容成为固定的存在。...【详细内容】
2021-12-15  唯一浩哥    Tags:Java基础   点击:(17)  评论:(0)  加入收藏
1、问题描述关于java中的日志管理logback,去年写过关于logback介绍的文章,这次项目中又优化了下,记录下,希望能帮到需要的朋友。2、解决方案这次其实是碰到了一个问题,一般的情况...【详细内容】
2021-12-15  软件老王    Tags:logback   点击:(19)  评论:(0)  加入收藏
本篇文章我们以AtomicInteger为例子,主要讲解下CAS(Compare And Swap)功能是如何在AtomicInteger中使用的,以及提供CAS功能的Unsafe对象。我们先从一个例子开始吧。假设现在我们...【详细内容】
2021-12-14  小西学JAVA    Tags:JAVA   点击:(22)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条