我对BitSet感到困惑。BitSet数据结构存储1和0吗？
BitSet
val b = BitSet(0, 2, 3)
表示在位位置0、2和3存储1？如果是，最大位数是多少，32还是64？
hec6srdp1#
Scala中的BitSet实现为Array[Long]，其中每个位表示数组中存在一个数字。一个这样的Long可以存储0到63的值，下一个可以存储64到127的值，等等，这是可能的，因为我们只讨论正数，不需要考虑符号。举个例子：
Array[Long]
Long
BitSet(0, 2, 3)
我们可以将所有这些数字存储在一个Long中，其二进制形式为：
1101
因为我们的取值范围是0到63，所以只对一个Long值有效。通常，Scala中BitSet的上限（即存储在其中的最大值）是Int.MaxValue，即2^31-1（2147483647）。为了存储它，您需要2147483647 / 64个“位”来表示数字，即~= 33554432个long。这就是为什么在位集中存储大量数字会非常昂贵的原因。通常只有当你处理的数字在几百左右的时候才推荐使用。顺便说一句，immutable.BitSet在Scala中有一个特殊的实现（BitSetLike trait的），即BitSet1和BitSet2，它们分别由一个1和两个long支持，避免了分配额外数组来 Package 它们的需要。
Int.MaxValue
2^31-1
2147483647 / 64
immutable.BitSet
BitSetLike
BitSet1
BitSet2
lyfkaqu12#
从the documentation开始：位集是非负整数的集合，表示为压缩成64位字的可变大小的位数组。位集的内存占用量由其中存储的最大数决定。如果API处理添加和删除Int，那么可以合理地认为可以设置的最大位是max整数，即2^31-1。查看scala.collection.immutable.BitSet的源代码，还有一个Assert不允许负整数（根据上面的描述，这是有意义的）：
Int
scala.collection.immutable.BitSet
def + (elem: Int): BitSet = { require(elem >= 0, "bitset element must be >= 0")
2条答案
按热度按时间hec6srdp1#
Scala中的
BitSet实现为Array[Long]，其中每个位表示数组中存在一个数字。一个这样的Long可以存储0到63的值，下一个可以存储64到127的值，等等，这是可能的，因为我们只讨论正数，不需要考虑符号。举个例子：
我们可以将所有这些数字存储在一个
Long中，其二进制形式为：因为我们的取值范围是0到63，所以只对一个
Long值有效。通常，Scala中
BitSet的上限（即存储在其中的最大值）是Int.MaxValue，即2^31-1（2147483647）。为了存储它，您需要2147483647 / 64个“位”来表示数字，即~= 33554432个long。这就是为什么在位集中存储大量数字会非常昂贵的原因。通常只有当你处理的数字在几百左右的时候才推荐使用。顺便说一句，
immutable.BitSet在Scala中有一个特殊的实现（BitSetLiketrait的），即BitSet1和BitSet2，它们分别由一个1和两个long支持，避免了分配额外数组来 Package 它们的需要。lyfkaqu12#
从the documentation开始：
位集是非负整数的集合，表示为压缩成64位字的可变大小的位数组。位集的内存占用量由其中存储的最大数决定。
如果API处理添加和删除
Int，那么可以合理地认为可以设置的最大位是max整数，即2^31-1。查看scala.collection.immutable.BitSet的源代码，还有一个Assert不允许负整数（根据上面的描述，这是有意义的）：