HashMap 面试常见的6连问,你能扛得住吗?
今日推薦
高手過招,招招致命
JDK1.8 中 HashMap 的底層實現(xiàn),我相信大家都能說上來個 一二,底層數(shù)據(jù)結(jié)構(gòu) 數(shù)組 + 鏈表(或紅黑樹) ,源碼如下
/**??*?數(shù)組??*/?? transient?Node<K,V>[]?table;??/**??*?鏈表結(jié)構(gòu)??*/?? static?class?Node<K,V>?implements?Map.Entry<K,V>?{??final?int?hash;??final?K?key;??V?value;??Node<K,V>?next;??Node(int?hash,?K?key,?V?value,?Node<K,V>?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<K,V>?parent;??//?red-black?tree?links??TreeNode<K,V>?left;??TreeNode<K,V>?right;??TreeNode<K,V>?prev;????//?needed?to?unlink?next?upon?deletion??boolean?red;??...圖片但面試往往會問的比較細,例如下面的容量問題,我們能答上來幾個?
1、table 的初始化時機是什么時候,初始化的 table.length 是多少、閥值(threshold)是多少,實際能容下多少元素
2、什么時候觸發(fā)擴容,擴容之后的 table.length、閥值各是多少?
3、table 的 length 為什么是 2 的 n 次冪
4、求索引的時候為什么是:h&(length-1),而不是 h&length,更不是 h%length
5、 Map map = new HashMap(1000); 當(dāng)我們存入多少個元素時會觸發(fā)map的擴容;Map map1 = new HashMap(10000); 我們存入第 10001個元素時會觸發(fā) map1 擴容嗎
6、為什么加載因子的默認值是 0.75,并且不推薦我們修改
由于我們平時關(guān)注的少,一旦碰上這樣的 連擊 + 暴擊,我們往往不知所措、無從應(yīng)對;接下來我們看看上面的 6 個問題,是不是真的難到無法理解 ,還是我們不夠細心、在自信的自我認為
斗智斗勇,見招拆招
上述的問題,我們?nèi)绾稳フ掖鸢?? 方式有很多種,用的最多的,我想應(yīng)該是上網(wǎng)查資料、看別人的博客,但我認為最有效、準(zhǔn)確的方式是讀源碼
問題 1:table 的初始化
HashMap 的構(gòu)造方法有如下 4 種
/**??*?構(gòu)造方法?1??*??*?通過?指定的?initialCapacity?和?loadFactor?實例化一個空的?HashMap?對象??*/?? 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??*??*?通過指定的?initialCapacity?和?默認的?loadFactor(0.75)?實例化一個空的?HashMap?對象??*/?? public?HashMap(int?initialCapacity)?{??this(initialCapacity,?DEFAULT_LOAD_FACTOR);?? }??/**??*?構(gòu)造方法?3??*??*?通過默認的?initialCapacity?和?默認的?loadFactor(0.75)?實例化一個空的?HashMap?對象??*/?? public?HashMap()?{??this.loadFactor?=?DEFAULT_LOAD_FACTOR;?//?all?other?fields?defaulted?? }??/**??*??*?構(gòu)造方法?4??*?通過指定的?Map?對象實例化一個?HashMap?對象??*/?? public?HashMap(Map<??extends?K,???extends?V>?m)?{??this.loadFactor?=?DEFAULT_LOAD_FACTOR;??putMapEntries(m,?false);?? }構(gòu)造方式 4 和 構(gòu)造方式 1 實際應(yīng)用的不多,構(gòu)造方式 2 直接調(diào)用的 1(底層實現(xiàn)完全一致),構(gòu)造方式 2 和 構(gòu)造方式 3 比較常用,而最常用的是構(gòu)造方式 3;此時我們以構(gòu)造方式 3 為前提來分析,而構(gòu)造方式 2 我們則在問題 5 中來分析
使用方式 1 實例化 HashMap 的時候,table 并未進行初始化,那 table 是何時進行初始化的了 ?平時我們是如何使用 HashMap 的,先實例化、然后 put、然后進行其他操作,如下
Map<String,Object>?map?=?new?HashMap();?? map.put("name",?"張三");?? map.put("age",?21);??//?后續(xù)操作?? ...既然實例化的時候未進行 table 的初始化,那是不是在 put 的時候初始化的了,我們來確認下
圖片resize() 初始化 table 或 對 table 進行雙倍擴容,源碼如下(注意看注釋)
/**??*?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<K,V>[]?resize()?{??Node<K,V>[]?oldTab?=?table;????????????????????//?第一次?put?的時候,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)?<?MAXIMUM_CAPACITY?&&??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?走到這里,進行默認初始化??newCap?=?DEFAULT_INITIAL_CAPACITY;????//?DEFAULT_INITIAL_CAPACITY?=?1?<<?4?=?16,?newCap?=?16;??newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);????//?newThr?=?0.75?*?16?=?12;??}??if?(newThr?==?0)?{????//?條件不滿足??float?ft?=?(float)newCap?*?loadFactor;??newThr?=?(newCap?<?MAXIMUM_CAPACITY?&&?ft?<?(float)MAXIMUM_CAPACITY????(int)ft?:?Integer.MAX_VALUE);??}??threshold?=?newThr;????????//?threshold?=?12;?重置閥值為12??@SuppressWarnings({"rawtypes","unchecked"})??Node<K,V>[]?newTab?=?(Node<K,V>[])new?Node[newCap];?????//?初始化?newTab,?length?=?16;??table?=?newTab;????????????//?table?初始化完成,?length?=?16;??if?(oldTab?!=?null)?{????//?此時條件不滿足,后續(xù)擴容的時候,走此if分支?將數(shù)組元素復(fù)制到新數(shù)組??for?(int?j?=?0;?j?<?oldCap;?++j)?{??Node<K,V>?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<K,V>)e).split(this,?newTab,?j,?oldCap);??else?{?//?preserve?order??Node<K,V>?loHead?=?null,?loTail?=?null;??Node<K,V>?hiHead?=?null,?hiTail?=?null;??Node<K,V>?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ù)組?? }自此,問題 1 的答案就明了了
table 的初始化時機是什么時候
一般情況下,在第一次 put 的時候,調(diào)用 resize 方法進行 table 的初始化(懶初始化,懶加載思想在很多框架中都有應(yīng)用!)
初始化的 table.length 是多少、閥值(threshold)是多少,實際能容下多少元素
默認情況下,table.length = 16; 指定了 initialCapacity 的情況放到問題 5 中分析
默認情況下,threshold = 12; 指定了 initialCapacity 的情況放到問題 5 中分析
默認情況下,能存放 12 個元素,當(dāng)存放第 13 個元素后進行擴容
問題 2 :table 的擴容
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<K,V>[]?tab;?Node<K,V>?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<K,V>?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<K,V>)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(已存放元素個數(shù))?>?thrshold(閥值),進行擴容??resize();??afterNodeInsertion(evict);??return?null;?? }還是調(diào)用 resize() 進行擴容,但與初始化時不同(注意看注釋)
/**??*?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<K,V>[]?resize()?{??Node<K,V>[]?oldTab?=?table;????????????????????//?此時的?table?!=?null,oldTab?指向舊的?table??int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;?//?oldCap?=?table.length;?第一次擴容時是?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)?<?MAXIMUM_CAPACITY?&&????//?oldCap左移一位;?newCap?=?16?<<?1?=?32;??oldCap?>=?DEFAULT_INITIAL_CAPACITY)??newThr?=?oldThr?<<?1;?//?double?threshold????????????//?newThr?=?12?<<?1?=?24;??}??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?<<?4?=?16,?newCap?=?16;??newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);??}??if?(newThr?==?0)?{????//?條件不滿足??float?ft?=?(float)newCap?*?loadFactor;??newThr?=?(newCap?<?MAXIMUM_CAPACITY?&&?ft?<?(float)MAXIMUM_CAPACITY????(int)ft?:?Integer.MAX_VALUE);??}??threshold?=?newThr;????????//?threshold?=?newThr?=?24;?重置閥值為?24??@SuppressWarnings({"rawtypes","unchecked"})??Node<K,V>[]?newTab?=?(Node<K,V>[])new?Node[newCap];?????//?初始化?newTab,?length?=?32;??table?=?newTab;????????????//?table?指向?newTab,?length?=?32;??if?(oldTab?!=?null)?{????//?擴容后,將?oldTab(舊table)?中的元素移到?newTab(新table)中??for?(int?j?=?0;?j?<?oldCap;?++j)?{??Node<K,V>?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<K,V>)e).split(this,?newTab,?j,?oldCap);??else?{?//?preserve?order??Node<K,V>?loHead?=?null,?loTail?=?null;??Node<K,V>?hiHead?=?null,?hiTail?=?null;??Node<K,V>?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;?? }自此,問題 2 的答案也就清晰了
什么時候觸發(fā)擴容,擴容之后的 table.length、閥值各是多少
當(dāng) size > threshold 的時候進行擴容
擴容之后的 table.length = 舊 table.length * 2,
擴容之后的 threshold = 舊 threshold * 2
問題 3、4 :2 的 n 次冪
table 是一個數(shù)組,那么如何最快的將元素 e 放入數(shù)組 ?當(dāng)然是找到元素 e 在 table 中對應(yīng)的位置 index ,然后 table[index] = e; 就好了;如何找到 e 在 table 中的位置了 ?
我們知道只能通過數(shù)組下標(biāo)(索引)操作數(shù)組,而數(shù)組的下標(biāo)類型又是 int ,如果 e 是 int 類型,那好說,就直接用 e 來做數(shù)組下標(biāo)(若 e > table.length,則可以 e % table.length 來獲取下標(biāo)),可 key - value 中的 key 類型不一定,所以我們需要一種統(tǒng)一的方式將 key 轉(zhuǎn)換成 int ,最好是一個 key 對應(yīng)一個唯一的 int (目前還不可能, int有范圍限制,對轉(zhuǎn)換方法要求也極高),所以引入了 hash 方法
static?final?int?hash(Object?key)?{??int?h;??return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);??//?這里的處理,有興趣的可以琢磨下;能夠減少碰撞?? }實現(xiàn) key 到 int 的轉(zhuǎn)換(關(guān)于 hash,本文不展開討論)。拿到了 key 對應(yīng)的 int h 之后,我們最容易想到的對 value 的 put 和 get 操作也許如下
//?put?? table[h?%?table.length]?=?value;??//?get?? e?=?table[h?%?table.length];直接取模是我們最容易想到的獲取下標(biāo)的方法,但是最高效的方法嗎 ?
我們知道計算機中的四則運算最終都會轉(zhuǎn)換成二進制的位運算
圖片我們可以發(fā)現(xiàn),只有 & 數(shù)是1時,& 運算的結(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 對應(yīng)的 value 會在同一個鏈表中,而 table 的有些位置則永遠不會有元素,這就導(dǎo)致 table 的空間未得到充分利用,同時還降低了 put 和 get 的效率(對比數(shù)組和鏈表);由于是 2 個數(shù)進行 & 運算,所以結(jié)果由這兩個數(shù)決定,如果我們把這兩個數(shù)都做下限制,那得到的結(jié)果是不是可控制在我們想要的范圍內(nèi)了 ?
我們需要利用好 & 運算的特點,當(dāng)右邊的數(shù)的低位二進制是連續(xù)的 1 ,且左邊是一個均勻的數(shù)(需要 hash 方法實現(xiàn),盡量保證 key 的 h 唯一),那么得到的結(jié)果就比較完美了。低位二進制連續(xù)的 1,我們很容易想到 2^n - 1; 而關(guān)于左邊均勻的數(shù),則通過 hash 方法來實現(xiàn),這里不做細究了。更多面試題,歡迎關(guān)注 公眾號Java面試題精選
自此,2 的 n 次冪的相關(guān)問題就清楚了
table 的 length 為什么是 2 的 n 次冪
為了利用位運算 & 求 key 的下標(biāo)
求索引的時候為什么是:h&(length-1),而不是 h&length,更不是 h%length
h%length 效率不如位運算快
h&length 會提高碰撞幾率,導(dǎo)致 table 的空間得不到更充分的利用、降低 table 的操作效率
給各位留個疑問:為什么不直接用 2^n-1 作為 table.length ?歡迎評論區(qū)留言
問題 5:指定 initialCapacity
當(dāng)我們指定了 initialCapacity,HashMap的構(gòu)造方法有些許不同,如下所示
圖片調(diào)用 tableSizeFor 進行 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 的時候,會將其用于 table 的 length,同時會重置 threshold 為 table.length * loadFactor
自此,問題 5 也就清楚了
Map map = new HashMap(1000); 當(dāng)我們存入多少個元素時會觸發(fā)map的擴容
此時的 table.length = 2^10 = 1024; threshold = 1024 * 0.75 = 768; 所以存入第 769 個元素時進行擴容
Map map1 = new HashMap(10000); 我們存入第 10001個元素時會觸發(fā) map1 擴容嗎
此時的 table.length = 2^14 = 16384; threshold = 16384 * 0.75 = 12288; 所以存入第 10001 個元素時不會進行擴容
問題6:加載因子
為什么加載因子的默認值是 0.75,并且不推薦我們修改
如果loadFactor太小,那么map中的table需要不斷的擴容,擴容是個耗時的過程
如果loadFactor太大,那么map中table放滿了也不不會擴容,導(dǎo)致沖突越來越多,解決沖突而起的鏈表越來越長,效率越來越低
而 0.75 這是一個折中的值,是一個比較理想的值
總結(jié)
1、table.length = 2^n,是為了能利用位運算(&)來求 key 的下標(biāo),而 h&(length-1) 是為了充分利用 table 的空間,并減少 key 的碰撞
2、加載因子太小, table 需要不斷的擴容,影響 put 效率;太大會導(dǎo)致碰撞越來越多,鏈表越來越長(轉(zhuǎn)紅黑樹),影響效率;0.75 是一個比較理想的中間值
3、table.length = 2^n、hash 方法獲取 key 的 h、加載因子 0.75、數(shù)組 + 鏈表(或紅黑樹),一環(huán)扣一環(huán),保證了 key 在 table 中的均勻分配,充分利用了空間,也保證了操作效率,環(huán)環(huán)相扣的,而不是心血來潮的隨意處理;缺了一環(huán),其他的環(huán)就無意義了!
4、網(wǎng)上有個 put 方法的流程圖畫的挺好,我就偷懶了
圖片參考
java提高篇(二三)-----HashMap
【原創(chuàng)】HashMap復(fù)習(xí)精講
面試官:"準(zhǔn)備用HashMap存1w條數(shù)據(jù),構(gòu)造時傳10000還會觸發(fā)擴容嗎?"
來源:cnblogs.com/youzhibing/p/11833040.html
推薦文章1、一款高顏值的 SpringBoot+JPA 博客項目2、超優(yōu) Vue+Element+Spring 中后端解決方案3、推薦幾個支付項目!4、推薦一個 Java 企業(yè)信息化系統(tǒng)5、一款基于 Spring Boot 的現(xiàn)代化社區(qū)(論壇/問答/社交網(wǎng)絡(luò)/博客)總結(jié)
以上是生活随笔為你收集整理的HashMap 面试常见的6连问,你能扛得住吗?的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 公司用的 MySQL 团队开发规范,非常
- 下一篇: 实现序列化与反序列化,一定要绕开这些坑!