[[347445]]

本文轉(zhuǎn)載自微信公眾號(hào)「Java極客技術(shù)」，作者鴨血粉絲。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java極客技術(shù)公眾號(hào)。  

Hello，大家好，我是阿粉~

不知道大家最近有沒(méi)有刷過(guò) Java 面試題，有沒(méi)有發(fā)現(xiàn)幾乎所有面試題或多或少都會(huì)包括 HashMap 面試題。

為什么 Java 中小小的一個(gè) HashMap，值得在面試中被反復(fù)提到?

阿粉認(rèn)為是因?yàn)?HashMap 太重要了，大家回看一下自己的業(yè)務(wù)代碼，是不是都有在使用 HashMap ?

即使你真的沒(méi)有直接使用，但是你使用的一些中間件，或者一些開(kāi)源框架，這些代碼肯定使用 HashMap 完成相關(guān)邏輯。

而 HashMap 包含很多核心知識(shí)點(diǎn)，從這些知識(shí)點(diǎn)可以考察出一個(gè)面試者基本知識(shí)掌握情況。

其實(shí)就算沒(méi)有面試，我們也應(yīng)該或多乎或少去了解 一下 HashMap 基本實(shí)現(xiàn)原理。因?yàn)槿绻褂?HashMap 不當(dāng)，很容易寫(xiě)出一連串 Bug，而且可能還不容易排查。

HashMap 面試題網(wǎng)上很多，但是其實(shí)怎么問(wèn)他都離不開(kāi)這些核心知識(shí)點(diǎn)。

這就像我們以前解答數(shù)學(xué)題一樣，背后答案都是圍繞核心數(shù)學(xué)公式。

所以我們只要掌握 HashMap 核心知識(shí)點(diǎn)，就不用再怕面試中再問(wèn)到。

這里阿粉整理一下，HashMap 涉及核心知識(shí)點(diǎn)如下：

• 底層數(shù)據(jù)結(jié)構(gòu)
• Hash 算法
• 尋址算法
• 擴(kuò)容
• 多線程并發(fā)

底層數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)與算法是最近面試越來(lái)越注重考查的一方面，尤其是對(duì)于校招來(lái)講，這一塊百分百會(huì)涉及。

而 HashMap 底層結(jié)構(gòu)一下子就涉及三大數(shù)據(jù)結(jié)構(gòu)，數(shù)組、鏈表、紅黑樹(shù)。

數(shù)組

HashMap 中元素實(shí)際保存在一個(gè)個(gè) Node 中，而Node 類(lèi)保存在底層數(shù)組中。

以上代碼來(lái)自 JDK1.8，JDK1.7 為 Entry 類(lèi)型。

實(shí)際上 Node 為 Entry 類(lèi)的子類(lèi)

鏈表

我們觀察一下Node 類(lèi)的數(shù)據(jù)結(jié)構(gòu)，

可以發(fā)現(xiàn) Node 類(lèi)中有一個(gè) next 字段，用于保存下一個(gè) Node 元素，通過(guò)這種方式就形成一個(gè)單向的鏈表。

那為什么需要鏈表那?

這可能與下面說(shuō)道 Hash算法有關(guān)，因?yàn)樵俸玫?Hash 算法，都有可能導(dǎo)致不同輸入產(chǎn)生相同的輸出。

來(lái)自:阮一峰的博客

如果不同的輸入得到了同一個(gè)哈希值，就發(fā)生了"哈希碰撞"(collision)。

哈希碰撞解決辦法很多，這里 HashMap 就采用拉鏈法，即使用一個(gè)鏈表保存碰撞的元素的。

其他辦法還有：

• 線行探查法
• 平方探查法
• 雙散列函數(shù)探查法

紅黑樹(shù)

由于鏈表查找元素復(fù)雜度為 O(N)，如果 HashMap 哈希碰撞很厲害，從而導(dǎo)致大部分元素落在同一個(gè)鏈表上，這就會(huì)導(dǎo)致 HashMap 性能會(huì)下降，極端一點(diǎn) HashMap O(1) 查詢復(fù)雜度退化成 O(N)的復(fù)雜度。

JDK1.8 中引入紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)，當(dāng)鏈表元素等于 8 時(shí)，鏈表轉(zhuǎn)化為紅黑樹(shù)，這樣查找復(fù)雜度就可以為 O(logn)。

圖片來(lái)自網(wǎng)絡(luò)

那為什么使用紅黑樹(shù)，而不是使用其他二叉樹(shù)，?

這是因?yàn)榧t黑樹(shù)對(duì)于新增與刪除的操作也都能保持O(logn) 新增,這樣就完美兼顧了查找與新增性能。

面試題

看完這個(gè)知識(shí)點(diǎn)，其實(shí)可以提很多相關(guān)數(shù)據(jù)結(jié)構(gòu)面試題，比如數(shù)組與鏈表區(qū)別。

所以看完這個(gè)，我們就需要去整理學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)。

Hash 算法

這里我們僅僅介紹一下 JDK1.8 Hash 算法。

它使用 key 的 hashcode 高低 16 位異或的方式計(jì)算產(chǎn)生。

通過(guò)這種方式，在后面尋址算法計(jì)算時(shí)候，降低碰撞的可能性。

尋址算法

當(dāng)我們計(jì)算得到 Hash 值以后，我們還需要計(jì)算這個(gè) Hash 值在數(shù)組中的位置。

簡(jiǎn)單的方式我們可以直接使用求模的方式定位，比如

hash=1000 
table.size=16 
n=hash%table.size=8 

但是 HashMap 采用的是另外一種更為精妙的算法：

這種方式等同求模法，但是計(jì)算性能會(huì)更好，但是這里我們需要注意了，這種方式前提為 n 也就是數(shù)組的長(zhǎng)度必須為 2 的冪次方。

這里阿粉就不具體計(jì)算了，感興趣的同學(xué)可以網(wǎng)上查找一下推導(dǎo)過(guò)程

面試題

為什么 HashMap 擴(kuò)容都是 2 的冪次方?

看完這個(gè)，大家這個(gè)面試題了吧。

擴(kuò)容

當(dāng) HashMap 元素過(guò)多時(shí)，這時(shí)必須擴(kuò)容，從而保證 HashMap 查找性能。

擴(kuò)容過(guò)程，我們就需要涉及以下幾個(gè)核心參數(shù)：

• 擴(kuò)展因子：loadFactor
• 實(shí)際元素?cái)?shù)量：size
• 數(shù)組長(zhǎng)度：capacity
• 擴(kuò)容的閾值大?。簍hreshold=capacity*loadFactor

當(dāng) HashMap 中元素?cái)?shù)量大于 threshold，HashMap 就會(huì)開(kāi)始擴(kuò)容。

JDK1.7 擴(kuò)容的時(shí)候，HashMap 每個(gè)元素將會(huì)重新計(jì)算 Hash 值，然后使用尋址算法，查找新的位置。

在 JDk1.8 中，采用了一種更精妙的算法：

其使用 e.hash & oldCap == 0， 元素要么放在原位置，要么放在原位置+原數(shù)組長(zhǎng)度。

這里解釋起來(lái)比較復(fù)雜，這里阿粉就不再詳細(xì)展開(kāi)，感興趣同學(xué)可以自行查找一下相關(guān)文章。

面試題

問(wèn)：加載因子為什么 0.75，而不是其他值?

答：可以說(shuō)是一個(gè)經(jīng)過(guò)考量的經(jīng)驗(yàn)值。加載因子涉及擴(kuò)容，下次擴(kuò)容的閾值=數(shù)組桶的大小*加載因子，如果加載因子太小，這就會(huì)導(dǎo)致閾值太小，這就會(huì)導(dǎo)致比較容易發(fā)生擴(kuò)容。

如果加載因子太大，那就會(huì)導(dǎo)致閾值太大，可能沖突會(huì)很多，導(dǎo)致查找效率下降。

多線程并發(fā)

好了，終于到到了最后一個(gè)知識(shí)點(diǎn)，多線程并發(fā)。

HashMap 在多線程并發(fā)情況下會(huì)怎么樣?

這里我們需要分 JDK1.7 與 JDK1.8 來(lái)講。

在 JDK1.7 中，由于擴(kuò)容遷移時(shí)采用了頭插法，從而將會(huì)導(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é)點(diǎn)， 
            newTable[i] = e; 
            e = next; 
        } 
    } 
} 

而一旦產(chǎn)生死鏈，極有可能導(dǎo)致程序陷入死循環(huán)，從而導(dǎo)致 CPU 使用率上升。

JDK1.8 中使用尾插法，從而解決這個(gè)問(wèn)題，但是依然還會(huì)存在相關(guān)問(wèn)題。

比如：

并發(fā)賦值時(shí)被覆蓋

并發(fā)的情況下，一個(gè)線程的賦值可能被另一個(gè)線程覆蓋，這就導(dǎo)致對(duì)象的丟失。

size 計(jì)算問(wèn)題

img

每次元素增加完成之后，size 將會(huì)加 1。這里采用 ++i方法，天然的并發(fā)不安全。

面試題

關(guān)于并發(fā)，這里可以提到很多面試題。

可以是線程相關(guān)的，也可以是并發(fā)編程相關(guān)。

不過(guò)如果面試官既然已經(jīng)提到這里，我們可以試著將他引導(dǎo)他如何解決 HashMap 并發(fā)編程的問(wèn)題，從而我們下面開(kāi)始回答出 ConcurrentHashMap。

最后

經(jīng)過(guò)上面一頓分析，我們可以看到小小一個(gè) HashMap 其實(shí)涉及到很多知識(shí)點(diǎn)，這些點(diǎn)拆開(kāi)來(lái)講就可以變成一道道面試題。

另外這些點(diǎn)在平常編程的過(guò)程中也要特別注意，一不小心我們就會(huì)踩一個(gè)大坑。

今天這篇文章主要提及一下，HashMap 涉及的知識(shí)點(diǎn)，所以阿粉沒(méi)有過(guò)多深入的分析，這里感興趣的同學(xué)可以在深入學(xué)習(xí)準(zhǔn)備一下。