List 系列差不多寫完了， 單線程環境下最重要的就是 ArrayList 和LinkedList，多線程環境下最重要的就是CopyOnWriteArrayList，新來的同學可以點擊鏈接回顧一下 List 的知識點。接下來，我要帶着 HashMap 去爬山了，注意不是六峯山，純粹就是爲了鍛鍊了一下身體，不不不，純粹是爲了和 HashMap 拉近關係，同學們注意不要掉隊。

說一句很廢的話，HashMap 是一個 Map，用來存儲 key-value 的鍵值對，每個鍵都可以精確地映射到一個值，然後我們可以通過這個鍵快速地找到對應的值。

對於一個 List 來說，如果要找到一個值，時間複雜度爲，如果 List 排序過的話，時間複雜度可以降低到（二分查找法），但如果是 Map 的話，大多數情況下，時間複雜度能夠降低到。

來看一下 HashMap 的特點：

• HashMap 的鍵必須是唯一的，不能重複。

• HashMap 的鍵允許爲 null，但只能有一個這樣的鍵；值可以有多個 null。

• HashMap 是無序的，它不保證元素的任何特定順序。

• HashMap 不是線程安全的；多線程環境下，建議使用 ConcurrentHashMap，或者使用 Collections.synchronizedMap(hashMap) 將 HashMap 轉成線程同步的。

• 只能使用關聯的鍵來獲取值。

• HashMap 只能存儲對象，所以基本數據類型應該使用其包裝器類型，比如說 int 應該爲 Integer。

• HashMap 實現了 Cloneable 和 Serializable 接口，因此可以拷貝和序列化。

01、HashMap 的重要字段

HashMap 有 5 個非常重要的字段，我們來了解一下。（JDK 版本爲 14）

transient Node<K,V>[] table;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

1）table 是一個 Node 類型的數組，默認長度爲 16，在第一次執行 resize() 方法的時候初始化。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
final HashMap.Node<K,V>[] resize() {
    newCap = DEFAULT_INITIAL_CAPACITY;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}

Node 是 HashMap 的一個內部類，實現了 Map.Entry 接口，本質上是一個鍵值對。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    HashMap.Node<K,V> next;


    Node(int hash, K key, V value, HashMap.Node<K,V> next) {
        ...
    }


    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }


    public final int hashCode() {
        ...
    }


    public final V setValue(V newValue) {
        ...
    }


    public final boolean equals(Object o) {
        ...
    }
}

2）size 就是 HashMap 中實際存儲的鍵值對數量，它和 table 的 length 是有區別的。

爲了說明這一點，我們來看下面這段代碼：

HashMap<String,Integer> map = new HashMap<>();
map.put("1", 1);

聲明一個 HashMap，然後 put 一個鍵值對。在 put() 方法處打一個斷點後進入，等到該方法臨近結束的時候加一個 watch（ table.length ），然後就可以觀察到如下結果。

也就是說，數組的大小爲 16，但 HashMap 的大小爲 1。

3）modCount 主要用來記錄 HashMap 實際操作的次數，以便迭代器在執行 remove() 等操作的時候快速拋出 ConcurrentModificationException，因爲 HashMap 和 ArrayList 一樣，也是 fail-fast 的。

關於 ConcurrentModificationException 的更多信息，請點擊下面的鏈接查看 03 小節的內容。

4）threshold 用來判斷 HashMap 所能容納的最大鍵值對數量，它的值等於數組大小 * 負載因子。默認情況下爲 12（16 * 0.75），也就是第一次執行 resize() 方法的時候。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;


final HashMap.Node<K,V>[] resize() {
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

5）loadFactor 爲負載因子，默認的 0.75 是對空間和時間效率上的一個平衡選擇，一般不建議修改，像我這種工作了十多年的老菜鳥，就從來沒有修改過這個值。

02、HashMap 的 hash 算法

Hash，一般譯作“散列”，也有直接音譯爲“哈希”的，這玩意什麼意思呢？就是把任意長度的數據通過一種算法映射到固定長度的域上（散列值）。

再直觀一點，就是對一串數據 wang 進行雜糅，輸出另外一段固定長度的數據 er——作爲數據 wang 的特徵。我們通常用一串指紋來映射某一個人，別小瞧手指頭那麼大點的指紋，在你所處的範圍內很難找出第二個和你相同的（人的散列算法也好厲害，有沒有？）。

對於任意兩個不同的數據塊，其散列值相同的可能性極小，也就是說，對於一個給定的數據塊，找到和它散列值相同的數據塊極爲困難。再者，對於一個數據塊，哪怕只改動它的一個比特位，其散列值的改動也會非常的大——這正是 Hash 存在的價值！

同學們已經知道了，HashMap 的底層數據結構是一個數組，那不管是增加、刪除，還是查找鍵值對，定位到數組的下標非常關鍵。

那 HashMap 是通過什麼樣的方法來定位下標呢？

第一步， hash() 方法：

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

第二步， putVal() 方法中的一行代碼：

n = (tab = resize()).length;
i = (n - 1) & hash;

爲了更容易理解，我把這兩步的方法合併到了一起：

String [] keys = {"沉","默","王","二"};
for (String k : keys) {
    int hasCode = k.hashCode();
    int right = hasCode >>> 16;
    int hash = hasCode ^ right;
    int i = (16 - 1) & hash;
    System.out.println(hash + " 下標：" + i);
}

1） k.hashCode() 用來計算鍵的 hashCode 值。對於任意給定的對象，只要它的 hashCode() 返回值是相同，那麼 hash() 方法計算得到的 Hash 碼就總是相同的。

要能夠做到這一點，就要求作爲鍵的對象必須是不可變的，並且 hashCode() 方法要足夠的巧妙，能夠最大可能返回不重複的 hashCode 值，比如說 String 類。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;


        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

2） >>> 爲無符號右移運算符，高位補 0，移多少位補多少個 0。

3） ^ 爲異或運算符，其運算規則爲 1^0 = 1、1^1 = 0、0^1 = 1、0^0 = 0。

4） & 爲按位與運算符，運算規則是將兩邊的數轉換爲二進制位，然後運算最終值，運算規則即（兩個爲真才爲真）1&1=1、1&0=0、0&1=0、0&0=0。

關於 >>> 、 ^ 、 & 運算符，涉及到二進制，本篇文章不再深入研究，感興趣的同學可以自行研究一下。

假如四個字符串分別是"沉","默","王","二"，它們通過 hash() 方法計算後值和下標如下所示：

27785 下標：9
40664 下標：8
29579 下標：11
20108 下標：12

應該說，這樣的 hash 算法非常巧妙，尤其是第二步。

HashMap 底層數組的長度總是 2 的 n 次方，當 length 總是 2 的 n 次方時， (length - 1) & hash 運算等價於對數組的長度取模，也就是 hash%length ，但是 & 比 % 具有更高的效率。

03、HashMap 的 put() 方法

HashMap 的 hash 算法我們是明白了，但似乎有一絲疑慮，就是萬一計算後的 hash 值衝突了怎麼辦？

比如說，“沉X”計算後的 hash 值爲 27785，其下標爲 9，放在了數組下標爲 9 的位置上；過了一會，又來個“沉Y”計算後的 hash 值也爲 27785，下標也爲 9，也需要放在下標爲 9 的位置上，該怎麼辦？

爲了模擬這種情況，我們來新建一個自定義的鍵類。

public class Key {
    private final String value;


    public Key(String value) {
        this.value = value;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Key key = (Key) o;
        return value.equals(key.value);
    }


    @Override
    public int hashCode() {
        if (value.startsWith("沉")) {
            return "沉".hashCode();
        }
        return value.hashCode();
    }
}

在 hashCode() 方法中，加了一個判斷，如果鍵是以“沉”開頭的話，就返回“沉”的 hashCode 值，這就意味着“沉X”和“沉Y”將會出現在數組的同一個下標上。

HashMap<Key,String> map = new HashMap<>();
map.put(new Key("沉X"),"沉默王二X");
map.put(new Key("沉Y"),"沉默王二Y");

那緊接着來看一下 put() 方法的源碼：

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

put() 方法會先調用 hash() 方法計算 key 的 hash 值，然後再調用內部方法 putVal() ：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
    // ①、數組 table 爲 null 時，調用 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 {
        HashMap.Node<K,V> e; K k;
        // ③、如果鍵已經存在了，並且 hash 值相同，直接覆蓋
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // ④、紅黑樹處理
        else if (p instanceof HashMap.TreeNode)
            e = ((HashMap.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);
                    // 如果鏈表長度大於 8 轉換爲紅黑樹處理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果鍵已經存在了，並且 hash 值相同，直接覆蓋
                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;
}

代碼裏我加了一些註釋，同學們一定要花點時間看一下。

如果哈希衝突的話，會執行 ② 處對應的 else 語句，先判斷鍵是否相等，相等的話直接覆蓋；否則執行 ④，做紅黑樹處理；如果不是，會執行 ⑤，把上一個節點的 next 賦值爲新的 Node。

也就是說，如果哈希衝突了，會在數組的同一個位置上增加鏈表，如果鏈表的長度大於 8，將會轉化成紅黑樹進行處理。

以上就是大牛們嘴裏常說的“鏈地址法”，簡單點說，就是數組加鏈表，由於鏈表的查詢效率比較低（時間複雜度爲），Java 8 又追加了紅黑樹（時間複雜度爲）。

留個小作業哈，同學們可以研究一下，當鍵爲 null 的時候，鍵值對存放在什麼位置上？

04、HashMap 的 get() 方法

理解了 HashMap 的 hash 算法和 put() 方法， get() 方法就很容易理解。

public V get(Object key) {
    HashMap.Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

首先計算 key 的 hash 值，當 hash 值確定後，鍵值對在數組中的下標位置也就確定了，然後再調用 getNode() 方法：

final HashMap.Node<K,V> getNode(int hash, Object key) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> 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) {
            if (first instanceof HashMap.TreeNode)
                return ((HashMap.TreeNode<K,V>)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;
}

其中 first = tab[(n - 1) & hash] 就可以快速的確定鍵對應的值，如果鍵相等並且鍵的 hash 相等，則直接返回；如果鍵的哈希衝突了，就先判斷是不是紅黑樹，不是的話就遍歷鏈表。

05、最後

說句實在話，在寫這篇文章之前，我對 HashMap 的認知並沒有這麼深刻，但寫完這篇文章後，我敢拍着胸脯信誓旦旦地說：“HashMap 我真的掌握了，同學們誰以後再問我，就可以把這篇文章甩給他了。”

這次爬山雖然很累，但確實收穫很大，值了！

------------------

公衆號：沉默王二（ID：cmower）
CSDN：沉默王二
這是一個有顏值卻靠才華喫飯的程序員，你知道，他的文章風趣幽默，讀起來就好像花錢一樣爽快。

長按下圖二維碼關注，你將感受到一個有趣的靈魂， 且每篇文章都有乾貨。