Java中非常紧凑的位数组

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 的另一种实现。

- dmcer

---

我很难想象这会在标准的Java库中存在。它并不是为此而设计的。不过，我敢打赌你可以找到一个第三方库来解决这个问题。 - Pace

我认为在你的情况下，自定义实现会更好。 - cx0der

Answer 1

如果您使用构造函数BitSet（int nbits）创建BitSet，则可以指定容量。如果容量估计错误并超过了容量，它会将大小加倍。 BitSet类确实具有私有的trimToSize方法，并且被writeObject和clone()调用。如果你克隆对象或对其进行序列化，它将把它修剪到正确的长度（假设该类通过ensureCapacity方法进行了过度扩展）。

- brianegge

---

好的，我会尽力进行翻译：没问题。注意，你实际上不需要使用复制的版本。原始版本已经被削减了(!)。 - Tom Hawtin - tackline

这很聪明。谢谢！ - dmcer

至少在 GrepCode 上的 openjdk source 中，在您指定初始大小且数组不需要增长的情况下，原始数据没有被截取。 - user2357112

Answer 2

您可能会受益于压缩的BitSet替代方案。例如，可以参考以下内容：

https://github.com/lemire/javaewah

http://roaringbitmap.org/

- Daniel Lemire