一、背景
之前公司项目需要对会员人群进行去重过滤，人群的维度是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 |
BitSet |
| |
| |
| cardinality |
| clear |
| clear |
| clear |
clone | |
| |
| flip |
| flip |
| get |
get | |
| hashCode |
| intersects |
| isEmpty |
| length |
| nextClearBit |
| nextSetBit |
| |
| set |
| set |
| set |
| set |
| size |
toString | |
|
附本人的调试代码：
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());
}
}