Was ist ein Hashtable?

In der Informatik ist ein Hashtable eine Datenstruktur zum Speichern von Daten, die aus einer Liste von Werten besteht, die als Schlüssel bezeichnet werden und mit einer entsprechenden Werteliste, die als Array bezeichnet wird, kombiniert werden.Zum Beispiel kann ein Firmenname mit seiner Adresse kombiniert werden.In der Regel 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 auf einen Hash mdash ordnet.Verbinden Sie den Firmennamen mit seiner Adresse, der Telefonnummer und seiner Geschäftskategorie beispielsweise.Der Zweck der Hash -Funktion besteht darin, jeden Schlüssel einem eindeutigen entsprechenden Wert im Array zuzuweisen.Dies wird allgemein als Hashing bezeichnet.Hash -Funktionen müssen ordnungsgemäß formatiert werden, damit ein Hashtable ordnungsgemäß funktioniert.

Die Leistung eines Hashtabels auf einem Datensatz hängt von der Effizienz seiner Hash -Funktion ab.Eine gute Hash -Funktion bietet typischerweise eine einheitliche Suche von Schlüssel und eine gleichmäßige Verteilung von Zuordnungen im entsprechenden Array.Eine Hash -Kollision tritt auf, wenn zwei Schlüssel dem gleichen entsprechenden Wert zugeordnet sind.Wenn eine Hash -Kollision auftritt, wird die Hash -Funktion normalerweise erneut ausgeführt, bis ein eindeutiger entsprechender Wert gefunden wird.Dies führt häufig zu längeren Hashing -Zeiten.Obwohl die Anzahl der Schlüssel in einem Hashtable normalerweise festgelegt ist, gibt es manchmal doppelte Schlüssel.Trotzdem hat ein gut gestalteter Hashtable effektive Hash-Funktionen, die jeden Schlüssel einem eindeutigen entsprechenden Wert im Array abbilden.

Manchmal können ineffiziente Hash -Funktionen in einem Hashtable auch eine Gruppe von Zuordnungen erzeugen.Wenn eine Hash -Funktion eine Gruppe von Zuordnungen für vorhandene Schlüssel erstellt, kann dies die Zeit erhöhen, die für die Suche nach den entsprechenden Werten benötigt wird.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, würde es normalerweise viel länger dauern, nach einem nicht zugewiesenen Wert für einen neuen Schlüssel zu suchen.

Der Lastfaktor ist ein weiteres Konzept im Zusammenhang mit der Effizienz einer Hash -Funktion.Der Lastfaktor ist die Menge der bereits vorhandenen Hashings in Bezug auf die Gesamtgröße des entsprechenden Arrays in einem Hashtable.Es wird normalerweise definiert, indem die Anzahl der bereits zugewiesenen Schlüssel durch die Größe des entsprechenden Arrays geteilt wird.Mit zunehmendem Lastfaktor hält eine gute Hash -Funktion normalerweise immer noch eine konstante Anzahl von Kollisionen und Clustern bis zu einem bestimmten Punkt.Oft kann dieser Schwellenwert verwendet werden, um zu bestimmen, wie effizient eine Hash -Funktion mit einer bestimmten Anzahl von Schlüssel ist und wann eine neue Hash -Funktion erforderlich ist.

Viele Informatikforscher haben sich bemüht, die perfekte Hash -Funktion mdash zu produzieren.Eine, die keine Kollisionen oder Cluster erzeugt, wenn sie einen zunehmenden Lastfaktor haben.Theoretisch ist der Schlüssel zur Erzeugung eines perfekten Hashtabels darin, eine perfekte Hash -Funktion zu erzeugen.Im Allgemeinen glauben die Forscher, dass eine perfekte Hash -Funktion eine ständige Leistung und Mdash haben sollte.die Anzahl der Kollisionen und Cluster mdash;mit einem zunehmenden Lastfaktor.Im schlimmsten Fall würde eine perfekte Hash -Funktion immer noch ein ständiges Hashing ermöglichen, ohne einen Schwellenwert zu erreichen.