Was ist der Erweiterungsmechanismus von Hashmap?

Der Erweiterungsmechanismus von Hashmap besteht darin, die Kapazität neu zu berechnen und das ursprüngliche Array durch ein neues Array zu ersetzen. Berechnen Sie alle Daten des ursprünglichen Arrays neu und fügen Sie ein neues Array ein. Wenn das Array vor der Kapazitätserweiterung den Maximalwert erreicht hat, setzen Sie den Schwellenwert direkt auf die maximale Ganzzahl und geben Sie ihn zurück.

Die Betriebsumgebung dieses Tutorials: Windows7-System, Java8, Dell G3-Computer.

Was ist Größenänderung?

Erweiterung (Größe ändern): Dient zur Neuberechnung der Kapazität und zum kontinuierlichen Hinzufügen von Elementen zum HashMap-Objekt. Wenn das Array im HashMap-Objekt keine weiteren Elemente laden kann, muss das Objekt die Länge des Arrays erweitern, damit dies möglich ist Weitere Elemente geladen werden. Natürlich können Arrays in Java nicht automatisch erweitert werden. Die Methode besteht darin, ein neues Array zu verwenden, um das vorhandene Array mit einer kleinen Kapazität zu ersetzen. Genauso wie wir einen kleinen Eimer zum Aufbewahren von Wasser verwenden auf einen größeren Eimer umsteigen.

Wann wird die Kapazität erweitert?

Beim Hinzufügen von Elementen zu einem Container wird die Anzahl der Elemente im aktuellen Container beurteilt. Wenn sie größer oder gleich dem Schwellenwert (Schwellenwert) ist, dh wenn die Anzahl der Elemente im aktuellen Container beträgt größer als die Länge des aktuellen Arrays multipliziert mit dem Wert des Ladefaktors, wird es automatisch erweitert.

Hashmap-Erweiterungsprinzip

Die HashMap-Erweiterung besteht darin, die Kapazität neu zu berechnen und kontinuierlich Elemente zur HashMap hinzuzufügen. Wenn HashMap keine neuen Elemente laden kann, muss das Objekt die Array-Kapazität erweitern, um weitere Elemente zu laden.

HashMap-Kapazitätserweiterungseigenschaften: Je größer der Ladefaktor, desto höher die Raumnutzung, desto mehr Elemente müssen vor der Erweiterung gefüllt werden, desto schneller ist der Put-Vorgang, aber die verknüpfte Liste kann leicht zu lang sein Die Wahrscheinlichkeit einer Hash-Kollision ist hoch und der Abrufvorgang ist langsam. Je kleiner der Ladefaktor, desto schneller ist der Abrufvorgang, desto kürzer ist die verknüpfte Liste und desto geringer ist die Wahrscheinlichkeit einer Hash-Kollision. Allerdings ist die Raumausnutzung gering. Zu viele Put-Elemente führen zu häufiger Erweiterung und beeinträchtigen die Leistung.

Das Kapazitätserweiterungsprinzip von HashMap: Die Methode von Hashmap besteht darin, das ursprüngliche Array durch ein neues Array zu ersetzen, alle Daten im ursprünglichen Array neu zu berechnen, das neue Array einzufügen und dann auf das neue Array zu verweisen Das Array hat vor der Erweiterung das Maximum erreicht. Setzen Sie dann den Schwellenwert direkt auf die maximal zurückgegebene Ganzzahl.

Der Erweiterungsprozess

Im Folgenden werden Quellcode + Bilder + Textbeschreibung verwendet, um den Erweiterungsprozess von HashMap vorzustellen.

/** 
 * HashMap 添加节点 
 * 
 * @param hash        当前key生成的hashcode 
 * @param key         要添加到 HashMap 的key 
 * @param value       要添加到 HashMap 的value 
 * @param bucketIndex 桶，也就是这个要添加 HashMap 里的这个数据对应到数组的位置下标 
 */  
void addEntry(int hash, K key, V value, int bucketIndex) {  
    //数组扩容条件：1.已经存在的key-value mappings的个数大于等于阈值  
    //             2.底层数组的bucketIndex坐标处不等于null  
    if ((size >= threshold) && (null != table[bucketIndex])) {  
        resize(2 * table.length);//扩容之后，数组长度变了  
        hash = (null != key) ? hash(key) : 0;//为什么要再次计算一下hash值呢？  
        bucketIndex = indexFor(hash, table.length);//扩容之后，数组长度变了，在数组的下标跟数组长度有关，得重算。  
    }  
    createEntry(hash, key, value, bucketIndex);  
}  
  
/** 
 * 这地方就是链表出现的地方，有2种情况 
 * 1，原来的桶bucketIndex处是没值的，那么就不会有链表出来啦 
 * 2，原来这地方有值，那么根据Entry的构造函数，把新传进来的key-value mapping放在数组上，原来的就挂在这个新来的next属性上了 
 */  
void createEntry(int hash, K key, V value, int bucketIndex) {  
    HashMap.Entry<K, V> e = table[bucketIndex];  
    table[bucketIndex] = new HashMap.Entry<>(hash, key, value, e);  
    size++;  
}

Wenn in der obigen addEntry-Methode die Größe (Anzahl der Elemente im aktuellen Container) größer oder gleich dem Schwellenwert (Array-Länge multipliziert mit dem Lastfaktor) ist und die BucketIndex-Koordinate des zugrunde liegenden Arrays nicht gleich Null ist, dann wird die Erweiterung (Größenänderung) durchgeführt ). Andernfalls findet die Erweiterung nicht statt.

Das Folgende konzentriert sich auf den Prozess der Erweiterung:

        void resize(int newCapacity) {   //传入新的容量
            Entry[] oldTable = table;    //引用扩容前的Entry数组
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
                threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
                return;
            }
     
            Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
            transfer(newTable);	此行有遗漏，勘误见下面引用	//！！将数据转移到新的Entry数组里
            table = newTable;                           //HashMap的table属性引用新的Entry数组
            threshold = (int) (newCapacity * loadFactor);此行有遗漏，勘误见下面引用//修改阈值
        }

Korrigiert von wenni328-Blogger: transfer(newTable); ==> transfer(newTable, initHashSeedAsNeeded(newCapacity));
threshold = (int) (newCapacity * LoadFactor); ==> Schwellenwert = (int)Math.min(newCapacity * LoadFactor, MAXIMUM_CAPACITY + 1);

Erhalten Sie vor der Erweiterung zunächst die Referenzadresse des Arrays vor der Erweiterung und speichern Sie es in der Variablen oldTable und bestimmen Sie dann, ob die Array-Länge vor der Erweiterung den im Typ int gespeicherten Maximalwert erreicht hat. Wenn ja, geben Sie die Erweiterung auf, da die Array-Kapazität das Maximum erreicht hat und nicht erweitert werden kann.

Das Bild unten zeigt den Status, nachdem das Programm den Code Entry[] newTable = new Entry[newCapacity]; ausgeführt hat:

Hier wird ein Array mit einer größeren Kapazität verwendet, um das vorhandene Array durch eine kleinere Kapazität zu ersetzen Die Methode transfer( ) kopiert die Elemente des ursprünglichen Entry-Arrays in das neue Entry-Array.

        void transfer(Entry[] newTable) {
            Entry[] src = table;                   //src引用了旧的Entry数组
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
                Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素
                if (e != null) {
                    src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
                    do {
                        Entry<K, V> next = e.next;
                        int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                        e.next = newTable[i]; //标记[1]
                        newTable[i] = e;      //将元素放在数组上
                        e = next;             //访问下一个Entry链上的元素
                    } while (e != null);
                }
            }
        }

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

Die Referenz von newTable[i] wird e.next zugewiesen, das heißt, verwendet die Kopfeinfügungsmethode einer einfach verknüpften Liste und neue Elemente an derselben Position werden immer am Kopf der verknüpften Liste platziert Auf diese Weise werden sie zunächst in einer Liste platziert. Das Element am Index wird schließlich am Ende der Eintragskette platziert (falls ein Hash-Konflikt auftritt). Elemente in derselben Eintragskette im alten Array können nach der Neuberechnung der Indexposition an unterschiedlichen Positionen im neuen Array platziert werden.

Der Übertragungsvorgang wird in Form von Bildern unten demonstriert (die roten Schriftarten in den Bildern unten zeigen die Unterschiede zu den obigen Bildern an. Die folgenden Bilder sind so und die Beschreibungen in roten Schriftarten werden nicht wiederholt)

Das Bild unten zeigt den Abschluss der Programmausführung. src[j] = null; Der Status nach dem Code (dies ist der Status während der ersten Schleife):

Weisen Sie zunächst die Referenzadresse des Arrays table[] dem Array src[] zu.

Dann soll Entry die verknüpfte Liste an der Position src[j] zur Speicherung übertragen. Da die verknüpfte Liste bei src[j] zur Speicherung an e übergeben wurde, können Sie mutig src[j]=null setzen und dann auf die Garbage Collection warten.

Das Bild unten zeigt den Status, nachdem das Programm den Code Entry ausgeführt hat (dies ist der Status während der ersten Schleife):

Hier ändern Sie zunächst den Wert von e .next Zurück zur nächsten Variablen. Nachfolgender Code ändert den Zeiger von e.next, sodass der Wert von e.next hier gesichert wird.

Das Bild unten zeigt den Status, nachdem das Programm den Code e.next = newTable[i]; ausgeführt hat (dies ist der Status während der ersten Schleife):

Da der Wert von newTable[3] null ist , also ist e.next null, wie in der Abbildung oben gezeigt.

Das Bild unten zeigt den Status, nachdem das Programm den newTable[i] = e;-Code ausgeführt hat (dies ist der Status während der ersten Schleife):

Das Bild unten zeigt den Status, nachdem das Programm den e ausgeführt hat = next; Code Status (dies ist der Status während der ersten Schleife):

Wie oben gezeigt, wird der Eintrag1-Knoten am Ende der Schleife erfolgreich eingefügt, da e!=null beurteilt wird Der obige Vorgang wird wiederholt, bis alle Knoten in die neue Tabelle verschoben sind.

Zusammenfassung

• Erweiterung ist ein besonders leistungsintensiver Vorgang. Wenn Programmierer HashMap verwenden, sollten sie daher die Größe der Karte schätzen und bei der Initialisierung einen ungefähren Wert angeben, um eine häufige Erweiterung der Karte zu vermeiden.
• Der Lastfaktor kann geändert werden oder größer als 1 sein. Es wird jedoch empfohlen, ihn nicht einfach zu ändern, es sei denn, die Situation ist sehr speziell.
• HashMap ist nicht threadsicher. Betreiben Sie HashMap nicht gleichzeitig in einer Umgebung. Es wird empfohlen, ConcurrentHashMap zu verwenden.
• JDK1.8 führt Rot-Schwarz-Bäume ein, um die Leistung von HashMap erheblich zu optimieren.

Weitere Kenntnisse zum Thema Programmierung finden Sie unter: Programmierunterricht! !

Das obige ist der detaillierte Inhalt vonWas ist der Erweiterungsmechanismus von Hashmap?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!