Scala - TrieMap vs Vector

Question

スカラーのTrieMapは、配列マップされたトライをベースにしています。Vectorは、ビットマップされたベクトルトライを読み取ります。

どちらの構造もハッシュトライと同じ考え方でバックアップされているのでしょうか、それとも違いがありますか？

Answer 1

いくつかの類似点がありますが、基本的に彼らは、異なるデータ構造です：

ベクトル

Vectorに関わる一切のハッシュはありません。インデックスはツリーへのパスを直接記述します。もちろん、ベクトルの占有インデックスは連続しています。

無視scala.collection.immutable.Vectorの生産の実装で表示ポインタを持つすべての策略は、レベルの最後のものを除いてベクター内のすべてのブランチノードは、（32スカラVectorの場合）子供の同じ数を有しています。これにより、単純なビット操作を使用したインデックス作成が可能になります。欠点は、ベクターの中央にあるスプライシング要素が高価であることです。 HashTrieMapで

のHashMap

、ハッシュコードは、ツリーへのパスです。つまり、占有指数はで、連続していません。ですが、均等に分布しています。これは、ツリー分岐ノードの異なる符号化を必要とする。 HashTrieMapで

は、ブランチノードはまでの32人の子供を持っている（しかし、あなたは非常に悪いハッシュコードの配布を持っている場合、唯一の子を持つブランチノードを持つことは完全に可能です）。どの子がどの位置に対応するかをエンコードするビットマップはIntです。つまり、HashTrieMapで値を検索すると、往々にして最新のCPUに組み込まれているCPUであるInteger.bitCountが頻繁に呼び出されます。ここで

あなたは、このようなVectorとHashMapとしてScalaのデータ構造の内部を見ることができます楽しいプロジェクトです：https://github.com/stanch/reftree

この答えでは画像は、このプロジェクトを使用して作成しました。