hashmap的擴容機制怎么理解

今天小編給大家分享一下hashmap的擴容機制怎么理解的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

hashmap的擴容機制是：重新計算容量，用一個新的數組替換原來的數組。重新計算原數組的所有數據并插入一個新數組，然后指向新數組；如果數組在容量擴展前已達到最大值，則直接將閾值設置為最大整數返回。

什么是擴容（resize）？

?擴容（resize）：就是重新計算容量，向HashMap對象里不停的添加元素，而HashMap對象內部的數組無法裝載更多的元素時，對象就需要擴大數組的長度，以便能裝入更多的元素。當然Java里的數組是無法自動擴容的，方法是使用一個新的數組代替已有的容量小的數組，就像我們用一個小桶裝水，如果想裝更多的水，就得換大水桶。

什么時候擴容？

?當向容器添加元素的時候，會判斷當前容器的元素個數，如果大于等于閾值(threshold)，即當前容器內的元素個數大于當前數組的長度乘以加載因子的值的時候，就要自動擴容了。

hashmap擴容原理

hashMap擴容就是重新計算容量，向hashMap不停的添加元素，當hashMap無法裝載新的元素，對象將需要擴大數組容量，以便裝入更多的元素。

HashMap容量擴展的特性，加載因子越大，空間利用率越高，擴容前需要填充的元素越多，put操作越快，但鏈表容易過長，hash碰撞概率大，get操作慢。加載因子越小，get操作越快，鏈表越短，hash碰撞概率低。但是，空間利用率低。put元素太多會導致頻繁擴容，影響性能。

HashMap的容量擴展原理：Hashmap的方法是用新數組替換原數組，重新計算原數組中的所有數據，插入新數組，然后指向新數組；如果數組在擴容前已經達到最大，則直接將閾值設置為最大整數返回。

擴容的過程

?下面采用源代碼+圖片+文字描述的方式介紹HashMap的擴容過程。

/** 
 * 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++;  
}

?上述addEntry方法中，如果size(當前容器內的元素個數)大于等于threshold（數組長度乘以負載因子），并且底層數組的bucketIndex坐標處不等于null，那么將會進行擴容（resize）。否則，不會進行擴容。

?下面將著重介紹一下擴容的過程：

        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);此行有遺漏，勘誤見下面引用//修改閾值
        }

由wenni328博友修正：transfer(newTable); ==> transfer(newTable, initHashSeedAsNeeded(newCapacity));
threshold = (int) (newCapacity * loadFactor); ==> threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

?擴容前首先獲取擴容前數組的引用地址存進oldTable變量中，然后判斷擴容前數組長度是否達到了int類型存儲的最大值，如果是則放棄此次擴容，因為數組容量已經達到最大，無法再擴容了。

?下圖為程序執行完Entry[] newTable = new Entry[newCapacity];代碼之后的狀態：

?這里就是使用一個容量更大的數組來代替已有的容量小的數組，transfer()方法將原有Entry數組的元素拷貝到新的Entry數組里。

        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);
        }

?newTable[i]的引用賦給了e.next，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置；這樣先放在一個索引上的元素終會被放到Entry鏈的尾部(如果發生了hash沖突的話）。在舊數組中同一條Entry鏈上的元素，通過重新計算索引位置后，有可能被放到了新數組的不同位置上。

?下面會以圖片的形式演示一下transfer的過程（下面圖片的紅色字體表示與上圖有區別的地方，后面圖片都是這樣，后面紅色字體說明不再贅述）

?下圖為程序執行完src[j] = null;代碼之后的狀態（這是第一次循環時的狀態）：

?首先，將table[]數組的引用地址賦值給src[]數組。

?然后，Entry<K, V> e = src[j];是將src[j]位置的鏈表交給e變量存儲。由于src[j]位置的鏈表已經交給e存儲了，所以可以大膽的將src[j]=null;然后等待垃圾回收。

?下圖為程序執行完Entry<K, V> next = e.next;代碼之后的狀態（這是第一次循環時的狀態）：

?這里先將e.next的值備份至next變量中，后續代碼會將e.next的指向更改，所以在這里將e.next的值備份。

?下圖為程序執行完e.next = newTable[i];代碼之后的狀態（這是第一次循環時的狀態）：

?由于newTable[3]的值為null，所以e.next為null，如上圖所示。

?下圖為程序執行完newTable[i] = e;代碼之后的狀態（這是第一次循環時的狀態）：

?下圖為程序執行完e = next;代碼之后的狀態（這是第一次循環時的狀態）：

?如上述所示，Entry1這個節點成功插入到了newTable中，一輪循環結束時，因為判斷e!=null，所以會再重復上述過程，直至所有節點移動到newTable中。

小結

• 擴容是一個特別耗性能的操作，所以當程序員在使用HashMap的時候，估算map的大小，初始化的時候給一個大致的數值，避免map進行頻繁的擴容。

• 負載因子是可以修改的，也可以大于1，但是建議不要輕易修改，除非情況非常特殊。

• HashMap是線程不安全的，不要在并發的環境中同時操作HashMap，建議使用ConcurrentHashMap。

• JDK1.8引入紅黑樹大程度優化了HashMap的性能。

以上就是“hashmap的擴容機制怎么理解”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。