BitSet处理海量数据

每天学Java

发布于 2020-06-02 10:18:47

1.6K00

代码可运行

文章被收录于专栏：每天学Java每天学Java

运行总次数：0

代码可运行

关于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那么说明存在