java python - Hash Array Mapped Tries(HAMT)



deutsch (5)

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!

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     

Es gibt zwei Abschnitte des Papiers, von denen ich denke, dass Sie sie vermisst haben. Der erste ist das Bit, das dem von Ihnen angegebenen Bit unmittelbar vorausgeht:

Oder der Schlüssel kollidiert mit einem vorhandenen. In diesem Fall muss der vorhandene Schlüssel durch eine Unter-Hash-Tabelle ersetzt und der nächste 5-Bit-Hash des vorhandenen Schlüssels berechnet werden. Wenn es immer noch eine Kollision gibt, wird dieser Prozess wiederholt, bis keine Kollision auftritt.

Wenn Sie also Objekt A in der Tabelle haben und Objekt B hinzufügen, das kollidiert, wird die Zelle, in der ihre Schlüssel kollidieren, ein Zeiger auf eine andere Untertabelle sein (wo sie nicht kollidieren).

Als nächstes beschreibt Abschnitt 3.7 des Papiers, das Sie verlinkt haben, die Methode zum Erzeugen eines neuen Hashs, wenn Sie das Ende Ihrer ersten 32 Bits ablaufen lassen:

Die Hash-Funktion wurde auf einen 32-Bit-Hash zugeschnitten. Der Algorithmus erfordert, dass der Hash auf eine beliebige Anzahl von Bits erweitert werden kann. Dies wurde erreicht, indem der Schlüssel erneut kombiniert wurde mit einer Ganzzahl, die die Trie-Stufe repräsentiert, wobei Null die Wurzel ist. Wenn also zwei Schlüssel den gleichen Anfangs-Hashwert ergeben, hat der erneute Hash eine Wahrscheinlichkeit von 1 zu 2 ^ 32 für eine weitere Kollision.

Wenn dies nichts zu erklären scheint, sage ich und ich werde diese Antwort ausführlicher erläutern.


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.


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 ).


Keine Notwendigkeit, es zu kompliziert zu machen. DigestUtils funktioniert gut und macht Sie bequem während der Arbeit mit MD5-Hashes.

DigestUtils.md5Hex(_hash);

oder

DigestUtils.md5(_hash);

Entweder können Sie andere Verschlüsselungsmethoden wie sha oder md verwenden.





java algorithm data-structures hash trie