hashmap的擴容機制怎么理解

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

創(chuàng)新互聯(lián)建站公司2013年成立，先為定海等服務(wù)建站，定海等地企業(yè)，進行企業(yè)商務(wù)咨詢服務(wù)。為定海企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

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

什么是擴容（resize）？

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

什么時候擴容？

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

hashmap擴容原理

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

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

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

擴容的過程

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

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

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

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

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

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

?下圖為程序執(zhí)行完Entry[] newTable = new Entry[newCapacity];代碼之后的狀態(tài)：

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

        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ù)組的每個元素
                if (e != null) {
                    src[j] = null;//釋放舊Entry數(shù)組的對象引用（for循環(huán)后，舊的Entry數(shù)組不再引用任何對象）
                    do {
                        Entry<K, V> next = e.next;
                        int i = indexFor(e.hash, newCapacity); //??！重新計算每個元素在數(shù)組中的位置
                        e.next = newTable[i]; //標(biāo)記[1]
                        newTable[i] = e;      //將元素放在數(shù)組上
                        e = next;             //訪問下一個Entry鏈上的元素
                    } while (e != null);
                }
            }
        }

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

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

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

?下圖為程序執(zhí)行完src[j] = null;代碼之后的狀態(tài)（這是第一次循環(huán)時的狀態(tài)）：

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

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

?下圖為程序執(zhí)行完Entry<K, V> next = e.next;代碼之后的狀態(tài)（這是第一次循環(huán)時的狀態(tài)）：

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

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

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

?下圖為程序執(zhí)行完newTable[i] = e;代碼之后的狀態(tài)（這是第一次循環(huán)時的狀態(tài)）：

?下圖為程序執(zhí)行完e = next;代碼之后的狀態(tài)（這是第一次循環(huán)時的狀態(tài)）：

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

小結(jié)

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

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

• HashMap是線程不安全的，不要在并發(fā)的環(huán)境中同時操作HashMap，建議使用ConcurrentHashMap。

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

以上就是“hashmap的擴容機制怎么理解”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

網(wǎng)頁標(biāo)題：hashmap的擴容機制怎么理解
文章鏈接：http://www.muchs.cn/article46/ghjjhg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、微信公眾號、靜態(tài)網(wǎng)站、網(wǎng)站設(shè)計公司、域名注冊、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)