Hashtable erstellen

[Rossibaer]

Hallo zusammen,

ich bin gerade dabei mir eine Hashtable Klasse zu erstellen. Eins vorweg mir geht es um die Implementierung nicht darum eine vorgefertigte Klasse zu verwenden! Deswegen habe ich auch keine spezielle Sprache angegeben.

Also dank Google etc. ist es mir in der Theorie so einigermaßen klar, wie ich das ganze aufziehe. Den Rest konnte ich mir mit .Net Reflektor und dem .Net Framework "reverse enginieren". Es ist so das das .Net Framework die Größe des Container-Arrays aus Primzahlen festlegt. Meine Frage ist nun warum die ausgerechnet Primzahlen verwenden? Hat es eine besondere Bewandnis oder ist es mehr willkürlich und kann genausogut durch andere Zahlen ersetzt werden?

Meine Überlegung bisher:
Die Positionierung der Einträge in der Hashtable würde ich über "Index = Hashcode modulo Hashtablegröße" ermitteln wollen. Mir ist aber nun nicht so klar warum da im .Net Framework ausgerechnet Primzahlen verwendet wurden. Schließlich kann eine Primzahl auch ein Faktor einer anderen Zahl sein und damit wäre schon für mich nichts außergewöhnliches mehr vorhanden. Oder sorgen die Primzahlen für eine bessere Verteilung innerhalb des Containers, was bei anderen Zahlen nicht wirklich gewährleistet wäre?

Grüße
Rossibaer

 

[edeltoaster]

Donald E. Knuth: The Art of Computer Programming:

"Für die meisten Eingabedaten ist z.B. die Wahl einer Zweierpotenz für m, also m = 2^i, ungeeignet, da dies der Extraktion der i-niedrigstwertigen Bits von k entspricht, so dass alle höherwertigen Bits bei der Hash-Berechnung ignoriert werden.
Für praxisrelevante Anwendungen liefert die Wahl einer Primzahl für m, welche nicht zu nah an einer Zweierpotenz liegt, eine geringe Anzahl von zu erwartenden Kollisionen bei vielen Eingabedatenverteilungen."

Zweiterpotenzen sind also nicht mal per se schlecht.
It just depends!

 

[3murmeln]

Was edeltoaster sagen will:

Durch die Primzahl im Modulo wandert der finale Index bei mehrfachem Modulo.
Bei einer geraden Zahl als Modulo wäre es egal, wie viele Male der Hashwert überläuft. Bei einer einfachen ungeraden Zahl würde nach x mal Überlauf irgendwann wieder der gleiche Index errechnet werden. Hier ein einfaches Beispiel

Hash 20; Modulo 10; finaler Index 0
Hash 40; Modulo 10; finaler Index 0
Hash 50; Modulo 10; finaler Index 0
...

Hash 20; Modulo 15; finaler Index 5
Hash 30; Modulo 15; finaler Index 0
Hash 40; Modulo 15; finaler Index 10
Hash 50; Modulo 15; finaler Index 5

Wenn der Modulo-Wert eine sehr große Primzahl ist, wird sicher gestellt, dass bei mehrfachem Modulo der finale Index immer ein anderer ist. Die statistische Verteilung ist dann einfach besser und damit die Auslastung des Arrays gleichmäßiger.

 

[Rossibaer]

Vielen Dank euch beiden.

Am Ende lag ich mit meiner Vermutung nicht ganz soweit weg. modulo Primzahl = bessere Verteilung. Das ich hier nicht die 2 nehmen kann, ist soweit auch klar, da die Verteilung sich unabhängig von der Größe immer auf gerade oder ungerade erstreckt. Und somit nur 2 Buckets im Array verwendet werden

Wahl einer Primzahl für m, welche nicht zu nah an einer Zweierpotenz liegt, eine geringe Anzahl von zu erwartenden Kollisionen bei vielen Eingabedatenverteilungen

Guter Tipp dass ich auch nicht jede Primzahl nehmen sollte...

Also nochmal vielen Dank
Rossibaer

PS: Ich sollte mal anfangen die Bücher meines Regals genauer zu lesen und nicht nur einfach zu überfliegen. "The Art of Computing Programming" findet sich lustiger weise auch dort...

 

[badday]

Moin,

das Buch habe ich mir auch schon mal angeschaut, ist es zu empfehlen?

Ich sollte mal anfangen die Bücher meines Regals genauer zu lesen und nicht nur einfach zu überfliegen.

Jetzt wo du es sagst , die Idee ist eigentlich ganz gut, denke darüber sollte ich auch nachdenken.

Gruß,

badday

 

[edeltoaster]

das ist eine ganze reihe bücher

 

[Rossibaer]

siehe The Art of Computer Programming