java deutsch Hash Array Mapped Tries(HAMT)




trie java (3)

Wenn ich einen "neuen" Hash berechnen und das Objekt bei diesem neuen Hash speichern würde; Wie könnten Sie jemals das Objekt in der Struktur nachschlagen? Wenn Sie nachschlagen, würde es nicht den "anfänglichen" Hash und nicht den "neu berechneten Hash" erzeugen.

Bei einer Suche wird der ursprüngliche Hash verwendet. Wenn die Bits im anfänglichen Hashwert erschöpft sind, ist eine der folgenden Bedingungen erfüllt:

  1. Wir enden mit einem Schlüssel / Wert-Knoten - zurückgeben
  2. wir enden mit einem Index-Knoten - das ist der Hinweis, dass wir tiefer gehen müssen, indem wir einen neuen Hash neu berechnen.

Der Schlüssel hier ist die Erschöpfung der Hash-Bits.

https://code.i-harness.com

Ich versuche, die Details eines HAMT . Ich hätte es selbst in Java implementiert, nur um es zu verstehen. Ich bin vertraut mit Tries und ich denke, ich bekomme das Hauptkonzept des HAMT.

Grundsätzlich gilt,

Zwei Arten von Knoten:

Schlüsselwert

Key Value Node:
  K key
  V value

Index

Index Node:
  int bitmap (32 bits)
  Node[] table (max length of 32)
  1. Generieren Sie einen 32-Bit-Hash für ein Objekt.
  2. Schritt für Schritt durch den Hash-Wert von 5 Bits. (0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31) Hinweis: Der letzte Schritt (7.) ist nur 2 Bits.
  3. Suchen Sie bei jedem Schritt die Position dieser 5-Bit-Ganzzahl in der Bitmap. zB integer==5 bitmap==00001
    1. Wenn das Bit eine 1 ist, existiert dieser Teil des Hashs.
    2. Wenn das Bit eine 0 ist, dann existiert der Schlüssel nicht.
  4. Wenn der Schlüssel vorhanden ist, finden Sie den Index in der Tabelle, indem Sie die Anzahl der 1-Zeichen in der Bitmap zwischen 0 und der Position zählen. zB integer==6 bitmap==0101010101 index==3
    1. Wenn die Tabelle auf einen Schlüssel / Wert-Knoten zeigt, vergleichen Sie die Schlüssel.
    2. Wenn die Tabelle auf einen Indexknoten zeigt, gehen Sie zu Schritt 2 und gehen einen Schritt weiter.

Der Teil, den ich nicht ganz verstehe, ist Kollisionserkennung und -minderung. In dem verlinkten Papier spielt er darauf an:

Der vorhandene Schlüssel wird dann in die neue Unter-Hash-Tabelle eingefügt und der neue Schlüssel hinzugefügt. Jedes Mal, wenn 5 weitere Bits des Hashs verwendet werden, verringert sich die Wahrscheinlichkeit einer Kollision um einen Faktor von 1/32. Gelegentlich kann ein gesamter 32-Bit-Hash-Wert verbraucht werden, und ein neuer Wert muss berechnet werden, um die zwei Schlüssel zu unterscheiden.

Wenn ich einen "neuen" Hash berechnen und das Objekt bei diesem neuen Hash speichern würde; Wie könnten Sie jemals das Objekt in der Struktur nachschlagen? Wenn Sie nachschlagen, würde es nicht den "anfänglichen" Hash und nicht den "neu berechneten Hash" erzeugen.

Ich muss etwas verpassen .....

BTW: Der HAMT funktioniert ziemlich gut, er sitzt in meinen Tests zwischen einer Hash-Karte und einer Baumkarte.

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     

Die Wahrscheinlichkeit einer Kollision ist vermutlich sehr gering und im Allgemeinen nur für große Bäume problematisch. In Anbetracht dessen ist es besser, nur Kollisionen in einem Array am Blatt zu speichern und es linear zu durchsuchen ( ich mache das in meinem C # HAMT ).


HAMT ist eine großartige und hoch performante Struktur, besonders wenn man unveränderliche Objekte benötigt, dh jedes Mal nach jeder Änderung wird eine neue Kopie einer Datenstruktur erstellt!

Was Ihre Frage zu Hash-Kollisionen anbelangt, habe ich eine C # -Implementierungsimplementierung gefunden (die jetzt fehlerhaft ist), die zeigt, wie sie funktioniert: Bei jeder Hash-Kollision wird der Schlüssel aufgefrischt und die Suche wird rekursiv wiederholt, bis die maximale Iterationsgrenze erreicht ist.

Zurzeit erforsche ich auch HAMP im funktionalen Programmierkontext und lerne bestehenden Code. Es gibt mehrere Referenzimplementierungen von HAMT in Haskell als Data.HshMap und in Clojure als PersistenceHashMap .

Es gibt einige andere einfachere Implementierungen im Internet, die sich nicht mit Kollisionen befassen, aber sie sind nützlich, um das Konzept zu verstehen. Hier sind sie in Haskell und OCaml

Ich habe einen schönen zusammenfassenden Artikel gefunden , der HAMT mit Bildern und Links zu Originalarbeiten von Phil Bagwell beschreibt.

Verwandte Punkte:

Bei der Implementierung von HAMT in F # habe ich festgestellt, dass die here beschriebene Implementierung der popCount-Funktion wirklich wichtig ist und 10-15% im Vergleich zur naiven Implementierung liefert, die in den nächsten Antworten im Link beschrieben wird. Nicht großartig, aber ein kostenloses Mittagessen.

Verwandte InMap-Strukturen ( Haskell und sein Port zu F # ) sind sehr gut, wenn der Schlüssel eine Ganzzahl sein kann und sie verwandte PATRICIA/Radix trie implementieren.

Ich glaube, dass alle diese Implementierungen sehr gut sind, um effiziente unveränderliche Datenstruktur und funktionale Sprachen in all ihrer Schönheit an diesen Beispielen zu lernen - sie scheinen wirklich zusammen!





trie