scala - 'BitSet' 存储位还是整数？

Question

我对 BitSet 感到困惑。 BitSet 数据结构是否存储 1 和 0？

val b = BitSet(0, 2, 3) 

表示位位置 0、2 和 3 存储 1？

如果是这样，最大值是多少？不。位数，32 位还是 64 位？

Answer 1

Scala 中的 BitSet 是作为 Array[Long] 实现的，其中每个位都表示数组中存在一个数字。 Long 在 Scala(在 JVM 上)中是 64 位的。一个这样的 Long 可以存储值 0 到 63，下一个可以存储 64 到 127，依此类推。这是可能的，因为我们只讨论正数，不需要考虑符号。

以你的例子为例:

BitSet(0, 2, 3)

我们可以将所有这些数字存储在一个 Long 中，二进制形式为:

1101

因为我们在 0 到 63 的范围内，所以这适用于单个 Long 值。

一般来说，Scala 中 BitSet 中存储的上限或最大值是 Int.MaxValue，即 2^31-1(2147483647)。为了存储它，您需要 2147483647/64 表示数字的“位”，即 ~= 33554432 长整数。这就是为什么在位集中存储大量数字会变得非常昂贵，并且通常只在处理数百个左右的数字时才推荐这样做。

作为旁注，immutable.BitSet 在 Scala 中有一个特殊的实现(BitSetLike 特性)，即 BitSet1 和 BitSet2，分别由 1 和 2 长型支持，避免了分配额外数组来包装它们的需要。