1.BitMap说明

本文是BitMap系列文章，
BitMap就是位图，
使用bit位来标记数值，
本文不介绍BitMap具体实现，
如果不清楚请见文末参考文章。

2.BitSet说明

本文介绍JDK中的BitSet,
是Java自带的BitMap的一种实现，
下面的示例代码基于JDK1.8。

BitSet实现了一个位向量，
它可以根据需要增长。
每一位都有一个布尔值，
默认值为false。
一个BitSet的位可以被非负整数索引，
即每一位都可以表示一个非负整数。
可以查找、设置、清除某一位。
BitSet可以进行逻辑运算，
包括逻辑与、或和异或。

3.构造方法

// 1.默认构造方法,位的大小默认为64
BitSet bs1 = new BitSet();
// 2.指定位的初始大小，实际为64
BitSet bs2 = new BitSet(16);
// 3.使用其他BitMap或者long数组创建
BitSet bs3 = BitSet.valueOf(bs2.toLongArray());

BitSet操作的对象是bit位，
值只有0或1,
可以对应false和true，
内部维护了一个long数组，
初始数组只有一个元素，
所以BitSet最小的nbits是64，
上面的第2个构造方法指定nbits时，
会把nbits除以64，然后加1，
作为long数组的初始化size，
注意nbits不能小于0。

当随着存储的元素越来越多，
BitSet内部会动态扩充，
最终内部是由N个long来存储。

4.设置,查找,清除操作

public static void testGetSetClear() {
    BitSet bs = new BitSet();
    int num = 9;
    // 设置num后，查询num，应该存在
    bs.set(num);
    boolean exist = bs.get(num);
    System.out.println(num + " set,    exist= " + exist);
    // 清除num后，查询num，应该不存在
    bs.clear(num);
    exist = bs.get(num);
    System.out.println(num + " remove, exist= " + exist);
}

运行代码输出：

9 set,    exist= true
9 remove, exist= false

5.逻辑运算

public static void testLogicOperation() {
    BitSet bs1 = new BitSet();
    BitSet bs2 = new BitSet();

    // 添加一些整数到BitSet中
    for (int i = 0; i < 11; i++) {
        if ((i % 2) == 0) {
            bs1.set(i);
        }
        if ((i % 5) != 0) {
            bs2.set(i);
        }
    }

    // 按照从小到大的顺序打印数组
    System.out.println("Initial pattern in bs1: ");
    System.out.println(bs1);
    System.out.println("\nInitial pattern in bs2: ");
    System.out.println(bs2);

    // 备份原始的bs2，下面的逻辑操作会修改bs2
    BitSet bs2Origin = BitSet.valueOf(bs2.toLongArray());
    // 1.AND 交集，取出相同的数字
    bs2.and(bs1);
    System.out.println("\nbs2 AND bs1: ");
    System.out.println(bs2);

    // 2.OR 并集，取出所有的数字
    bs2 = BitSet.valueOf(bs2Origin.toLongArray());
    bs2.or(bs1);
    System.out.println("\nbs2 OR bs1: ");
    System.out.println(bs2);

    // 3.XOR 差集， bs2和bs1中不相同的数字集合
    bs2 = BitSet.valueOf(bs2Origin.toLongArray());
    bs2.xor(bs1);
    System.out.println("\nbs2 XOR bs1: ");
    System.out.println(bs2);

    // 4.AND NOT 差集，bs2中不存在于bs1中的数字的集合
    bs2 = BitSet.valueOf(bs2Origin.toLongArray());
    bs2.andNot(bs1);
    System.out.println("\nbs2 AND NOT bs1: ");
    System.out.println(bs2);
}

运行代码输出：

Initial pattern in bs1: 
{0, 2, 4, 6, 8, 10}

Initial pattern in bs2: 
{1, 2, 3, 4, 6, 7, 8, 9}

bs2 AND bs1: 
{2, 4, 6, 8}

bs2 OR bs1: 
{0, 1, 2, 3, 4, 6, 7, 8, 9, 10}

bs2 XOR bs1: 
{0, 1, 3, 7, 9, 10}

bs2 AND NOT bs1: 
{1, 3, 7, 9}

6.实现排序去重

如下有一组无序的整数：
{ 1, 2, 3, 29, 22, 0, 3, 29 }
使用BitMap进行排序和去重，
同时展示了更多的BitMap的用法：

public static void testSortAndUniqueArray() {
    int[] array = new int[] { 1, 2, 3, 29, 22, 0, 3, 29 };
    BitSet bitSet = new BitSet(array.length);
    // 将数组内容组bitmap
    for (int i = 0; i < array.length; i++) {
        bitSet.set(array[i], true);
    }
    System.out.println("bitset可以存储的数量：" + bitSet.size());
    System.out.println("bitset实际存储的数量：" + bitSet.cardinality());
    System.out.println("排序去重后：" + bitSet);

    // 使用迭代器访问数据
    System.out.print("迭代器输出：");
    Iterator<Integer> iterator = bitSet.stream().iterator();
    StringJoiner sj = new StringJoiner(",", "{", "}");
    while (iterator.hasNext()) {
        sj.add(String.valueOf(iterator.next()));
    }
    System.out.println(sj);
}

运行代码输出：

bitset可以存储的数量：64
bitset实际存储的数量：6
排序去重后：{0, 1, 2, 3, 22, 29}
迭代器输出：{0,1,2,3,22,29}

7.参考文章

Bitmap简介