java - Java多位/紧凑小整数数组

Question

我正在实现一些布隆过滤器变体，一个非常有用的数据结构将是一个紧凑的多位数组；也就是说，一个数组，其中每个元素都是大约 4 位的紧凑整数。

空间效率在这里是最重要的，所以虽然一个普通的整数数组会给我我想要的功能，但它会比必要的更笨重。

在我尝试用位算术自己实现这个功能之前，我想知道是否有人知道那里已经提供了这种数据结构的库。

编辑：静态大小很好。理想的情况是在每个单元的比特数方面灵活的实现。不过，这可能有点希望（没有双关语？）。

Answer 1

如果您在创建后不修改数组，java.util.BitSet则为您进行所有位掩码，但访问速度很慢，因为您必须单独获取每个位并自己进行掩码以从 4 位重新创建 int。

话虽如此，自己编写可能是最好的方法。自己做位运算并不难，因为每个字节只有 2 个值，所以解码高位(array[i] & 0xF0) >> 4和低位是array[i] & 0x0F

Answer 2

看看http://code.google.com/p/javaewah/提供的压缩 BitSet ，它允许自由设置位，并通过使用的压缩算法确保它有效地使用内存。

即类似的东西

        EWAHCompressedBitmap32 set = new EWAHCompressedBitmap32();
        set.set(0);
        set.set(1000000);

仍然只占用几个字节，而不是 Java BitSet 的 1 MB...

您应该能够通过将索引相应地乘以 BitSet 来将 4 位整数映射到 BitSet