Hallo,
es geht um Hashing, und zwar mit der Modulo-Funktion.
fast alle Bücher oder Beispiele aus dem Internet nehmen die Primzahlen her. Also die Funktion ist z.B. mod(13). Aber mir ist nicht klar warum es fast ausschliesslich Primzahlen sind. Es würde doch auch mit mod(10) funktionieren.
Kennt sich da jemand auf dem Gebiet aus?
Gruss
Maria
Mahlzeit!
es geht um Hashing, und zwar mit der Modulo-Funktion.
fast alle Bücher oder Beispiele aus dem Internet nehmen die
Primzahlen her.
Aber nur welche die möglichst weit von 2 entfernt sind.
Also die Funktion ist z.B. mod(13). Aber mir
ist nicht klar warum es fast ausschliesslich Primzahlen sind.
Es würde doch auch mit mod(10) funktionieren.
Na klar, nur stell dir ein Dezimales System vor. Die Rechenvorschrift
wäre lediglich ein wegstreichen der letzten Stelle. Diese Stelle
würde also gar nicht zur Hashbildung genutzt.
Aus dem gleichen Grund nimmt man keine Zweierpotenzen, da dies auch
nur ein wegstreichen der niederwertigen Bits entspricht.
Beste Ergebnisse liefern dann halt Primzahlen, da in der Regel
niemand ein System zu einer Primzahl nutzt.
Gruß
Stefan
Hallo,
der Hauptgrund ist, dass der Hashwert von der kompletten Eingabe abhängen soll, weil man hofft, dass so eher eine gleichförmige Verteilung erreicht wird, wenn man über die Menge der Eingabewerte wenig weiß. Wenn du z. B. Geldbeträge in eine Hashfunktion hineinsteckst, und in der Währung des Landes gibt es als kleinste Münze 5 (Lire o. ä.), dann würden mit Modulo 10 nur die Werte 5 und 0 je erreicht. Dieses Problem stellt sich immer, wenn es einen größten gemeinsamen Teiler > 1 zwischen deinem gewählten Modul und den Eingabewerten gibt; der ist bei Primzahlen definitionsgemäß die Primzahl selbst und somit das Optimum.
Wenn die Eingabewerte endlich und bekannt sind (z. B. Schlüsselwörter einer Programmiersprache) , kann es deutlich schneller zu berechnende Funktionen als Modulo geben, z. B. Quersumme der ASCII-Werte, die sogar eineindeutig sind.
cu
1 Like
Hi Maria,
(oder alle andren, die sich das im nachhinein nochmal ergooglen 
)
dass man in der hashfunktion primzahlen verwendet liegt daran, dass man modulo der tabellenlänge rechnet und diese meist eine prime länge haben.
Dies kommt daher, da man beim einfügen in eine hashtabelle beim hashing unter umständen eine kollisionsstrategie bereitstellen muss, sollte das zielfeld bereits belegt sein.
optimalerweise checkt so eine strategie in ihrem verlauf alle felder höchstens einmal, da man sonst einen zyklus erreichen könnte.
und gerade für primzahlen existiert eine kollisionsstrategie, die nachweislich kein feld doppelt besucht aber alle abdeckt im worst case (alles bis auf eins belegt)
diese strategie nennt sich alternierende quadratische sondierung und kann bei interesse auf wikipedia nachgelesen werden.
MfG
Thomas