1. 概述
在本教程中，我们将了解RoaringBitmap。我们将使用对一组的一些基本操作作为RoaringBitmap的示例。此外，我们将在 Java 中的RoaringBitmap和BitSet之间执行性能测试。
2. RoaringBitmap简介
RoaringBitmap数据结构由于其高性能和压缩比，通常用于分析、搜索和大数据项目。它背后的想法来自位图索引，这是一种用于有效表示数字数组的数据结构。它类似于JavaBitSet，但经过压缩。
压缩大整数集，同时保持对单个元素的快速访问是RoaringBitmap的显着优势。RoaringBitmap在内部使用不同类型的容器来实现此目的。
3. RoaringBitmap的工作原理
RoaringBitmap是一组无符号整数，由不相交子集的容器组成。每个子集都有一个16位的键索引，可以保存大小为2^16的值。这允许将无符号32位整数存储为Java short，因为最坏的情况下只需要16位来表示单个32位值。容器大小的选择还确保在最坏的情况下，容器仍然适合现代CPU的L1缓存。
下图表示RoaringBitmap结构的外观：
整数的 16 个最高有效位是存储桶或块键。每个数据块表示区间 （0<= n < 2^16） 中值范围的基数。此外，如果值范围内没有数据，则不会创建块。
下图是具有不同数据的RoaringBitmap示例：
在第一个块中，我们存储 2 的前 10 个倍数。此外，在第二个块中，我们有 100 个连续的整数，从 65536 开始。图像中的最后一个块具有介于 131072 和 19660 之间的偶数。
4. RoaringBitmap内的容器
RoaringBitmap中有三种主要类型的容器 - 数组、位图和运行容器。根据分区集的特征，运行容器、位图容器或数组容器是保存分区数据的容器的实现。
当我们将数据添加到RoaringBitmap时，在内部，它会根据值是否适合容器键所涵盖的范围来决定是创建新容器还是更改现有容器。
4.1. RoaringBitmap的数组容器
数组容器不压缩数据，只保存少量数据。它所占用的空间量与它所保存的数据量成正比:每个是两个字节。数组容器使用的数据类型是短数据类型。整数按排序顺序存储。此外，数组的初始容量为4，元素的最大数量为4096。阵列容量动态变化。然而，咆哮位图在内部将数组容器转换为位图容器时，元素数量超过4096。
让我们看一个在RoaringBitmap中向数组容器插入数据的例子。我们的号码是131090。最有效的16位是0000 0000 0000 0010，这是我们的密钥。下16位为0000 0000 0001 0010。当我们把它转换成十进制进制时，它的值是18。现在，在我们插入数据之后，这是我们RoaringBitmap结构：
我们可以注意到，插入后，对于由 16 个最高有效位表示的键，数组容器的基数为 5。
4.2. RoaringBitmap的位图容器
位图容器是bitset的经典实现。
RoaringBitmap使用一个长数组来存储位图数据。数组容量为1024，与数组容器不同，数组容器是动态扩展的数组。位图容器不需要找到位置。相反，它直接访问索引。为了观察它是如何工作的，我们将使用一个简单的示例。我们将在RoaringBitmap中插入数字32786。前16位为0000 0000 0000 0000。其余位为十进制表示的1000 0000 0001 0010或32786。这个值表示要在位图容器中设置的索引。
让我们看看带有新信息的RoaringBitmap：
4.3.RoaringBitmap的运行容器
当位图的区域有大量干净的单词时，运行长度编码(RLE)是最佳的容器选择。它使用一个short数据类型数组。
偶数下标处的值表示运行的开始，奇数下标处的值表示运行的长度。容器的基数是通过遍历整个运行数组来计算的。
例如，下图向我们展示了一个连续整数序列的容器。然后，在RLE执行之后，容器只有四个值:
这些值表示为11后面有四个连续递增的值，27后面有两个连续递增的值。
这种压缩算法的工作方式取决于数据的紧凑程度或连续性。如果我们有100个都在一行的short，它可以将它们从200字节压缩到4字节，但如果它们都在不同的位置，编码后它将从200字节变成400字节。
5.RoaringBitmap中的Union
在简要介绍RoaringBitmap之后，在我们进入代码示例之前，我们需要将RoaringBitmap依赖项添加到我们的pom.xml文件中：
<dependency>
<groupId>org.roaringbitmap</groupId>
<artifactId>RoaringBitmap</artifactId>
<version>0.9.38</version>
</dependency>集合的联合是在RoaringBitmap上测试的第一个操作。首先，让我们声明两个RoaringBitmap实例。第一个将是A，第二个将是B：
@Test
void givenTwoRoaringBitmap_whenUsingOr_thenWillGetSetsUnion() {
RoaringBitmap expected = RoaringBitmap.bitmapOf(1, 2, 3, 4, 5, 6, 7, 8);
RoaringBitmap A = RoaringBitmap.bitmapOf(1, 2, 3, 4, 5);
RoaringBitmap B = RoaringBitmap.bitmapOf(4, 5, 6, 7, 8);
RoaringBitmap union = RoaringBitmap.or(A, B);
assertEquals(expected, union);
}在上面的代码中，我们声明了两个RoaringBitmap实例。我们使用RoaringBitmap提供的bitmapOf（）static Factory 方法创建实例。然后，我们使用or（） 方法来执行集合联合操作。在后台，此操作在设置位图之间完成逻辑OR。这是一个线程安全操作。
6.RoaringBitmap中的交叉点
我们可以在集合上执行的另一个有用的操作是交集。
让我们实现交叉问题的测试用例。与并集一样，交集操作在RoaringBitmap 中非常简单：
@Test
void givenTwoRoaringBitmap_whenUsingAnd_thenWillGetSetsIntersection() {
RoaringBitmap expected = RoaringBitmap.bitmapOf(4, 5);
RoaringBitmap A = RoaringBitmap.bitmapOfRange(1, 6);
RoaringBitmap B = RoaringBitmap.bitmapOf(4, 5, 6, 7, 8);
RoaringBitmap intersection = RoaringBitmap.and(A, B);
assertEquals(expected, intersection);
}我们在此测试用例中使用来自RoaringBitmap类的另一个静态工厂方法声明A集。bitmapOfRange（）static 方法创建一个新的RoaringBitmap。在后台，bitmapOfRange（） 方法创建一个新实例，并使用add（） 方法将范围内的数据添加到RoaringBitmap中。在这种情况下，add（） 方法接收两个长整型值作为表示下限和上限的参数。下限是包含的。相比之下，上限被排除在结果集范围之外。add（） 方法接收两个int值作为参数，对于当前 API 版本已弃用。
然后，我们使用and（） 方法来执行我们的交集操作。顾名思义，and（） 方法在两个集合之间执行逻辑AND操作。此操作是线程安全的。
7.RoaringBitmap的差异
除了并集和交集之外，我们还有集合运算的相对互补。
接下来，让我们使用RoaringBitmap 构建集合差的测试用例：
@Test
void givenTwoRoaringBitmap_whenUsingAndNot_thenWillGetSetsDifference() {
RoaringBitmap expected = RoaringBitmap.bitmapOf(1, 2, 3);
RoaringBitmap A = new RoaringBitmap();
A.add(1L, 6L);
RoaringBitmap B = RoaringBitmap.bitmapOf(4, 5, 6, 7, 8);
RoaringBitmap difference = RoaringBitmap.andNot(A, B);
assertEquals(expected, difference);
}像我们前面的代码示例一样，我们声明了两个集合，A和B。对于这种情况，我们使用不同的方法来实例化A集。我们首先创建一个空的RoaringBitmap。然后，我们使用add（） 方法，与上一节中描述的bitmapOfRange（） 方法相同。
andNot（） 方法执行A和B 之间的集合差。从逻辑角度来看，此操作执行按位ANDNOT（差分）操作。只要给定的位图保持不变，此操作就是线程安全的。
8.RoaringBitmap中的异或运算
此外，我们在RoaringBitmap中具有 XOR（独占或）操作。此操作类似于集合的相对补集，但结果集中省略了两个集合之间的公共元素。
我们使用xor（） 方法来执行此操作。让我们跳到我们的测试代码示例：
@Test
void givenTwoRoaringBitmap_whenUsingXOR_thenWillGetSetsSymmetricDifference() {
RoaringBitmap expected = RoaringBitmap.bitmapOf(1, 2, 3, 6, 7, 8);
RoaringBitmap A = RoaringBitmap.bitmapOfRange(1, 6);
RoaringBitmap B = RoaringBitmap.bitmapOfRange(4, 9);
RoaringBitmap xor = RoaringBitmap.xor(A, B);
assertEquals(expected, xor);
}简而言之，RoaringBitmap类中的xor（） 方法执行按位XOR操作并且是线程安全的。
9. 比较性能与位集
此外，让我们在RoaringBitmap和JavaBitSet之间构建一个简单的性能测试。对于每种集合类型，我们测试前面描述的操作：并集、交集、差分和异或。
我们使用Java微基准工具（JMH）来实现我们的性能测试。首先，我们需要将依赖项添加到我们的pom.xml文件中：
<dependency>
<groupId>org.openjdk.jmh</groupId>
<artifactId>jmh-generator-annprocess</artifactId>
<version>1.36</version>
</dependency>
<dependency>
<groupId>org.openjdk.jmh</groupId>
<artifactId>jmh-core</artifactId>
<version>1.36</version>
</dependency>最新版本的JMH Core和JMH注释处理器依赖项可以在Maven Central中找到。
9.1. 声明基准测试范围
接下来，我们在设置测试的初始条件时声明我们的类和集合：
@State(Scope.Thread)
class BitSetsBenchmark {
private RoaringBitmap rb1;
private BitSet bs1;
private RoaringBitmap rb2;
private BitSet bs2;
private final static int SIZE = 10_000_000;
}最初，我们声明每种类型的两组，BitSet和RoaringBitmap。然后，我们设置最大大小。SIZE变量是我们用作设置大小的上限。
我们将在此类中执行所有测试。此外，我们还使用Scope.ThreadforState和默认的吞吐量基准模式。
我们将在操作后生成一个新集合，以避免改变我们的输入数据结构。避免突变对于并发上下文很重要。这就是为什么对于BitSet情况，我们将克隆输入集，以便结果数据不会改变输入集。
9.2. 基准数据设置
接下来，让我们为测试设置数据：
@Setup
public void setup() {
rb1 = new RoaringBitmap();
bs1 = new BitSet(SIZE);
rb2 = new RoaringBitmap();
bs2 = new BitSet(SIZE);
for (int i = 0; i < SIZE / 2; i++) {
rb1.add(i);
bs1.set(i);
}
for (int i = SIZE / 2; i < SIZE; i++) {
rb2.add(i);
bs2.set(i);
}
}我们的两个位集初始化为SIZE。然后，对于第一个RoaringBitmap和BitSet，我们添加/设置值，最高为SIZE / 2，不包括在内。对于其他两个集合，我们将SIZE / 2中的值添加到SIZE中。
9.3. 基准测试
最后，让我们编写测试代码。让我们从联合操作开始：
@Benchmark
public RoaringBitmap roaringBitmapUnion() {
return RoaringBitmap.or(rb1, rb2);
}
@Benchmark
public BitSet bitSetUnion() {
BitSet result = (BitSet) bs1.clone();
result.or(bs2);
return result;
}第二个操作是交集：
@Benchmark
public RoaringBitmap roaringBitmapIntersection() {
return RoaringBitmap.and(rb1, rb2);
}
@Benchmark
public BitSet bitSetIntersection() {
BitSet result = (BitSet) bs1.clone();
result.and(bs2);
return result;
}第三个是区别：
@Benchmark
public RoaringBitmap roaringBitmapDifference() {
return RoaringBitmap.andNot(rb1, rb2);
}
@Benchmark
public BitSet bitSetDifference() {
BitSet result = (BitSet) bs1.clone();
result.andNot(bs2);
return result;
}最后一个是异或操作：
@Benchmark
public RoaringBitmap roaringBitmapXOR() {
return RoaringBitmap.xor(rb1, rb2);
}
@Benchmark
public BitSet bitSetXOR() {
BitSet result = (BitSet) bs1.clone();
result.xor(bs2);
return result;
}9.4. 基准测试结果
执行基准测试后，我们得到以下结果：
Benchmark Mode Cnt Score Error Units
BitSetsBenchmark.bitSetDifference thrpt 25 3890.694 ± 313.808 ops/s
BitSetsBenchmark.bitSetIntersection thrpt 25 3542.387 ± 296.007 ops/s
BitSetsBenchmark.bitSetUnion thrpt 25 3012.666 ± 503.821 ops/s
BitSetsBenchmark.bitSetXOR thrpt 25 2872.402 ± 348.099 ops/s
BitSetsBenchmark.roaringBitmapDifference thrpt 25 12930.064 ± 527.289 ops/s
BitSetsBenchmark.roaringBitmapIntersection thrpt 25 824167.502 ± 30176.431 ops/s
BitSetsBenchmark.roaringBitmapUnion thrpt 25 6287.477 ± 250.657 ops/s
BitSetsBenchmark.roaringBitmapXOR thrpt 25 6060.993 ± 607.562 ops/s正如我们所注意到的，RoaringBitmap的性能优于BitSet操作。尽管有这些结果，但我们需要考虑何时使用每种类型。
在某些情况下，尝试使用压缩位图是浪费。例如，这可能是当我们有一个小型数据宇宙时。如果我们可以在不增加内存使用的情况下解压缩BitSet，则压缩位图可能不适合我们。如果不需要压缩，BitSet可提供出色的速度。
