學習背景

由于整個HashMap底層原始碼實作很多，很難全部剖析，望見諒，本文主要挑選作業和面試經常遇到的一些重點和難點進行剖析即可，希望對你有所幫助！
在進入正文之前，我們知道JDK底層原始碼很多地方都用到了位運算以及進制相關的知識，HashMap底層也不例外，二進制是計算機底層存盤格式，你電腦上所有東西，檔案，視頻，音樂，全部是二進制方式存盤的，十進制就是我們平時的阿拉伯數字沒啥可說，在學習本文時，建議先快速了解下Java幾種位運算以及常見進制說明，特別是二進制的位運算，可以查看我的這篇文章進行快速了解下 https://blog.csdn.net/JustinQin/article/details/120505776

HashMap特性

• 繼承AbstractMap抽象類，實作Map介面以及Cloneable, java.io.Serializable克隆和序列化
• 底層是由陣列+鏈表組成的哈希表，JDK1.8鏈表長度超過8并且table陣列大小大于64時才會將鏈表優化為紅黑樹
• 增刪改查的效率都比較高，但多執行緒環境下是不安全的，可能存在問題
• 存盤的元素是鍵值對，key鍵是唯一的，并且允許為key/value為null但不保證順序
• 通過key的hash值計算出需要存放在哈希表中的陣列位置index
• 默認初始化容量大小為0，第一次呼叫put真正給默認大小16，每次擴容oldCap << 1即原來容量的2倍
• 常用的API方法put(key,value)/get(key)/size()/isEmpty()/containsKey(key)/remove(key)
• 底層原始碼關鍵屬性table、threshold、loadFactor、modCount、size

HashMap添加元素四步曲

前奏：HashMap如何添加一個元素？

HashMap底層資料結構主要通過put(K key, V value)方法添加元素，底層四步曲如下：

• 第一步曲：根據key得到hashCode值
• 第二步曲：根據hashCode值計算出hash值
• 第三步曲：根據hash值計算出哈希表陣列index下標
• 第四步曲：將元素節點保存到哈希表指定陣列index下標

HashMap添加元素的示例代碼：

        HashMap<Object, Object> map = new HashMap<>();
        map.put("name","Justin");

HashMap底層put(key,value)方法原始碼：

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

再看下，hash方法實作原始碼：

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

接下來將解讀HashMap底層原始碼添加元素四部曲具體實作

第一步曲：根據key得到hashCode值

以上面示例代碼說明，這里key是字串"name"，String重寫了計算字串hashCode值的hashCode()方法，原始碼如下：

計算得到hashCode值為3373707

第二步曲：根據hashCode值計算出hash值

hash值計算的程序用到了^（異或）和>>>(無符號右移)兩種位運算
(h = key.hashCode()) ^ (h >>> 16) 即 (3373707) ^ (3373707 >>> 16)
這里為了方便展示，二進制每四位使用空格格式化，位運算程序如下：

計算key="name"的hash值二進制結果是1100110111101010111000轉成十進制為3373752

進制在線轉換：https://c.runoob.com/front-end/58/

即計算key="name"的hash值為3373752，也可以debug斷點往后查看hash值剛好也是這個值

第三步曲：根據hash值計算出哈希表陣列index下標

公式：i = (n - 1) & hash

這里公式(n - 1) & hash 用到了&按位與運算（都為1則得1），奧妙之處在于n表示HashMap中的陣列容量大小，并且剛好是16,32,64…2的次方，這種情況其實是等效于 hash % n 取模計算出的陣列index下標值，并且下標不會超過容量(n-1)即能夠保證不會陣列下標越界

但是HashMap這里沒有使用%取模，而是使用位運算，直接對記憶體資料進行操作，效率最高，如果使用%取模需要先將記憶體資料轉成十進制再進行運算，多了這部分的性能開銷，效率會變低

HashTable底層倒是用的%取模，hash值與十六進制0x7FFFFFFF做按位與運算目的是為了保證hash值始終是正數

有的小伙伴可能會問了，使用%取模計算，那這里為啥HashTable還在用，我想說的是其實也可以優化，只不過HashTable本身就是主打synchronized執行緒安全，也就不考慮優化%取模為位運算了吧

第四步曲：將元素節點保存到哈希表指定陣列index下標

    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;
        if ((p = tab[i = (n - 1) & hash]) == null)
            //該位置首次添加節點，則直接新建節點添加
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            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);
                        //如果遍歷指定位置的鏈表現有節點已經是大于等于8個了
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //則當前節點，需要通過該方法進行添加
                            //如果陣列容量大于64，該程序會進行鏈表轉化為紅黑樹
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //HashMap對于key已經存在的處理情況是
            //除非該key對應的value為null，否則一律不做任何處理
            //Hashtable中則是會直接更新key對應的value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //集合修改次數，沒操作一次+1
        ++modCount;
        //HashMap容量大小大于臨界值，則進行resize()擴容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

終曲：為什么HashMap底層原始碼用這么多位運算？

關于位運算的使用，文中在介紹第三步曲時，也提到了HashMap計算陣列下標使用%取模和位運算的問題，使用于位運算的奧妙之處在直接從記憶體讀取資料進行計算，不需要轉成十進制，如果使用%取模需要先轉成十進制，有性能開銷，效率比較低

HashMap底層除了文中提到的^按位異或、>>>無符號右移、&按位與位運算，其實在HashMap的擴容機制resize()中，還用到了<<左移運算
oldCap << 1

這里oldCap << 1剛好是兩倍，可以總結的說一個數與n進行左移運算，結果為這個數乘以2的n次方
oldCap << 1 等值 oldCap = oldCap * (2的n次方)
同理，一個數與n進行右移運算結果為這個數除以2的n次方
oldCap >> 1 等值 oldCap = oldCap / (2的n次方)

**

HashMap鏈表轉為紅黑樹

紅黑樹結構

紅黑樹五大特性

• 節點有紅色或黑色兩種；
• 根節點是黑色；
• 葉子節點全部是黑色(如圖方框是葉子節點)；
• 紅色節點必須配兩個黑色節點（即保證任意路不會出現兩個連續紅色節點）；
• 從任意節點到該節點下所有葉子節點包含的黑色節點個數相同（也簡稱黑高），

HashMap鏈表轉為紅黑樹程序

代碼示例：

public class Test {
    public static void main(String[] args) {
        HashMap<Object, Object> map = new HashMap<Object, Object>();
        //下標為0
        map.put(null, "Justin");
        map.put(16, "Justin");

        //下標為8
        map.put(8, "Justin");      //鏈表第1個節點
        map.put(24, "Justin");     //鏈表第2個節點
        map.put(40, "Justin");     //鏈表第3個節點
        map.put(56, "Justin");     //鏈表第4個節點
        map.put(72, "Justin");     //鏈表第5個節點
        map.put(88, "Justin");     //鏈表第6個節點
        map.put(104, "Justin");    //鏈表第7個節點
        map.put(120, "Justin");    //鏈表第8個節點
        map.put("name", "Justin"); //在添加第9個節點時，鏈表會被轉換為紅黑樹
    }
}

上述代碼添加元素完成后，大多數人認為，底層哈希表的資料結構如下：

看起來好像沒啥毛病，但實際哈希表index=8的位置鏈表并不會轉成紅黑樹，原因如下：

再來看下treeifyBin(tab,hash)為什么不將鏈表轉成紅黑樹？

其中tab.length < MIN_TREEIFY_CAPACITY表示只要哈希表陣列大小于64容量的，不可能會發生鏈表樹化的程序，所以示例代碼中，在哈希表陣列下標index=8位置，添加第9個key="name"元素時，此時哈希表大小只有16， tab.length < MIN_TREEIFY_CAPACITY即16 < 64 接進行resize()擴容并重新計算各個元素存盤的位置了，并不會走后面的鏈表轉紅黑樹的程序，

當添加key="name"節點時，會進行擴容，容量大小由16變為32，此時oldMap資料遷移到newMap后資料排列如何呢？
這里比較簡單，沒涉及到紅黑樹的拆分，而且鏈表長度都是大于1個的，直接由(hash & oldCap)重新計算位置：

public class Test {
    public static void main(String[] args) {
        cal(null,0);
        cal(16,0);

        cal(8,8);
        cal(24,8);
        cal(40,8);
        cal(56,8);
        cal(88,8);
        cal(72,8);
        cal(104,8);
        cal(120,8);
        cal("name",8);
    }

    static void cal(Object key,int oldIndex) {
        //將oldMap容量和節點hash值進行&按位與運算
        if( (16 & hash(key)) ==  0){//結果為0，節點放到newMap位置與在oldMap下標index位置一樣
            System.out.println("原key=" + key + "，遷移到newMap陣列下標位置為：" + oldIndex);
        }else{//結果不為0，節點放到newMap位置剛好等于oldMap下標index位置 + oldMap陣列容量大小
            System.out.println("原key=" + key + "，遷移到newMap陣列下標位置為：" + (oldIndex + 16));
        }
    }

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

原來所有key，遷移到newMap后陣列index下標位置如下：

原key=null，遷移到newMap陣列下標位置為：0
原key=16，遷移到newMap陣列下標位置為：16
原key=8，遷移到newMap陣列下標位置為：8
原key=24，遷移到newMap陣列下標位置為：24
原key=40，遷移到newMap陣列下標位置為：8
原key=56，遷移到newMap陣列下標位置為：24
原key=88，遷移到newMap陣列下標位置為：24
原key=72，遷移到newMap陣列下標位置為：8
原key=104，遷移到newMap陣列下標位置為：8
原key=120，遷移到newMap陣列下標位置為：24
原key=name，遷移到newMap陣列下標位置為：24

所以示例代碼，添加元素后，正確的資料結構應該是這樣的：

通過debug斷點，也可以看到擴容后節點主要被分配到了8、16、24這個三個陣列下標位置：

不過一般情況下，HashMap擴容是發生在添加元素時，最后通過++size > threshold判斷容量大于臨界值時，才進行resize()擴容

HashMap擴容機制

• 擴容情況1：第一次添加元素會進行擴容，默認初始化容量為16
• 擴容情況2：哈希表容量小于64時，鏈表長度每次大于8，都會進行resize()擴容
• 擴容情況3：HashMap容量大于臨界值時

幾種擴容情況的原始碼如下：

    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)
            //擴容情況1：第一次添加元素會進行擴容，默認初始化容量為16
            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;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            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
                            //擴容情況2：見treeifyBin方法說明
                            treeifyBin(tab, hash);
                        break;
                    }
                    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(); //擴容情況3：HashMap容量大于臨界值時
        afterNodeInsertion(evict);
        return null;
    }

treeifyBin原始碼如下：

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //擴容情況2：哈希表容量小于64時，鏈表長度每次大于8，都會進行resize()擴容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize(); 
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            //鏈表樹化的程序...
        }
    }

再來看HashMap的resize()擴容關鍵原始碼：

    final Node<K,V>[] resize() {
        ...
        if (oldCap > 0) {
            ...
            //oldCap << 1即2倍擴容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        ...
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            //遍歷oldMap按一定規則，遷移資料到newMap
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        //對于哈希表陣列后鏈表只有一個節點的
                        //需要根據hash值重新計算新的下標位置
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        //對紅黑樹進行拆分
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //對于哈希表陣列后鏈表有多個節點的
                        //通過(hash & oldMap)演算法以及lo、hi節點進行分組巧妙遷移
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //這里是&按位與運算是oldMap遷移資料到newMap的奧妙之處
                            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;
                            //按位與結果為0的，節點遷移到newMap下標與oldMap中下標一樣
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            //按位與結果不為0的，節點遷移到newMap下標
                            //則剛好等于原oldMap中下標 + oldCap老容量
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

可以看到其實HashMap擴容機制很簡單，核心就是newCap = oldCap << 1即2倍擴容機制，難點在于oldMap舊資料遷移到newMap的程序，會涉及紅黑樹的拆分以及哈希表陣列后鏈表有多個節點用的位運算(hash & oldMap)以及lo、hi兩種節點，這個有點理解，特別是剛讀原始碼的小伙伴，讀不懂可以先放放，以后在慢慢深入理解，

HashMap獲取元素

map.get("name");

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

這里hash值的獲取跟添加元素一模一樣：

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

主要看下獲取節點元素getNode實作原始碼：

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //這里是確定元素在哈希表哪個陣列下標，跟添加元素中原理一樣
        //也是通過位運算(n-1) & hash能確定元素所在陣列index下標
        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))))
                //每次都進行key判斷和equals比較，都一樣說明是要找的元素直接回傳
                return first;
            if ((e = first.next) != null) {//繼續取鏈表下一節點
                //如果節點是紅黑樹，則呼叫紅黑樹查找方法能快速找到節點元素回傳
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //只是普通節點，則對鏈表進行遍歷，逐一比對節點的key，找到就回傳
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

HashMap常用的API方法

HashMap底層原始碼關鍵屬性

本文對HashMap特性及底層資料結構暫時分析到這里，希望對你有所幫助！

如果你是一名Java初學者，建議先去學習本文提到的HashMap特性以及常用API如何使用，然后查看原始碼了解幾個關鍵屬性有什么用，再深入剖析增、刪、查方法底層實作的原理，其他Java基礎類別庫也是一樣，你會發現其中用到了很多資料結構與演算法、位運算等奧妙之處，