JDK1.8源碼：HashMap解讀

HashMap

是我們最常用的集合類型之一了。也由于其高效、使用友善，我們有必要對其内部進行梳理一番。

JDK1.8源碼中，關于

Map

的類圖關系如下：

JDK1.8源碼：HashMap解讀

`Map` 家族的對比

從

Map

的類圖關系中，我們可以看出還是蠻豐富的。需要用到順序的，可以使用

TreeMap

，需要線程安全的可以使用

HashTable

和

ConcurrentHashMap

。其各自特點總結如下：

類	特點
`HashMap`	存儲資料無序；非線程安全；key可為，但是其桶索引為0；效率為O(1)
`HashTable`	遠古時代就具有的，存儲資料無序；線程安全，但是是使用笨重的 `Synchronized` ；key不可為
`ConcurrentHashMap`	新貴，存儲資料無序；線程安全，采用 `CAS` ；key不可為
`TreeMap`	存儲資料有序；非線程安全
`LinkedHashMap`	存儲資料有序；非線程安全

讓我們先從

HashMap

開始。

`HashMap` 概述

JDK1.8源碼：HashMap解讀

JDK1.7中，

HashMap

由數組和連結清單構成，當連結清單資料特别多的時候，很明顯的其效率受到影響。于是，在JDK1.8中的

HashMap

當連結清單資料過長時，轉為紅黑樹的資料結構。

`HashMap` 源碼

我們選取常用的幾個方法（執行個體化、put）來看下源碼。

`HashMap` 屬性

//Map預設初始化的容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    //Map的最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //預設負載因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //連結清單轉為紅黑樹的門檻值
    static final int TREEIFY_THRESHOLD = 8;

    //紅黑樹轉為連結清單的門檻值
    static final int UNTREEIFY_THRESHOLD = 6;

    //連結清單轉為紅黑樹表的門檻值
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    //桶數組
    transient Node<K,V>[] table;

    //對Map的entrySet結果緩存
    transient Set<Map.Entry<K,V>> entrySet;

    //key-value對的數量
    transient int size;

    //增加或者删除Map元素、rehash的次數
    transient int modCount;

    //HashMap需要resize的門檻值
    int threshold;

    //負載因子
    final float loadFactor;

`HashMap` 初始化

選取個複雜點的構造方法：

//initialCapacity表示HashMap的容量，loadFactor表示負載因子
    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;
        //tableSizeFor是将initialCapacity轉為不小于其的最小2的幂次方
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    //tableSizeFor的方法如下
    //目前算法我看的不太明白
    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;
    }

大家通過源代碼可以看到，初始化時，可以說幾乎沒發生沒什麼事情。隻指派了

loadFactor

和確定

Map

的容量為2的幂次方。

這裡就有個問題？為什麼需要確定

Map

的容量為2的幂次方？其實這是個非正常的設計，正常的設計是把桶的大小設計為素數（參考：https://blog.csdn.net/liuqiyao_01/article/details/14475159）。在講完

put

方法後我們來闡述。

其實，這裡可以看作是

Map

的延遲初始化。在首次

put

元素時，會初始化屬性

table

。在這裡順便提下

table

的類型

Node

。在為連結清單時，其資料結構為：

//連結清單節點
static class Node<K,V> implements Map.Entry<K,V> {
        //key的hash值
        final int hash;
        //Map的key值
        final K key;
        //Map的key對應的value
        V value;
        //下一個元素
        Node<K,V> next;

        //省略getter&setter、equals
    }

當轉為紅黑樹時，其結構為：

//樹節點
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;
}

`HashMap put` 方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //1.首次存入元素時，會在resize方法中初始化table
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //2.如果key對應的索引位置（(n - 1) & hash）沒有元素，則直接存入元素
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {//3.如果key對應的索引位置有元素
            Node<K,V> e; K k;
            //3.1 如果key相同，則直接覆寫key對應的value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //3.2 如果key不同，判斷Node是否屬于紅黑樹類型，是則入樹
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//3.3 Node屬于連結清單節點類型
                for (int binCount = 0; ; ++binCount) {
                    //3.3.1 下一個節點為空，則插傳入連結表中
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //3.3.1.1 節點數量是否超過樹化的門檻值，超過則進行樹化。注意此處并非一定會轉化為紅黑樹，還會判斷屬性table的長度，可以參考treeifyBin方法
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
                    
                    //3.3.2 下一個節點不為空，判斷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;
                //為LinkedHashMap預備
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //添加修改次數
        ++modCount;
        //超過門檻值則配置設定空間，重新rehash運算
        if (++size > threshold)
            resize();
        //為LinkedHashMap預備
        afterNodeInsertion(evict);
        return null;
    }

我們可以畫個流程圖：

JDK1.8源碼：HashMap解讀

其他的方法，譬如

get

、

remove

等，主要的都是先要确定

key

對應的索引。即

hash & (n - 1)

。其中

hash

為

key

對應的

hash

值，

為

capacity

，即

Map

的容量。

我們先來看下

hash

的計算：

static final int hash(Object key) {
        int h;
        //如果為null，則索引為0；否則是其hashCode低16位與hashCode高16位的抑或結果
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

為什麼

hashCode

需要與其高16為抑或？簡單點說就是讓高位和低位都參與運算，使

key

的分布盡量更均勻些。參見https://zhuanlan.zhihu.com/p/21673805

有了

hash

值之後，我們可以計算索引的位置了。一般都是取模運算，但是大家都知道計算機是二進制的，位運算會比取餘快多了。是以這裡的

hash & (n - 1)

可以看做是用空間來換取時間。因為當

為2的幂次方時，

n-1

的二進制恰恰全是

，其與

hashCode

的二進制與值正好是取模的結果。這裡就回答了上面為什麼需要確定

Map

的容量為2的幂次方的問題。

HashMap

的源碼目前就分析到這裡。流程其實說起來不是很難，難的關鍵就是為什麼設計者會是這樣的設計？這恰恰是我們需要多思考的。本篇在關于這一點上還是遠遠不足的，大家可以多搜尋幾篇來看看，多思考思考。

JDK1.8源碼：HashMap解讀

`Map` 家族的對比

`HashMap` 概述

`HashMap` 源碼

`HashMap` 屬性

`HashMap` 初始化

`HashMap put` 方法

繼續閱讀

Objective-C中的Observer模式實作

HashMap相關面試題

Map的keySet方法關于iterator()的方法

如何下載下傳JDK的曆史版本

HashMap、HashSet、ArrayList實作機制

jasperreport中可以使用List作為資料源

Passing parameters to a Jasper report

java HashMap 與HashTable的差別

[轉]編寫高效的Android代碼

java增強for循環周遊Map集合問題

重新認識HashMap

WebService CXF學習（進階篇2）：複雜對象傳遞(List，Map)

Java1.8 對HashMap的resize()的了解

JAVA并發, 反射, NIO

Java中Integer和int的差別

JDK1.8中JVM記憶體分析

JDK1.8源碼：HashMap解讀

Map 家族的對比

HashMap 概述

HashMap 源碼

HashMap 屬性

HashMap 初始化

HashMap put 方法

繼續閱讀

`Map` 家族的對比

`HashMap` 概述

`HashMap` 源碼

`HashMap` 屬性

`HashMap` 初始化

`HashMap put` 方法