Hashing mit offener Adressierung

[ahnungsloser (Gast)]

Hallo,

warum muss beim Hashing mit offener Adressierung die Tabellengröße eine 
Primzahl sein?

[Klaus W. (mfgkw)]

Das muß sie nicht unbedingt sein, aber es reduziert etwas
Kollisionen (oft) und verbessert damit etwas die Effizienz.

Je nach Berechnung der Positionen im Einzelfall kann es vorkommen,
daß bestimmte Teiler gehäuft vorkommen, also z.B. jeder zweite, oder
jeder dritte oder jeder soundsovielte.
Oft auch kombiniert, z.B. könnte die Wahrscheinlichkeit
sowohl für Vielfache von 2 als auch 7 etwas höher sein als andere
Werte. Hat in einem solchen Fall meine Tabelle eine Länge eines
Vielfachen von 14, sind einige Stellen überfüllt, während andere
leer laufen. Das ist natürlich ungünstig.
Mit einer Tabellenlänge, die eine Primzahl ist, werden solche
Schlüssel besser verteilt.

Hat man eine ideale Schlüsselberechnung, ist die genaue
Tabellenlänge egal; auch eine nicht-Primzahl wäre ok.
Das weiß man aber oft nicht so genau, und eine Primzahl schadet
auch nicht und hilft halt oft etwas; deshalb nimmt man sie.

[(prx) A. K. (prx)]

Wobei das eine Abwägung sein kann. Mit Primzahl hat man eine Division an 
der Backe, andernfalls vielleicht nicht. Jetzt kommt es drauf an, was 
teurer ist: die Kollisionen oder die Divisionen. 
Datenstruktur-Theoretiker sind da gnadenlos, für sind alle skalaren 
Operation gleich teuer.