JavaBitSet学习

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一、背景

之前公司项目需要对会员人群进行去重过滤，人群的维度是user_id；

因此采用了BitSet做简单的去重，方案将user_id作为bitset中的bit索引；

通过and\or\xor基础运算实现，以公司2亿会员生产bitSet来算，容量24m(不压缩)，主要的and\or\xor运算平均耗时5毫秒，按现有BitSet的数据结构，未来可以支持20亿会员；

举例：

皇冠人群：1\3\5\63\65\67\69\127

活跃人群：5\65\68\127

业务需求：

1、需要提取出既是皇冠又是活跃的会员

2、需要提取出皇冠和活跃两部分会员，但是要保证不重复

3、需要皇冠人群中不活跃的会员

假设两个人群的量都是千万级的人群，我们该如何处理？

这里我们借助了JavaBitSet的位运算来实现可以这样来实现：

需求1：

1、皇冠人群 and 活跃人群取出交集

需求2：

1、皇冠人群 or 活跃人群取出并集

需求3:

1、活跃人群 and 皇冠人群取出交集

2、皇冠人群 xor 交集人群取出非活跃的皇冠会员

二、BitSet入门：

BitSet的原理

Java BitSet可以按位存储，计算机中一个字节(byte)占8位(bit)；

而BitSet是位操作的对象，值只有0或1（即true 和 false），内部维护一个long数组，初始化只有一个long segement，所以BitSet最小的size是64；随着存储的元素越来越多，BitSet内部会自动扩充，一次扩充64位，最终内部是由N个long segement 来存储；

默认情况下，BitSet所有位都是0即false；

正如上述方案来说：

皇冠人群是一个BitSet，其中1\3\5\63\65\67\69\127对应位为1；即橙色部分；

活跃人群也是一个BitSet，其中5\65\68\127对应位为1；即橙色部分；

而64个位为一个long数组，因此64对应的位就被分配到第2个long数组；

BitSet的应用场景

海量数据去重、排序、压缩存储

BitSet的基本操作

and（与）、or（或）、xor（异或）

BitSet的优缺点

优点：

l 按位存储，内存占用空间小

l 丰富的api操作

缺点：

l 线程不安全

l BitSet内部动态扩展long型数组，若数据稀疏会占用较大的内存

BitSet为什么选择long型数组作为内部存储结构

JDK选择long数组作为BitSet的内部存储结构是出于性能的考虑，在and和or的时候减少循环次数，提高性能；

因为BitSet提供and和or这种操作，需要对两个BitSet中的所有bit位做and或者or，实现的时候需要遍历所有的数组元素。使用long能够使得循环的次数降到最低，所以Java选择使用long数组作为BitSet的内部存储结构。

举个例子：

当我们进行BitSet中的and, or, xor操作时，要对整个bitset中的bit都进行操作，需要依次读出bitset中所有的word，如果是long数组存储，我们可以每次读入64个bit,而int数组存储时，只能每次读入32个bit。

BitSet源码解析

参考JunitTest断点查看代码，了解BitSet每个方法的实现逻辑

附：

源码解析博文：http://www.cnblogs.com/lqminn/archive/2012/08/30/2664122.html

Java移位基础知识：https://www.cnblogs.com/hongten/p/hongten_java_yiweiyunsuangfu.html

三、Java BitSet API简介

BitSet()
创建一个新的位 set。

BitSet(int nbits)
创建一个位 set，它的初始大小足以显式表示索引范围在 0 到 nbits-1 的位。

`void`	and`(BitSet set)` 对此目标位 set 和参数位 set 执行逻辑与操作。
`void`	andNot`(BitSet set)` 清除此 `BitSet` 中所有的位，其相应的位在指定的 `BitSet` 中已设置。
`int`	cardinality`()` 返回此 `BitSet` 中设置为 `true` 的位数。
`void`	clear`()` 将此 BitSet 中的所有位设置为 `false`。
`void`	clear`(int bitIndex)` 将索引指定处的位设置为 `false`。
`void`	clear`(int fromIndex, int toIndex)` 将指定的 `fromIndex`（包括）到指定的 `toIndex`（不包括）范围内的位设置为 `false`。
`Object`	clone`()` 复制此 `BitSet`，生成一个与之相等的新 `BitSet`。
`boolean`	equals`(Object obj)` 将此对象与指定的对象进行比较。
`void`	flip`(int bitIndex)` 将指定索引处的位设置为其当前值的补码。
`void`	flip`(int fromIndex, int toIndex)` 将指定的 `fromIndex`（包括）到指定的 `toIndex`（不包括）范围内的每个位设置为其当前值的补码。
`boolean`	get`(int bitIndex)` 返回指定索引处的位值。
`BitSet`	get`(int fromIndex, int toIndex)` 返回一个新的 `BitSet`，它由此 `BitSet` 中从 `fromIndex`（包括）到 `toIndex`（不包括）范围内的位组成。
`int`	hashCode`()` 返回此位 set 的哈希码值。
`boolean`	intersects`(BitSet set)` 如果指定的 `BitSet` 中有设置为 `true` 的位，并且在此 `BitSet` 中也将其设置为`true`，则返回 ture。
`boolean`	isEmpty`()` 如果此 `BitSet` 中没有包含任何设置为 `true` 的位，则返回 ture。
`int`	length`()` 返回此 `BitSet` 的“逻辑大小”：`BitSet` 中最高设置位的索引加 1。
`int`	nextClearBit`(int fromIndex)` 返回第一个设置为 `false` 的位的索引，这发生在指定的起始索引或之后的索引上。
`int`	nextSetBit`(int fromIndex)` 返回第一个设置为 `true` 的位的索引，这发生在指定的起始索引或之后的索引上。
`void`	or`(BitSet set)` 对此位 set 和位 set 参数执行逻辑或操作。
`void`	set`(int bitIndex)` 将指定索引处的位设置为 `true`。
`void`	set`(int bitIndex, boolean value)` 将指定索引处的位设置为指定的值。
`void`	set`(int fromIndex, int toIndex)` 将指定的 `fromIndex`（包括）到指定的 `toIndex`（不包括）范围内的位设置为 `true`。
`void`	set`(int fromIndex, int toIndex, boolean value)` 将指定的 `fromIndex`（包括）到指定的 `toIndex`（不包括）范围内的位设置为指定的值。
`int`	size`()` 返回此 `BitSet` 表示位值时实际使用空间的位数。
`String`	toString`()` 返回此位 set 的字符串表示形式。
`void`	xor`(BitSet set)` 对此位 set 和位 set 参数执行逻辑异或操作。

附本人的调试代码：

package com.vip.amd.bitset; import org.junit.*;
import org.junit.Test; import java.util.BitSet; /**
* @author xupeng.zhang
* @date 2017/12/2 0002
*/
public class BitSetTest {
//全量bitset
private static BitSet allBitSet = new BitSet();
//偶数bitset
private static BitSet evenBitSet = new BitSet();
//奇数bitset
private static BitSet oddBitSet = new BitSet();
//空bitset
private static BitSet emptyBitSet = new BitSet(); @BeforeClass
public static void init(){
for (int i = 0; i < 63; i++) {
allBitSet.set(i);
if (i % 2 == 0) {
evenBitSet.set(i);
}else{
oddBitSet.set(i);
}
}
} //测试初始化
@Test
public void testInit(){
//断点进去看
BitSet initBitSet1 = new BitSet(55);
BitSet initBitSet2 = new BitSet(129);
} //测试基础的and\or\xor运算
@org.junit.Test
public void testOper(){
//System.out.println(evenBitSet.toByteArray());
evenBitSet.and(allBitSet);
System.out.println("偶数Bit and 全量Bit："+evenBitSet);
evenBitSet.xor(allBitSet);
System.out.println("偶数Bit xor 全量Bit："+evenBitSet);
evenBitSet.or(allBitSet);
System.out.println("偶数Bit or 全量Bit："+evenBitSet);
} //测试动态扩展，每次是以64位为单位
@org.junit.Test
public void testExpand(){
testSize();
allBitSet.set(100000000);
System.out.println("全量Bit-设置64之后大小：" + allBitSet.size()/8/1024/1024+"m");
System.out.println("全量Bit-设置64之后长度：" + allBitSet.length());
System.out.println("全量Bit-设置64之后实际true的个数：" + allBitSet.cardinality());
} //oddBitSet过滤掉evenBitSet
@Test
public void testOddFilterEvenBitSet(){
oddBitSet.set(2);
oddBitSet.set(4);
oddBitSet.set(6);
System.out.println("过滤前：oddBitSet:"+oddBitSet);
evenBitSet.and(oddBitSet);
oddBitSet.xor(evenBitSet);
System.out.println("oddBitSet过滤evenBitSet相同的元素的结果："+oddBitSet);
} //偶数和奇数bitset合并去重之后和allbitSet内容一致
@Test
public void testOddAndEventBitSet(){
oddBitSet.set(2);
oddBitSet.set(4);
oddBitSet.set(6);
System.out.println("偶数BitSet合并前："+evenBitSet);
System.out.println("奇数BitSet合并前："+oddBitSet);
System.out.println("------------------------");
oddBitSet.or(evenBitSet);
System.out.println("偶数BitSet合并后："+evenBitSet);
System.out.println("奇数BitSet合并后："+oddBitSet);
System.out.println("全亮BitSet内容是："+allBitSet);
Assert.assertTrue(oddBitSet.equals(allBitSet));
} //返回true的个数
@org.junit.Test
public void testCardinality(){
System.out.println("偶数Bit-true的个数：" + evenBitSet.cardinality());
} //判断是否为空
@org.junit.Test
public void testIsEmpty(){
System.out.println("全量Bit-判断非空：" + allBitSet.isEmpty());
System.out.println("空 Bit-判断非空：" + emptyBitSet.isEmpty());
} //根据下表开始结束获取
@org.junit.Test
public void testGetFromEnd(){
System.out.println("全量Bit-[0,5]：" + allBitSet.get(0, 5));
System.out.println("空 Bit-[0,5]：" + emptyBitSet.get(0, 5));
} //判断是否存在bitset
@org.junit.Test
public void testGet(){
System.out.println("全量Bit-下标为2是否存在:" + allBitSet.get(2));
System.out.println("偶数Bit-下标为1是否存在:" + evenBitSet.get(1));
System.out.println("偶数Bit-下标为2是否存在:" + evenBitSet.get(2));
} //计算bitset内存大小
@org.junit.Test
public void testSize(){
System.out.println("空 Bit-大小：:" + emptyBitSet.size()+"byte");
System.out.println("偶数Bit-大小：" + evenBitSet.size() + "byte");
System.out.println("全量Bit-大小：" + allBitSet.size() + "byte");
} //计算bitset长度（bitset最大数+1）
@org.junit.Test
public void testLength(){
System.out.println("全量Bit-长度：" + allBitSet.length());
System.out.println("偶数Bit-长度：" + evenBitSet.length());
}
}