Vorteil von auf Primzahlen skalierten Hashmaps?

[idefix2]

Wenn Du nur eine Hashfunktion und keine Familie verwendest, ist die Grösse des Hash Arrays ziemlich sicher völlig egal. Primzahlen bringen da keinen Vorteil (aber auch keinen Nachteil). Die Funktion, die in Alzaimars Hashfunktion verwendet wird, verteilt Dir die Bits ohnehin recht gleichmässig über die vollen 32 Bit. Ich denke, es wäre schneller und um nichts schlechter, Hashmaps der Grösse 2 hoch n zu verwenden und die Hash Adresse einfach zu maskieren, statt modulo Primzahl zu operieren. Letzteres würfelt die Bits natürlich nocheinmal gründlich durcheinander, aber ich glaube nicht, dass das die Verteilung verbessert. Ich würde mir einmal die Verteilung der Werte an Hand von Echtdaten anschauen.

edit: Natürlich fallen beim Maskieren die höherwertigen Bits ganz weg und werden nicht berücksichtigt, aber nachdem die niederwertigen Bits bei dem Algorithmus recht gleichmässig verteilt sein sollten, wird letztlich die Verteilung auch nicht schlechter sein, als wenn man mittels Modulo ungerade Zahl (es muss keine Primzahl sein, weil jede ungerade Zahl ist teilerfremd zu 2 hoch n) alle Bits berücksichtigt. Ausserdem könnte man die höherwerigen Bits berücksichtigen, in dem man z.B. für einen 10 Bit breiten index
x and (x shr 8) and (x shr 16) and (x shr 24) and 1023
verwendet, da spielen dann alle Bits mit.