The expansion mechanism of hashmap is: recalculate the capacity and replace the original array with a new array. Recalculate all the data of the original array and insert a new array, and then point to the new array; if the array has reached the maximum value before capacity expansion, directly set the threshold to the maximum integer and return it.

#The operating environment of this tutorial: windows7 system, java8, Dell G3 computer.

What is resize?

?Capacity expansion (resize): It is to recalculate the capacity and continuously add elements to the HashMap object. When the array inside the HashMap object cannot load more elements, the object needs to be expanded. The length of the array so that more elements can be accommodated. Of course, arrays in Java cannot be automatically expanded. The method is to use a new array to replace the existing array with a small capacity. Just like we use a small bucket to hold water, if we want to hold more water, we have to change to a larger bucket. .

When will the capacity be expanded?

When adding elements to a container, the number of elements in the current container will be judged. If it is greater than or equal to the threshold (threshold), that is, the number of elements in the current container is greater than the length of the current array. When multiplied by the value of the loading factor, it will automatically expand.

Hashmap expansion principle

HashMap expansion is to recalculate the capacity and continuously add elements to hashMap. When hashMap cannot load new elements, The object will need to expand the array capacity to accommodate more elements.

HashMap capacity expansion characteristics, the greater the loading factor, the higher the space utilization, the more elements need to be filled before expansion, the faster the put operation, but the linked list is easy to pass Long, hash collision probability is high, and get operation is slow. The smaller the loading factor, the faster the get operation, the shorter the linked list, and the lower the probability of hash collision. However, space utilization is low. Too many put elements will lead to frequent expansion and affect performance.

The capacity expansion principle of HashMap: The Hashmap method is to replace the original array with a new array, recalculate all the data in the original array, insert the new array, and then point to the new array; If the array has reached the maximum before expansion, the threshold is directly set to the maximum integer and returned.

The expansion process

The following uses source code, pictures, and text descriptions to introduce the expansion process of HashMap.

/** 
 * HashMap 添加節(jié)點(diǎn) 
 * 
 * @param hash        當(dāng)前key生成的hashcode 
 * @param key         要添加到 HashMap 的key 
 * @param value       要添加到 HashMap 的value 
 * @param bucketIndex 桶，也就是這個(gè)要添加 HashMap 里的這個(gè)數(shù)據(jù)對(duì)應(yīng)到數(shù)組的位置下標(biāo) 
 */  
void addEntry(int hash, K key, V value, int bucketIndex) {  
    //數(shù)組擴(kuò)容條件：1.已經(jīng)存在的key-value mappings的個(gè)數(shù)大于等于閾值  
    //             2.底層數(shù)組的bucketIndex坐標(biāo)處不等于null  
    if ((size >= threshold) && (null != table[bucketIndex])) {  
        resize(2 * table.length);//擴(kuò)容之后，數(shù)組長(zhǎng)度變了  
        hash = (null != key) ? hash(key) : 0;//為什么要再次計(jì)算一下hash值呢？  
        bucketIndex = indexFor(hash, table.length);//擴(kuò)容之后，數(shù)組長(zhǎng)度變了，在數(shù)組的下標(biāo)跟數(shù)組長(zhǎng)度有關(guān)，得重算。  
    }  
    createEntry(hash, key, value, bucketIndex);  
}  
  
/** 
 * 這地方就是鏈表出現(xiàn)的地方，有2種情況 
 * 1，原來(lái)的桶bucketIndex處是沒(méi)值的，那么就不會(huì)有鏈表出來(lái)啦 
 * 2，原來(lái)這地方有值，那么根據(jù)Entry的構(gòu)造函數(shù)，把新傳進(jìn)來(lái)的key-value mapping放在數(shù)組上，原來(lái)的就掛在這個(gè)新來(lái)的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++;  
}

In the above addEntry method, if size (number of elements in the current container) is greater than or equal to threshold (array length multiplied by load factor), and the bucketIndex coordinate of the underlying array is not equal to null, then it will be executed Expansion (resize) . Otherwise, the expansion will not occur.

The following will focus on the expansion process:

        void resize(int newCapacity) {   //傳入新的容量
            Entry[] oldTable = table;    //引用擴(kuò)容前的Entry數(shù)組
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {  //擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大(2^30)了
                threshold = Integer.MAX_VALUE; //修改閾值為int的最大值(2^31-1)，這樣以后就不會(huì)擴(kuò)容了
                return;
            }
     
            Entry[] newTable = new Entry[newCapacity];  //初始化一個(gè)新的Entry數(shù)組
            transfer(newTable);	此行有遺漏，勘誤見(jiàn)下面引用	//??！將數(shù)據(jù)轉(zhuǎn)移到新的Entry數(shù)組里
            table = newTable;                           //HashMap的table屬性引用新的Entry數(shù)組
            threshold = (int) (newCapacity * loadFactor);此行有遺漏，勘誤見(jiàn)下面引用//修改閾值
        }

Corrected by wenni328 blogger: transfer(newTable); ==> transfer(newTable, initHashSeedAsNeeded(newCapacity));
threshold = (int) (newCapacity * loadFactor); ==> threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1);

Before expansion, first obtain the reference address of the array before expansion and store it in the oldTable variable, and then determine whether the length of the array before expansion reaches int The maximum value stored in the type. If so, the expansion will be given up because the array capacity has reached the maximum and cannot be expanded.

The picture below shows the state after the program executes the Entry[] newTable = new Entry[newCapacity]; code:

## ?

Here is the use of a larger capacity An array is used to replace the existing array with a small capacity. The transfer() method copies the elements of the original Entry array to the new Entry array.

        void transfer(Entry[] newTable) {
            Entry[] src = table;                   //src引用了舊的Entry數(shù)組
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) { //遍歷舊的Entry數(shù)組
                Entry<K, V> e = src[j];             //取得舊Entry數(shù)組的每個(gè)元素
                if (e != null) {
                    src[j] = null;//釋放舊Entry數(shù)組的對(duì)象引用（for循環(huán)后，舊的Entry數(shù)組不再引用任何對(duì)象）
                    do {
                        Entry<K, V> next = e.next;
                        int i = indexFor(e.hash, newCapacity); //?。≈匦掠?jì)算每個(gè)元素在數(shù)組中的位置
                        e.next = newTable[i]; //標(biāo)記[1]
                        newTable[i] = e;      //將元素放在數(shù)組上
                        e = next;             //訪問(wèn)下一個(gè)Entry鏈上的元素
                    } while (e != null);
                }
            }
        }

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

The reference of newTable[i] is assigned to e.next, that is,

uses the head insertion method of a singly linked list, and new elements at the same position will always be placed at the head of the linked list. position; in this way, elements placed on an index first will eventually be placed at the end of the Entry chain (if a hash conflict occurs). Elements in the same Entry chain in the old array may be placed in different positions in the new array after recalculating the index position.

The transfer process will be demonstrated in the form of pictures below (the red fonts in the pictures below indicate the differences from the above pictures, the following pictures are like this, and the descriptions in red fonts will not be repeated)

The picture below shows the state after the program executes the src[j] = null; code (this is the state during the first loop):

First, assign the reference address of the table[] array to the src[] array.

Then, Entry e = src[j]; is to transfer the linked list at the src[j] position to the e variable for storage. Since the linked list at src[j] has been given to e for storage, you can boldly set src[j]=null; and then wait for garbage collection.

The picture below shows the state after the program executes the Entry next = e.next; code (this is the state during the first loop):

The value of e.next is first backed up to the next variable. Subsequent code will change the pointer of e.next, so the value of e.next is backed up here.

The picture below shows the state after the program executes the e.next = newTable[i]; code (this is the state during the first loop):
#?

## Since the value of newTable[3] is null, e.next is null, as shown in the figure above.

The picture below shows the state after the program executes the newTable[i] = e; code (this is the state during the first loop):

?

## The following picture shows the state after the program executes the e = next; code (this is the state during the first loop):

As shown above, Entry1 This node is successfully inserted into newTable. At the end of the cycle, because e!=null is judged, the above process will be repeated until all nodes are moved to newTable.

Summary

Expansion is a particularly performance-intensive operation, so when programmers use HashMap, they estimate the size of the map and provide it during initialization. A rough value to avoid frequent map expansion.

• The load factor can be modified, or it can be greater than 1, but it is recommended not to modify it easily unless the situation is very special.
• HashMap is thread-unsafe. Do not operate HashMap at the same time in a concurrent environment. It is recommended to use ConcurrentHashMap.
• JDK1.8 introduces red-black trees to greatly optimize the performance of HashMap.
• For more programming-related knowledge, please visit:

Programming Teaching

! !

The above is the detailed content of What is the expansion mechanism of hashmap?. For more information, please follow other related articles on the PHP Chinese website!