| | | ハッシュトライ | 目次 |
ハッシュトライは不変な集合やマップを効率的に実装するための標準的な方法です。 ハッシュトライはimmutable.HashMapでサポートされています。 その表現は全てのノードが32個の要素か32個のサブツリーを含むという点でベクタと似ています。 しかし、キーの選択はハッシュコードに基づいて実施されます。 例えばマップから与えられたキーを探す場合、最初にキーのハッシュコードを計算します。 そして下位の5ビットを最初のサブツリーを選択するのに使い、続いてその次の5bit、という風に続けます。 選択は1つのノード中の全ての要素について、そのレベルまでに選択されたハッシュコードのビットが他の要素のものと異なるようになるところで止まります。
ハッシュトライは合理的な速さを持つ参照と、合理的な速さを持つ関数的な挿入(+)および削除(-)の良いバランスを保っています。 これがScalaのマップと集合のデフォルト実装として使われている理由です。 さらに言えば、Scalaは5個未満の要素を持つマップと集合に対するさらなる最適化を備えています。 1から4要素までの集合とマップはその要素(またはマップの場合キーと値の組)を単にフィールドとして持つ1つのオブジェクトとして保持します。 空の不変な集合と空の不変なマップはそれぞれ1つのオブジェクトです。空の集合やマップは常に空なので重複して保持する必要はありません。
続いては: 赤黒木
| | | ハッシュトライ | 目次 |