【81期】面試官：說(shuō)說(shuō)HashMap 中的容量與擴(kuò)容實(shí)現(xiàn)

程序員的成長(zhǎng)之路

互聯(lián)網(wǎng)/程序員/技術(shù)/資料共享?

閱讀本文大概需要 12?分鐘。

來(lái)自：cnblogs.com/youzhibing/p/11833040.html

高手過(guò)招，招招致命

JDK1.8 中 HashMap 的底層實(shí)現(xiàn)，我相信大家都能說(shuō)上來(lái)個(gè) 一二，底層數(shù)據(jù)結(jié)構(gòu) 數(shù)組 + 鏈表（或紅黑樹） ，源碼如下

/**
?*?數(shù)組
?*/
transient?Node[]?table;

/**
?*?鏈表結(jié)構(gòu)
?*/
static?class?Node<K,V>?implements?Map.Entry<K,V>?{
????final?int?hash;
????final?K?key;
????V?value;
????Node?next;

????Node(int?hash,?K?key,?V?value,?Node?next)?{
????????this.hash?=?hash;
????????this.key?=?key;
????????this.value?=?value;
????????this.next?=?next;
????}

????public?final?K?getKey()????????{?return?key;?}
????public?final?V?getValue()??????{?return?value;?}
????public?final?String?toString()?{?return?key?+?"="?+?value;?}

????public?final?int?hashCode()?{
????????return?Objects.hashCode(key)?^?Objects.hashCode(value);
????}

????public?final?V?setValue(V?newValue)?{
????????V?oldValue?=?value;
????????value?=?newValue;
????????return?oldValue;
????}

????public?final?boolean?equals(Object?o)?{
????????if?(o?==?this)
????????????return?true;
????????if?(o?instanceof?Map.Entry)?{
????????????Map.Entry?e?=?(Map.Entry)o;
????????????if?(Objects.equals(key,?e.getKey())?&&
????????????????Objects.equals(value,?e.getValue()))
????????????????return?true;
????????}
????????return?false;
????}
}

/**
?*?紅黑樹結(jié)構(gòu)
?*/
static?final?class?TreeNode<K,V>?extends?LinkedHashMap.Entry<K,V>?{
????TreeNode?parent;??//?red-black?tree?links
????TreeNode?left;
????TreeNode?right;
????TreeNode?prev;????//?needed?to?unlink?next?upon?deletion
????boolean?red;
????...

但面試往往會(huì)問(wèn)的比較細(xì)，例如下面的容量問(wèn)題，我們能答上來(lái)幾個(gè)？

1、table 的初始化時(shí)機(jī)是什么時(shí)候，初始化的 table.length 是多少、閥值（threshold）是多少，實(shí)際能容下多少元素

2、什么時(shí)候觸發(fā)擴(kuò)容，擴(kuò)容之后的 table.length、閥值各是多少？

3、table 的 length 為什么是 2 的 n 次冪

4、求索引的時(shí)候?yàn)槭裁词牵篽&(length-1)，而不是 h&length，更不是 h%length

5、 Map map = new HashMap(1000); 當(dāng)我們存入多少個(gè)元素時(shí)會(huì)觸發(fā)map的擴(kuò)容；Map map1 = new HashMap(10000); 我們存入第 10001個(gè)元素時(shí)會(huì)觸發(fā) map1 擴(kuò)容嗎

6、為什么加載因子的默認(rèn)值是 0.75，并且不推薦我們修改

由于我們平時(shí)關(guān)注的少，一旦碰上這樣的 連擊 + 暴擊，我們往往不知所措、無(wú)從應(yīng)對(duì)；接下來(lái)我們看看上面的 6 個(gè)問(wèn)題，是不是真的難到無(wú)法理解 ，還是我們不夠細(xì)心、在自信的自我認(rèn)為

斗智斗勇，見招拆招

上述的問(wèn)題，我們?nèi)绾稳フ掖鸢?? 方式有很多種，用的最多的，我想應(yīng)該是上網(wǎng)查資料、看別人的博客，但我認(rèn)為最有效、準(zhǔn)確的方式是讀源碼

問(wèn)題 1：table 的初始化

HashMap 的構(gòu)造方法有如下 4 種

/**
?*?構(gòu)造方法?1
?*
?*?通過(guò)?指定的?initialCapacity?和?loadFactor?實(shí)例化一個(gè)空的?HashMap?對(duì)象
?*/
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;
????this.threshold?=?tableSizeFor(initialCapacity);
}

/**
?*?構(gòu)造方法?2
?*
?*?通過(guò)指定的?initialCapacity?和?默認(rèn)的?loadFactor(0.75)?實(shí)例化一個(gè)空的?HashMap?對(duì)象
?*/
public?HashMap(int?initialCapacity)?{
????this(initialCapacity,?DEFAULT_LOAD_FACTOR);
}

/**
?*?構(gòu)造方法?3
?*
?*?通過(guò)默認(rèn)的?initialCapacity?和?默認(rèn)的?loadFactor(0.75)?實(shí)例化一個(gè)空的?HashMap?對(duì)象
?*/
public?HashMap()?{
????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?//?all?other?fields?defaulted
}

/**
?*
?*?構(gòu)造方法?4
?*?通過(guò)指定的?Map?對(duì)象實(shí)例化一個(gè)?HashMap?對(duì)象
?*/
public?HashMap(Map?m)?{
????this.loadFactor?=?DEFAULT_LOAD_FACTOR;
????putMapEntries(m,?false);
}

構(gòu)造方式 4 和 構(gòu)造方式 1 實(shí)際應(yīng)用的不多，構(gòu)造方式 2 直接調(diào)用的 1（底層實(shí)現(xiàn)完全一致），構(gòu)造方式 2 和 構(gòu)造方式 3 比較常用，而最常用的是構(gòu)造方式 3；此時(shí)我們以構(gòu)造方式 3 為前提來(lái)分析，而構(gòu)造方式 2 我們則在問(wèn)題 5 中來(lái)分析

使用方式 1 實(shí)例化 HashMap 的時(shí)候，table 并未進(jìn)行初始化，那 table 是何時(shí)進(jìn)行初始化的了 ？平時(shí)我們是如何使用 HashMap 的，先實(shí)例化、然后 put、然后進(jìn)行其他操作，如下

Map?map?=?new?HashMap();
map.put("name",?"張三");
map.put("age",?21);

//?后續(xù)操作
...

既然實(shí)例化的時(shí)候未進(jìn)行 table 的初始化，那是不是在 put 的時(shí)候初始化的了，我們來(lái)確認(rèn)下

resize() 初始化 table 或 對(duì) table 進(jìn)行雙倍擴(kuò)容，源碼如下（注意看注釋）

/**
?*?Initializes?or?doubles?table?size.??If?null,?allocates?in
?*?accord?with?initial?capacity?target?held?in?field?threshold.
?*?Otherwise,?because?we?are?using?power-of-two?expansion,?the
?*?elements?from?each?bin?must?either?stay?at?same?index,?or?move
?*?with?a?power?of?two?offset?in?the?new?table.
?*
?*?@return?the?table
?*/
final?Node[]?resize()?{
????Node[]?oldTab?=?table;????????????????????//?第一次?put?的時(shí)候，table?=?null
????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;?//?oldCap?=?0
????int?oldThr?=?threshold;????????????????????????//?threshold=0,?oldThr?=?0
????int?newCap,?newThr?=?0;
????if?(oldCap?>?0)?{????//?條件不滿足，往下走
????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????threshold?=?Integer.MAX_VALUE;
????????????return?oldTab;
????????}
????????else?if?((newCap?=?oldCap?<1)??????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????newThr?=?oldThr?<1;?//?double?threshold
????}
????else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold
????????newCap?=?oldThr;
????else?{???????????????//?zero?initial?threshold?signifies?using?defaults?走到這里，進(jìn)行默認(rèn)初始化
????????newCap?=?DEFAULT_INITIAL_CAPACITY;????//?DEFAULT_INITIAL_CAPACITY?=?1?<
????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);????//?newThr?=?0.75?*?16?=?12;
????}
????if?(newThr?==?0)?{????//?條件不滿足
????????float?ft?=?(float)newCap?*?loadFactor;
????????newThr?=?(newCap?float)MAXIMUM_CAPACITY??
??????????????????(int)ft?:?Integer.MAX_VALUE);
????}
????threshold?=?newThr;????????//?threshold?=?12;?重置閥值為12
????@SuppressWarnings({"rawtypes","unchecked"})
????????Node[]?newTab?=?(Node[])new?Node[newCap];?????//?初始化?newTab,?length?=?16;
????table?=?newTab;????????????//?table?初始化完成,?length?=?16;
????if?(oldTab?!=?null)?{????//?此時(shí)條件不滿足，后續(xù)擴(kuò)容的時(shí)候，走此if分支?將數(shù)組元素復(fù)制到新數(shù)組
????????for?(int?j?=?0;?j?????????????Node?e;
????????????if?((e?=?oldTab[j])?!=?null)?{
????????????????oldTab[j]?=?null;
????????????????if?(e.next?==?null)
????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;
????????????????else?if?(e?instanceof?TreeNode)
????????????????????((TreeNode)e).split(this,?newTab,?j,?oldCap);
????????????????else?{?//?preserve?order
????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????Node?next;
????????????????????do?{
????????????????????????next?=?e.next;
????????????????????????if?((e.hash?&?oldCap)?==?0)?{
????????????????????????????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;
????????????????????}
????????????????????if?(hiTail?!=?null)?{
????????????????????????hiTail.next?=?null;
????????????????????????newTab[j?+?oldCap]?=?hiHead;
????????????????????}
????????????????}
????????????}
????????}
????}
????return?newTab;????//?新數(shù)組
}

自此，問(wèn)題 1 的答案就明了了

table 的初始化時(shí)機(jī)是什么時(shí)候

一般情況下，在第一次 put 的時(shí)候，調(diào)用 resize 方法進(jìn)行 table 的初始化（懶初始化，懶加載思想在很多框架中都有應(yīng)用！）

初始化的 table.length 是多少、閥值（threshold）是多少，實(shí)際能容下多少元素

• 默認(rèn)情況下，table.length = 16; 指定了 initialCapacity 的情況放到問(wèn)題 5 中分析

• 默認(rèn)情況下，threshold = 12; 指定了 initialCapacity 的情況放到問(wèn)題 5 中分析

• 默認(rèn)情況下，能存放 12 個(gè)元素，當(dāng)存放第 13 個(gè)元素后進(jìn)行擴(kuò)容

問(wèn)題 2 ：table 的擴(kuò)容

putVal 源碼如下

/**
?*?Implements?Map.put?and?related?methods
?*
?*?@param?hash?hash?for?key
?*?@param?key?the?key
?*?@param?value?the?value?to?put
?*?@param?onlyIfAbsent?if?true,?don't?change?existing?value
?*?@param?evict?if?false,?the?table?is?in?creation?mode.
?*?@return?previous?value,?or?null?if?none
?*/
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)
????????n?=?(tab?=?resize()).length;
????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????tab[i]?=?newNode(hash,?key,?value,?null);
????else?{
????????Node?e;?K?k;
????????if?(p.hash?==?hash?&&
????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????e?=?p;
????????else?if?(p?instanceof?TreeNode)
????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);
????????else?{
????????????for?(int?binCount?=?0;?;?++binCount)?{
????????????????if?((e?=?p.next)?==?null)?{
????????????????????p.next?=?newNode(hash,?key,?value,?null);
????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
????????????????????????treeifyBin(tab,?hash);
????????????????????break;
????????????????}
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????break;
????????????????p?=?e;
????????????}
????????}
????????if?(e?!=?null)?{?//?existing?mapping?for?key
????????????V?oldValue?=?e.value;
????????????if?(!onlyIfAbsent?||?oldValue?==?null)
????????????????e.value?=?value;
????????????afterNodeAccess(e);
????????????return?oldValue;
????????}
????}
????++modCount;
????if?(++size?>?threshold)?????????????//?當(dāng)size（已存放元素個(gè)數(shù)）?>?thrshold（閥值），進(jìn)行擴(kuò)容
????????resize();
????afterNodeInsertion(evict);
????return?null;
}

還是調(diào)用 resize() 進(jìn)行擴(kuò)容，但與初始化時(shí)不同（注意看注釋）

/**
?*?Initializes?or?doubles?table?size.??If?null,?allocates?in
?*?accord?with?initial?capacity?target?held?in?field?threshold.
?*?Otherwise,?because?we?are?using?power-of-two?expansion,?the
?*?elements?from?each?bin?must?either?stay?at?same?index,?or?move
?*?with?a?power?of?two?offset?in?the?new?table.
?*
?*?@return?the?table
?*/
final?Node[]?resize()?{
????Node[]?oldTab?=?table;????????????????????//?此時(shí)的?table?!=?null，oldTab?指向舊的?table
????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;?//?oldCap?=?table.length;?第一次擴(kuò)容時(shí)是?16
????int?oldThr?=?threshold;????????????????????????//?threshold=12,?oldThr?=?12;
????int?newCap,?newThr?=?0;
????if?(oldCap?>?0)?{????//?條件滿足，走此分支
????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????threshold?=?Integer.MAX_VALUE;
????????????return?oldTab;
????????}
????????else?if?((newCap?=?oldCap?<1)?//?oldCap左移一位;?newCap?=?16?<
?????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????newThr?=?oldThr?<1;?//?double?threshold????????????//?newThr?=?12?<
????}
????else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold
????????newCap?=?oldThr;
????else?{???????????????//?zero?initial?threshold?signifies?using?defaults
????????newCap?=?DEFAULT_INITIAL_CAPACITY;????//?DEFAULT_INITIAL_CAPACITY?=?1?<
????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);
????}
????if?(newThr?==?0)?{????//?條件不滿足
????????float?ft?=?(float)newCap?*?loadFactor;
????????newThr?=?(newCap?float)MAXIMUM_CAPACITY??
??????????????????(int)ft?:?Integer.MAX_VALUE);
????}
????threshold?=?newThr;????????//?threshold?=?newThr?=?24;?重置閥值為?24
????@SuppressWarnings({"rawtypes","unchecked"})
????????Node[]?newTab?=?(Node[])new?Node[newCap];?????//?初始化?newTab,?length?=?32;
????table?=?newTab;????????????//?table?指向?newTab,?length?=?32;
????if?(oldTab?!=?null)?{????//?擴(kuò)容后，將?oldTab(舊table)?中的元素移到?newTab（新table）中
????????for?(int?j?=?0;?j?????????????Node?e;
????????????if?((e?=?oldTab[j])?!=?null)?{
????????????????oldTab[j]?=?null;
????????????????if?(e.next?==?null)
????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;????????//?
????????????????else?if?(e?instanceof?TreeNode)
????????????????????((TreeNode)e).split(this,?newTab,?j,?oldCap);
????????????????else?{?//?preserve?order
????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????Node?next;
????????????????????do?{
????????????????????????next?=?e.next;
????????????????????????if?((e.hash?&?oldCap)?==?0)?{
????????????????????????????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;
????????????????????}
????????????????????if?(hiTail?!=?null)?{
????????????????????????hiTail.next?=?null;
????????????????????????newTab[j?+?oldCap]?=?hiHead;
????????????????????}
????????????????}
????????????}
????????}
????}
????return?newTab;
}

自此，問(wèn)題 2 的答案也就清晰了

什么時(shí)候觸發(fā)擴(kuò)容，擴(kuò)容之后的 table.length、閥值各是多少

• 當(dāng) size > threshold 的時(shí)候進(jìn)行擴(kuò)容

• 擴(kuò)容之后的 table.length = 舊 table.length * 2,

• 擴(kuò)容之后的 threshold = 舊 threshold * 2

問(wèn)題 3、4 ：2 的 n 次冪

table 是一個(gè)數(shù)組，那么如何最快的將元素 e 放入數(shù)組 ？當(dāng)然是找到元素 e 在 table 中對(duì)應(yīng)的位置 index ，然后 table[index] = e; 就好了；如何找到 e 在 table 中的位置了 ？

我們知道只能通過(guò)數(shù)組下標(biāo)（索引）操作數(shù)組，而數(shù)組的下標(biāo)類型又是 int ，如果 e 是 int 類型，那好說(shuō)，就直接用 e 來(lái)做數(shù)組下標(biāo)（若 e > table.length，則可以 e % table.length 來(lái)獲取下標(biāo)），可 key - value 中的 key 類型不一定，所以我們需要一種統(tǒng)一的方式將 key 轉(zhuǎn)換成 int ，最好是一個(gè) key 對(duì)應(yīng)一個(gè)唯一的 int (目前還不可能, int有范圍限制，對(duì)轉(zhuǎn)換方法要求也極高)，所以引入了 hash 方法

static?final?int?hash(Object?key)?{
????int?h;
????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);　　//?這里的處理，有興趣的可以琢磨下；能夠減少碰撞
}

實(shí)現(xiàn) key 到 int 的轉(zhuǎn)換（關(guān)于 hash，本文不展開討論）。拿到了 key 對(duì)應(yīng)的 int h 之后，我們最容易想到的對(duì) value 的 put 和 get 操作也許如下

//?put
table[h?%?table.length]?=?value;

//?get
e?=?table[h?%?table.length];

直接取模是我們最容易想到的獲取下標(biāo)的方法，但是最高效的方法嗎 ？

我們知道計(jì)算機(jī)中的四則運(yùn)算最終都會(huì)轉(zhuǎn)換成二進(jìn)制的位運(yùn)算

我們可以發(fā)現(xiàn)，只有 & 數(shù)是1時(shí)，& 運(yùn)算的結(jié)果與被 & 數(shù)一致

1&1=1;
0&1=0;
1&0=0;
0&0=0;

這同樣適用于多位操作數(shù)

1010&1111=1010;??????=>?10&15=10;
1011&1111=1011;??????=>?11&15=11;
01010&10000=00000;???=>?10&16=0;
01011&10000=00000;???=>?11&16=0;

我們是不是又有所發(fā)現(xiàn)：10 & 16 與 11 & 16 得到的結(jié)果一樣，也就是沖突（碰撞）了，那么 10 和 11 對(duì)應(yīng)的 value 會(huì)在同一個(gè)鏈表中，而 table 的有些位置則永遠(yuǎn)不會(huì)有元素，這就導(dǎo)致 table 的空間未得到充分利用，同時(shí)還降低了 put 和 get 的效率（對(duì)比數(shù)組和鏈表）；由于是 2 個(gè)數(shù)進(jìn)行 & 運(yùn)算，所以結(jié)果由這兩個(gè)數(shù)決定，如果我們把這兩個(gè)數(shù)都做下限制，那得到的結(jié)果是不是可控制在我們想要的范圍內(nèi)了 ？

我們需要利用好 & 運(yùn)算的特點(diǎn)，當(dāng)右邊的數(shù)的低位二進(jìn)制是連續(xù)的 1 ，且左邊是一個(gè)均勻的數(shù)（需要 hash 方法實(shí)現(xiàn)，盡量保證 key 的 h 唯一），那么得到的結(jié)果就比較完美了。低位二進(jìn)制連續(xù)的 1，我們很容易想到 2^n - 1; 而關(guān)于左邊均勻的數(shù)，則通過(guò) hash 方法來(lái)實(shí)現(xiàn)，這里不做細(xì)究了。更多面試題，歡迎關(guān)注 公眾號(hào)Java面試題精選

自此，2 的 n 次冪的相關(guān)問(wèn)題就清楚了

table 的 length 為什么是 2 的 n 次冪

為了利用位運(yùn)算 & 求 key 的下標(biāo)

求索引的時(shí)候?yàn)槭裁词牵篽&(length-1)，而不是 h&length，更不是 h%length

• h%length 效率不如位運(yùn)算快

• h&length 會(huì)提高碰撞幾率，導(dǎo)致 table 的空間得不到更充分的利用、降低 table 的操作效率

給各位留個(gè)疑問(wèn)：為什么不直接用 2^n-1 作為 table.length ？歡迎評(píng)論區(qū)留言

問(wèn)題 5：指定 initialCapacity

當(dāng)我們指定了 initialCapacity，HashMap的構(gòu)造方法有些許不同，如下所示　

調(diào)用 tableSizeFor 進(jìn)行 threshold 的初始化

/**
?*?Returns?a?power?of?two?size?for?the?given?target?capacity.
?*?返回?>=?cap?最小的?2^n
?*?cap?=?10,?則返回?2^4?=?16;
?*?cap?=?5,?則返回?2^3?=?8;
?*/
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;
}

雖然此處初始化的是 threshold，但后面初始化 table 的時(shí)候，會(huì)將其用于 table 的 length，同時(shí)會(huì)重置 threshold 為 table.length * loadFactor

自此，問(wèn)題 5 也就清楚了

Map map = new HashMap(1000); 當(dāng)我們存入多少個(gè)元素時(shí)會(huì)觸發(fā)map的擴(kuò)容

此時(shí)的 table.length = 2^10 = 1024; threshold = 1024 * 0.75 = 768; 所以存入第 769 個(gè)元素時(shí)進(jìn)行擴(kuò)容

Map map1 = new HashMap(10000); 我們存入第 10001個(gè)元素時(shí)會(huì)觸發(fā) map1 擴(kuò)容嗎

此時(shí)的 table.length = 2^14 = 16384; threshold = 16384 * 0.75 = 12288; 所以存入第 10001 個(gè)元素時(shí)不會(huì)進(jìn)行擴(kuò)容

問(wèn)題6：加載因子

為什么加載因子的默認(rèn)值是 0.75，并且不推薦我們修改

• 如果loadFactor太小，那么map中的table需要不斷的擴(kuò)容，擴(kuò)容是個(gè)耗時(shí)的過(guò)程

• 如果loadFactor太大，那么map中table放滿了也不不會(huì)擴(kuò)容，導(dǎo)致沖突越來(lái)越多，解決沖突而起的鏈表越來(lái)越長(zhǎng)，效率越來(lái)越低

• 而 0.75 這是一個(gè)折中的值，是一個(gè)比較理想的值

總結(jié)

1、table.length = 2^n，是為了能利用位運(yùn)算（&）來(lái)求 key 的下標(biāo)，而 h&(length-1) 是為了充分利用 table 的空間，并減少 key 的碰撞

2、加載因子太小， table 需要不斷的擴(kuò)容，影響 put 效率；太大會(huì)導(dǎo)致碰撞越來(lái)越多，鏈表越來(lái)越長(zhǎng)（轉(zhuǎn)紅黑樹），影響效率；0.75 是一個(gè)比較理想的中間值

3、table.length = 2^n、hash 方法獲取 key 的 h、加載因子 0.75、數(shù)組 + 鏈表（或紅黑樹），一環(huán)扣一環(huán)，保證了 key 在 table 中的均勻分配，充分利用了空間，也保證了操作效率，環(huán)環(huán)相扣的，而不是心血來(lái)潮的隨意處理；缺了一環(huán)，其他的環(huán)就無(wú)意義了！

4、網(wǎng)上有個(gè) put 方法的流程圖畫的挺好，我就偷懶了

推薦閱讀：

【80期】說(shuō)出Java創(chuàng)建線程的三種方式及對(duì)比

【79期】別找了，回答Spring中Bean的生命周期，這里幫你總結(jié)好了！

【78期】別找了，Java集合面試問(wèn)題這里幫你總結(jié)好了！

5T技術(shù)資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機(jī)，樹莓派，等等。在公眾號(hào)內(nèi)回復(fù)「2048」，即可免費(fèi)獲取??！

微信掃描二維碼，關(guān)注我的公眾號(hào)

朕已閱?