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?