数据结构Java多位/紧凑型小整数数组

Question

我正在努力实现一些bloom过滤器变体，一个非常有用的数据结构是一个紧凑的多位阵列；也就是说，一个数组，其中每个元素是一个约4位的压缩整数

在这里，空间效率是最重要的，所以虽然一个普通的整数数组可以提供我想要的功能，但它会比需要的体积更大

在我尝试用位算法实现这个功能之前，我想知道是否有人知道已经提供了这样一个数据结构的库

编辑：静态大小可以。 理想的情况是在每个单元的位数方面具有灵活性的实现。这可能是一个有点多的希望，虽然（没有双关语的意图？）

Answer 1

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

比如说

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

仍将只占用几个字节，而不是像Java位集那样占用一个MB

通过将索引乘以相应的位集中，您应该能够将4位整数映射到位集中

Answer 2

If you aren't modifying the array after creation, java.util.BitSet does all the bit masking for you but is slow to access since you have to fetch each bit individually and do the masking yourself to re-create the int from 4 bits.

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