7
Ich kenne das Grundprinzip der Hash-Tabelle Datenstruktur. Wenn ich eine Hash-Tabelle der Größe N habe, muss ich meine Daten so gleichmäßig wie möglich in diese N Buckets verteilen.Wie implementiert man eine Hash-Tabelle mit dynamischer Größe?
Aber in Wirklichkeit haben die meisten Sprachen ihre eingebauten Hash-Tabellentypen. Wenn ich sie verwende, muss ich die Größe der Hashtabelle nicht vorher wissen. Ich lege einfach alles hinein, was ich will. Zum Beispiel in Ruby:
h = {}
10000000.times{ |i| h[i]=rand(10000) }
Wie kann es das tun?
Ein schöner Vorgang ist die Größe der Tabelle zu verdoppeln, und wenn Sie nach einem Wert suchen, hashen Sie seinen Schlüssel und führen eine modulu Suche in Ihrer Hashtabelle aus, beginnend mit 'hash% current_size', dann' hash % current_size/2' usw. Wenn Sie den Wert gefunden haben, können Sie ihn erneut ausführen. Auf diese Weise können Sie faules Re-Hashing durchführen, ohne zu viel Leistung zu verlieren, da häufig abgerufene Werte automatisch regeneriert werden. –
@DvirVolk, faul rehash ist nett. Sie kennen den Eintrag in der obersten Hash-Tabelle bereits und wissen, wo Sie aus niedrigeren Hash-Tabellen einfügen können. Aber Sie könnten Situation haben, wenn ein Eintrag die ganze Tabelle leerer Eimer enthält. Diese "incremental resizing" von wiki ist eine Lösung der tradoff Geschwindigkeit für die Größe der Daten, wie ich es verstehe (schließlich halten Sie 2 * N Buckets, wobei N die Größe der obersten Hashtabelle ist). Die Verdoppelung der Größe ist gut für das "Kopieren aller Einträge" durch die Tatsache, dass Sie einzelne Buckets in zwei teilen oder zwei in eins zusammenführen müssen (ohne Hash-Neuberechnung), indem Sie verknüpfte Listen alter Buckets wiederverwenden. – ony