Gegeben eine ganze Zahl m, eine Hash-Funktion definiert auf T ist eine Karte T -> {0, 1, 2, ..., m - 1}. Wenn k ein Element von T ist und m eine positive ganze Zahl ist, bezeichnen wir hash(k, m) seinen Hashwert.Warum verwenden Menschen Hash (k) = c * k mit einer Primzahl c
Der Einfachheit halber haben die meisten Hash-Funktionen die Form hash(k, m) = f(k) % m, wobei f eine Zuordnung von T zum Satz von ganzen Zahlen ist.
In dem Fall, wo m = 2^p (die oft an den Modulo m Betrieb verwendet wird, ist billig) und T ist ein Satz von ganzen Zahlen, die ich unter Verwendung f(k) = c * k viele Leute gesehen, mit c eine Primzahl ist.
Ich verstehe, wenn Sie eine Funktion des Formulars f(k) = c * k wählen möchten, müssen Sie gcd(c, m) = 1 für jede Hash-Tabelle Größe m haben. Auch wenn eine Primzahl zur Rechnung passt, ist c = 1 auch gut.
Also meine Frage ist die folgende: Warum verwenden Menschen immer noch f(k) = prime * k als ihre Hash-Funktion? Was für ein schönes Anwesen hat es?
http://cs.stackexchange.com/questions/11029/why-is-it-best-to-use-a-prime-number-as-a-mod-in-a-hashing-funktion – Joe
http : //stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modul – nos
Keiner dieser Links beantwortet meine Frage. Zum Beispiel erklären sie in dem von Joe gegebenen Link, warum es eine gute Idee ist, ein Prim für 'm' zu verwenden. Ich stimme übrigens ihrem Standpunkt zu. Aber meine Frage ist anders. – InsideLoop