|
|
|
ハッシュトライ | 目次 |
最新版は Scala Documentation に移行しました。
ハッシュトライは不変集合と不変マップを効率的に実装する標準的な方法だ。ハッシュトライは、immutable.HashMap クラスによりサポートされている。 データ構造は、全てのノードに 32個の要素か 32個の部分木があるという意味でベクトルに似ている。しかし、キーの選択はハッシュコードにより行われる。たとえば、マップから任意のキーを検索する場合、まずキーのハッシュコードを計算する。その後、最初の部分木を選択するのにハッシュコードの下位 5ビットが使われ、次の 5ビットで次の部分木が選択される、という具合だ。ノード内の全ての要素が、その階層までで選ばれているビット範囲内でお互いと異なるハッシュコードを持った時点で選択は終了する。
ハッシュトライは、サイズ相応の高速な検索と、相応に効率的な関数型加算 (+) と減算 (-) の調度良いバランスが取れている。そのため、ハッシュトライは Scala の不変マップと不変集合のデフォルトの実装を支えている。実は、Scala は要素が 5個未満の不変集合と不変マップに関して、更なる最適化をしている。1 〜 4個の要素を持つ集合とセットは、要素 (マップの場合は、キー/値のペア) をフィールドとして持つ単一のオブジェクトとして格納する。空の不変集合と、空の不変マップは、ぞれぞれ単一のオブジェクトである。空の不変集合や不変マップは、空であり続けるため、データ構造を複製する必要はない。
続いては、赤黒木
|
|
|
ハッシュトライ | 目次 |