Hashfunktion nach Mulitplikationsmethode für einen Schlüssel k und Tabelle mit m Slots Funktion
Ablauf
- Wähle Konstante A im Bereich ⇒ Alles zwischen 0 und 1
- Multipliziere Schlüssel k mit A
- Extrahiere den gebrochenen Teil von k*A ⇒ Also mod 1
- Multipliziere dies mit m
- Runde Wert ab (bei Python mit int)
Beispiel k = 21 m = 8 A = 0,618
210,618 = 13,978 0,9788 = 7,824 int(7,824) = 7 h(21) = 7
Wie wählt man ?
A = (√5 – 1) / 2 ≈ 0.6180339… → Knuths recommendation/goldener Schnitt ⇒ weil (√5–1)/2 ’ne irrationale Zahl ist und laut Equidistribution-Theorem sind die fractional parts von k·A dann gleichmäßig auf verteilt
- Irrationalität heißt: k·A kann nie zyklisch werden → keine periodischen Muster
Vorteil
Wert von m spielt keine kritische Rolle. (Oft als Potenz von 2 gewählt)
Nachteil
langsamer als Divisionsmethode