Java中BitSet简介

codingman included in Java

2020-05-25 3619 words 8 minutes

Contents

1. 概述

在本教程中，我们将了解如何使用 BitSet 来表示位向量。

首先，我们将从不使用*boolean[]*背后的基本原理开始。然后在熟悉了 BitSet内部之后，我们将仔细研究它的 API。

2. 位数组

为了存储和操作位数组，有人可能会争辩说我们应该使用 *boolean[]*作为我们的数据结构。乍一看，这似乎是一个合理的建议。

但是， boolean[]中的每个boolean成员通常消耗一个字节而不是一个位 。因此，当我们有严格的内存要求，或者我们只是想减少内存占用时，*boolean[]*远非理想。

为了使事情更具体，让我们看看具有 1024 个元素的*boolean[]*消耗了多少空间：

boolean[] bits = new boolean[1024];
System.out.println(ClassLayout.parseInstance(bits).toPrintable());

理想情况下，我们期望该阵列占用 1024 位内存。然而，Java 对象布局 (JOL) 揭示了一个完全不同的现实：

[Z object internals:
 OFFSET  SIZE      TYPE DESCRIPTION            VALUE
      0     4           (object header)        01 00 00 00 (00000001 00000000 00000000 00000000) (1)
      4     4           (object header)        00 00 00 00 (00000000 00000000 00000000 00000000) (0)
      8     4           (object header)        7b 12 07 00 (01111011 00010010 00000111 00000000) (463483)
     12     4           (object header)        00 04 00 00 (00000000 00000100 00000000 00000000) (1024)
     16  1024   boolean [Z.                    N/A
Instance size: 1040 bytes

如果我们忽略对象头的开销，数组元素会消耗 1024 字节，而不是预期的 1024 位。这比我们预期的多 700% 的内存。

可寻址性问题和字撕裂是boolean不仅仅是一位的主要原因。

为了解决这个问题，我们可以使用数字数据类型（例如long）和按位运算的组合。这就是BitSet的用武之地。

3. BitSet的工作原理

正如我们前面提到的，为了实现每个标志一位的内存使用，BitSet API 使用了基本数字数据类型和按位运算的组合。

为了简单起见，假设我们要用一个byte来表示八个标志。首先，我们用零初始化这个单byte的所有位：

现在，如果我们想将位置 3 的位设置为 true，我们应该首先将数字 1 左移 3 位：

然后 or其结果与当前byte值：

如果决定在索引 7 处设置该位，将发生相同的过程：

如上所示，我们执行左移 7 位，并使用or运算符将结果与前一个byte值组合。

3.1. 获取位索引

要检查特定位索引是否设置为 true，我们将使用 and运算符。例如，下面是我们检查索引 3 是否设置的方法：

对值 1 执行左移三位
将结果与当前byte值相加
如果结果大于零，则我们找到了匹配项，并且实际设置了该位索引。否则，请求的索引是明确的或等于 false

上图展示了索引三的get操作步骤。但是，如果我们查询一个明确的索引，结果会有所不同：

由于 and结果等于 0，索引 4 是明确的。

3.2. 增加存储

目前，我们只能存储一个 8 位的向量。为了超越这个限制，我们只需要使用一个 byte数组，而不是单个 byte，就是这样！

现在，每次我们需要设置、获取或清除特定索引时，我们都应该首先找到对应的数组元素。例如，假设我们要设置索引 14：

如上图所示，在找到正确的数组元素后，我们确实设置了合适的索引。

此外，如果我们想在此处设置超过 15 的索引， BitSet将首先扩展其内部数组。只有在扩展数组并复制元素后，它才会设置请求的位。这有点类似于*ArrayList *在内部的工作方式。

到目前为止，为了简单起见，我们使用了byte 数据类型。然而， BitSet API 在内部使用了一个long值数组。

4. BitSet API

现在我们对该理论有了足够的了解，是时候看看 BitSet API 是什么样子了。

首先，让我们将1024 位的BitSet实例的内存占用与我们之前看到的boolean[] 进行比较：

BitSet bitSet = new BitSet(1024);
System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());

这将打印 BitSet实例的浅大小及其内部数组的大小：

java.util.BitSet@75412c2fd object externals:
          ADDRESS       SIZE TYPE             PATH         VALUE
        70f97d208         24 java.util.BitSet              (object)
        70f97d220        144 [J               .words       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

如上所示，它在内部使用具有 16 个元素（16 * 64 位 = 1024 位）的long[]。无论如何，**这个实例总共使用了 168 个字节，而 boolean[]使用了 1024 个字节。

我们拥有的位越多，占用空间差异就越大。例如，要存储 1024 * 1024 位，*boolean[]*消耗 1 MB，而 BitSet实例消耗大约 130 KB。

4.1. 构造BitSet

创建 BitSet实例的最简单方法是使用无参数构造函数：

BitSet bitSet = new BitSet();

这将创建一个大小为 one的long[] 的BitSet实例。当然，如果需要，它可以自动增长这个数组。也可以创建一个具有初始位数的 BitSet：

BitSet bitSet = new BitSet(100_000);

在这里，内部数组将有足够的元素来容纳 100,000 位。当我们已经对要存储的位数有了合理的估计时，这个构造函数就派上用场了。在这种用例中，它可以防止或减少数组元素在增长时不必要的复制。

甚至可以从现有的 long[]、byte[]、LongBuffer 和 ByteBuffer 创建 BitSet。例如，这里我们从给定的 long[]创建一个BitSet实例：

BitSet bitSet = BitSet.valueOf(new long[] { 42, 12 });

*valueOf() *静态工厂方法还有三个重载版本来支持其他提到的类型。

4.2. 设置位

我们可以使用 *set(index) *方法将特定索引的值设置为 true：

BitSet bitSet = new BitSet();
bitSet.set(10);
assertThat(bitSet.get(10)).isTrue();

像往常一样，索引是从零开始的。甚至可以使用set(fromInclusive, toExclusive) 方法将一系列位设置为true**：

bitSet.set(20, 30);
for (int i = 20; i <= 29; i++) {
    assertThat(bitSet.get(i)).isTrue();
}
assertThat(bitSet.get(30)).isFalse();

从方法签名中可以明显看出，开始索引是包含的，而结束索引是排除的。

当我们说设置索引时，我们通常是指将其设置为 true。尽管有这个术语，我们可以使用 *set(index, boolean) *方法将特定的位索引设置为 false：

bitSet.set(10, false);
assertThat(bitSet.get(10)).isFalse();

此版本还支持设置一系列值：

bitSet.set(20, 30, false);
for (int i = 20; i <= 29; i++) {
    assertThat(bitSet.get(i)).isFalse();
}

4.3. 清除位

我们可以使用 *clear(index) *方法简单地清除它，而不是将特定的位索引设置为 false：

bitSet.set(42);
assertThat(bitSet.get(42)).isTrue();
        
bitSet.clear(42);
assertThat(bitSet.get(42)).isFalse();

此外，我们还可以使用*clear(fromInclusive, toExclusive) *重载版本清除一系列位：

bitSet.set(10, 20);
for (int i = 10; i < 20; i++) {
    assertThat(bitSet.get(i)).isTrue();
}
bitSet.clear(10, 20);
for (int i = 10; i < 20; i++) {
    assertThat(bitSet.get(i)).isFalse();
}

有趣的是，如果我们在不传递任何参数的情况下调用此方法，它将清除所有设置的位：

bitSet.set(10, 20);
bitSet.clear();
for (int i = 0; i < 100; i++) { 
    assertThat(bitSet.get(i)).isFalse();
}

如上所示，调用 *clear() *方法后，所有位都设置为零。

4.4. 获取位

到目前为止，我们相当广泛地使用了*get(index) *方法。设置请求的位索引后，此方法将返回 true。否则，它将返回 false：

bitSet.set(42);
assertThat(bitSet.get(42)).isTrue();
assertThat(bitSet.get(43)).isFalse();

与 set和 clear类似，我们可以使用*get(fromInclusive, toExclusive) *方法获取一系列位索引：

bitSet.set(10, 20);
BitSet newBitSet = bitSet.get(10, 20);
for (int i = 0; i < 10; i++) {
    assertThat(newBitSet.get(i)).isTrue();
}

如上所示，该方法返回当前一个的 [20, 30) 范围内的另一个 BitSet。也就是说，bitSet 变量的索引 20等价于newBitSet变量的索引 0 。

4.5. 翻转位

**要否定当前位索引值，我们可以使用 flip(int) 方法。也就是说，它会将true值变为false，反之亦然：

bitSet.set(42);
bitSet.flip(42);
assertThat(bitSet.get(42)).isFalse();
bitSet.flip(12);
assertThat(bitSet.get(12)).isTrue();

类似地，我们可以使用*flip(fromInclusive, toExclusive) *方法对一系列值实现相同的效果：

bitSet.flip(30, 40);
for (int i = 30; i < 40; i++) {
    assertThat(bitSet.get(i)).isTrue();
}

4.6. 长度

BitSet有三种类似长度的方法。*size() 方法返回内部数组可以表示的位数。例如，由于无参数构造函数分配一个带有一个元素的long[]*数组，那么 *size()*将为其返回 64：

BitSet defaultBitSet = new BitSet();
assertThat(defaultBitSet.size()).isEqualTo(64);

一个 64 位的数字，我们只能表示 64 位。当然，如果我们显式传递位数，这将改变：

BitSet bitSet = new BitSet(1024);
assertThat(bitSet.size()).isEqualTo(1024);

此外，cardinality() 方法表示BitSet中设置的位数：

assertThat(bitSet.cardinality()).isEqualTo(0);
bitSet.set(10, 30);
assertThat(bitSet.cardinality()).isEqualTo(30 - 10);

起初，此方法返回零，因为所有位都是 false。将 [10, 30) 范围设置为 true后，cardinality()方法调用返回 20。 **此外，length() 方法返回最后一个设置位的索引之后的一个索引：

assertThat(bitSet.length()).isEqualTo(30);
bitSet.set(100);
assertThat(bitSet.length()).isEqualTo(101);

一开始最后设置的索引是 29，所以这个方法返回 30。当我们把索引 100 设置为 true 时， *length()*方法返回 101。另外值得一提的是，如果所有位都清除，这个方法将返回 0。

最后，当BitSet中至少有一个设置位时， *isEmpty() *方法返回 false。否则，它将返回 true：

assertThat(bitSet.isEmpty()).isFalse();
bitSet.clear();
assertThat(bitSet.isEmpty()).isTrue();

4.7. 与其他 BitSet结合

intersects(BitSet) 方法接受另一个 BitSet并在两个BitSet有共同点时返回 true。也就是说，它们在同一索引中至少有一个设置位：

BitSet first = new BitSet();
first.set(5, 10);
BitSet second = new BitSet();
second.set(7, 15);
assertThat(first.intersects(second)).isTrue();

[7, 9] 范围在两个 BitSet中都设置了，因此此方法返回 true。

也可以对两个BitSet执行逻辑AND操作：

first.and(second);
assertThat(first.get(7)).isTrue();
assertThat(first.get(8)).isTrue();
assertThat(first.get(9)).isTrue();
assertThat(first.get(10)).isFalse();

这将在两个BitSet之间执行逻辑AND，并用结果修改第一个变量。同样，我们也可以对两个BitSet执行逻辑XOR：

first.clear();
first.set(5, 10);
first.xor(second);
for (int i = 5; i < 7; i++) {
    assertThat(first.get(i)).isTrue();
}
for (int i = 10; i < 15; i++) {
    assertThat(first.get(i)).isTrue();
}

还有其他方法，例如 andNot(BitSet) 或 or(BitSet) ，它们可以对两个BitSet执行其他逻辑操作。

4.8. 各种各样的

从 Java 8 开始，有一个 stream() 方法可以流式传输BitSet的所有设置位。例如：

BitSet bitSet = new BitSet();
bitSet.set(15, 25);
bitSet.stream().forEach(System.out::println);

这会将所有设置的位打印到控制台。由于这将返回一个 IntStream ，我们可以执行常见的数值运算，例如求和、平均、计数等。例如，这里我们计算设置位的数量：

assertThat(bitSet.stream().count()).isEqualTo(10);

此外，**nextSetBit(fromIndex) 方法将返回从 fromIndex开始的下一个设置位索引：

assertThat(bitSet.nextSetBit(13)).isEqualTo(15);

fromIndex本身包含在此计算中。当BitSet中没有任何真正的位时，它将返回 -1：

assertThat(bitSet.nextSetBit(25)).isEqualTo(-1);

同样，nextClearBit(fromIndex) 返回从fromIndex开始的下一个清除索引：

assertThat(bitSet.nextClearBit(23)).isEqualTo(25);

另一方面，*previousClearBit(fromIndex) *以相反方向返回最近的清除索引的索引：

assertThat(bitSet.previousClearBit(24)).isEqualTo(14);

previousSetBit(fromIndex) 也是如此：

assertThat(bitSet.previousSetBit(29)).isEqualTo(24);
assertThat(bitSet.previousSetBit(14)).isEqualTo(-1);

此外，我们可以分别使用 *toByteArray() *或 toLongArray() 方法将BitSet转换为 *byte[]*或 long[]：

byte[] bytes = bitSet.toByteArray();
long[] longs = bitSet.toLongArray();