江苏龙网

  1. 主页 > 生活百科 > >

BitSet处理海量数据

BitSet


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万，循环中仅做判断，这里不涉及其他操作，我们看一下光判断的耗时
【BitSet处理海量数据】 //全部用户 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


推荐阅读


上一篇：六种无线传输模式，你都知道吗？

下一篇：梦到已经去世的亲人预示着什么 梦到已经去世的亲人还活着