HashMap 是使用頻率最高的數據類型之一，同時也是面試必問的問題之一，尤其是它的底層實現原理，既是常見的面試題又是理解 HashMap 的基石，所以重要程度不言而喻。

HashMap 底層實現

HashMap 在 JDK 1.7 和 JDK 1.8 的底層實現是不一樣的，在 JDK 1.7 中，HashMap 使用的是數組 + 鏈表實現的，而 JDK 1.8 中使用的是數組 + 鏈表或紅黑樹實現的。HashMap 在 JDK 1.7 中的實現如下圖所示：

HashMap 在 JDK 1.8 中的實現如下圖所示：

我們本文重點來學習主流版本 JDK 1.8 中的 HashMap。HashMap 中每個元素稱之為一個哈希桶(bucket)，哈希桶包含的內容有 4 個：

• hash 值
• key
• value
• next(下一個節點)

HashMap 插入流程

HashMap 元素新增的實現源碼如下(下文源碼都是基于主流版本 JDK 1.8)：

public V put(K key, V value) { 
    // 對 key 進行哈希操作 
    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; 
    // 哈希表為空則創建表 
    if ((tab = table) == null || (n = tab.length) == 0) 
        n = (tab = resize()).length; 
    // 根據 key 的哈希值計算出要插入的數組索引 i 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        // 如果 table[i] 等于 null，則直接插入 
        tab[i] = newNode(hash, key, value, null); 
    else { 
        Node<K,V> e; K k; 
        // 如果 key 已經存在了，直接覆蓋 value 
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k)))) 
            e = p; 
        // 如果 key 不存在，判斷是否為紅黑樹 
        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; 
                } 
                //  key 已經存在直接覆蓋 value 
                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) 
        resize(); 
    afterNodeInsertion(evict); 
    return null; 
} 

上述的源碼都添加了相應的代碼注釋，簡單來說 HashMap 的元素添加流程是，先將 key 值進行 hash 得到哈希值，根據哈希值得到元素位置，判斷元素位置是否為空，如果為空直接插入，不為空判斷是否為紅黑樹，如果是紅黑樹則直接插入，否則判斷鏈表是否大于 8，且數組長度大于 64，如果滿足這兩個條件則把鏈表轉成紅黑樹，然后插入元素，如果不滿足這兩個條件中的任意一個，則遍歷鏈表進行插入，它的執行流程如下圖所示：

為什么要將鏈表轉紅黑樹?

JDK 1.8 中引入了新的數據結構紅黑樹來實現 HashMap，主要是出于性能的考量。因為鏈表超過一定長度之后查詢效率就會很低，它的時間復雜度是 O(n)，而紅黑樹的時間復雜度是 O(logn)，因此引入紅黑樹可以加快 HashMap 在數據量比較大的情況下的查詢效率。

哈希算法實現

HashMap 的哈希算法實現源碼如下：

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

其中，key.hashCode() 是 Java 中自帶的 hashCode() 方法，返回一個 int 類型的散列值，后面 hashCode 再右移 16 位，正好是 32bit 的一半，與自己本身做異或操作(相同為 0，不同為 1)，主要是為了混合哈希值的高位和低位，增加低位的隨機性，這樣就實現了 HashMap 的哈希算法。

總結

HashMap 在 JDK 1.7 時，使用的是數組 + 鏈表實現的，而在 JDK 1.8 時，使用的是數組 + 鏈表或紅黑樹的方式來實現的，JDK 1.8 之所以引入紅黑樹主要是出于性能方面的考慮。HashMap 在插入時，會判斷當前鏈表的長度是否大于 8 且數組的長度大于 64，如果滿足這兩個條件就會把鏈表轉成紅黑樹再進行插入，否則就是遍歷鏈表插入。

參考文檔：https://tech.meituan.com/2016/06/24/java-hashmap.html

本文轉載自微信公眾號「Java面試真題解析」，可以通過以下二維碼關注。轉載本文請聯系Java面試真題解析公眾號。