在 Java 中使用 BitSet 处理长数据

Question

我有一个范围为 0 到 Long.MAX_VALUE、
的大型数据集并想使用 BitSet 搜索任何重复项。

虽然 Java BitSet 的功能不允许太长。
用BitSet可以实现吗？

// incoming data have range 0 to 9,223,372,036,854,775,807 (Long max value)  
// e.g. 1, 3, 5, 1, 2_000_000_000, 2_000_000_000
// expected output: 1, 2_000_000_000, as they appear twice

long[] myData = new long[]{1, 3, 5, 1, 2_000_000_000, 2_000_000_000};
// int[] myData = new int[]{1, 3, 5, 1}; // it working well for int array
BitSet bs = new BitSet();
        
for(int i = 0; i < myData.length; i++) {
    if(bs.get(myData[i])) {  // fail here as bitset only accept int
        System.out.println("duplicated number: " + myData[i]);
    } else {
        bs.set(myData[i]); // same here
    }
}

Answer 1

BitSet 可以通过查看之前设置的位来使用。那将构成重复值。但是，您不能设置大于 Integer.MAX_VALUE 的位位置（对于多头来说，处理如此大的范围是不可行的）。所以它不适用于您建议的范围。而且我猜你仍然想记录重复项。

我会使用 Map<Long,Long> 来计算频率。然后您可以确定所提供的每个值的确切计数。定位 map 的下一个 Key 相当于计算哪个内部 long 值持有所需的位。所以我不认为性能是这里的一个因素。

如果您只是想消除重复项，那么只需将它们放在 Set<Long>

根据您的评论，查看这个在 BitSet 中保存一个大值的简单测试。

BitSet bitSet = new BitSet();
bitSet.set(Integer.MAX_VALUE);
long[] backingArray = bitSet.toLongArray();
System.out.printf("Size of backing array = %,d longs.%n",backingArray.length);

版画

Size of backing array = 33,554,432 longs.

在 Java 中使用 BitSet 处理长数据

Handling Long data with BitSet in Java

java

bitset