java - 咆哮位图使用比普通位集更多的存储空间

Question

我有一个位集，我用它来跟踪一个项目是否存在的例子

b = 01100110000

它表示第 2 项和第 3 项存在，第 1 项和第 4 项不存在。

在搜索可以优化此位集数组的库时。我遇到了Roaring bitmaps这听起来非常令人兴奋。

我用它做了一个快速测试，

    public static void main(String[] args) throws IOException {
        RoaringBitmap roaringBitMap = new RoaringBitmap();
        BitSet bitSet = new BitSet(5000);
        double prob = 0.001;
        Random random = new Random();
        for (int i = 0; i < 5000; i++) {
            if (random.nextDouble() < prob) {
                bitSet.set(i);
                roaringBitMap.add(i);
            }
        }
        System.out.println(bitSet.cardinality());
        System.out.println("bitset bytes: "+ bitSet.size());
        System.out.println("RoaringBitmap bytes: " + roaringBitMap.getSizeInBytes() * 8);
    }

基本上我们正在设置一些值并检查数据结构的整体大小。

当我们使用多个概率值运行它时。我得到了

<表类="s-表"><头>概率字节bitset 字节RoaringBitmap 字节数<正文>0.00150562880.0150569440.1505678720.999505665616

如果您看到随着我们插入越来越多的数字，RoaringBitmap 的内存占用量会增加。

1. 这是预期的吗？
2. 在最坏的情况下，它不应该退回到基于位集的实现吗？
3. 不能将 0.999 视为 0.001 的倒数并且我们能够将其存储在 288 字节中吗？
4. 当我们进行服务间调用和使用 jackson 库(但不是基于字节的序列化库)时，将这些位集表示为字符串的最佳方式是什么

Answer 1

当条目数量较少时似乎是这种情况，但是当我们增加条目数量时，差异变得不那么明显了。虽然没有得到 lib 作者的确认(我问了 here 并跟进了 here )

<表类="s-表"><头>概率条目数bitset位RoaringBitmap 位节省 %<正文>0.0015000050048928980.0150000500487744840.1500005004865616-310.999500005004865616 <- 注意它不会增加-310.0015000005000328704980.0150000050003280720830.1500000500032524480-40.999500000500032524480 <- 注意它不会增加-40.0015000000050000000835232980.0150000000500000008036368830.1500000005000000050016240-0.030.999500000005000000050016240 <- 注意它不会增加-0.03

看着这个，似乎随着条目数量的增加，他们可能只在幕后使用位图。重要的是不要盲目使用该库，针对您的用例进行测试。