Hashtabellen finden sehr oft ihren Weg in Anwendungen, bei denen es wichtig ist, bei einer relativ konstanten Laufzeit, Datensätze mit Hilfe eines Schlüssels zu finden.
Beispiel (Quellcode): hashtable.cpp
Download (Quellcode): hashtable.zip
Beschreibung
Die Funktion einer Hashtabelle ist sehr einfach. Die Schlüsselwerte werden mit einer Konvertierungsfunktion (Hashfunktion) in einen Wert gewandelt, der direkt als Index für ein Datenfeld benutzt wird. Durch die Verringerung des Schlüssels auf einen kleineren Wertebereich, kann es zu Kollisionen kommen. Das heißt auch, dass die Werte keine eindeutige Referenz für den Schlüssel sind. Somit muss, in der Designphase des Endproduktes, schon drauf geachtet werden, wie mit Kollisionen umgegangen werden soll. Da gibt es gleich einen ganzen Schwung an Möglichkeiten:
Ignorieren. Je nach Bedarf der Anwendung, kann der neue Schlüssel wichtiger sein als ein Älterer, z.B. oft bei Kompressionssuchbäumen oder statistischen Daten.
Datenfeld erweitern. Um die Kollisionen…