Implementieren Sie eine Hashtabelle der Größe 67 für Hashing mit linearem Sondieren. Verwenden Sie für die
Tabelle die folgende Hashfunktion für einen String der Länge n > 1:
h(sn) = (((h(sn-1) << 8) + sn) mod k) mit k = 67, h(s0) = s0
Dabei sei sn der ASCII-Code1 des n-ten Zeichens eines Wortes. Das erste Zeichen eines Wortes ist mit s0 bezeichnet.
Mit << lassen sich bitweise Verschiebungen nach links ermöglichen. D.h. die Eingabe wird um die
angegebene Anzahl an Bits in Richtung des höchstwertigen Bits verschoben und mit Nullen aufgefüllt. (4 Punkte)
Beispiel für die bitweise Verschiebung: 10001101 << 4 = 11010000
Beispiel zur Anwendung der Hashfunktion anhand des Strings "abc":
h(’c’) = (h(’b’) << 8) + ’c’) mod 67 = (((((h(’a’) << 8) + ’b’) mod 67) << 8) + ’c’) mod 67
= (((((’a’ << 8) + ’b’) mod 67) << 8) + ’c’) mod 67
= ((((97 << 8) + 98) mod 67) << 8) + 99) mod 67
= 27
Tabelle die folgende Hashfunktion für einen String der Länge n > 1:
h(sn) = (((h(sn-1) << 8) + sn) mod k) mit k = 67, h(s0) = s0
Dabei sei sn der ASCII-Code1 des n-ten Zeichens eines Wortes. Das erste Zeichen eines Wortes ist mit s0 bezeichnet.
Mit << lassen sich bitweise Verschiebungen nach links ermöglichen. D.h. die Eingabe wird um die
angegebene Anzahl an Bits in Richtung des höchstwertigen Bits verschoben und mit Nullen aufgefüllt. (4 Punkte)
Beispiel für die bitweise Verschiebung: 10001101 << 4 = 11010000
Beispiel zur Anwendung der Hashfunktion anhand des Strings "abc":
h(’c’) = (h(’b’) << 8) + ’c’) mod 67 = (((((h(’a’) << 8) + ’b’) mod 67) << 8) + ’c’) mod 67
= (((((’a’ << 8) + ’b’) mod 67) << 8) + ’c’) mod 67
= ((((97 << 8) + 98) mod 67) << 8) + 99) mod 67
= 27
