So lösen Sie ein Hash-Konfliktproblem mit HashMap in Java

1. Hash-Algorithmus und Hash-Tabelle

Um den Hash-Konflikt zu verstehen, müssen Sie zunächst den Hash-Algorithmus und die Hash-Tabelle verstehen. Der Hash-Algorithmus besteht darin, eine Eingabe beliebiger Länge über einen Hash-Algorithmus in eine Ausgabe fester Länge umzuwandeln . Dieses Ausgabeergebnis ist ein Hash-Wert. Die Hash-Tabelle wird auch als „Hash-Tabelle“ bezeichnet. Es handelt sich um eine Datenstruktur, die über den Schlüssel direkt auf den Speicherort zugreift Ordnen Sie den Schlüssel einem bestimmten Ort in der Tabelle zu, um die Daten an diesem Ort zu erhalten, wodurch die Datensuche beschleunigt wird. Der Hash-Konflikt ist auf den Hash-Algorithmus zurückzuführen. Die berechneten Daten sind unbegrenzt , und der Bereich des berechneten Ergebnisses ist begrenzt Ja, es wird immer unterschiedliche Daten geben und die nach der Berechnung erhaltenen Werte sind gleich, dann kommt es in diesem Fall zu einem sogenannten Hash-Konflikt

3 Es gibt Vier Möglichkeiten, Hash-Konflikte zu lösen

Die offene Adressierungsmethode wird auch als lineare Erkennung bezeichnet. Die Methode besteht darin, an der Stelle zu beginnen, an der der Konflikt auftritt, eine freie Stelle in der Hash-Tabelle in einer bestimmten Reihenfolge zu finden und dann die widersprüchlichen Elemente darin zu speichern Standort. In Java verwendet ThreadLocal die lineare Erkennungsmethode, um Hash-Konflikte zu lösen.

• Wie in der Abbildung gezeigt, wird key=name am Index 1 der Hash-Tabelle gespeichert, vorausgesetzt, dass Der berechnete Index ist ebenfalls 1, dann tritt ein Hash-Konflikt auf und die Methode zur offenen Adressierung besteht darin, einen freien Speicherort zu finden, um den widersprüchlichen Schlüssel zu speichern. Dies ist eine gängige Methode Das Verständnis besteht darin, eine einseitig verknüpfte Liste zum Speichern des Schlüssels mit Hash-Konfliktspeicher zu verwenden, z. B. HashMap
Wie in der Abbildung gezeigt, werden die widersprüchlichen Schlüssel direkt in Form einer einseitig verknüpften Liste gespeichert

Dann besteht die Hash-Methode darin, den Schlüssel über eine bestimmte Hash-Funktion zu berechnen. Wenn ein Konflikt auftritt, kann die Hash-Funktion diesen hashen und so lange berechnen, bis keine Konflikte mehr auftreten Einen gewissen Einfluss auf die Leistung haben

Die Einrichtung eines öffentlichen Entfernungsbereichs besteht darin, die Hash-Tabelle in zwei Teile zu unterteilen: die Tabelle und die Vorteilstabelle. Alle widersprüchlichen Elemente werden in der Vorteilstabelle platziert

4 JDK1.8-Version

HashMap in der JDK1.8-Version verwendet die Kettenadressierungsmethode und den Rot-Schwarz-Baum, um das Problem des Hash-Konflikts zu lösen Wenn die Länge der verknüpften Liste größer oder gleich 8 ist und die Kapazität der Hash-Tabelle größer als 64 ist, wird durch das Hinzufügen zur verknüpften Liste eine Transformation ausgelöst Liste in einen rot-schwarzen Baum

Das obige ist der detaillierte Inhalt vonSo lösen Sie ein Hash-Konfliktproblem mit HashMap in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!