Analyse des Implementierungsprinzips von HashMap in Java

Der Inhalt dieses Artikels befasst sich mit der Analyse des Implementierungsprinzips von HashMap in Java. Ich hoffe, dass er für Freunde hilfreich ist.

1. HashMap-Übersicht:
HashMap ist eine asynchrone Implementierung der Map-Schnittstelle basierend auf Hash-Tabellen. Diese Implementierung stellt alle optionalen Zuordnungsvorgänge bereit und ermöglicht Nullwerte und Nullschlüssel. Diese Klasse garantiert nicht die Reihenfolge der Zuordnung und insbesondere nicht, dass die Reihenfolge unveränderlich ist.
2. HashMap-Datenstruktur:
In der Programmiersprache Java gibt es zwei grundlegendste Strukturen, eine ist ein Array und die andere ist ein simulierter Zeiger (Referenz). Alle Datenstrukturen können mit diesen beiden Grundstrukturen erstellt werden, und HashMap ist keine Ausnahme. HashMap ist eigentlich eine „Linked-List-Hash“-Datenstruktur, die eine Kombination aus einem Array und einer verknüpften Liste darstellt.
Wie Sie auf dem Bild oben sehen können, ist die unterste Ebene von HashMap eine Array-Struktur und jedes Element im Array ist eine verknüpfte Liste. Wenn eine neue HashMap erstellt wird, wird ein Array initialisiert.

/** 
 * The table, resized as necessary. Length MUST Always be a power of two. 
 */  transient Entry[] table;  

static class Entry<K,V> implements Map.Entry<K,V> {  
    final K key;  
    V value;  
    Entry<K,V> next;  
    final int hash;  
    ……  
}

3. HashMap-Zugriffsimplementierung:
1) Speicherung:

public V put(K key, V value) {  
    // HashMap允许存放null键和null值。  
    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。  
    if (key == null)  
        return putForNullKey(value);  
    // 根据key的keyCode重新计算hash值。  
    int hash = hash(key.hashCode());  
    // 搜索指定hash值在对应table中的索引。  
    int i = indexFor(hash, table.length);  
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。  
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
        Object k;  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
            V oldValue = e.value;  
            e.value = value;  
            e.recordAccess(this);  
            return oldValue;  
        }  
    }  
    // 如果i索引处的Entry为null，表明此处还没有Entry。  
    modCount++;  
    // 将key、value添加到i索引处。  
    addEntry(hash, key, value, i);  
    return null;  
}

Wie aus dem obigen Quellcode ersichtlich ist: Wenn wir ein Element in die HashMap einfügen, berechnen wir zunächst den Hash-Wert basierend auf dem HashCode des Schlüssels neu und erhalten das Element im Array basierend auf der Hash-Wert-Position (d. h. Index). Wenn an dieser Position im Array andere Elemente gespeichert sind, werden die Elemente an dieser Position in Form einer verknüpften Liste gespeichert, wobei die neu hinzugefügten Elemente an dieser Position platziert werden der Kopf der Kette und die ersten hinzugefügten am Ende der Kette. Wenn an dieser Position im Array kein Element vorhanden ist, wird das Element direkt an dieser Position im Array platziert.
Die Methode addEntry(hash, key, value, i) platziert das Schlüssel-Wert-Paar basierend auf dem berechneten Hash-Wert am i-Index der Array-Tabelle. addEntry ist eine von HashMap bereitgestellte Paketzugriffsmethode. Der Code lautet wie folgt:

void addEntry(int hash, K key, V value, int bucketIndex) {  
    // 获取指定 bucketIndex 索引处的 Entry   
    Entry<K,V> e = table[bucketIndex];  
    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry  
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
    // 如果 Map 中的 key-value 对的数量超过了极限  
    if (size++ >= threshold)  
    // 把 table 对象的长度扩充到原来的2倍。  
        resize(2 * table.length);  
}

Wenn das System beschließt, die Schlüssel-Wert-Paare in der HashMap zu speichern, berücksichtigt es den Wert im Eintrag überhaupt nicht. und berechnet und kombiniert sie nur anhand des Schlüssels. Bestimmen Sie den Speicherort jedes Eintrags. Wir können den Wert in der Map-Sammlung vollständig als Zubehör zum Schlüssel betrachten. Nachdem das System den Speicherort des Schlüssels ermittelt hat, kann der Wert dort gespeichert werden.

Die Methode hash(int h) berechnet den Hash basierend auf dem HashCode des Schlüssels neu. Dieser Algorithmus fügt eine High-Bit-Berechnung hinzu, um Hash-Konflikte zu verhindern, die entstehen, wenn das Low-Bit unverändert bleibt und sich das High-Bit ändert.

static int hash(int h) {  
    h ^= (h >>> 20) ^ (h >>> 12);  
    return h ^ (h >>> 7) ^ (h >>> 4);  
}

Wir können sehen, dass wir zum Auffinden eines Elements in einer HashMap die Position im entsprechenden Array basierend auf dem Hash-Wert des Schlüssels finden müssen. Die Berechnung dieser Position erfolgt über den Hash-Algorithmus. Wie bereits erwähnt, ist die Datenstruktur von HashMap eine Kombination aus Array und verknüpfter Liste. Daher hoffen wir natürlich, dass die Elementpositionen in dieser HashMap so gleichmäßig wie möglich verteilt sind, sodass sich an jeder Position nur ein Element befindet Wir verwenden den Hash-Algorithmus, um zu erhalten. An dieser Position können wir sofort erkennen, dass das Element an der entsprechenden Position das ist, was wir wollen, ohne die verknüpfte Liste durchlaufen zu müssen, was die Effizienz der Abfrage erheblich optimiert.

Für jedes gegebene Objekt ist der Hash-Codewert, der vom Programm berechnet wird, das die Methode hash(int h) aufruft, immer derselbe, solange der Rückgabewert von hashCode() gleich ist. Das erste, woran wir denken, ist, den Hash-Wert modulo zur Array-Länge zu nehmen, damit die Verteilung der Elemente relativ gleichmäßig ist. Der Verbrauch der „Modulo“-Operation ist jedoch immer noch relativ groß. Dies geschieht in HashMap: Rufen Sie die Methode indexFor(int h, int length) auf, um zu berechnen, an welchem ​​Index des Tabellenarrays das Objekt gespeichert werden soll. Der Code der Methode indexFor(int h, int length) lautet wie folgt:

static int indexFor(int h, int length) {  
    return h & (length-1);  
}

Diese Methode ist sehr clever. Sie verwendet h & (table.length -1), um das Speicherbit des Objekts abzurufen. und die Länge des zugrunde liegenden Arrays von HashMap Es beträgt immer 2 hoch n-tel Dies ist die Geschwindigkeitsoptimierung von HashMap. Im HashMap-Konstruktor gibt es den folgenden Code:

int capacity = 1;  
    while (capacity < initialCapacity)  
        capacity <<= 1;

Dieser Code stellt sicher, dass die Kapazität von HashMap während der Initialisierung immer 2 hoch n-tel beträgt, d. h. die Länge des zugrunde liegenden Arrays beträgt immer 2 hoch n-tel Leistung.
Wenn die Länge immer 2 hoch n-tel ist, entspricht die Operation h& (Länge-1) der Verwendung der Modulo-Länge, also h%Länge, aber & ist effizienter als %.
Wenn die Länge des Arrays 2 hoch n beträgt, ist die Wahrscheinlichkeit, denselben Index für verschiedene Schlüssel zu berechnen, gering, sodass die Daten gleichmäßig auf dem Array verteilt sind, was bedeutet, dass die Kollisionswahrscheinlichkeit gering ist. Im Gegensatz dazu ist die Abfrage zu diesem Zeitpunkt nicht erforderlich, um die verknüpfte Liste an einer bestimmten Position zu durchlaufen, sodass die Abfrageeffizienz höher ist.

Gemäß dem Quellcode der obigen Put-Methode ist ersichtlich, dass das Programm beim Versuch, ein Schlüssel-Wert-Paar in eine HashMap einzufügen, zunächst den Speicherort des Eintrags basierend auf bestimmt hashCode()-Rückgabewert des Schlüssels: Wenn die hashCode()-Rückgabewerte zweier Eingabeschlüssel gleich sind, sind ihre Speicherorte gleich. Wenn die Schlüssel dieser beiden Einträge durch einen Gleichheitsvergleich den Wert „true“ zurückgeben, überschreibt der Wert des neu hinzugefügten Eintrags den Wert des ursprünglichen Eintrags in der Sammlung, der Schlüssel wird jedoch nicht überschrieben. Wenn die Schlüssel dieser beiden Einträge beim Gleichheitsvergleich den Wert „false“ zurückgeben, bildet der neu hinzugefügte Eintrag eine Eintragskette mit dem ursprünglichen Eintrag in der Sammlung, und der neu hinzugefügte Eintrag befindet sich an der Spitze der Eintragskette – siehe Beschreibung weiter der Methode addEntry() für spezifische Anweisungen.
(2) Lesen Sie

public V get(Object key) {  
    if (key == null)  
        return getForNullKey();  
    int hash = hash(key.hashCode());  
    for (Entry<K,V> e = table[indexFor(hash, table.length)];  
        e != null;  
        e = e.next) {  
        Object k;  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
            return e.value;  
    }  
    return null;  
}

有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

3) 归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
4.    HashMap的resize（rehash）：
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
5.    HashMap的性能参数：
  HashMap 包含如下几个构造器：
  HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
  HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
  HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。
  HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。
  initialCapacity：HashMap的最大容量，即为底层数组的长度。
  loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。
  负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。
  HashMap的实现中，通过threshold字段来判断HashMap的最大容量：

threshold = (int)(capacity * loadFactor);

结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：

if (size++ >= threshold)     
    resize(2 * table.length);

6.    Fail-Fast机制：
我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

HashIterator() {  
    expectedModCount = modCount;  
    if (size > 0) { // advance to first entry  
    Entry[] t = table;  
    while (index < t.length && (next = t[index++]) == null)  
        ;  
    }  
}

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：
  注意到modCount声明为volatile，保证线程之间修改的可见性。

final Entry<K,V> nextEntry() {     
    if (modCount != expectedModCount)     
        throw new ConcurrentModificationException();

在HashMap的API中指出：

Iteratoren, die von den „Sammlungsansichtsmethoden“ aller HashMap-Klassen zurückgegeben werden, sind ausfallsicher: Wenn die Karte nach der Erstellung des Iterators strukturell geändert wird, außer durch die Methode „remove“ des Iterators selbst, ist jede andere Zeit gegeben In irgendeiner Weise geändert wird, löst der Iterator eine ConcurrentModificationException aus. Daher wird der Iterator angesichts gleichzeitiger Änderungen schnell vollständig ausfallen, ohne dass das Risiko eines willkürlichen nichtdeterministischen Verhaltens zu einem unbestimmten Zeitpunkt in der Zukunft besteht.

Beachten Sie, dass das ausfallsichere Verhalten von Iteratoren nicht garantiert ist und es im Allgemeinen unmöglich ist, feste Garantien zu geben, wenn nicht synchronisierte gleichzeitige Änderungen vorliegen. Fail-Fast-Iteratoren lösen ConcurrentModificationException auf Best-Effort-Basis aus. Daher ist es ein Fehler, ein Programm zu schreiben, das auf dieser Ausnahme basiert. Der richtige Ansatz besteht darin, das Fail-Fast-Verhalten von Iteratoren nur zur Erkennung von Programmfehlern zu verwenden.

Verwandte Empfehlungen:

Vertiefendes Verständnis des Implementierungsprinzips von HashMap in Java (Bild)

Detaillierte Erläuterung des Prinzips und Implementierung einer Java Lock-freien Hashmap

Das obige ist der detaillierte Inhalt vonAnalyse des Implementierungsprinzips von HashMap in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!