為什么不管大廠還是小廠，面試總是要提到 HashMap？
本文轉(zhuǎn)載自微信公眾號「Java極客技術(shù)」，作者鴨血粉絲。轉(zhuǎn)載本文請聯(lián)系Java極客技術(shù)公眾號。
Hello，大家好，我是阿粉~
不知道大家最近有沒有刷過 Java 面試題，有沒有發(fā)現(xiàn)幾乎所有面試題或多或少都會包括 HashMap 面試題。
為什么 Java 中小小的一個 HashMap，值得在面試中被反復(fù)提到?
阿粉認(rèn)為是因為 HashMap 太重要了，大家回看一下自己的業(yè)務(wù)代碼，是不是都有在使用 HashMap ?
即使你真的沒有直接使用，但是你使用的一些中間件，或者一些開源框架，這些代碼肯定使用 HashMap 完成相關(guān)邏輯。
而 HashMap 包含很多核心知識點，從這些知識點可以考察出一個面試者基本知識掌握情況。
其實就算沒有面試，我們也應(yīng)該或多乎或少去了解 一下 HashMap 基本實現(xiàn)原理。因為如果使用 HashMap 不當(dāng)，很容易寫出一連串 Bug，而且可能還不容易排查。
HashMap 面試題網(wǎng)上很多，但是其實怎么問他都離不開這些核心知識點。
這就像我們以前解答數(shù)學(xué)題一樣，背后答案都是圍繞核心數(shù)學(xué)公式。
所以我們只要掌握 HashMap 核心知識點，就不用再怕面試中再問到。
這里阿粉整理一下，HashMap 涉及核心知識點如下：
- 底層數(shù)據(jù)結(jié)構(gòu)
- Hash 算法
- 尋址算法
- 擴(kuò)容
- 多線程并發(fā)
底層數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)與算法是最近面試越來越注重考查的一方面，尤其是對于校招來講，這一塊百分百會涉及。
而 HashMap 底層結(jié)構(gòu)一下子就涉及三大數(shù)據(jù)結(jié)構(gòu)，數(shù)組、鏈表、紅黑樹。
數(shù)組
HashMap 中元素實際保存在一個個 Node 中，而Node 類保存在底層數(shù)組中。
以上代碼來自 JDK1.8，JDK1.7 為 Entry 類型。
實際上 Node 為 Entry 類的子類
鏈表
我們觀察一下Node 類的數(shù)據(jù)結(jié)構(gòu)，
可以發(fā)現(xiàn) Node 類中有一個 next 字段，用于保存下一個 Node 元素，通過這種方式就形成一個單向的鏈表。
那為什么需要鏈表那?
這可能與下面說道 Hash算法有關(guān)，因為再好的 Hash 算法，都有可能導(dǎo)致不同輸入產(chǎn)生相同的輸出。
來自:阮一峰的博客
如果不同的輸入得到了同一個哈希值，就發(fā)生了"哈希碰撞"(collision)。
哈希碰撞解決辦法很多，這里 HashMap 就采用拉鏈法，即使用一個鏈表保存碰撞的元素的。
其他辦法還有：
- 線行探查法
- 平方探查法
- 雙散列函數(shù)探查法
紅黑樹
由于鏈表查找元素復(fù)雜度為 O(N)，如果 HashMap 哈希碰撞很厲害，從而導(dǎo)致大部分元素落在同一個鏈表上，這就會導(dǎo)致 HashMap 性能會下降，極端一點 HashMap O(1) 查詢復(fù)雜度退化成 O(N)的復(fù)雜度。
JDK1.8 中引入紅黑樹數(shù)據(jù)結(jié)構(gòu)，當(dāng)鏈表元素等于 8 時，鏈表轉(zhuǎn)化為紅黑樹，這樣查找復(fù)雜度就可以為 O(logn)。
圖片來自網(wǎng)絡(luò)
那為什么使用紅黑樹，而不是使用其他二叉樹，?
這是因為紅黑樹對于新增與刪除的操作也都能保持O(logn) 新增,這樣就完美兼顧了查找與新增性能。
面試題
看完這個知識點，其實可以提很多相關(guān)數(shù)據(jù)結(jié)構(gòu)面試題，比如數(shù)組與鏈表區(qū)別。
所以看完這個，我們就需要去整理學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)相關(guān)知識。
Hash 算法
這里我們僅僅介紹一下 JDK1.8 Hash 算法。
它使用 key 的 hashcode 高低 16 位異或的方式計算產(chǎn)生。
通過這種方式，在后面尋址算法計算時候，降低碰撞的可能性。
尋址算法
當(dāng)我們計算得到 Hash 值以后，我們還需要計算這個 Hash 值在數(shù)組中的位置。
簡單的方式我們可以直接使用求模的方式定位，比如
- hash=1000
- table.size=16
- n=hash%table.size=8
但是 HashMap 采用的是另外一種更為精妙的算法：
這種方式等同求模法，但是計算性能會更好，但是這里我們需要注意了，這種方式前提為 n 也就是數(shù)組的長度必須為 2 的冪次方。
這里阿粉就不具體計算了，感興趣的同學(xué)可以網(wǎng)上查找一下推導(dǎo)過程
面試題
為什么 HashMap 擴(kuò)容都是 2 的冪次方?
看完這個，大家這個面試題了吧。
擴(kuò)容
當(dāng) HashMap 元素過多時，這時必須擴(kuò)容，從而保證 HashMap 查找性能。
擴(kuò)容過程，我們就需要涉及以下幾個核心參數(shù)：
- 擴(kuò)展因子：loadFactor
- 實際元素數(shù)量：size
- 數(shù)組長度：capacity
- 擴(kuò)容的閾值大小：threshold=capacity*loadFactor
當(dāng) HashMap 中元素數(shù)量大于 threshold，HashMap 就會開始擴(kuò)容。
JDK1.7 擴(kuò)容的時候，HashMap 每個元素將會重新計算 Hash 值，然后使用尋址算法，查找新的位置。
在 JDk1.8 中，采用了一種更精妙的算法：
其使用 e.hash & oldCap == 0， 元素要么放在原位置，要么放在原位置+原數(shù)組長度。
這里解釋起來比較復(fù)雜，這里阿粉就不再詳細(xì)展開，感興趣同學(xué)可以自行查找一下相關(guān)文章。
面試題
問：加載因子為什么 0.75，而不是其他值?
答：可以說是一個經(jīng)過考量的經(jīng)驗值。加載因子涉及擴(kuò)容，下次擴(kuò)容的閾值=數(shù)組桶的大小*加載因子，如果加載因子太小，這就會導(dǎo)致閾值太小，這就會導(dǎo)致比較容易發(fā)生擴(kuò)容。
如果加載因子太大，那就會導(dǎo)致閾值太大，可能沖突會很多，導(dǎo)致查找效率下降。
多線程并發(fā)
好了，終于到到了最后一個知識點，多線程并發(fā)。
HashMap 在多線程并發(fā)情況下會怎么樣?
這里我們需要分 JDK1.7 與 JDK1.8 來講。
在 JDK1.7 中，由于擴(kuò)容遷移時采用了頭插法，從而將會導(dǎo)致產(chǎn)生死鏈。
- void transfer(Entry[] newTable, boolean rehash) {
- int newCapacity = newTable.length;
- for (Entry<K,V> e : table) {
- while(null != e) {
- Entry<K,V> next = e.next;
- if (rehash) {
- e.hash = null == e.key ? 0 : hash(e.key);
- }
- int i = indexFor(e.hash, newCapacity);
- // 以下代碼導(dǎo)致死鏈的產(chǎn)生
- e.next = newTable[i];
- // 插入到鏈表頭結(jié)點，
- newTable[i] = e;
- e = next;
- }
- }
- }
而一旦產(chǎn)生死鏈，極有可能導(dǎo)致程序陷入死循環(huán)，從而導(dǎo)致 CPU 使用率上升。
JDK1.8 中使用尾插法，從而解決這個問題，但是依然還會存在相關(guān)問題。
比如：
并發(fā)賦值時被覆蓋
并發(fā)的情況下，一個線程的賦值可能被另一個線程覆蓋，這就導(dǎo)致對象的丟失。
size 計算問題
img
每次元素增加完成之后，size 將會加 1。這里采用 ++i方法，天然的并發(fā)不安全。
面試題
關(guān)于并發(fā)，這里可以提到很多面試題。
可以是線程相關(guān)的，也可以是并發(fā)編程相關(guān)。
不過如果面試官既然已經(jīng)提到這里，我們可以試著將他引導(dǎo)他如何解決 HashMap 并發(fā)編程的問題，從而我們下面開始回答出 ConcurrentHashMap。
最后
經(jīng)過上面一頓分析，我們可以看到小小一個 HashMap 其實涉及到很多知識點，這些點拆開來講就可以變成一道道面試題。
另外這些點在平常編程的過程中也要特別注意，一不小心我們就會踩一個大坑。
今天這篇文章主要提及一下，HashMap 涉及的知識點，所以阿粉沒有過多深入的分析，這里感興趣的同學(xué)可以在深入學(xué)習(xí)準(zhǔn)備一下。
