來自：非科班的科班

本文思維導(dǎo)圖

HashMap簡介

HashMap 是很常用的一種集合框架，其底層實現(xiàn)方式在 JDK 1.7和 JDK 1.8中卻有很大區(qū)別。

HashMap 是用來存儲數(shù)據(jù)的，它底層在JDK 1.7是數(shù)組+鏈表實現(xiàn)的，而JDK 1.8是使用數(shù)組+鏈表+紅黑樹實現(xiàn)，通過對 key 進行哈希計算等操作后得到數(shù)組下標，把 value 等信息存放在鏈表或紅黑樹存在此位置。

如果兩個不同的 key 運算后獲取的數(shù)組下標一致，就出現(xiàn)了哈希沖突。數(shù)組默認長度是16，如果實際數(shù)組長度超過一定的值，就會進行擴容。

HashMap的面試不管小廠還是大廠都是高頻問點，特別是大廠一定會深究底層，采用持續(xù)的追問，知道你懷疑人生，在Java7和Java8中對HashMap的數(shù)據(jù)結(jié)構(gòu)進行了很大的優(yōu)化。

今天這篇文章就以HashMap的高頻問點為主，層層的剖析HasMap的底層實現(xiàn)，話不多說，直接進入正題。

問點一：你了解HashMap的底層數(shù)據(jù)結(jié)構(gòu)嗎？

對于HashMap的底層數(shù)據(jù)結(jié)構(gòu)在Java7和Java8中的實現(xiàn)是不同的，在Java7中是采用數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)進行實現(xiàn)，而在Java8中是采用數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的。

說時遲那時快，剛話說完，從兜里拿出筆和紙，啪地一聲放在桌子上畫了起來，許久之后，出現(xiàn)了兩幅jdk7和jdk8的HashMap的內(nèi)部結(jié)構(gòu)圖：

當單向鏈表的值>8的時候，鏈表就會轉(zhuǎn)換為紅黑樹進行存儲數(shù)據(jù)，具體詳細的紅黑樹介紹之前已經(jīng)寫過一篇，這里就不再贅述，未詳細了解的請移至這一篇[B樹、B-樹、B+樹、B*樹圖文詳解]。

在面試大廠的時候，其實答到這里，還是不完整的，為什么呢？因為你想你說的上面的實際由jdk7和jdk8轉(zhuǎn)變的一個結(jié)果，但是重要的為什么要這樣做？你還沒有回答。

如果你聰明點的話，就不會等著面試官拋出接下來的問題？而是自己去回答這個為什么？不是等著面試官繼續(xù)拋出這個為什么？一個會聊天的人他會去猜測對方想知道什么？

問點二：為什么JDK 7使用數(shù)組+鏈表？JDK8中為什么要使用紅黑樹？哈希沖突是怎么回事？HashMap又是怎么解決的？

在深入這些問題之前，首先要了解一些概念，比如什么是hash函數(shù)，對于hash函數(shù)，之前已經(jīng)詳細的寫過一篇，這里就不再贅述，詳細參考這一篇[大白話之哈希表和哈希算法]。

哈希沖突是怎么回事呢？當<k,v>的數(shù)據(jù)將要存進HashMap中的時候，會先，把k值經(jīng)過hash函數(shù)進行計算得到hash值，再通過hash值進行計算得到數(shù)據(jù)在數(shù)組的下標，在jdk7中的源碼如下：

//key 進行哈希計算
int hash = hash(key);
//獲取數(shù)組下標
int i = indexFor(hash, table.length);

通過計算后的下標，從而得到數(shù)組的對應(yīng)下標的位置，最后把k，v值存進去，同樣的當再次第二次存值的時候，同樣把k，v傳進來，當k再次進行計算出數(shù)組下標index，有可能和第一次計算的index的值相同。

為什么有可能相同呢？這個是hash函數(shù)的原因，看完上面推薦的那篇hash函數(shù)詳細介紹你就懂了。當兩次的計算index相同，這就是hash沖突。

但是，兩次的需要存進去的value值是不同的，這就出現(xiàn)了同一個數(shù)組后面有一條鏈表，會比較鏈表上的每一個value值與當前的value是否相同，若是不相同，通過頭插法，將數(shù)值插入鏈表中。如下圖所示：

public V put(K key, V value) {
　　　　　//數(shù)組為空就進行初始化
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
　　　　　//key 進行哈希計算
        int hash = hash(key);
　　　　　//獲取數(shù)組下標
        int i = indexFor(hash, table.length);
　　　　　//如果此下標有值，遍歷鏈表上的元素，key 一致的話就替換 value 的值
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
　　　　　//新增一個key
        addEntry(hash, key, value, i);
        return null;
    }

put方法中主要做了以下幾件事：

1. 判斷table數(shù)組是否為空，若為空進行初始化table數(shù)組。

2. 判斷key值是否為null，將null是作為key存進去。

3. 若key不為空，通過key計算出數(shù)組下標，判斷table[i]是否為空。

4. 若是不為空通過鏈表循環(huán)，判斷在鏈表中是否存在與該key相等，若是存在，直接將value替換成新的value。若是table[i]為空或者鏈表中不存在與之相同的key，就addEntry(hash, key, value, i)新增一個節(jié)點。

接下來看看addEntry(hash, key, value, i)新增節(jié)點的源碼如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
//數(shù)組長度大于閾值且存在哈希沖突（即當前數(shù)組下標有元素），就將數(shù)組擴容至2倍
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

這個方法很簡單，直接就是判斷當前數(shù)組的大小是否>=threshold并且table[bucketIndex]是否為null。若成立擴容，然后rehash，重新得到新數(shù)組的下標值，最后 createEntry(hash, key, value, bucketIndex)創(chuàng)建新節(jié)點。

最后來看一下createEntry(hash, key, value, bucketIndex)創(chuàng)建新節(jié)點的源碼如下：

void createEntry(int hash, K key, V value, int bucketIndex) {
　　//此位置有元素，就在鏈表頭部插入新元素（頭插法）
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

該方法就是通過頭插法加入新節(jié)點，方法非常簡單，相信都能看懂。經(jīng)過上面對put方法的源碼分析，在jdk 7 中put操作的原理圖如下所示：

因此在JDK 8中為了優(yōu)化HashMap的查詢效率，將內(nèi)部的結(jié)構(gòu)改為數(shù)組+鏈表+和紅黑樹，當一個哈希桶后面的鏈表長度>8的時候，就會將鏈表轉(zhuǎn)化為紅黑樹，紅黑樹是二分查找，提高了查詢的效率。接下來通過JDK 8的put源碼分析如下：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}


final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
　　　　　//數(shù)組為空就初始化
        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;
　　　　　　　//key 相同就覆蓋原來的值
            if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
　　　　　　　//樹節(jié)點插入數(shù)據(jù)
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
　　　　　　　　　　　　//鏈表，尾插法插入數(shù)據(jù)
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
　　　　　　　　　　　　　　//鏈表長度超過8，就把鏈表轉(zhuǎn)為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
　　　　　　　　　　　　//key相同就覆蓋原來的值
                    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;
　　　　　//數(shù)組長度大于閾值，就擴容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

通過分析源碼，上面的方法主要做了以下幾件事：

1. 判斷當前桶是否為空，空的就需要初始化（resize 中會判斷是否進行初始化）。

2. 根據(jù)當前 key 的 hashcode 定位到具體的桶中并判斷是否為空，為空表明沒有 Hash 沖突就直接在當前位置創(chuàng)建一個新桶即可。

3. 如果當前桶有值（ Hash 沖突），那么就要比較當前桶中的 key、key 的 hashcode 與寫入的 key是否相等，相等就賦值給 e。

4. 如果當前桶為紅黑樹，那就要按照紅黑樹的方式寫入數(shù)據(jù)。

5. 如果是個鏈表，就需要將當前的 key、value 封裝成一個新節(jié)點寫入到當前桶的后面（形成鏈表）。

6. 接著判斷當前鏈表的大小是否大于預(yù)設(shè)的閾值，大于時就要轉(zhuǎn)換為紅黑樹。

7. 如果在遍歷過程中找到 key 相同時直接退出遍歷。

8. 如果 e != null 就相當于存在相同的 key,那就需要將值覆蓋。

9. 最后判斷是否需要進行擴容。

繼續(xù)看下 treeifyBin 的源碼：

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
　　　　　//鏈表轉(zhuǎn)為紅黑樹時，若此時數(shù)組長度小于64，擴容數(shù)組
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
　　　　　　　//鏈表轉(zhuǎn)為樹結(jié)構(gòu)
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

由此可以看到1.8中，數(shù)組有兩種情況會發(fā)生擴容：

1. 一是超過閾值

2. 二是鏈表轉(zhuǎn)為紅黑樹且數(shù)組元素小于64時

由此在jdk1.8中，默認長度為16情況下，要么元素一直放在同一下標，鏈表轉(zhuǎn)為紅黑樹且數(shù)組元素小于64時就會擴容，要么超過閾值12時才會擴容。

依據(jù)上面的源碼分析，在JDK 1.8中put方法的執(zhí)行的原理圖如下：

問點三：HashMap的擴容機制是怎么樣的？JDK7與JDK8有什么不同嗎？

JDK 1.7的擴容條件是數(shù)組長度大于閾值且存在哈希沖突，在JDK 7中的擴容的源碼如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
　　　　　//數(shù)組長度大于閾值且存在哈希沖突（即當前數(shù)組下標有元素），就將數(shù)組擴容至2倍
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

而JDK 1.8擴容條件是數(shù)組長度大于閾值或鏈表轉(zhuǎn)為紅黑樹且數(shù)組元素小于64時，源碼中的體現(xiàn)如下所示：

//數(shù)組長度大于閾值，就擴容
if (++size > threshold)
      resize();

//鏈表轉(zhuǎn)為紅黑樹時，若此時數(shù)組長度小于64，擴容數(shù)組
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
      resize();

問點四：HashMap中的鍵值可以為Null嗎？能簡單說一下原理嗎？

在JDK7中是允許null存進去的，通過 putForNullKey(value)方法來存儲key為null值，具體的實現(xiàn)的源代碼如下：

if (key == null)
    return putForNullKey(value);

而在JDK 8中當傳進key為null值的時候，就直接將hash值取0，進行計算存入值的位置。

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

問點五：HashMap中能put兩個相同的Key嗎？為什么能或為什么不能？

這個問題比較簡單，在JDK7和JDK8中的做法是一樣的，若是存入的key值一樣，就會將原來的key所對應(yīng)的value值直接替換掉，可以從源碼中看出：

// JDK1.7
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
       V oldValue = e.value;
       // 直接替換原來的value值
       e.value = value;
       e.recordAccess(this);
       return oldValue;
 }

// JDK 1.8
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;
        }
        // 存在key值相同
        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)
        // 替換掉原來value值
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

問點六：聊一聊JDK 7的HashMap中的“死鎖”是怎么回事？

HashMap是線程不安全的，在HashMap的源碼中并未對其操作進行同步執(zhí)行，所以在并發(fā)訪問的時候就會出現(xiàn)線程安全的問題。

由于上一篇的ConcurrentHashMap篇中講到了死鎖，也畫了圖，但是很多讀者說看不懂，這里我的鍋，在這里詳細的進行圖解。

假設(shè)：有線程A和線程B，并發(fā)訪問HashMap中的數(shù)據(jù)。假設(shè)HashMap的長度為2(這里只是為了講解方便假設(shè)長度為2)，鏈表的結(jié)構(gòu)圖如下所示：

此時，線程A執(zhí)行到transfer函數(shù)中（transfer函數(shù)是resize擴容方法中調(diào)用的另一個方法），當執(zhí)行（1）位置的時候，如下所示：

/**
* Transfers all entries from current table to newTable.
*/
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; ---------------------(1)
        if (rehash) {
            e.hash = null == e.key ? 0 : hash(e.key);
        }
        int i = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
    } // while
    }
}

此時線程A掛起，在此時在線程A的棧中就會存在如下值：

e = 4
next = 8

此時線程B執(zhí)行put的操作，并發(fā)現(xiàn)在進行put操作的時候需要擴容，當線程B執(zhí)行 transfer函數(shù)中的while循環(huán)，即會把原來的table變成新一table（線程B自己的棧中），再寫入到內(nèi)存中。

執(zhí)行的過程如下圖所示（假設(shè)兩個元素在新的hash函數(shù)下也會映射到同一個位置）：

問點七：HashMap是線程安全的嗎？為什么安全或者不安全？

從上圖JDK8的put操作原理圖中可以看出為HashMap的put方法的詳細過程，其中造成線程不安全的方法主要是resize(擴容)方法.

假設(shè)，現(xiàn)在有線程A 和線程B 共同對同一個HashMap進行put操作，假設(shè)A和B插入的Key-Value中key的hashcode是相同的,這說明該鍵值對將會插入到Table的同一個下標的,也就是會發(fā)生哈希碰撞。

此時HashMap按照平時的做法是形成一個鏈表(若超過八個節(jié)點則是紅黑樹),現(xiàn)在我們插入的下標為null(Table[i]==null)則進行正常的插入。

此時線程A進行到了這一步正準備插入，這時候線程A堵塞，線程B獲得運行時間，進行同樣操作，也是Table[i]==null 。此時它直接運行完整個put方法,成功將元素插入.。

隨后，線程A獲得運行時間接上上面的判斷繼續(xù)運行，進行了Table[i]==null的插入(此時其實應(yīng)該是Table[i]!=null的操作，因為前面線程B已經(jīng)插入了一個元素了)，這樣就會直接把原來線程B插入的數(shù)據(jù)直接覆蓋了，如此一來就造成了線程不安全問題.

問點八：為什么重寫對象的Equals方法時，要重寫HashCode方法？這個和HashMap有關(guān)系嗎？為什么？

對于這個問題，我之前已經(jīng)詳細寫過一篇文章，這里就不再做贅述。

特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：
長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝