Beste Weg, um die Größe einer hash-Tabelle
Ich bin meine eigene Implementierung hash eine Tabelle für die Bildung verwendet.
Was wäre der beste Weg, um zu erhöhen wird eine hash-Tabelle der Größe?
Ich derzeit die doppelte hash-array-Größe.
Den Hash-Funktion, die ich verwende, ist: Taste mod arraysize.
Das problem mit diesem ist, dass, wenn die Schlüssel: 2, 4, 6, 8, dann die array-Größe wird nur weiter zunehmen.
Was ist der beste Weg zur überwindung dieses Problems? Gibt es eine bessere Möglichkeit der Erhöhung einer hash-Tabelle der Größe? Würde die änderung meiner Hash-Funktion helfen?
HINWEIS: Meine keys sind alle ganzen zahlen!
- Schreiben Sie Ihre eigene Implementierung? Warum? Der beste Weg ist noch nie Größenänderung.
- Ja. Und manchmal Größenänderung erforderlich ist, weil Sie nicht wissen, wie viele Elemente Hinzugefügt werden. Ich mache meine eigene Implementierung, da es für meine CS Kurs in der Universität.
- Es gibt keine "beste" Möglichkeit. Es wird immer ein Kompromiss sein.
- (Aber wie schon andere gesagt haben, Sie brauchen, um richtig zu hash-Ihr Schlüssel.)
- Suche nach einem Weg/Umsetzung die nie brauchen, um die Größe (Kopie) der zugrunde liegenden array - (s)/Struktur(s) ist der beste Weg. Wenn man entwirft einen Weg, um zu wachsen die zugrunde liegende Struktur ohne die Notwendigkeit, Daten kopieren, dann die neue Karte wird sein, in der Nähe von perfekten Daten-storage-Lösung
- Aber in der Regel Weise zu minimieren, dass das kopieren weniger effizient für die Suche.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Hash-Tabellen oft umgehen dieses problem, indem sichergestellt wird, dass die hash-Tabellengröße eine Primzahl ist. Wenn Sie die Größe der Tabelle ändern, doppelklicken Sie die Größe und dann die Runde bis zu der ersten Primzahl, die größer als, die. Tut dies vermeidet die clustering-Probleme ähnlich, was Sie beschreiben.
Nun, es dauert ein wenig Zeit, um die nächste Primzahl, aber nicht eine ganze Menge. Im Vergleich zum Zeitaufwand bei der Aufbereitung der hash-Tabelle der Inhalt, Suche die nächste Primzahl, nimmt fast keine Zeit überhaupt. Sehen Die Optimierung der falschen Sache für eine Beschreibung.
Wenn Sie versuchen, zu implementieren Ihre eigenen hash-Tabelle, hier einige Tipps:
mod
für die hash-Funktion.Quadratic Probing
finden der endgültigen position für Kollisionenh(x,i) = (Hash(x) + i*i) mod TableSize
für diei
th Kollision.Hier ist eine elegante Umsetzung für
Quadratic Probing
:OpenJDK verwendet Potenzen von 2 für die Kapazität einer HashMap, die dazu führen, um eine Menge von Kollisionen, wenn die keys sind alle vielfachen einer Potenz von zwei. Es verhindert, dass diese durch aufbringen einer weiteren hash-Funktion auf der Oberseite des Schlüssels hashCode:
Hashing und hash-Funktionen sind ein Komplexes Thema, glücklicherweise mit vielen online-Ressourcen.
Es ist nicht klar, wie bestimmen Sie die array-Größe in den ersten Platz.
In der Java -
HashMap
Umsetzung, die Größe des zugrunde liegenden array ist immer eine Potenz von 2 ist. Dies hat den leichten Vorteil, dass Sie nicht brauchen, um zu berechnen, modulo, kann aber die Berechnung der array-index alsindex = hashValue & (array.length-1)
(das entspricht einer modulo-operation, wennarray.length
ist eine Potenz von 2 ist).Darüber hinaus die
HashMap
verwendet einige "magic-Funktion" zu reduzieren, die Anzahl von hash-Kollisionen für den Fall, dass mehrere hash-Werte unterscheiden sich nur durch einen Konstanten Faktor, wie in deinem Beispiel.Die tatsächliche Größe des Arrays wird dann bestimmt durch eine "load-Faktors". (Sie können sogar angeben, das als Konstruktor-parameter von
HashMap
). Wenn die Anzahl der array-Einträge, die besetzt sind übersteigtloadFactor * array.length
, dann die Länge des Arrays verdoppelt wird.Diese Auslastung kann einen bestimmten trade-off: Wenn die Auslastung hoch ist (0.9 oder so), dann wird es wahrscheinlicher sein, dass hash-Kollisionen auftreten. Wenn es gering ist (0,3 oder so), dann hash-Kollisionen eher unwahrscheinlich, aber es gibt eine Menge von "verschwendetem" Speicherplatz, weil nur wenige Einträge des Arrays tatsächlich besetzt werden, an jedem Punkt der Zeit.