Java多位/紧凑型小整数阵列

我正在努力实现一些布隆过滤器变体，并且一个非常有用的数据结构将是一个紧凑的多位数组;也就是说，每个元素是一个大约4位的紧凑整数的数组。Java多位/紧凑型小整数阵列

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

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

编辑：静态尺寸很好。理想情况下，实现方式对于每个单元的位数是灵活的。尽管这可能有点希望（不是双关语意图？）。

['java.util.BitSet']（http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html）？ – rgettman

除非我误解，BitSet是每个单元1位。我可以用一些算术来实现我在寻找的东西（或者对于每个int有16个4位单元的int数组顶部），但这似乎是一个足够通用的用例，希望有人在那里已经做到了。 –

如果不修改创建后的阵列，java.util.BitSet做所有的位掩膜你，但速度很慢访问，因为你必须单独提取每个位，做自己掩盖重新创建从INT 4比特。

说了写自己可能是最好的方式去。这样做的位算术自己并不困难，因为它的每个字节只有2值，从而解码高位是(array[i] & 0xF0) >> 4和低位是array[i] & 0x0F

2013-08-20 21:32:04 dkatzel

我可能最终只是这样做。它变得更复杂，尽管如果我最终想要，比如6位而不是4位。 –

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

I.e.像

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

仍将只占几个字节，而不是一个MB作为与Java位集合...

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

2015-07-10 11:38:59 centic

回答