Hashing

Hashing ist supereffizient. Das Suchen, Einfügen und Löschen eines Elements mithilfe von Hashing dauert O(1). Ein Element kann in O(log n) Zeit in einem ausgewogenen Suchbaum gefunden werden. Gibt es eine effizientere Möglichkeit, nach einem Element in einem Container zu suchen? In diesem Kapitel wird eine Technik namens Hashing vorgestellt. Sie können Hashing verwenden, um eine Karte oder einen Satz zu implementieren, um ein Element in O(1)-Zeit zu suchen, einzufügen und zu löschen.

Was ist Hashing?

Hashing verwendet eine Hashing-Funktion, um einen Schlüssel einem Index zuzuordnen. Bevor wir Hashing einführen, werfen wir einen Blick auf Map, eine Datenstruktur, die mithilfe von Hashing implementiert wird. Denken Sie daran, dass eine map (eingeführt in Abschnitt) ein Containerobjekt ist, das Einträge speichert. Jeder Eintrag besteht aus zwei Teilen: einem Schlüssel und einem Wert. Mit dem Schlüssel, auch Suchschlüssel genannt, wird nach dem entsprechenden Wert gesucht. Beispielsweise kann ein Wörterbuch in einer Karte gespeichert werden, in der die Wörter die Schlüssel und die Definitionen der Wörter die Werte sind.

Eine Karte wird auch als Wörterbuch, als Hash-Tabelle oder als assoziatives Array bezeichnet.

Das Java Collections Framework definiert die java.util.Map-Schnittstelle zum Modellieren von Karten. Drei konkrete Implementierungen sind java.util.HashMap, java.util.LinkedHashMap und java.util.TreeMap. java.util.HashMap wird mithilfe von Hashing implementiert, java.util.LinkedHashMap mithilfe von LinkedList und java.util.TreeMap mithilfe von Red -schwarze Bäume.

Wenn Sie den Index eines Elements im Array kennen, können Sie das Element mithilfe des Index in O(1)-Zeit abrufen. Bedeutet das also, dass wir die Werte in einem Array speichern und den Schlüssel als Index verwenden können, um den Wert zu finden? Die Antwort lautet „Ja“ – wenn Sie einen Schlüssel einem Index zuordnen können. Das Array, das die Werte speichert, wird als Hash-Tabelle bezeichnet. Die Funktion, die einen Schlüssel einem Index in der Hash-Tabelle zuordnet, wird als Hash-Funktion bezeichnet. Wie in der folgenden Abbildung dargestellt, ruft eine Hash-Funktion einen Index von einem Schlüssel ab und verwendet den Index, um den Wert für den Schlüssel abzurufen. Hashing ist eine Technik, die den Wert mithilfe des vom Schlüssel erhaltenen Index abruft, ohne eine Suche durchzuführen.

Wie entwirft man eine Hash-Funktion, die aus einem Schlüssel einen Index erzeugt? Idealerweise möchten wir eine Funktion entwerfen, die jeden Suchschlüssel einem anderen Index in der Hash-Tabelle zuordnet. Eine solche Funktion wird als perfekte Hash-Funktion bezeichnet. Allerdings ist es schwierig, eine perfekte Hash-Funktion zu finden. Wenn zwei oder mehr Schlüssel demselben Hashwert zugeordnet sind, spricht man von einer Kollision. Obwohl es Möglichkeiten gibt, mit Kollisionen umzugehen, die später in diesem Kapitel besprochen werden, ist es besser, Kollisionen von vornherein zu vermeiden. Daher sollten Sie eine schnelle und einfach zu berechnende Hash-Funktion entwerfen, die Kollisionen minimiert.

Das obige ist der detaillierte Inhalt vonHashing. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!