リストマップ不変なコレクションの具象クラス赤黒木不変ビットセット目次

不変ビットセット

ビットセット(BitSet)は小さな整数のコレクションを大きな整数のビットとして表します。 例えば、3, 2, および0を含むビットセットは二進数で1101と表現でき、十進数では13です。

内部では、ビットセットは64bitのLongの配列を使います。 配列の最初のLongは整数0から63のために使われ、次は64から127、といった風です。 よって、集合内の最大の整数が数百程度以下の場合、ビットセットはとてもコンパクトです。

ビットセットに対する演算はとても高速です。 含有テストは定数時間です。 集合への要素の追加はビットセットの配列内にあるLongの数に比例しますが、典型的には少数です。 これはビットセットの利用の簡単な例です:

scala> val bits = scala.collection.immutable.BitSet.empty
bits: scala.collection.immutable.BitSet = BitSet()
scala> val moreBits = bits + 3 + 4 + 4
moreBits: scala.collection.immutable.BitSet = BitSet(3, 4)
scala> moreBits(3)
res26: Boolean = true
scala> moreBits(0)
res27: Boolean = false

続いては: リストマップ


リストマップ不変なコレクションの具象クラス赤黒木不変ビットセット目次