java - Java中非常紧凑的位数组

Question

我正在寻找一种在 Java 中存储密集可变长度位数组的非常紧凑的方法。现在，我正在使用，但对于大小为nBitSet的位向量，它似乎平均使用1.5*n 位的存储空间。通常，这不是问题，但在这种情况下，存储的位数组是应用程序内存占用的重要部分。所以，让它们变小一点真的很有帮助。

BitSet 所需的空间似乎是由于用于支持数据结构的 long 数组在每次扩展以容纳更多位时往往会翻倍：

// BitSet's resizing code
private void ensureCapacity(int wordsRequired) {
  if (words.length < wordsRequired) {
    // Allocate larger of doubled size or required size
    int request = Math.max(2 * words.length, wordsRequired);
    words = Arrays.copyOf(words, request);
    sizeIsSticky = false;
  }
}

我可以编写自己的 BitSet 替代实现，更保守地扩展后端数据结构。但是，如果我不需要的话，我真的很讨厌复制标准类库中已经存在的功能。

Answer 1

如果BitSet使用构造函数创建，则BitSet(int nbits)可以指定容量。如果你猜错了容量，然后再过去，它将增加一倍。

该类BitSet确实有一个trimToSize私有方法，由 writeObject 和 clone() 调用。如果你克隆你的对象，或者序列化它，它会将它修剪到正确的长度（假设类通过 ensureCapacity 方法过度扩展它）。

Answer 2

您可能会从压缩的 BitSet 替代方案中受益。参见例如：

https://github.com/lemire/javaewah

http://roaringbitmap.org/