Hashing und Falten
Hashing
Eine Hashfunktion berechnet aus einem Schlüssel einen Index, damit der Schlüssel wieder mit O(1) gefunden werden kann.
Nach Gray/Reuter kann man die Hash-Funktion in zwei Etappen berechnen:
- Zusammenfalten des Schlüssels in ein Long Integer durch sog. Falten
- Auf diese Zahl wird dann eine weitere Hashfunktion angewandt
Wir experimentieren hier mit zwei Faltungsmethoden und zwei Hashfunktionen.
8bit Falten
Ein Schlüssel, der nun aus alphanumerischen Zeichen besteht, die in 8 Bits
dargestellt werden, können in 4er Gruppen zusammengefasst werden, dann passen sie in einen 32 bit long-Integer.
Diese so entstehenden Integer werden dann mit der xor-Funktion zu einem Long
zusammengezählt. (xor macht eine Addition modulo 2 auf jeder Bitstelle).
Damit wird sozusagen das Informationspotenial des Schlüssels komprimiert, und es bleibt eine möglichst große Entropie übrig.
6bit
Die meiste Information in alphanumerischen Schlüsseln steckt in den Buchstaben
a-z. Die andere Information vernichten wir wie folgt:
- Großbuchstaben kommen selten vor, und dienen zur besseren Menschenlesbarkeit. Daher wandeln wir diese in Kleinbuchstaben um.
- Sonstige Buchstaben (Umlaute und Ziffern), sollen auch nur ganz selten
vorkommen.
Die 26 Buchstaben von a-z passen schön in 5 bits. Dann haben wir noch
einige Zahlen frei. Diese Packen wir noch die im sonstigen und die Ziffern,
in dem wir die letzen 3 bits auf 27 noch zuzählen.
So packen wir den long nun mit 6 dieser zu 5bit komprimierten Buchstaben
und hoffen, daß durch das Falten insgesamt noch mehr Information erhalten bleibt. Letzters wollen wir empirisch nachprüfen.
Hashing
Nun komprimieren wir den durch Faltung erhaltenen long noch mehr.
Wir machen dies mit zwei Methoden:
- Modulo 2 er-Potenz
- Wir betrachten nur die hinteren Bits des Long
- Faltung
- Unterteilen den Long in bitgruppen, die wir mit xor zusammenzählen
Literatur und Links
- [GR93]
- Gray,Reuter: "Transaction Processing: Concepts and Techniques", Morgan Kaufmann 1993
Rudolf Weber Informatik- und Netzwerkverein Ravensburg e.V.