Gast
#1720424
Hallo, warum muss beim Hashing mit offener Adressierung die Tabellengröße eine Primzahl sein?
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.
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.