概覽

在本教程中，我們将學習關于Roaring Bitmap的知識。我們将使用一些基本操作作為RoaringBitmap的示例。此外，我們還将在Java中執行RoaringBitmap和BitSet之間的性能測試。

Roaring Bitmap 簡介

Roaring Bitmap的資料結構因高性能和壓縮比而常用于分析、搜尋和大資料項目。它的設計靈感來自于位圖索引，一種有效表示數字數組的資料結構。它類似于Java BitSet，但具有壓縮功能。
在保持對單個元素快速通路的同時壓縮大整數集合是 Roaring Bitmap 的一個重要優勢。Roaring Bitmap 内部使用不同類型的容器來實作這一點。

Roaring Bitmap是如何工作的

一組Roaring Bitmap是由不相交子集容器組成的無符号整數集。每個子集都有一個16位鍵索引，并且可以容納大小為2^16的值範圍。這使得無符号32位整數可以存儲為Java shorts，因為最壞情況下隻需要16位來表示單個32位值。

整數的16個最高有效位是桶或塊鍵。每個資料塊表示區間（0<= n < 2^16）中值範圍的基礎。此外，如果值範圍内沒有資料，則不會建立該資料塊。

下圖是具有不同資料的咆哮位圖示例：

在第一個塊中，我們存儲了 2 的前 10 個倍數。此外，在第二個塊中，我們有 100 個從 65536 開始的連續整數。圖像中的最後一個塊具有 131072 到 19660 之間的偶數。

Roaring Bitmap的容器

Roaring Bitmap中的容器主要分為三種——數組、位圖和運作容器。根據分區集的特性，Run Container、Bitmap Container 或 Array Container 是儲存分區資料的容器的實作。

當我們向 roaring bitmap 添加資料時，在内部，它會根據值是否适合容器鍵覆寫的範圍來決定是建立一個新容器還是更改現有容器。

數組容器

Array Container 不壓縮資料，隻儲存少量資料。它占用的空間量與其儲存的資料量成正比：每個都是兩個位元組。
Array Container使用的資料類型是short。整數按排序順序存儲。
此外，數組的初始容量為4，最大元素數量為4096。數組容量是動态變化的。然而，當元素數量超過4096時，Roaring Bitmap會将Array Container内部轉換為Bitmap Container。
讓我們看一個在 Roaring Bitmap 中向數組容器插入資料的例子。我們有數字 131090。最高的16位是0000 0000 0000 0010，這是我們的鍵值。低16位是0000 0000 0001 0010。當我們将其轉換為十進制時，它的值為18。現在，在插入資料後，這就是我們 Roaring Bitmap 的結構：

我們可以注意到，插入後，Array Container 的基數對于最高 16 位代表的鍵為 5。

Roaring Bitmap容器

Bitmap Container 是 bitset 的經典實作。
使用長數組來存儲位圖資料。該數組容量恒定為1024，不像動态擴充數組的Array Container。Bitmap Container不需要查找位置，而是直接通路索引。
為了觀察它的工作原理，我們将使用一個簡單的例子。我們将把數字32786插入到Roaring位圖中。前16位是0000 0000 0000 0000。其餘的位是1000 0000 0001 0010或者在十進制表示中為32786。這個值代表要在位圖容器中設定的索引。讓我們看看帶有新資訊的Roaring位圖：

RoaringBitmap 的運作容器

Run-length Encoding（RLE）是位圖中某個區域有大量幹淨單詞時的最佳容器選擇。它使用短資料類型數組。
偶數索引處的值表示運作的開始，奇數索引處的值表示這些運作的長度。通過周遊完整的運作數組來計算容器的基數。
例如，下圖向我們展示了一個包含連續整數序列的容器。然後，在 RLE 執行之後，容器隻有四個值：

這些值表示為11後跟随四個連續遞增的值，以及27後跟随兩個連續遞增的值。

這個壓縮算法的工作方式取決于資料的緊湊程度或連續性。如果我們有100個短整數都在一排，它可以将它們從200位元組壓縮到4位元組，但如果它們分散在不同位置，編碼後大小會從200位元組變為400位元組。

RoaringBitmap中的聯合

在我們開始代碼示例之前，讓我們簡要介紹一下 Roaring Bitmap，并将 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()靜态工廠方法來建立執行個體。然後，我們使用or()方法執行集合并操作。在幕後，此操作在設定位圖之間完成邏輯OR運算。這是一個線程安全的操作。

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()靜态方法建立了一個新的RoaringBitmap。在底層，bitmapOfRange()方法建立了一個新執行個體，并使用add()方法将資料添加到Roaring Bitmap範圍内。在本例中，add()方法接收兩個長整型值作為參數，表示下限和上限。下限是包含的，而上限則不包含在結果集範圍内。對于目前API版本，接收兩個int值作為參數的add()方法已被棄用。
然後，我們使用and()方法執行交集操作。正如其名稱所示，and()方法在兩個集合之間執行邏輯AND操作。此操作是線程安全的。

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（差）運算。隻要給定的位圖保持不變，此操作就是線程安全的。

RoaringBitmap的異或運算

此外，Roaring Bitmap 中還有 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()方法執行的是按位異或運算，是線程安全的。

和BitSet對比下性能

此外，讓我們在 RoaringBitmap 和 Java BitSet 之間建構一個簡單的性能測試。對于每個集合類型，我們測試前面描述的操作：聯合、交集、差異和異或。

我們使用 Java Microbenchmark Harness (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>

聲明基準範圍

接下來，我們在為測試設定初始條件時聲明我們的類和集合：

@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。 SIZE 變量是我們将用作集合大小的上限。

我們将在本課程中執行所有測試。此外，我們使用 Scope.Thread 作為 State 和預設的吞吐量基準模式

我們将在操作後生成一個新集合，以避免改變我們的輸入資料結構。避免突變對于并發上下文很重要。這就是為什麼，對于 BitSet 案例，我們将克隆輸入集，這樣結果資料就不會改變輸入集。

基準資料設定

接下來，讓我們為測試設定資料：

@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);
    }
}

我們的兩個 BitSet 集合被初始化為 SIZE。然後，對于第一個 RoaringBitmap 和 BitSet，我們将值添加/設定為 SIZE / 2，不包括在内。對于其他兩組，我們将 SIZE / 2 的值添加到 SIZE。

基準測試

最後，讓我們編寫測試代碼。讓我們從聯合操作開始：

@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;
}

基準測試結果

執行我們的基準測試後，我們得到以下結果：

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 可提供出色的速度。

結論

在本文中，我們了解了咆哮的位圖資料結構。我們讨論了 RoaringBitmap 的一些操作。此外，我們在 RoaringBitmap 和 BitSet 之間進行了一些性能測試。結果，我們了解到前者的表現優于後者。

英文位址：

https://www.baeldung.com/java-roaring-bitmap-intro

RoaringBitmap的簡介

概覽

Roaring Bitmap 簡介

Roaring Bitmap是如何工作的

Roaring Bitmap的容器

數組容器

Roaring Bitmap容器

RoaringBitmap 的運作容器

RoaringBitmap中的聯合

RoaringBitmap 中的交集

RoaringBitmap的差集

RoaringBitmap的異或運算

和BitSet對比下性能

聲明基準範圍

基準資料設定

基準測試

基準測試結果

結論

英文位址：

繼續閱讀

Spring 容器原始 Bean 是如何建立的？

SpringBoot 實作資料加密脫敏（注解 + 反射 + AOP）

Spring-1-透徹了解Spring XML的必備知識

SpringBoot 開發入門—Springboot基礎架構

緩存注解大揭秘：SpringCloud中如何使用緩存注解？

Spring Cloud Gateway：新一代微服務API網關

4個好用的springboot開源項目#程式員#計算機#幹貨分享

香港教育大學MPPM開放24Spring入學申請！CET6可申。内地考研失敗有英語六級的孩子可以關注一下

一套基于Spring Cloud開發的智慧工地項目管理平台源碼

springboot如何優雅的實作異常重試機制

精通Spring 5.0：深入了解自動化配置的條件化注解

怎樣快速搭建 Spring 的源碼環境，用 IDEA啊！！

使用filebeat收集并解析springboot日志

SpringCloud基礎概念篇

Springboot整合GraphQL使你的API更易了解可讀性更強

Spring Boot Jar包與遠端調試