Hash-Tabellen

werden zu effizienten Implementierung von Mengen und Tabellen verwendet.

ist eine Hash-Funktion auf dem Element- oder Schlüssel-Datentyp.

Eine Hash-Funktion ist eine Abbildung des Elementbereiches auf ein Intervall der natürlichen Zahlen [0 .. max-1].

Die Suche nach einem Element wird durch einen indizierten Zugriff in ein Feld realisiert.

Wenn dieses alleine zum Ziel führen würde, hätte man eine Suche in O(1), also nicht mehr abhängig von der Größe der zu durchsuchenden Menge.

Dieses Ziel kann nicht vollständig erreicht werden.
Dazu wäre eine injektive Hash-Funktion Voraussetzung.

Solche Funktionen existieren im Allgemeinen nicht, da der Elementbereich üblicherweise unbeschränkt viele Elemente enthält.

Aber es gibt sehr effizente Implementierungen,
die für einen großen Bereich von Anwendungen diese Laufzeit fast erreichen.

Die Qualität der Implementierung hängt stark von der Wahl der Hash-Funktion ab.

Die Hash-Funktion sollte alle Werte des Elementbereichs gleichmäßig auf das Intervall abbilden.

Ähnliche Elemente sollten möglichst nicht auf den gleichen Wert abgebildet werden und auch nicht einen ähnlichen Hash-Wert besitzen.

Die hier vorgestellte Implementierung ist eine sehr rudimentäre Implementierung.

Sie verwendet ein Feld fester Länge. Elemente,
deren Hash-Wert gleich dem eines schon eingetragenen Wertes sind, werden in die erste freie Stelle hinter dem Hash-Index eingetragen.

Dieses funktioniert nur dann, wenn die Anzahl der zu speichernden Elemente kleiner als die Länge des Index-Intervalls ist.

Sie funktioniert effizient nur dann, wenn die Anzahl signifikant kleiner ist, z.B. max 70% der Größe der Tabelle beträgt.

In der hier vorgestellte Lösung wird, wenn die Anzahl der Elemente steigt, eine Vergrößerung und Reorganisation der gesamten Hash-Tabelle vorgenommen.
Dadurch bleibt der effiziente Zugriff auf Elemente erhalten.

Solche Reorganisationen der gesamten Tabelle dürfen nicht zu häufig gemacht werden,
da sonst die Gesamt-Rechenzeit zu sehr steigt.

Das Löschen von Elementen in dieser einfachen Implementierung ist weder effizient noch einfach zu realisieren.
Daher sind diese Methoden nicht implementiert.

Persistente Implementierungen sind nicht sinnvoll, da keine Objekte gemeinsam genutzt werden können.
Es müsste immer die gesamte Tabelle kopiert werden.

In der Hash-Tabelle werden nicht die Elemente selbst gespeichert, sondern verkettete Listen von Schlüssel-Wert-Paaren.

Dadurch wird das Löschen einfach.
Es wird auf das Löschen in den verketteten Listen zurückgeführt.

Solange die verketteten Listen nur wenige Elemente enthalten, wird eine gute Laufzeit erreicht und es wird wenig unbenutzter Speicher im Array verschwendet.

Globale Reorganisationen sind aber immer noch notwendig, damit die Überlauf-Listen nicht zu lang werden.

Kombination einer Hash-Funktion mit einem binären Suchbaum

Anstatt mit dem Schlüssel direkt zu arbeiten, wird der Hash-Wert des Schlüssels im binären Suchbaum genutzt.
Zusätzlich wird in den Knoten des Baumes der echte Schlüssel und eine (immer kurz bleibende) Liste von Werten gespeichert.

Wenn mit einer guten Hash-Funktion und 64- oder 32-Bit Hash-Werten gearbeitet wird, gibt es nur sehr, sehr selten Kollisionen und die Wertelisten sind immer sehr kurz, fast immer mit der Länge 1.

Eine Reorganisation entfällt.

Der schlechteste Fall, Einfügen aus einer sortierten Liste, entfällt, da die Hash-Werte nicht mehr sortiert sind.

Es muss also nicht mit einem ausbalancierten Suchbaum gearbeitet werden.

Persistente Implementierungen für diese Hash-Tabellen sind wieder Speicher- und Laufzeit-effizient.

Kombination mit einem binären Patricia-Baum

Binären Patrizia-Bäume sind eine sehr effiziente Implementierung für Maps, bei denen der Schlüssel ein Int-Wert ist (32- oder 64-Bit Zahlbereich).

Die Laufzeit für Suchen und Einfügen ist dort immer in der Kompexitätsklasse O(1).

Die Kombination mit einer Hash-Funktion ermöglicht es, auch Maps mit anderen Schlüsseln, z.B. Zeichenreihen zu verwenden.

Für Kollisionen braucht wieder nur ein ganz einfaches Verfahren gewählt werden, z.B. wieder eine verkettete Liste.

Hash-Funktionen mit 64, 128 oder mehr Bits für den Hash-Wert

Bei der Verwendung einer guten 64-Bit Hash-Funktion oder einer auch einfachen kryptografischen Hash-Funktion, MD5, SHA1, ... werden Kollisionen sehr selten.

Bei kryptografischen Hash-Funktionen sind Kollisionen so selten, dass die Wahrscheinlichkeit eines Fehlers im Rechner, z.B. das Kippen eines Bits, sehr viel höher ist als eine Kollision.

Dadurch kann man so arbeiten, als sein die Hash-Funktion injektiv, Kollisionen werden einfach ignoriert.

Dieses Vorgehen wird z.B. in Versionsverwaltungssystemen, z.B. git, genutzt, um alle Versionen aller Quellen eindeutig durch Hash-Werte zu identifizieren und im Dateisystem einfach zugreifbar zu machen.

wird in der Vorlesung entwickelt