Hallo,
kennt jemand den Unterschied zwischen einem Hash Table und einem Look Up Table? Bei beiden verwendet man doch einen Schlüssel, um auf vorberechnete Daten zuzugreifen oder gibt es keinen Unterschied?
Gruß Patrick
Hi Patrick 
Bei einer Hash-Tabelle berechnet man aus einem zu speichernden Objekt seine Position innerhalb eines Feldes. Angenommen, du möchtest schnell auf Wörter zugreifen und diese in einer Liste mit 200 Elementen ablegen. Dann könntest du die Wörter natürlich in die Liste einfügen, sortieren, und mittels binärer Suche wiederfinden. Schneller geht es jedoch mittels Hashing. Aus den einzelnen Buchstaben string[i] berechnest du über eine Hash-Funktion die Hash-Adresse h für einen String. Eine sehr gute Hash-Funktion ist z.B.
h= 0;
for (i=0; i
Jetzt wird der String an Position h in der Liste abgelegt! Das ist Hashing. Ein Problem beim Hashing ist die Handhabung von Kollisionen, wenn also 2 Strings die selbe Hash-Adresse erhalten. Dieses Problem kann man durch die Wahl von sehr guten Hash-Funktionen minimieren. Die oben angegebene 65599-Funktion ist sehr gut, sie arbeitet hervorragend, wenn die Größe deiner Liste nicht 200, sondern eine Primzahl ist!
Ein LUT (Look-Up-Table) ist im Prinzip eine Relation. Du rechnest damit die Symbole x einer Menge X in Symbole y der Menge Y um. Ein Beispiel:
int LUT[]= { 1, 4, 9, 16, 25, 36, ... };
Offensichtlich erhälst du jetzt mit LUT[i] das Quadrat von i. Ein LUT kann auch dazu eingesetzt werden, um sich Speicherpositionen innerhalb einer Liste zu merken.
Der entscheidende Unterschied zwischen HASH und LUT ist aber eigentlich, dass ein HASH eine große Menge auf eine kleine abbildet, wohingegen ein LUT eine Menge auf eine genauso große Menge abbildet.
Ich hoffe, das war jetzt nicht zu theoretisch :smile:
cu Stefan.