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那样占用一个MB ...

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