'BitSet' 存储位还是整数？

Question

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

val b = BitSet(0, 2, 3) 

意味着为位位置 0、2 和 3 存储 1？

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

Answer 1

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

鉴于你的例子：

BitSet(0, 2, 3)

我们可以将所有这些数字存储在单个 中Long，二进制将是：

1101

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

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

作为旁注，immutable.BitSet在 Scala 中有一个特殊的实现（BitSetLike特征），即BitSet1and BitSet2，它们分别由一个和两个 long 支持，避免需要分配一个额外的数组来包装它们。