BitSet值得使用吗？

Question

我创建了一个具有大量布尔字段的Java对象。当我开始质疑BitSet是否有用时，我正在考虑使用它。

当然，一个人会出于内存的原因使用它，因为一个boolean单独是8位，一个数组中有4位。使用BitSet，每个值都存储为一个位。然而，，节省下来的内存不会被以下开销吹出水面吗？

• BitSet类和方法定义元数据(每个运行时)
• 在语义上检索值所需的对象(使用BitSet的每个类)
• bits数组在BitSet中的元数据(每个实例)

与使用boolean的比较：

• 布尔值(每个实例)

让我们来看看下面的课：

private boolean isVisible; // 8 bits per boolean * 82 booleans = ~0.6Kb
// 81 lines later...
private boolean isTasty;

// ...

public boolean isVisible() { return isVisible; }
// ...
public boolean isTasty() { return isTasty; }

public void setVisible(boolean newVisibility) { isVisible = newVisibility; }
// ...
public void setTasty(boolean newTastiness) { isTasty = newTastiness; }

现在，如果我要将所有的boolean合并到一个BitSet中，并且仍然保持代码语义，我可能会这样做：

private static final int _K_IS_VISIBLE = 1; // 32 bits per key * 82 keys = ~2.5Kb
// ...
private static final int _K_IS_TASTY = 82;
private BitSet bools = new BitSet(82); // 2 longs = 64b

// ...

public boolean isVisible() { return bools.get(_K_IS_VISIBLE); }
// ...
public boolean isTasty() { return bools.get(_K_IS_TASTY); }

public void setVisible(boolean newVisibility) { bools.set(_K_IS_VISIBLE, newVisibility); }
// ...
public void setTasty(boolean newTastiness) { bools.set(_K_IS_TASTY, newTastiness); }

tl;dr

costOfUsingBitSet =
    bitSetMethodsAndClassMetaData + // BitSet class overhead
    (numberOfKeysToRetrieveBits * Integer.SIZE) + // Semantics overhead
    (numberOfBitSetsUsed * floor((bitsPerBitSet / Long.SIZE) + 1)); // BitSet internal array overhead

可能还有更多。而使用booleans则是：

costOfBooleans = 
    (numberOfBooleansOutsideArrays * 8) + 
    (numberOfBooleansInsideArrays * 4);

我觉得BitSet 的开销要高得多。我说得对吗？

Answer 1

boolean[]和BitSet的空间比较不错

https://www.baeldung.com/java-boolean-array-bitset-performance

​

他们好像在这里换了标签。在BitSet中，每个内存应该有更多的位(蓝色)。

这里的主要优点是，BitSet在内存占用方面超过了boolean[]，只有极少量的比特除外。

在您的示例中，另一种方法是使用2 long作为位标志。

class A {
// 1st set
private static final long IS_VISIBLE_MASK = 1; 
...
private static final long IS_DARK_MASK = 1 << 63 ; 

// 2nd set...
private static final long IS_TASTY_MASK = 1;
...

// IS_VISIBLE_MASK .. IS_DARK_MASK
long data1;

// IS_TASTY_MASK ...
long data2;

boolean isDark = (data1 & IS_DARK_MASK) != 0; 

}

局限性

BitSet有一些愚蠢的限制，因为您可以达到最大的Integer.MAX_VALUE位。我需要尽可能多的数据存储在内存中。因此修改了原来的实现有两种方式：

• 对于固定大小的LongBitSets (即用户在构建时指定长度)，计算量更少。
• 它可以到达最大可能的字阵列中的最后一位。

添加了有关这条线限制的详细信息

Answer 2

BitSet内存将更少，只使用一位就会大大提高效率。无论您有多少类实例，您正在查看的方法开销都是一次，因此它的成本基本上被摊还到0。

boolean相对于boolean或BitSet数组的优点是它不是Object，因此您的间接方向少了一个级别。

缓存命中是性能的主要驱动因素，因此您必须权衡较少的缓存命中，以及由于较高的内存消耗而将数据从缓存中逐出的可能性更高。

粗略地说，一些boolean的速度会更快，但内存会更多，因为您有更多的字段或更接近于庞大的数字，所以规模将达到BitSet的最高值。