Java中非常紧凑的Bitarray

Question

我正在寻找一种在Java中存储密集可变长度比特阵的非常紧凑的方法.现在,我正在使用BitSet,但它似乎平均使用1.5*n位存储空间用于大小为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和克隆()调用.如果您克隆对象或对其进行序列化,则会将其修剪为正确的长度(假设类通过ensureCapacity方法对其进行了扩展).

Answer 2

您可能会受益于压缩的BitSet替代方案.参见例如:

https://github.com/lemire/javaewah

http://roaringbitmap.org/