Hashs und Dictionaries

Hashs

Dictionaries

Problem
Es ist zu prüfen, ob der Wort (Klartext) in einem Dictionary vorhanden ist.

Normale Herangehensweise
Hashe jeden Eintrag im Dictionary und vergleiche den entstandenen Hash mit dem Original.

Nach dieser Methode müssen:

Ideen zur Optimierung
Man erstellt einmal eine Hashtable, die den Hash und eine Referenz auf dessen Klartext beinhaltet:

Dictionary

Index Word
0 Hallo
1 Welt

HashTable I

Hash Reference Dictionary
**************** 0
**************** 1

Vorteil
Man braucht das Dictionary nur einmal zu hashen. Hashs lassen sich außerdem einfacher als Texte sortieren und somit einfacher durchsuchen, zum Beispiel per binärer Suche. Jetzt ist die Zeit beim Erzeugen der Hashs verringert (nahezu gleich 0), die Zeit der Suche ebenfalls. Es fehlt noch der Vergleich.

Um den Vergleich zu optimieren, versucht man die Anzahl der zu vergleichenden Bytes auf 4 (4 Byte = 32 Bit = Registergröße der heutigen Prozessoren) zu minimieren.
Dazu erstellt man einen weitere Hashtable bestehend aus einfachen Hashs aus der HT(HashTable) I.

HashTable II

Hash Reference HT I
**** 0, 5, 16
**** 1, 3 ,7

Diese Hashs sind mit hoher Wahrscheinlichkeit nicht mehr eindeutig, was zur Folge hat, dass man nach Finden des Hash in HT II nur noch eine stark eingeschrenkte Anzahl von Hashes aus HT I überprüfen muss.

Ein weiterer Vorteil ist, dass das Fehlen eines Wortes schon nach Durchgang von HT II fest steht.