Auf Multiplikation basierende Hash-Funktionen II

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]

CONST bitsperword = 32; (* size of INTEGER in bits *)
TYPE HashValue = INTEGER;
   (* [0..n-1], n = 2^m, m < bitsperword *)

PROCEDURE Hash(k: INTEGER) : HashValue;
BEGIN (* assuming big-endianness *)
   RETURN SHORT(SYSTEM.LSH(a * k, m - bitsperword))
END Hash;

*In Oberon liefert die Multiplikation von zwei 32-Bit-Zahlen nur die niedrigwertigen 32 Bits.
 
*Die Operation LSH (logical shift) aus dem Modul SYSTEM verschiebt die Bits des 1. Parameters um die im 2. Parameter angegebene Anzahl. Da m - bitsperword negativ ist, wird nach rechts geschoben.
 
*Die links nachkommenden Bits werden dabei alle auf 0 gesetzt.
 
*Entsprechend ergeben sich anschließend die m niedrigwertigen Bits aus der Multiplikation, und die verbleibenden Bits sind 0.
 
*Das Resultat liegt somit im Intervall [0, 2m-1].
 
*So funktioniert es auf ``big endian''-Maschinen, bei denen die höherwertigen Bits weiter links stehen. Auf ``little endian''-Maschinen müßte stattdessen bitsperword - m angegeben werden.
 

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999