簡介：

HashMap最早出現在JDK1.2中，底層基於散列算法實現。

HashMap 允許 null 鍵和 null 值，是非線程安全類，在多線程環境下可能會存在問題。

1.8版本的HashMap數據結構：

為什麼有的是鏈表有的是紅黑樹？

默認鏈表長度大於8時轉為樹

結構

Node是HhaspMap中的一個靜態內部類 ：

<code>//Node是單向鏈表，實現了Map.Entry接口
static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;
    //構造函數
    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    // getter and setter ... toString ...
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this) 

            return true;
        if (o instanceof Map.Entry) {
            Map.Entry,?> e = (Map.Entry,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}/<code>

TreeNode 是紅黑樹的數據結構。

<code>static final class TreeNode extends LinkedHashMap.Entry {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node next) {
        super(hash, key, val, next);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode root() {
        for (TreeNode r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    } 
/<code>

類定義

<code>public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable /<code>

變量

<code>/**
 * 默認初始容量16(必須是2的冪次方)
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
 * 最大容量，2的30次方
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默認加載因子，用來計算threshold
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 鏈表轉成樹的閾值，當桶中鏈表長度大於8時轉成樹 
   threshold = capacity * loadFactor
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 進行resize操作時，若桶中數量少於6則從樹轉成鏈表 

 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 桶中結構轉化為紅黑樹對應的table的最小大小

 當需要將解決 hash 衝突的鏈表轉變為紅黑樹時，
 需要判斷下此時數組容量，
 若是由於數組容量太小（小於　MIN_TREEIFY_CAPACITY　）
 導致的 hash 衝突太多，則不進行鏈表轉變為紅黑樹操作，
 轉為利用　resize() 函數對　hashMap 擴容
 */
static final int MIN_TREEIFY_CAPACITY = 64;
/**
 保存Node節點的數組
 該表在首次使用時初始化，並根據需要調整大小。 分配時，
 長度始終是2的冪。
 */
transient Node[] table;

/**
 * 存放具體元素的集
 */
transient Set<map.entry>> entrySet;

/**
 * 記錄 hashMap 當前存儲的元素的數量
 */
transient int size;

/**
 * 每次更改map結構的計數器 

 */
transient int modCount;

/**
 * 臨界值 當實際大小(容量*填充因子)超過臨界值時，會進行擴容
 */
int threshold;

/**
 * 負載因子：要調整大小的下一個大小值（容量*加載因子）。
 */
final float loadFactor;

/<map.entry>/<code>

構造方法

<code>/**
 * 傳入初始容量大小，使用默認負載因子值 來初始化HashMap對象
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 默認容量和負載因子
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
 * 傳入初始容量大小和負載因子 來初始化HashMap對象
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小於0，否則報錯
    if (initialCapacity < 0) 

        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 初始容量不能大於最大值，否則為最大值                                       
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //負載因子不能小於或等於0，不能為非數字    
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 初始化負載因子                                       
    this.loadFactor = loadFactor;
    // 初始化threshold大小
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 找到大於或等於 cap 的最小2的整數次冪的數。
 */
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;
}
/<code>

tableSizeFor方法詳解：

用位運算找到大於或等於 cap 的最小2的整數次冪的數。比如10，則返回16

1. 讓cap-1再賦值給n的目的是使得找到的目標值大於或等於原值。例如二進制0100,十進制是4,若不減1而直接操作，答案是0001 0000十進制是16，明顯不符合預期。
2. 對n右移1位：001xx...xxx，再位或：011xx...xxx
3. 對n右移2位：00011...xxx，再位或：01111...xxx
4. 對n右移4位...
5. 對n右移8位...
6. 對n右移16位,因為int最大就2^32所以移動1、2、4、8、16位並取位或,會將最高位的1後面的位全變為1。
7. 再讓結果n+1，即得到了2的整數次冪的值了。

附帶一個實例：

loadFactor 負載因子

對於 HashMap 來說，負載因子是一個很重要的參數，該參數反應了 HashMap 桶數組的使用情況。

通過調節負載因子，可使 HashMap 時間和空間複雜度上有不同的表現。

當我們調低負載因子時，HashMap 所能容納的鍵值對數量變少。

擴容時，重新將鍵值對存儲新的桶數組裡，鍵的鍵之間產生的碰撞會下降，鏈表長度變短。

此時，HashMap 的增刪改查等操作的效率將會變高，這裡是典型的拿空間換時間。

相反，如果增加負載因子（負載因子可以大於1），HashMap 所能容納的鍵值對數量變多，空間利用率高，但碰撞率也高。

這意味著鏈表長度變長，效率也隨之降低，這種情況是拿時間換空間。至於負載因子怎麼調節，這個看使用場景了。

一般情況下，我們用默認值就可以了。大多數情況下0.75在時間跟空間代價上達到了平衡所以不建議修改。

查找

<code>public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 獲取hash值
static final int hash(Object key) {
    int h;
    // 拿到key的hash值後與其五符號右移16位取與
    // 通過這種方式，讓高位數據與低位數據進行異或，以此加大低位信息的隨機性，變相的讓高位數據參與到計算中。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final Node getNode(int hash, Object key) {
    Node[] tab; 
    Node 
 first, e; 
    int n; K k;
    // 定位鍵值對所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判斷桶中第一項(數組元素)相等
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶中不止一個結點
        if ((e = first.next) != null) {
            // 是否是紅黑樹，是的話調用getTreeNode方法
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            // 不是紅黑樹的話，在鏈表中遍歷查找    
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}/<code>

注意：

1. HashMap的hash算法(hash()方法)。
2. (n - 1) & hash等價於對 length 取餘。

添加

<code>public V put(K key, V value) {
    // 調用hash(key)方法來計算hash 
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; 
    Node p; 
    int n, i;
    // 容量初始化：當table為空，則調用resize()方法來初始化容器
    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 e; K k;
        // 比較桶中第一個元素(數組中的結點)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //如果鍵的值以及節點 hash 等於鏈表中的第一個鍵值對節點時，則將 e 指向該鍵值對
            e = p;
        // 如果桶中的引用類型為 TreeNode，則調用紅黑樹的插入方法
        else if (p instanceof TreeNode)
            // 放入樹中
            e = ((TreeNode)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值與插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //判斷要插入的鍵值對是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 鍵值對數量超過閾值時，則進行擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}/<code>

事實上，new HashMap();完成後，如果沒有put操作，是不會分配存儲空間的。

1. 當桶數組 table 為空時，通過擴容的方式初始化 table
2. 查找要插入的鍵值對是否已經存在，存在的話根據條件判斷是否用新值替換舊值
3. 如果不存在，則將鍵值對鏈入鏈表中，並根據鏈表長度決定是否將鏈表轉為紅黑樹
4. 判斷鍵值對數量是否大於閾值，大於的話則進行擴容操作

擴容機制

在 HashMap 中，桶數組的長度均是2的冪，閾值大小為桶數組長度與負載因子的乘積。

當 HashMap 中的鍵值對數量超過閾值時，進行擴容。

HashMap 按當前桶數組長度的2倍進行擴容，閾值也變為原來的2倍（如果計算過程中，閾值溢出歸零，則按閾值公式重新計算）。

擴容之後，要重新計算鍵值對的位置，並把它們移動到合適的位置上去。

<code>final Node[] resize() {
    // 拿到數組桶 

    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果數組桶的容量大與0
    if (oldCap > 0) {
        // 如果比最大值還大，則賦值為最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果擴容後小於最大值 而且 舊數組桶大於初始容量16， 閾值左移1(擴大2倍)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果數組桶容量<=0 且 舊閾值 >0
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 新容量=舊閾值
        newCap = oldThr;
    // 如果數組桶容量<=0 且 舊閾值 <=0
    else {               // zero initial threshold signifies using defaults
        // 新容量=默認容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 新閾值= 負載因子*默認容量
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新閾值為0
    if (newThr == 0) {
        // 重新計算閾值
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 更新閾值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        // 創建新數組 

        Node[] newTab = (Node[])new Node[newCap];
    // 覆蓋數組桶    
    table = newTab;
    // 如果舊數組桶不是空，則遍歷桶數組，並將鍵值對映射到新的桶數組中
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是紅黑樹
                else if (e instanceof TreeNode)
                    // 重新映射時，需要對紅黑樹進行拆分
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 如果不是紅黑樹，則按鏈表處理
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    // 遍歷鏈表，並將鏈表節點按原順序進行分組
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else 

                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 將分組後的鏈表映射到新桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}/<code>

整體步驟：

1. 計算新桶數組的容量 newCap 和新閾值 newThr
2. 根據計算出的 newCap 創建新的桶數組，桶數組 table 也是在這裡進行初始化的
3. 將鍵值對節點重新映射到新的桶數組裡。如果節點是 TreeNode 類型，則需要拆分紅黑樹。如果是普通節點，則節點按原順序進行分組。

總結起來，一共有三種擴容方式：

1. 使用默認構造方法初始化HashMap。

從前文可以知道HashMap在一開始初始化的時候會返回一個空的table，並且thershold為0。

因此第一次擴容的容量為默認值DEFAULT_INITIAL_CAPACITY也就是16。

同時threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。

1. 指定初始容量的構造方法初始化HashMap。

那麼從下面源碼可以看到初始容量會等於threshold，

接著threshold = 當前的容量（threshold） * DEFAULT_LOAD_FACTOR。

1. HashMap不是第一次擴容。

如果HashMap已經擴容過的話，那麼每次table的容量以及threshold量為原有的兩倍。

loadFactor小數位為 0，整數位可被2整除且大於等於8時，在某次計算中就可能會導致 newThr 溢出歸零。

疑問和進階

1. JDK1.7是基於數組+單鏈表實現（為什麼不用雙鏈表）

首先，用鏈表是為了解決hash衝突。

單鏈表能實現為什麼要用雙鏈表呢?(雙鏈表需要更大的存儲空間)

2. 為什麼要用紅黑樹，而不用平衡二叉樹？

插入效率比平衡二叉樹高，查詢效率比普通二叉樹高。所以選擇性能相對摺中的紅黑樹。

3. 重寫對象的Equals方法時，要重寫hashCode方法，為什麼？跟HashMap有什麼關係？

equals與hashcode間的關係:

1. 如果兩個對象相同（即用equals比較返回true），那麼它們的hashCode值一定要相同；
2. 如果兩個對象的hashCode相同，它們並不一定相同(即用equals比較返回false)

因為在 HashMap 的鏈表結構中遍歷判斷的時候，特定情況下重寫的 equals 方法比較對象是否相等的業務邏輯比較複雜，循環下來更是影響查找效率。

所以這裡把 hashcode 的判斷放在前面，只要 hashcode 不相等就玩兒完，不用再去調用複雜的 equals 了。

很多程度地提升 HashMap 的使用效率。

所以重寫 hashcode 方法是為了讓我們能夠正常使用 HashMap 等集合類，因為 HashMap 判斷對象是否相等既要比較 hashcode 又要使用 equals 比較。

而這樣的實現是為了提高 HashMap 的效率。

附上源碼圖：

4. HashMap為什麼不直接使用對象的原始hash值呢?

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

我們發現，HashMap的哈希值是通過上面的方式獲取，而不是通過key.hashCode()方法獲取。

原因：

通過移位和異或運算，可以讓 hash 變得更復雜，進而影響 hash 的分佈性。

5. 既然紅黑樹那麼好，為啥hashmap不直接採用紅黑樹，而是當大於8個的時候才轉換紅黑樹？

因為紅黑樹需要進行左旋，右旋操作， 而單鏈表不需要。

以下都是單鏈表與紅黑樹結構對比。

如果元素小於8個，查詢成本高，新增成本低。

如果元素大於8個，查詢成本低，新增成本高。

至於為什麼選數字8，是大佬折中衡量的結果-.-，就像loadFactor默認值0.75一樣。

以上就是在HashMap源碼分析，希望可以幫助到你，下面展示了部分資料，也希望也能幫助到大家，對編程感興趣想進階的朋友，如果能幫到你請點贊、點贊、點贊：

整理的 pdf 文檔：

源碼分析專題部分課程：

獲取方式

點贊，收藏並轉發文章後點擊小編頭像或暱稱，關注後私信回覆：【11】 即可

舉手之勞，非常感謝！！！

閱讀更多 java架構師小旭 的文章

關鍵字: 源碼 數據結構 分析