1.定義

HashMap是實現(xiàn)了Map接口的key-value集合，實現(xiàn)了所有map的操作洞斯，允許key和value為null,hashMap不是線程安全的尝丐。

從上面的定義提出兩個疑問

1.HashMap內部的實現(xiàn)是怎樣的?

2.HashMap不是線程安全的掺逼，是因為什么?

下文的分析將圍繞這兩個問題開始吃媒，另外本文源碼來自與JDK_1.8.0_131

2.結構

2.1 類圖結構

image

如上圖所示，是HashMap的類圖結構吕喘，其主要實現(xiàn)赘那、繼承了以下接口和類:

1.Map 接口： 定義將鍵值映射到值的對象，Map規(guī)定不能包含重復的鍵值氯质，每個鍵最多可以映射一個值,這個接口是用來替換Dictionary類募舟。

2.AbstractMap 類： 提供了一個Map骨架的實現(xiàn),盡量減少了實現(xiàn)Map接口所需要的工作量

3.Cloneable 接口： 實現(xiàn)了該接口的類可以顯示的調用Object.clone()方法，合法的對該類實例進行字段復制闻察，如果沒有實現(xiàn)Cloneable接口的實例上調用Obejct.clone()方法拱礁，會拋出CloneNotSupportException異常。正常情況下蜓陌，實現(xiàn)了Cloneable接口的類會以公共方法重寫Object.clone()

4.Serializable 接口： 實現(xiàn)了該接口標示了類可以被序列化和反序列化觅彰，具體的 查詢序列化詳解

2.2 基本屬性及構造方法

2.2.1 基本屬性

HashMap的基本屬性如代碼所示：

//默認的初始化容量為16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大的容量吩蔑，容量的值必須是2的冪并且小于最大的容量钮热，最大值為2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//加載因子默認值為0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//計數(shù)閾值，超過這個值將會使用樹形結構替代鏈表結構
static final int TREEIFY_THRESHOLD = 8;

//由樹形結構轉換成鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;

//樹形結構最小的容量為64
static final int MIN_TREEIFY_CAPACITY = 64;

//鏈表數(shù)組
transient Node<K,V>[] table;

//HashMap中value的集合
transient Set<Map.Entry<K,V>> entrySet;

//HashMap的長度
transient int size;

//調整大小的下一個大小值
int threshold;

//hashtable的加載因子
final float loadFactor;

2.2.2 構造方法

HashMap提供了4個構造方法烛芬，如下所示

1.public HashMap(int initialCapacity, float loadFactor)：需要傳入自定義的initialCapacity(初始化容量)隧期，loadFactor(加載因子)

2.public HashMap(int initialCapacity)：需要傳入自定義的initialCapacity(初始化容量)飒责，實際在平時的使用過程中如果可以大概知道數(shù)據(jù)量，建議使用這種構造方法仆潮，原因是指定了HashMap的容量之后宏蛉，可以避免沒必要的擴容操作，從而減少了浪費性置。

3.public HashMap()：默認的構造方法拾并，按照初始值創(chuàng)建HashMap

4.public HashMap(Map<? extends K, ? extends V> m)：需要傳入一個Map集合

3.原理

3.1 內部結構

image

如上圖所示，是HashMap內部實現(xiàn)的結構圖鹏浅，正如2.2.1中介紹的其內部是個Node<K,V>類型的數(shù)組嗅义。數(shù)組中保存的有兩種數(shù)據(jù)結構，第一種是鏈表隐砸，第二種是樹形結構(使用的是紅黑樹之碗，后面的文章中會做詳細介紹)，下面通過源碼了解下HashMap是如何實現(xiàn)這樣的結構的季希。

3.2 實現(xiàn)

3.2.1 添加元素

如下為HashMap添加元素的put方法的源碼褪那，

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
/**
 * hash:為hash值
 * key:保存的key
 * value:保存的value
 * onlyIfAbsent:如果為true,不改變已經存在的值
 * evict:如果為false,表示table處于創(chuàng)造模式
**/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判斷table是否為空或者長度為0，若是則調用resize()新建數(shù)組
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //然后定位當前需要保存的值在數(shù)組中位置式塌，如果沒有沖突博敬，即當前位置上沒有值則新增節(jié)點并將其添加
    if ((p = tab[i = (n - 1) & hash]) == null)
      //這里當hash=0時，即key值為空時峰尝，該值將會保存在tab[0]的位置
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //判斷是否為新增的元素是否為第一個元素(hash與key去判斷)冶忱，如果是則獲取第一個元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 判斷是否為樹形節(jié)點，如果是則新增一個樹形節(jié)點
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        // 是鏈表節(jié)點
            for (int binCount = 0; ; ++binCount) {
                //循環(huán)查找境析，直到鏈表末尾囚枪，添加新節(jié)點
                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與key相等 則終止循環(huán)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 節(jié)點的引用向后移動
                p = e;
            }
        }
        // 存在key對應的value時劳淆，按照條件替換并返回舊值
        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中大體上可以分為三個步驟：

1.定位：首先計算出key對應的hash值，在將(tab.length()-1) & hash方式定位出當前添加的key-value在Node<K,V>[] tab中的索引位置(其實這里有個問題沛鸵，就是為啥(tab.length()-1) & hash這種方式能保證分配的相對均勻括勺，由于tab.length()是2的n次方的,
(tab.length()-1) & hash運算等于對tab.length()進行取模運算，但是&操作相對于%操作曲掰，性能肯定是更優(yōu)的疾捍，疑問為什么更優(yōu))

2.解決hash沖突：
首先介紹下解決Hash沖突的方式實際上有兩種，第一種是開放尋址栏妖，指的是當桶中位置被占據(jù)時乱豆，將通過探尋的方式，來尋找到未被占據(jù)的哈希桶吊趾，第二種是分離鏈接宛裕，將每個哈希桶當做鏈表的頭瑟啃，當發(fā)生hash沖突時，在鏈表中進行操作揩尸。而HashMap中使用的方式是第二種方式蛹屿，這一步是HashMap實現(xiàn)的關鍵，其步驟如下：

• 1.根據(jù)定位在tab中的位置岩榆，找到根節(jié)點错负，若根節(jié)點為空則直接新增節(jié)點，若不為空則分為三種情況處理

• 2.判斷新加入的key-value勇边，是不是加在根節(jié)點湿颅，若是則獲取

• 3.若不是，則判斷是否為TreeNode類型粥诫，若是TreeNode類型則新增TreeNode節(jié)點

• 4.若不是油航，則循環(huán)處理（這里也有兩種情況，一種是添加的key已經存在怀浆，則根據(jù)條件覆蓋原值谊囚，另一種是key不存在，則在鏈表尾部添加節(jié)點）,還有點需要注意的是执赡，鏈表中添加元素會去判斷镰踏，若鏈表的長度大于設定的閾值8，會將鏈表結構轉換成樹形結構

3.擴容：判斷當前HashMap的size是否大于閾值threshold沙合，如果大于了閾值則進行擴容操作奠伪，

3.2.2 具體細節(jié)

在上面的整體流程中，可以大概理解HashMap是如何工作的首懈，下面將詳細介紹一下操作實現(xiàn)的細節(jié)：

1.新增節(jié)點：這個方法比較簡單就是調用Node類的構造方法绊率，創(chuàng)建一個Node節(jié)點對象

2.新增TreeNode：這個詳細可參考JAVA學習-紅黑樹詳解

3.鏈表轉樹形：具體分為兩步，第一將所有的節(jié)點變成TreeNode類型的究履，第二構建紅黑樹滤否，具體代碼可以去查看treeifyBin()方法的代碼實現(xiàn)。

4.擴容：如下代碼是HashMap中的擴容操作的具體實現(xiàn)最仑，從代碼中可以看出擴容操作主要分為以下幾步：

• 計算新容量：根據(jù)老數(shù)組的容量確定擴容后的容量值藐俺，一般擴容為老容量的2倍
• 創(chuàng)建新數(shù)組：根據(jù)新的容量創(chuàng)建數(shù)組，需要盡量避免擴容的發(fā)生泥彤，因為產生新的數(shù)組必然是會消耗一定的內存空間欲芹。
• 元素放置到新數(shù)組：循環(huán)遍歷老數(shù)組，將元素重新放置到新數(shù)組中吟吝，分為3種情況如下所示

  • 根節(jié)點:定位在新數(shù)組中的位置菱父，通過e.hash & (newCap - 1)進行定位，直接放置到根節(jié)點的位置

  • 樹形節(jié)點：樹形節(jié)點其實方式和鏈表節(jié)點是類似的，但是其中會考慮是否將樹轉換為鏈表的情況滞伟，稍微復雜點，若想了解的更加清楚可以查看源碼中的split方法進行學習炕贵。

  • 鏈表節(jié)點：對于鏈表節(jié)點代碼中使用了兩個引用去記錄梆奈，當e.hash & oldCap的結果為0時使用loTail記錄，反而使用hiHead称开，后面根據(jù)定位將整條鏈表賦值給新的數(shù)組亩钟，值得注意的是這里面并未倒置鏈表。
    其中有幾點存在疑問的：

    • 第一：定位為什么不是j就是j+oldCap?

    首先擴容操作之后新的容量變?yōu)榕f容量的兩倍鳖轰，則若原容量為n=16(10000),n-1=15(01111),則擴容之后n=32(100000),n-1=31(011111),而在HashMap中定位元素的位置是通過(n-1) & hash的方式清酥，可以比較擴容前與擴容后的n-1,實際上就是高位上多了個1，那么現(xiàn)在假設元素hash值高位上為0蕴侣，則運算后該元素在擴容前后的位置并不會發(fā)生變化焰轻，而假設元素hash的高位上是1，則運算后該元素在擴容前的位置為h昆雀，則擴容后的位置為h+newCap/2,即為h+oldCap辱志，從而可以看出擴容后定位要么是擴容前的位置，要么是擴容前的位置+老的容量

    • 第二：e.hash & oldCap這個是來判斷什么?

    通過問題1狞膘，這個問題就很明顯了e.hash & oldCap是用來判斷hash值高位上的值是0還是1的揩懒，可以看出假如是1則&運算后得到的結果肯定為大于0，反而肯定等于0

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //獲取老的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;//擴容的閾值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        //超過最大的容量值為2^30挽封，則返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }//新容量為老容量的兩倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
                 //擴容的閾值也變?yōu)樵瓉淼膬杀?            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    //創(chuàng)建了新容量的數(shù)組
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
    //循環(huán)老數(shù)組已球，將老數(shù)組中的元素從新放置到新的數(shù)組中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)//只有一個元素的情況，直接定位并添加到數(shù)組中
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)//樹形
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 鏈表重新裝填到新數(shù)組中
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> 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;
}

3.2.3 查找元素

如下代碼是HashMap中查找元素實際調用的代碼

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //定位頭節(jié)點
    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 TreeNode)
                return ((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;
}

其實通過上面代碼可以清晰看出它的思想辅愿，就是去根據(jù)hash遍歷查找智亮，首先第一步，肯定是找到在數(shù)組中頭節(jié)點的位置即通過(n-1) & hash值定位到其頭節(jié)點点待，這種方式也就是在新增元素時的定位操作鸽素，下面就是幾種情況去處理：

• 1.判斷頭節(jié)點是不是查找的元素，若是則直接返回了亦鳞，若不是則繼續(xù)查找馍忽。
• 2.判斷是否為TreeNode節(jié)點，若是則遍歷紅黑樹查找燕差，詳細可參考JAVA學習-紅黑樹詳解
• 3.判斷是否為鏈表節(jié)點遭笋，若是則遍歷鏈表查找

4.總結

通過本文可以了解以下幾點：

1.HashMap的內部實現(xiàn)是數(shù)組+(鏈表/紅黑樹實現(xiàn)的),即回答了本文提出的第一個問題

2.HashMap內部是如何解決hash沖突以及如何進行擴容操作的。

需要注意的是,HashMap不是線程安全的徒探，因此在涉及線程安全的情況下盡量不要使用HashMap瓦呼，再就是在使用HashMap時可以盡量減少其擴容的操作，在可估算數(shù)據(jù)量的情況下可以指定HashMap的初始化容量测暗，當然這是相對的央串，若數(shù)據(jù)量太大磨澡，還是建議別這樣做。還有一點就是本文是基于JDK_1.8.0_131,還有很多細節(jié)的實現(xiàn)并未做詳細的說明质和，如果想要了解的更多稳摄，可以閱讀源碼進行學習，若發(fā)現(xiàn)有存在問題的地方饲宿，望指正厦酬。

本文主要參考鏈接如下
Java8系列之重新認識HashMap