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 an einen Hash ordnet und den Firmennamen beispielsweise mit seiner Adresse, der Telefonnummer und seiner Geschäftskategorie verbindet. 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 typischAlly sorgt für ein einheitliches Aussehen 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 werden. 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 Cluster 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 ein großer ClusterDie Werte wurden bereits zugewiesen, es würde in der Regel viel länger dauern, um 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 festzustellen, 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 zu produzieren - eine, die keine Kollisionen oder Cluster erzeugt, wenn sie einen zunehmenden Lastfaktor haben. Theoretisch ist der Schlüssel zur Herstellung eines perfekten Hashtabels für ProfiDuce eine perfekte Hash -Funktion. Im Allgemeinen glauben die Forscher, dass eine perfekte Hash -Funktion eine ständige Leistung - die Anzahl der Kollisionen und Cluster - mit zunehmendem Lastfaktor haben sollte. In schlimmsten Szenarien würde eine perfekte Hash -Funktion immer noch ein ständiges Hashing ermöglichen, ohne eine Schwelle zu erreichen.