关于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?