Uppdelnings resten metod

Den kvarvarande division metod (se även modulo ) tillhandahåller en hashfunktion .

Funktionen är: ${\ displaystyle h (k) = k {\ bmod {m}}}$

${\ displaystyle m}$ är storleken på hashtabellen.

egenskaper

1. Hashfunktionen kan beräknas mycket snabbt
2. Valet av tabellstorlek påverkar kollisionssannolikheten för funktionsvärdena för .${\ displaystyle m}$${\ displaystyle h}$

För de flesta ingångsdata är till exempel valet av en effekt på två för , det vill säga, olämpligt, eftersom detta motsvarar extraktion av de minst signifikanta bitarna av , så att alla de mer betydande bitarna ignoreras i hashberäkningen. ${\ displaystyle m}$${\ displaystyle m = 2 ^ {i}}$${\ displaystyle i}$${\ displaystyle k}$

För praktiska tillämpningar, valet av ett primtal för vilket inte är en mersenneprimtal ger ett lågt antal kollisioner kan förväntas med många indata distributioner.${\ displaystyle m}$

Hashing av strängar

Strängar kan hasas med delningsmetoden genom att konvertera dem till heltal vid basen , där teckenuppsättningens storlek anger. ${\ displaystyle b}$${\ displaystyle b}$

För att undvika överflöd av heltal kan Horner-schemat användas för att beräkna hashvärdet för nycklar . Följande exempel visar beräkningen av ett hash-värde för en 7-bitars ASCII- teckensträng . ${\ displaystyle s}$

${\ displaystyle k {\ bmod {m}} = (\ ldots (s_ {1} \ cdot 128 + s_ {2}) {\ bmod {m}}) \ cdot 128 + s_ {3}) {\ bmod { m}}) \ cdot 128+ \ ldots + s_ {l-1}) {\ bmod {m}}) \ cdot 128 + s_ {l}) {\ bmod {m}}}$

Detta innebär att maximalt möjligt mellanresultat kan uppstå. ${\ displaystyle \ left (m-1 \ right) \ cdot 128 + 127}$

Visas i pseudokod :

Parameter: natürliche Zahlen i, h=0; Feld s
 for i = 0 to i < länge_von(s)
	h = (h * 128 + s[i]) mod m;
Ergebnis: h.

Multiplikationen med 128 = 2^7motsvarar den vänstra bitförskjutningsoperationen << 7 .

litteratur

• Donald E. Knuth : Konsten att datorprogrammering . Volym 3: Sortering och sökning. 2: a upplagan. Addison-Wesley, Upper Saddle River NJ bland annat 1998, ISBN 0-201-89685-0 , s.515.

Individuella bevis

1. ↑ Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Introduktion till algoritmer . 2: a upplagan. MIT Press bland annat, Cambridge MA bland annat 2001, ISBN 0-262-03293-7 , s. 231 .