Sortieralgorithmen
Suchalgorithmen
Datenstrukturen
Verschiedenes
Quellen
Hashing (engl.: Zerhacken) ist ein sehr effizientes Verfahren, um Datensätze in Form von Schlüsseln auf eine Tabelle abzubilden, um die Suche danach, bzw. den Zugriff darauf zu erleichtern. Dies geschieht mittels arithmetischer Transformation, d.h. für jeden Datensatz wird explizit eine Tabellenadresse berechnet, unter der dieser dann gespeichert wird. Am besten eignen sich dafür natürliche Zahlen von 1 bis N, wobei jede Zahl N eine Adresse in der Tabelle widerspiegelt. Dabei treten jedoch diverse Probleme auf, wie in der folgenden Beschreibung ersichtlich werden wird. Um eine effiziente Suche zu gewährleisten, muß bei Hashalgorithmen ein Kompromiß zwischen Zeit- und Platzbedarf getroffen werden. Steht genügend Speicherplatz zur Verfügung, läßt sich die Anzahl der Zugriffe auf die Tabelle auf einen einzigen reduzieren. Ist hingegen der Zeitbedarf nicht von Bedeutung, kann die Größe der Tabelle minimiert werden. Ein typisches Anwendungsfeld für Hashalgorithmen sind zum Beispiel Datenbanksysteme, da sie dort eine wichtige Hilfe für den Zugriff und die Suche nach einzelnen Datensätzen darstellen. Weitere Anwendungsfelder sind Symboltabellen von Compilern, assoziative Arrays, oder Dictionaries.
Nächste Seite: Berechnung und Arbeitsweise
Aufwärts: Algorithmen
Vorherige Seite: Optimierung
Inhalt
