9
Wenn ich einen Schlüsselsatz von 1000 habe, was ist eine geeignete Größe für meine Hash-Tabelle, und wie ist das bestimmt?Eine geeignete Tabellengröße für einen Hash auswählen
A
Antwort
9
Es hängt von dem Ladefaktor ab (der "Prozentsatz voll" Punkt, wo die Tabelle seine Größe vergrößert und seine Elemente neu verteilt). Wenn Sie wissen, dass Sie genau 1000 Einträge haben und diese Zahl sich nie ändern wird, können Sie den Ladefaktor auf 1.0 und die Anfangsgröße auf 1000 für maximale Effizienz einstellen. Wenn Sie sich nicht sicher über die genaue Größe wären, könnten Sie den Ladefaktor auf den Standardwert von 0,75 belassen und Ihre ursprüngliche Größe auf 1334 (erwartete Größe/LF) für wirklich gute Leistung, zu einem Preis von zusätzlichem Speicher setzen.
können Sie den folgenden Konstruktor verwenden, um die Auslastung zu setzen:
Hashtable(int initialCapacity, float loadFactor)
1
3
Sie müssen auch in der Hash-Funktion berücksichtigen.
eine Faustregel schlägt vor, die Tabellengröße ungefähr doppelt zu machen, so dass es Raum zum Erweitern gibt und hoffentlich die Anzahl der Kollisionen klein bleibt. Eine andere Faustregel besagt, dass Sie eine Art von Modulo-bezogenem Hashing durchführen, dann runden Sie Ihre Tabellengröße bis zur nächstgrößeren Primzahl ab und verwenden Sie diese Primzahl als Modulo-Wert.
Welche Art von Dingen hashst du? Mehr Details sollten besseren Rat generieren.
0
Zweimal gut ist.
Sie haben kein großes Tastenset. Machen Sie sich keine Gedanken über schwierige Diskussionen über Ihre HashTable-Implementierung und gehen Sie für das Jahr 2000.
+0
2000 macht keine gute Größe, weil es nicht prim ist. 2001 wäre gut, es ist nicht Prime, aber zumindest nicht einmal. Wird die Schlüssel in der Tabelle viel besser verteilen. Eine gute Hashtable wird sich um eine gute Hash-Funktion kümmern, aber die meiste Zeit wird die Größe verwendet. – ReneS
+0
Dies ist eine interessante Frage. Ihre Aussage ist richtig, wenn Sie einen Hash-Schlüssel vom Typ verwenden: H (s) = s [0] + b * s [1] + b^2s [2] + ... [N] Ich denke, der heutige Industriestandard ist um 2^k als Größe und bessere Hash-Funktionen wie Jenkins zu verwenden. Als ich das letzte Mal nachgesehen habe, arbeitete die Std mit Prime. – fulmicoton
+0
Prime und ungerade Zahlen sind cooler;) – ReneS
1
Lassen Sie es wachsen. Bei dieser Größe ist die automatische Handhabung in Ordnung. Ansonsten ist 2 x Größe + 1 eine einfache Formel. Prime-Nummern sind auch gut, aber sobald Ihr Datensatz eine bestimmte Größe erreicht, kann die Hash-Implementierung entscheiden, die Tabelle neu zu erstellen und zu vergrößern.
Ihre Schlüssel treiben die Effektivität und sind hoffentlich deutlich genug.
Fazit: Stellen Sie die Größenfrage, wenn Sie Probleme wie Größe oder langsame Leistung haben, anders als das: Mach dir keine Sorgen!
+0
Mach dir Sorgen, wenn Performance * in diesem Bereich * zum Problem wird. Wenn Sie versuchen, damit umzugehen, werden Sie eher einen Fehler einfügen oder einfach unnötig komplexen Code haben, der ein Wartungsproblem verursachen kann. –
+0
Ich stimme zu. Haben Sie das Problem zuerst und suchen Sie danach eine Lösung. – ReneS
0
Ich möchte wiederholen, was oben https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany sagte. 1000 scheint mir kein sehr großer Hasch zu sein. Ich habe eine Menge Hashtables über diese Größe in Java verwendet, ohne viel Leistungsprobleme zu sehen. Und ich mache mich kaum mit der Größe oder dem Ladefaktor herum.
Wenn Sie einen Profiler auf Ihrem Code ausgeführt haben und festgestellt haben, dass die Hashtabelle Ihr Problem ist, dann fangen Sie unbedingt an, zu optimieren. Sonst würde ich nicht davon ausgehen, dass du ein Problem hast, bis du dir sicher bist.
Nach allem, in den meisten Code, ist das Leistungsproblem nicht, wo Sie denken, dass es ist. Ich versuche nicht zu antizipieren.
Verwandte Themen
- 1. Maximale Tabellengröße für eine MySQL-Datenbank
- 2. Eine geeignete Hash-Funktion zur Erkennung von Datenkorruption/Datenintegritätsprüfung?
- 3. Auswählen eines Multiplikators für eine (String-) Hash-Funktion
- 4. Behalten Sie eine konstante Tabellengröße bei?
- 5. SQL Anywhere 11 - Tabellengröße
- 6. SQL Azure-Tabellengröße
- 7. Der am besten geeignete Container für einen reinen Datencontainer?
- 8. Tabellengröße mit JPA-Abfragesprache
- 9. Geeignete Subjektname für ADFS Zertifikat
- 10. erhalten Tabellengröße aus dem Namen Datenbank
- 11. Richten Sie einen Hash für Ganzzahlen ein?
- 12. einen Hash von Hashes
- 13. Ist Javascript eine geeignete Plattform für die Kryptographie? Oder kann es sein?
- 14. Einen Hash von Hash in Perl filtern
- 15. Wie kann die Tabellengröße für den Datumsdatentyp reduziert werden?
- 16. Soll ich einen Redis-Hash oder einen Ruby-Hash verwenden?
- 17. MySQL-Trigger einen Hash für einen auto_increment Index
- 18. sql alle für nur eine Tabelle auswählen
- 19. Einen Hash dekodieren
- 20. geeignete Daten für Fp-Growth und Assoziationsregeln
- 21. Wie Rails Formular für eine Sammlung auswählen
- 22. Geeignete Backpropagation-Parameter
- 23. geeignete Layout-Histogramme
- 24. java.util.Stack geeignete Datenstruktur?
- 25. Gibt es eine Hash-Funktion für Datumsangaben?
- 26. Hash-Wert für eine std :: unordered_map
- 27. Eine minimale Hash-Funktion für C?
- 28. Das richtige Design für eine Website auswählen?
- 29. Wie berechnet man einen Hash für eine Zeichenfolge (URL) in Bash für wget Caching
- 30. Bestätigen Sie einen gesalzenen Hash
Angenommen, die Hash-Funktion verhält sich gut über die Menge der erwarteten Schlüssel. Eine selbstgebraute Hash-Funktion kann sich in einer minimal großen Tabelle nicht gut verhalten. Für eine selbst gebraute Funktion müssten Sie Experimente durchführen. –
Wenn die Hash-Funktion nicht korrekt ist, werden kollidierende Elemente im gleichen Bucket (in einer LinkedList) gespeichert. Die Tabelle mit der minimalen Größe hat keinerlei Auswirkungen auf die Leistung. –