首先我們運(yùn)行一段代碼：

此時(shí)運(yùn)行，程序正常，接下來我們將注釋放開：

此時(shí)運(yùn)行發(fā)現(xiàn)，OOM了：

為什么new出來HashMap的時(shí)候并沒有報(bào)OOM，而是在第一次進(jìn)行put操作的時(shí)候才報(bào)的OOM？我們來看下map的源碼。

設(shè)置數(shù)組長(zhǎng)度、擴(kuò)容閾值

創(chuàng)建Map時(shí)可以指定元素個(gè)數(shù)，也可以不指定。先來看下不指定元素個(gè)數(shù)的構(gòu)造方法：

public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 設(shè)置加載因子為0.75}static final float DEFAULT_LOAD_FACTOR = 0.75f;

當(dāng)進(jìn)行put操作時(shí)，會(huì)進(jìn)行resize擴(kuò)容操作：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) //初始table為空 n = (tab = resize()).length; //觸發(fā)resize操作 //省略... } //省略...}transient Node[] table;

看下resize擴(kuò)容的核心代碼：

final Node[] resize() { Node[] oldTab = table; //初始table為空 int oldCap = (oldTab == null) ? 0 : oldTab.length; //所以oldCap為0 int oldThr = threshold; //初始threshold為0 所以oldThr為0 int newCap, newThr = 0; if (oldCap > 0) { //省略... } else if (oldThr > 0) //省略... else { newCap = DEFAULT_INITIAL_CAPACITY; //設(shè)置新數(shù)組長(zhǎng)度為16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //設(shè)置新map可容納元素個(gè)數(shù)為16*0.75 } if (newThr == 0) { //省略... } threshold = newThr; //為threshold賦值為newThr 代表擴(kuò)容后的map的可容納元素個(gè)數(shù)上限 當(dāng)map中元素個(gè)數(shù)超過threshold會(huì)觸發(fā)擴(kuò)容操作 @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; //設(shè)置table為擴(kuò)容后的新數(shù)組 //省略... return newTab;}static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

如果指定元素個(gè)數(shù)，例如：

Map<String,String> map = new HashMap<String,String>(17);public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); //加載因子0.75}public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //加載因子0.75 this.threshold = tableSizeFor(initialCapacity); //設(shè)置threshold為最接近initialCapacity的2次冪的值}static final float DEFAULT_LOAD_FACTOR = 0.75f;

調(diào)用tableSizeFor方法為threshold賦值，看下tableSizeFor的代碼：

static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

這個(gè)函數(shù)是用來對(duì)你申請(qǐng)的容量進(jìn)行處理讓他變成最接近你申請(qǐng)的容量的2次冪的大小，這里注意：假如你申請(qǐng)的容量為0，最后處理的結(jié)果會(huì)變成1，代表著你最小的容量為1。

我們自己測(cè)試一下，tableSizeFor(17)=32：

public static void main(String[] args) { int number = 17; System.out.println(tableSizeFor(number)); //32}public static int tableSizeFor(int number) { int n = number - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

補(bǔ)充：

算術(shù)右移(>>)

右移是按最左邊(高位)來補(bǔ)的(即如果是1就補(bǔ)1,如果是0就補(bǔ)0,不改變?cè)撐坏闹?。另一種說法，正數(shù)右移高位補(bǔ)0，負(fù)數(shù)右移高位補(bǔ)1。

邏輯右移(>>>)

不管最左邊一位是0還是1,都補(bǔ)0。另一種說法，無論是正數(shù)還是負(fù)數(shù)，高位通通補(bǔ)0。

同樣的，當(dāng)put元素時(shí)會(huì)觸發(fā)map的擴(kuò)容操作。

接下來看下指定元素個(gè)數(shù)時(shí)，Map擴(kuò)容的核心源碼。

final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; //初始table為空 oldCap=0 int oldThr = threshold; //此時(shí)threshold已經(jīng)有值(2的n次冪) int newCap, newThr = 0; if (oldCap > 0) { //省略... } else if (oldThr > 0) newCap = oldThr; //擴(kuò)容后map的數(shù)組長(zhǎng)度 else { 省略... } if (newThr == 0) { float ft = (float)newCap * loadFactor; //設(shè)置擴(kuò)容后map的threshold newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; //省略... return newTab;}

總結(jié)一下，如果沒有指定元素個(gè)數(shù)，則擴(kuò)容后的數(shù)組長(zhǎng)度默認(rèn)為16，如果指定元素個(gè)數(shù)，則擴(kuò)容后的數(shù)組長(zhǎng)度為與指定的元素個(gè)數(shù)最接近的2次冪的值，比如指定元素個(gè)數(shù)為17,則數(shù)組長(zhǎng)度為32。threshold的取值都是固定數(shù)組長(zhǎng)度*加載因子(0.75,0.75并不是一個(gè)絕對(duì)的，只是在時(shí)間和空間上可能map的效率最高)。

再回到一開始的問題，new的時(shí)候沒有OOM但是在put的時(shí)候卻OOM了，因?yàn)樵趎ew的時(shí)候只是設(shè)置threshold值，而且設(shè)置的值還是比最大整數(shù)大的2次冪,在擴(kuò)容的時(shí)候，需要分配數(shù)組內(nèi)存，所以O(shè)OM了。

數(shù)據(jù)遷移

上面其實(shí)只是分析了resize操作關(guān)于設(shè)置數(shù)組長(zhǎng)度、擴(kuò)容閾值的代碼，真正擴(kuò)容后數(shù)據(jù)遷移都省略了，接下來看下數(shù)據(jù)遷移部分：

final Node[] resize() { //省略... if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { //遍歷老數(shù)組 Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果老數(shù)組的某一索引位置沒有鏈表，則將計(jì)算該索引位置的元素在新數(shù)組的索引位置 else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); else { //如果索引位置有鏈表 Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { //將索引位置的鏈表拆分成loHead->loTail和hiHead->hiTail兩個(gè)鏈表，順序保持不變 if (loTail == null) loHead = e; else loTail.next = e; //尾插法 loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; //新數(shù)組索引位置放入loHead鏈表 } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; //新數(shù)組索引位置+原始數(shù)組長(zhǎng)度位置放入hiHead鏈表 } } } } } return newTab;}

舉例說明下e.hash&oldCap==0來區(qū)分該放到loHead還是hiHead鏈表，下面是我的理解：

0 1 0 0 0 8 //假設(shè)原數(shù)組長(zhǎng)度8 即oldCap=80 0 0 1 1 3 j=0 //假設(shè)原數(shù)組0索引位置存在3 6 12 三個(gè)數(shù)組成的鏈表0 0 1 1 0 6 j=0 3->6 //經(jīng)e.hash&oldCap計(jì)算 3和6結(jié)果均為0 所以組成loHead：3-60 1 1 0 0 12 j=8 [0+8] //而12與8與操作結(jié)果不等于0 所以組成hiHead：12在擴(kuò)容時(shí)?將3->6放入新數(shù)組的0索引位置，將12放入新數(shù)組的8索引位置

這樣的好處是不用計(jì)算鏈表的每一個(gè)元素在新數(shù)組對(duì)應(yīng)的索引位置了，同時(shí)也保持了元素在鏈表中的順序。

總結(jié)

以上是生活随笔為你收集整理的扩容是元素还是数组_Map扩容源码的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。