Was ist eine Hashtabelle?
In der Informatik ist eine Hash-Tabelle eine Datenstruktur zum Speichern von Daten, die aus einer Liste von Werten besteht, die als Schlüssel bezeichnet werden und mit einer entsprechenden Liste von Werten, die als Array bezeichnet wird, gepaart werden. Beispielsweise kann ein Firmenname mit seiner Adresse verknüpft werden. Typischerweise hat jeder Wert im Array eine Positionsnummer, die als Hash bezeichnet wird. Die Hash-Funktion ist im Allgemeinen eine Reihe von Anweisungen oder ein Algorithmus, der jeden Schlüsselwert einem Hash zuordnet. So wird beispielsweise der Unternehmensname mit seiner Adresse, seiner Telefonnummer und seiner Unternehmenskategorie verbunden. Der Zweck der Hash-Funktion besteht darin, jedem Schlüssel einen eindeutigen entsprechenden Wert im Array zuzuweisen. Dies wird allgemein als Hashing bezeichnet. Hash-Funktionen müssen ordnungsgemäß formatiert sein, damit eine Hash-Tabelle ordnungsgemäß funktioniert.
Die Leistung einer Hash-Tabelle für einen Datensatz hängt von der Effizienz ihrer Hash-Funktion ab. Eine gute Hash-Funktion sorgt normalerweise für eine einheitliche Suche nach Schlüsseln und eine gleichmäßige Verteilung der Zuordnungen im entsprechenden Array. Eine Hash-Kollision tritt auf, wenn zwei Schlüssel demselben entsprechenden Wert zugewiesen werden. Wenn eine Hash-Kollision auftritt, wird die Hash-Funktion normalerweise erneut ausgeführt, bis ein eindeutiger entsprechender Wert gefunden wird. Dies führt normalerweise zu längeren Hashing-Zeiten. Obwohl die Anzahl der Schlüssel in einer Hash-Tabelle in der Regel festgelegt ist, kann es vorkommen, dass doppelte Schlüssel vorhanden sind. Trotzdem verfügt eine gut gestaltete Hash-Tabelle über effektive Hash-Funktionen, die jeden Schlüssel einem eindeutigen entsprechenden Wert im Array zuordnen.
Manchmal können ineffiziente Hash-Funktionen in einer Hash-Tabelle auch eine Gruppe von Zuordnungen erzeugen. Wenn eine Hash-Funktion eine Gruppe von Zuordnungen für vorhandene Schlüssel erstellt, kann dies den Zeitaufwand für die Suche nach den entsprechenden Werten erhöhen. Dies kann das Hashing für zukünftige Schlüssel verlangsamen, da die meisten Hash-Funktionen im Allgemeinen nach der nächsten verfügbaren Position im Array suchen. Wenn bereits eine große Gruppe von Werten zugewiesen wurde, dauert es in der Regel viel länger, nach einem nicht zugewiesenen Wert für einen neuen Schlüssel zu suchen.
Der Lastfaktor ist ein weiteres Konzept, das sich auf die Effizienz einer Hash-Funktion bezieht. Der Lastfaktor ist die Anzahl der bereits vorhandenen Hashings im Verhältnis zur Gesamtgröße des entsprechenden Arrays in einer Hashtabelle. Sie wird normalerweise definiert, indem die Anzahl der bereits zugewiesenen Schlüssel durch die Größe des entsprechenden Arrays geteilt wird. Wenn der Lastfaktor zunimmt, behält eine gute Hash-Funktion normalerweise eine konstante Anzahl von Kollisionen und Clustern bis zu einem bestimmten Punkt bei. Oft kann dieser Schwellenwert verwendet werden, um zu bestimmen, wie effizient eine Hash-Funktion mit einer bestimmten Anzahl von Schlüsseln ist und wann eine neue Hash-Funktion erforderlich sein kann.
Viele Informatiker haben sich bemüht, die perfekte Hash-Funktion zu erzeugen - eine, die bei zunehmendem Lastfaktor keine Kollisionen oder Cluster erzeugt. Theoretisch besteht der Schlüssel zum Erzeugen einer perfekten Hash-Tabelle darin, eine perfekte Hash-Funktion zu erzeugen. Im Allgemeinen glauben die Forscher, dass eine perfekte Hash-Funktion eine konstante Leistung - die Anzahl der Kollisionen und Cluster - mit zunehmendem Lastfaktor aufweisen sollte. Im schlimmsten Fall würde eine perfekte Hash-Funktion immer noch konstantes Hashing ermöglichen, ohne einen Schwellenwert zu erreichen.