Übliche Größe einer Hash-Tabelle
-
Hallo,
mich würde einmal interessieren, wie groß so eine Hashtabelle einer Hashmap ungefähr ist. Ich habe nämlich mal gelesen, dass es bei Qt eine Funktion qHash() gibt, die für verschiedene Datentypen überladen ist und einen unsigned int zurückgibt. Würde man aber ein Array von Pointern auf Values der Größe UINT_MAX anlegen, würde der RAM nicht ausreichen. Also muss es ja einen Kompromiss zwischen Größe und Geschwindigkeit geben. Wird dann der Hash-Wert einfach z.B. Modulo 1024 genommen, oder was passiert da?
mfg,
wxSkip
-
Das hängt von der Anzahl der Elemente ab und ist ist eine Abwägung zwischen Speicherverbrauch und tolerierbarer Kollisionswahrscheinlichkeit. Typischerweise passen Hashtables ihre Größe selbst an, vergleichbar dem Neuallozieren bei einem std::vector.
-
Das heißt, bei jeder Größenanpassung muss der Hashwert neu ausgerechnet werden, um dann wieder Modulo genommen zu werden? (außer natürlich, man speichert den Hashwert gleich mit dem Element ab)
-
Jupp.
Und bei einer gut gewählten Hashfunktion muss der Table nicht viel grösser sein als die Anzahl der Elemente.
Man kann auch bei den meisten Implementierungen die Table-Grösse voreinstellen, ala
vector::reserve. Dadurch kann man teure re-allocation (re-hash) Operationen vermeiden, wenn man eine Anzahl an Elementen kennt, von der man annehmen kann, dass sie kaum jemals überschritten wird. (Und es OK ist bei jeder Operation gleich von Anfang an soviel Speicher zu verwenden wie ein entsprechend grosser Table braucht.)
