Coder Wiki | Algorithmen

In eine Hashtabelle werden Daten mit Indizes gespeichert. Über die Indizes kann man die Daten abrufen. Der Index stellt im Idealfall die genaue Position des gesuchten Elementes in der Tabelle dar. Dieser Idealfall ist nicht immer gegeben, es kann zu Kollisionen kommen.

Wegen der möglichen Kollisionen werden die Daten in Buckets gespeichert, die mehrere Datenelemente mit dem gleichen Hash-Wert aufnehmen können. Das Array selbst enthält nur noch einen Verweis auf einen Bucket, der zu diesem Hash-Wert gehört. Um das gesuchte Element zu finden, muss gegebenenfalls eine weitere Suche über die Elemente im Bucket durchgeführt werden. Ist die Hashtabelle ausgewogen, befinden sich nur wenige Datensätze in einem Bucket und der letzte Schritt hat einen geringen Aufwand.

Man kann die Hashtabelle in einem normalen Array ohne Buckets implementieren. In diesem Fall spricht man von einer offenen Adressierung.

Es gibt mehrere Varianten wie man eine offene Adressierumg implementieren kann:

Problem beim Sondieren ist, dass die Löschoperation sehr aufwendig ist. Im einfach Fall kann man den Inhalt nur als gelöscht "markieren".

Das Problem hat die Ketten-Implementierung - die jedoch mit zusätzlichem Speicher aufwarten muss.

Beim dynamischen Hashing wird vermieden, dass die Hashtabelle überläuft.