30

HAMTの詳細について頭を悩ませようとしています。理解するためだけに、Javaで自分で実装したでしょう。私は Tries に精通しており、HAMT の主なコンセプトを理解していると思います。

基本的、

2 種類のノード:

キー/値

Key Value Node:
  K key
  V value

索引

Index Node:
  int bitmap (32 bits)
  Node[] table (max length of 32)
  1. オブジェクトの 32 ビット ハッシュを生成します。
  2. 一度に 5 ビットずつハッシュをステップスルーします。(0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31) 注: 最後のステップ (7 番目) は 2 ビットのみです。
  3. 各ステップで、ビットマップ内のその 5 ビット整数の位置を見つけます。例えばinteger==5 bitmap==00001
    1. ビットが 1 の場合、ハッシュのその部分が存在します。
    2. ビットが 0 の場合、キーは存在しません。
  4. キーが存在する場合は、ビットマップ内の 0 から位置までの 1 の数を数えて、テーブルのインデックスを見つけます。例えばinteger==6 bitmap==0101010101 index==3
    1. テーブルがキー/値ノードを指している場合は、キーを比較します。
    2. テーブルがインデックス ノードを指している場合は、1 ステップ先の 2 に進みます。

私がよく理解していない部分は、衝突の検出と軽減です。リンクされた論文で、彼はそれをほのめかしています：

次に、既存のキーが新しいサブハッシュ テーブルに挿入され、新しいキーが追加されます。ハッシュの 5 ビットが使用されるたびに、衝突の確率は 1/32 に減少します。32 ビット ハッシュ全体が消費される場合があり、2 つのキーを区別するために新しいハッシュを計算する必要があります。

「新しい」ハッシュを計算し、その新しいハッシュにオブジェクトを格納するとします。構造内のオブジェクトをどのように検索できますか? ルックアップを行うとき、「再計算されたハッシュ」ではなく「初期」ハッシュを生成しませんか。

私は何かが欠けているに違いない.....

ところで: HAMT はかなりうまく機能します。私のテストでは、ハッシュ マップとツリー マップの間に位置しています。

Data Structure                    Add time   Remove time     Sorted add time Sorted remove time   Lookup time     Size     
Java's Hash Map                   38.67 ms   18 ms           30 ms           15 ms                16.33 ms        8.19 MB        
HAMT                              68.67 ms   30 ms           57.33 ms        35.33 ms             33 ms           10.18 MB       
Java's Tree Map                   86.33 ms   78 ms           75 ms           39.33 ms             76 ms           8.79 MB        
Java's Skip List Map              111.33 ms  106 ms          72 ms           41 ms                72.33 ms        9.19 MB
4

4 に答える 4

7

HAMT は、特に不変オブジェクトが必要な場合、つまり変更後にデータ構造の新しいコピーが作成されるたびに、優れたパフォーマンスの高い構造です。

ハッシュの衝突に関するあなたの質問については、それがどのように機能するかを示すC#実装(現在はバグがあります) を見つけました: ハッシュの衝突ごとにキーが再ハッシュされ、最大反復回数の制限に達するまでルックアップが再帰的に再試行されます。

現在、関数型プログラミングのコンテキストで HAMP を調査し、既存のコードを学習しています。Haskell には Data.HshMap として、Clojure には PersistenceHashMapとして HAMTのリファレンス実装がいくつかあります。

ウェブ上には、衝突を処理しない単純な実装が他にもいくつかありますが、それらは概念を理解するのに役立ちます。ここではHaskellとOCamlで

写真付きで HAMT を説明し、Phil Bagwell による元の研究論文へのリンクを掲載している、すばらしい要約記事記事を見つけました。

関連するポイント:

F# で HAMT を実装しているときに、ここで説明されている popCount 関数の実装が非常に重要であり、リンクの次の回答で説明されている単純な実装と比較して 10-15% になることに気付きました。素晴らしいものではありませんが、無料のランチです。

関連する IntMap 構造 ( HaskellとそのF# への移植) は、キーが整数であり、関連するPATRICIA/Radix trieを実装している場合に非常に優れています。

これらの実装はすべて、効率的な不変データ構造と関数型言語をこれらの例のすべての美しさで学ぶのに非常に優れていると思います-それらは本当に一緒に輝いています!

于 2013-11-07T09:27:10.427 に答える
7

この論文には、あなたが見落としていると思われるセクションが 2 つあります。最初は、引用したビットの直前のビットです。

または、キーが既存のものと衝突します。その場合、既存のキーをサブハッシュ テーブルに置き換え、既存のキーの次の 5 ビット ハッシュを計算する必要があります。それでも衝突が発生する場合は、衝突が発生しなくなるまでこのプロセスが繰り返されます。

したがって、テーブルにオブジェクト A があり、衝突するオブジェクト B を追加すると、それらのキーが衝突したセルは別のサブテーブル (衝突しない場所) へのポインターになります。

次に、リンクした論文のセクション 3.7 では、最初の 32 ビットの終わりを使い果たしたときに新しいハッシュを生成する方法について説明しています。

ハッシュ関数は、32 ビット ハッシュを提供するように調整されました。このアルゴリズムでは、ハッシュを任意のビット数に拡張できる必要があります。これは、ゼロがルートであるトライレベルを表す整数と組み合わせたキーを再ハッシュすることによって達成されました。したがって、2 つのキーが同じ初期ハッシュを与える場合、再ハッシュは 2^32 分の 1 の確率でさらに衝突します。

これで何も説明できない場合は、言ってください。この回答をより詳細に拡張します。

于 2013-11-23T09:31:04.027 に答える
1

「新しい」ハッシュを計算し、その新しいハッシュにオブジェクトを格納するとします。構造内のオブジェクトをどのように検索できますか? ルックアップを行うとき、「再計算されたハッシュ」ではなく「初期」ハッシュを生成しませんか。

ルックアップを行う場合、初期ハッシュが使用されます。初期ハッシュのビットが使い果たされると、次の条件のいずれかが真になります。

  1. キー/値ノードで終了します-それを返します
  2. 最終的にはインデックス ノードになります。これは、新しいハッシュを再計算することでさらに深くする必要があるというヒントです。

ここで重要なのは、ハッシュ ビットの枯渇です。

于 2014-07-25T07:32:21.623 に答える