Implementierung von HashMap Java 8

Gemäß folgendem Linkdokument: Java HashMap-Implementierung

Ich bin verwirrt mit der Implementierung von HashMap(oder besser gesagt einer Verbesserung in HashMap). Meine Fragen sind:

zuerst

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

Warum und wie werden diese Konstanten verwendet? Ich möchte einige klare Beispiele dafür. Wie erzielen sie damit einen Leistungsgewinn?

Zweitens

Wenn Sie den Quellcode von HashMapin JDK sehen, finden Sie die folgende statische innere Klasse:

static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
    HashMap.TreeNode<K, V> parent;
    HashMap.TreeNode<K, V> left;
    HashMap.TreeNode<K, V> right;
    HashMap.TreeNode<K, V> prev;
    boolean red;

    TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
        super(arg0, arg1, arg2, arg3);
    }

    final HashMap.TreeNode<K, V> root() {
        HashMap.TreeNode arg0 = this;

        while (true) {
            HashMap.TreeNode arg1 = arg0.parent;
            if (arg0.parent == null) {
                return arg0;
            }

            arg0 = arg1;
        }
    }
    //...
}

Wie wird es benutzt? Ich möchte nur eine Erklärung des Algorithmus .

HashMapenthält eine bestimmte Anzahl von Eimern. Hiermit wird hashCodebestimmt, in welchen Eimer diese gelegt werden sollen. Stellen Sie sich der Einfachheit halber als Modul vor.

Wenn unser Hashcode 123456 lautet und wir 4 Eimer haben, wird 123456 % 4 = 0der Artikel in den ersten Eimer, Eimer 1, verschoben.

Wenn unsere Hashcode-Funktion gut ist, sollte sie eine gleichmäßige Verteilung bieten, damit alle Buckets etwas gleich verwendet werden. In diesem Fall verwendet der Bucket eine verknüpfte Liste zum Speichern der Werte.

Sie können sich jedoch nicht darauf verlassen, dass Leute gute Hash-Funktionen implementieren. Menschen schreiben oft schlechte Hash-Funktionen, was zu einer ungleichmäßigen Verteilung führt. Es ist auch möglich, dass wir mit unseren Eingaben einfach Pech haben.

Je geringer diese Verteilung ist, desto weiter bewegen wir uns von O (1) -Operationen und desto näher kommen wir O (n) -Operationen.

Die Implementierung von Hashmap versucht dies zu mildern, indem einige Buckets in Bäumen anstatt in verknüpften Listen organisiert werden, wenn die Buckets zu groß werden. Dafür ist da TREEIFY_THRESHOLD = 8. Wenn ein Eimer mehr als acht Elemente enthält, sollte er zu einem Baum werden.

Dieser Baum ist ein rot-schwarzer Baum. Es wird zuerst nach Hash-Code sortiert. Wenn die Hash-Codes identisch sind, wird die compareToMethode verwendet, Comparableob die Objekte diese Schnittstelle implementieren, andernfalls der Identitäts-Hash-Code.

Wenn Einträge aus der Karte entfernt werden, kann sich die Anzahl der Einträge im Bucket verringern, sodass diese Baumstruktur nicht mehr erforderlich ist. Dafür ist das da UNTREEIFY_THRESHOLD = 6. Wenn die Anzahl der Elemente in einem Bucket unter sechs fällt, können Sie auch wieder eine verknüpfte Liste verwenden.

Endlich gibt es die MIN_TREEIFY_CAPACITY = 64.

Wenn eine Hash-Map größer wird, ändert sie automatisch ihre Größe, um mehr Buckets zu haben. Wenn wir eine kleine Hash-Karte haben, ist die Wahrscheinlichkeit, dass wir sehr volle Eimer bekommen, ziemlich hoch, da wir nicht so viele verschiedene Eimer haben, in die wir Sachen stecken können. Es ist viel besser, eine größere Hash-Karte mit mehr Eimern zu haben, die weniger voll sind. Diese Konstante besagt im Grunde, dass wir nicht damit beginnen sollen, Eimer in Bäume zu verwandeln, wenn unsere Hash-Karte sehr klein ist. Stattdessen sollte die Größe geändert werden, damit sie zuerst größer wird.

Um Ihre Frage zum Leistungsgewinn zu beantworten, wurden diese Optimierungen hinzugefügt, um den schlimmsten Fall zu verbessern . Ich spekuliere nur, aber Sie würden aufgrund dieser Optimierungen wahrscheinlich nur dann eine spürbare Leistungsverbesserung feststellen, wenn Ihre hashCodeFunktion nicht sehr gut wäre.

Einfacher ausgedrückt (so viel ich könnte einfacher) + einige weitere Details.

Diese Eigenschaften hängen von vielen internen Dingen ab, deren Verständnis sehr cool wäre - bevor Sie direkt zu ihnen wechseln.

TREEIFY_THRESHOLD -> Wenn ein einzelner Bucket dies erreicht (und die Gesamtzahl überschreitet MIN_TREEIFY_CAPACITY), wird er in einen perfekt ausbalancierten rot / schwarzen Baumknoten umgewandelt . Warum? Wegen der Suchgeschwindigkeit. Denken Sie anders darüber nach:

Die Suche nach einem Eintrag in einem Bucket / Bin mit Integer.MAX_VALUE- Einträgen würde höchstens 32 Schritte dauern .

Ein Intro zum nächsten Thema. Warum ist die Anzahl der Behälter / Eimer immer eine Zweierpotenz ? Mindestens zwei Gründe: Schneller als Modulo-Betrieb und Modulo bei negativen Zahlen sind negativ. Und Sie können einen Eintrag nicht in einen "negativen" Eimer legen:

 int arrayIndex = hashCode % buckets; // will be negative

 buckets[arrayIndex] = Entry; // obviously will fail

Stattdessen wird anstelle von Modulo ein netter Trick verwendet:

 (n - 1) & hash // n is the number of bins, hash - is the hash function of the key

Das ist semantisch dasselbe wie Modulo-Operation. Die unteren Bits bleiben erhalten. Dies hat eine interessante Konsequenz, wenn Sie Folgendes tun:

Map<String, String> map = new HashMap<>();

Im obigen Fall wird die Entscheidung, wohin ein Eintrag geht, basierend auf den letzten 4 Bits nur Ihres Hashcodes getroffen.

Hier kommt das Multiplizieren der Eimer ins Spiel. Unter bestimmten Bedingungen (die genaue Erklärung würde viel Zeit in Anspruch nehmen ) werden die Eimer doppelt so groß. Warum? Wenn die Größe der Eimer verdoppelt wird, kommt noch ein Bit ins Spiel .

Sie haben also 16 Buckets - die letzten 4 Bits des Hashcodes entscheiden, wohin ein Eintrag geht. Sie verdoppeln die Eimer: 32 Eimer - 5 letzte Bits entscheiden, wohin der Eintrag geht.

Als solches wird dieser Prozess als erneutes Hashing bezeichnet. Dies könnte langsam werden. Das heißt (für Leute, die sich interessieren), da HashMap "gescherzt" wird als: schnell, schnell, schnell, langsam . Es gibt andere Implementierungen - Suche pausenlose Hashmap ...

Jetzt kommt UNTREEIFY_THRESHOLD nach dem erneuten Hashing ins Spiel. Zu diesem Zeitpunkt werden einige Einträge möglicherweise von diesen Bins zu anderen verschoben (sie fügen der (n-1)&hashBerechnung ein weiteres Bit hinzu - und als solches möglicherweise zu anderen Buckets), und dies kann erreicht werden UNTREEIFY_THRESHOLD. An dieser Stelle zahlt es sich nicht aus, den Mülleimer als red-black tree node, sondern als LinkedList, wie zu halten

 entry.next.next....

MIN_TREEIFY_CAPACITY ist die Mindestanzahl von Buckets, bevor ein bestimmter Bucket in einen Baum umgewandelt wird.

TreeNodeist eine alternative Möglichkeit, die Einträge zu speichern, die zu einem einzelnen Bin des gehören HashMap. In älteren Implementierungen wurden die Einträge eines Fachs in einer verknüpften Liste gespeichert. Wenn in Java 8 die Anzahl der Einträge in einem Bin einen Schwellenwert ( TREEIFY_THRESHOLD) überschritten hat , werden sie in einer Baumstruktur anstelle der ursprünglichen verknüpften Liste gespeichert. Dies ist eine Optimierung.

Aus der Implementierung:

/*
 * Implementation notes.
 *
 * This map usually acts as a binned (bucketed) hash table, but
 * when bins get too large, they are transformed into bins of
 * TreeNodes, each structured similarly to those in
 * java.util.TreeMap. Most methods try to use normal bins, but
 * relay to TreeNode methods when applicable (simply by checking
 * instanceof a node).  Bins of TreeNodes may be traversed and
 * used like any others, but additionally support faster lookup
 * when overpopulated. However, since the vast majority of bins in
 * normal use are not overpopulated, checking for existence of
 * tree bins may be delayed in the course of table methods.

Sie müssten es visualisieren: Angenommen, es gibt einen Klassenschlüssel, bei dem nur die Funktion hashCode () überschrieben wird, um immer den gleichen Wert zurückzugeben

public class Key implements Comparable<Key>{

  private String name;

  public Key (String name){
    this.name = name;
  }

  @Override
  public int hashCode(){
    return 1;
  }

  public String keyName(){
    return this.name;
  }

  public int compareTo(Key key){
    //returns a +ve or -ve integer 
  }

}

und dann füge ich woanders 9 Einträge in eine HashMap ein, wobei alle Schlüssel Instanzen dieser Klasse sind. z.B

Map<Key, String> map = new HashMap<>();

    Key key1 = new Key("key1");
    map.put(key1, "one");

    Key key2 = new Key("key2");
    map.put(key2, "two");
    Key key3 = new Key("key3");
    map.put(key3, "three");
    Key key4 = new Key("key4");
    map.put(key4, "four");
    Key key5 = new Key("key5");
    map.put(key5, "five");
    Key key6 = new Key("key6");
    map.put(key6, "six");
    Key key7 = new Key("key7");
    map.put(key7, "seven");
    Key key8 = new Key("key8");
    map.put(key8, "eight");

//Since hascode is same, all entries will land into same bucket, lets call it bucket 1. upto here all entries in bucket 1 will be arranged in LinkedList structure e.g. key1 -> key2-> key3 -> ...so on. but when I insert one more entry 

    Key key9 = new Key("key9");
    map.put(key9, "nine");

  threshold value of 8 will be reached and it will rearrange bucket1 entires into Tree (red-black) structure, replacing old linked list. e.g.

                  key1
                 /    \
               key2   key3
              /   \   /  \

Die Baumdurchquerung ist schneller {O (log n)} als die LinkedList {O (n)}, und wenn n wächst, wird der Unterschied signifikanter.

Die Änderung in der HashMap-Implementierung wurde mit JEP-180 hinzugefügt . Der Zweck war:

Verbessern Sie die Leistung von java.util.HashMap unter Bedingungen hoher Hash-Kollision, indem Sie ausgeglichene Bäume anstelle von verknüpften Listen zum Speichern von Karteneinträgen verwenden. Implementieren Sie dieselbe Verbesserung in der LinkedHashMap-Klasse

Reine Leistung ist jedoch nicht der einzige Gewinn. Es verhindert auch einen HashDoS-Angriff , falls eine Hash-Map zum Speichern von Benutzereingaben verwendet wird, da der rot-schwarze Baum , der zum Speichern von Daten im Bucket verwendet wird, die Komplexität der Einfügung im ungünstigsten Fall in O (log n) aufweist. Der Baum wird verwendet, nachdem bestimmte Kriterien erfüllt sind - siehe Eugenes Antwort .

Um die interne Implementierung von Hashmap zu verstehen, müssen Sie das Hashing verstehen. Hashing in seiner einfachsten Form ist eine Möglichkeit, einen eindeutigen Code für eine Variable / ein Objekt zuzuweisen, nachdem eine Formel / ein Algorithmus auf seine Eigenschaften angewendet wurde.

Eine echte Hash-Funktion muss dieser Regel folgen -

„Die Hash-Funktion sollte jedes Mal den gleichen Hash-Code zurückgeben, wenn die Funktion auf gleiche oder gleiche Objekte angewendet wird. Mit anderen Worten, zwei gleiche Objekte müssen konsistent denselben Hash-Code erzeugen. “