6

トライ マップとは、ペイロードがハッシュ テーブルではなくトライに格納される連想配列を意味します。

ハッシュ マップ/テーブルを使用している場合、使用するキーは通常文字列です。いくつかのトライベースのマップに対するハッシュマップの利点は何ですか? ハッシュマップの方が速いと読んだことがありますが、一貫したハッシュ関数は (char) 配列の各要素をチェックして最終的なハッシュを確認し、配列を1回反復する必要があるようです。試行では、同様に配列を 1 回だけ反復処理する必要があります。

これは、小さなオブジェクトをエンコードするときに、より多くのメモリを使用するように思えます (キーで小文字のアルファ文字のみを許可する場合でも、ノードごとに 26 個のポインターであり、多くの場合、キーごとに複数のノードです)。サイズ変更について心配する必要はありません。ハッシュ マップが非常に一般的であるのに、トライ マップを見たことがないのはなぜですか?

4

2 に答える 2

12

あなたが Scala プログラマーである場合に備えて、TrieMap は「ハッシュ配列にマップされたトライの並行スレッドセーフなロックフリー実装」です。現時点では、Java 標準ライブラリには何もありません。

于 2015-03-19T22:50:40.883 に答える
9

ハッシュ マップは、より一般的であるため、トライ マップよりも一般的です。トライがシーケンスに対して機能するのに対し、ハッシュ マップはハッシュ可能な任意のオブジェクトに対して機能するように作成できます。また、ハッシュ テーブルは要素を近くに格納するため、一般的な実装で参照の局所性が向上します。

(厳密に言えば、すべてのオブジェクトは一連のビットですが、一般的なトライでは、トライに格納する前にユーザーがオブジェクトをシリアル化する必要があります。これは、カスタム ハッシュ関数を定義する場合と比べてかなり不便です。)

于 2011-04-08T08:30:23.853 に答える