ハッシュテーブル

目次

ハッシュテーブル

ハッシュテーブルは要素を元となる配列に保持し、要素をそのハッシュコードから特定される位置に置きます。 ハッシュテーブルへの要素の追加は、配列に同じハッシュコードを持つ要素が既にある場合を除いて定数時間しかかかりません。 そのためハッシュテーブルは保持しているオブジェクトがハッシュコードの良い分布を持つかぎりとても高速です。 その結果、Scalaの可変なマップとセット型のデフォルト実装はハッシュテーブルに基づくものです。 mutable.HashSetおよびmutable.HashMapという名前で直接使うこともできます。

ハッシュ集合とマップは他の集合やマップと同じように使えます。 これは簡単な例です:

scala> val map = scala.collection.mutable.HashMap.empty[Int,String]

map: scala.collection.mutable.HashMap[Int,String] = Map()

scala> map += (1 -> "make a web site")

res42: map.type = Map(1 -> make a web site)

scala> map += (3 -> "profit!")

res43: map.type = Map(1 -> make a web site, 3 -> profit!)

scala> map(1)

res44: String = make a web site

scala> map contains 2

res46: Boolean = false

ハッシュテーブルに対する繰り返しは特定の順序を保障しません。 繰り返しは単に元となる配列をたまたまそこにあった順番で処理していくだけです。 繰り返しの順序を保障したい場合は、通常のものではなく線形ハッシュマップや集合を使います。 線形ハッシュマップは要素を追加した順に持つ線形リストを含む点を除いて通常のものと同じです。 このようなコレクションに対する繰り返しは要素を最初に追加した順と常に同じ順となります。

続いては: 弱ハッシュテーブル

ハッシュテーブル

目次