目錄1. HashMap的家族定位2. HashMap的數(shù)據(jù)結(jié)構(gòu)2.1 Hash表的基本概念2.2 Hash沖突2.3 HashMap數(shù)據(jù)結(jié)構(gòu)3. HashMap的重要變量3.1 常量3.2 變量3.3 辨析size、capacity、threshold4. HashMap重要方法和源碼解析4.1 構(gòu)造方法4.2 resize方法4.3 hash方法4.4 put方法參考文獻(xiàn)1. HashMap的家族定位

接口java.util.Map有四個(gè)常用的實(shí)現(xiàn)類，如圖是它們之間的類繼承關(guān)系。

(資料圖片僅供參考)

下面我將一一介紹其性能特點(diǎn)。

HashMap：最常用的Map實(shí)現(xiàn)類，通過使用Hash表結(jié)構(gòu)，提高查找速度；使用鍵值對(duì)作為存儲(chǔ)節(jié)點(diǎn)，只允許一個(gè)key值為null，允許多個(gè)value值為null；線程不安全，對(duì)于線程安全有要求的程序，可以考慮使用：sychronizedMap或者ConcurrentHashMap；HashTable同樣使用Hash表結(jié)構(gòu)，提高查找效率；線程安全，但是安全層級(jí)低于ConcurrentHashMap，不常用。LinkedHashMap繼承自HashMap，使用Hash表結(jié)構(gòu)，提高查找效率；鏈表插入維持插入順序。TreeMapsortedMap接口的實(shí)現(xiàn)類，可使用特定的排序規(guī)則對(duì)鍵值對(duì)進(jìn)行排序；

對(duì)四種常見的實(shí)現(xiàn)類的性能比較如下圖所示：

2. HashMap的數(shù)據(jù)結(jié)構(gòu)2.1 Hash表的基本概念

Hash表是數(shù)據(jù)結(jié)構(gòu)和算法課程中學(xué)習(xí)到的一種重要的數(shù)據(jù)結(jié)構(gòu)。主要設(shè)計(jì)思想是：

使用一個(gè)長度為n的數(shù)組存儲(chǔ)相關(guān)數(shù)據(jù)。使用hash函數(shù)實(shí)現(xiàn)內(nèi)容和數(shù)組下標(biāo)的對(duì)應(yīng)，也就是hash函數(shù)的函數(shù)值為0~n之間。hash函數(shù)相同的輸入?yún)?shù)一定會(huì)產(chǎn)生相同函數(shù)值，不同內(nèi)容盡量做到函數(shù)值分散。在hash函數(shù)值對(duì)應(yīng)的下標(biāo)寫入該內(nèi)容。下次查找某元素的時(shí)候，先根據(jù)hash函數(shù)生成下標(biāo)，然后再隨機(jī)訪問數(shù)組，這樣查找效率大大提高了。

類似于一個(gè)叫賈斯汀·費(fèi)爾蘭德·亨利皮特潘（復(fù)雜內(nèi)容）的人，在酒店前臺(tái)（hash函數(shù)）入住酒店的房間編號(hào)是1004（hash函數(shù)值/數(shù)組下標(biāo)）。需要找他的人，只需要去酒店前臺(tái)查詢他住在1004房間，直接去1004房間找人就可以了，不需要一個(gè)一個(gè)房間去找。

2.2 Hash沖突

在上面的流程說明中，我們可以發(fā)現(xiàn)Hash表的實(shí)現(xiàn)關(guān)鍵就在于Hash函數(shù)，一個(gè)好的hash函數(shù)應(yīng)該保證不同的輸入內(nèi)容盡量分散其函數(shù)值。當(dāng)存入的數(shù)據(jù)過多，hash函數(shù)性能較差的時(shí)候，可能會(huì)出現(xiàn)hash沖突：

A和B是兩個(gè)不同的存儲(chǔ)內(nèi)容，但是經(jīng)過hash函數(shù)計(jì)算，得到的hash函數(shù)值相同，因此兩個(gè)內(nèi)容存儲(chǔ)在數(shù)組的同一位置。例如：賈斯汀·費(fèi)爾蘭德·亨利皮特潘和特朗普·懂王·建國同志兩個(gè)人在酒店前臺(tái)分配到的房間號(hào)都是1004，但是房間只有一張床，這時(shí)兩個(gè)人就會(huì)發(fā)生沖突。

解決沖突主要有兩種思路：

開放定址法：發(fā)生沖突的時(shí)候，后到來的元素放棄已被占用的位置，尋找新的插入位置。（再找）鏈地址法：發(fā)生沖突的時(shí)候，后到來的元素在原有位置的基礎(chǔ)上，使用鏈表的方式存儲(chǔ)。（排隊(duì)）HashMap使用的就是鏈地址法。2.3 HashMap數(shù)據(jù)結(jié)構(gòu)

節(jié)點(diǎn)NodeNode是HashMap的一個(gè)基本存儲(chǔ)單元，從源碼中可見Node實(shí)現(xiàn)了Map.Entry接口，存放的是鍵值對(duì)。在JDK1.8中的源碼中，Node的定義如下所示：

static class Node implements Map.Entry {    final int hash;    //用來定位數(shù)組索引位置    final K key;    V value;    Node next;   //鏈表的下一個(gè)node    Node(int hash, K key, V value, Node next) { ... }    public final K getKey(){ ... }    public final V getValue() { ... }    public final String toString() { ... }    public final int hashCode() { ... }    public final V setValue(V newValue) { ... }    public final boolean equals(Object o) { ... }}

JDK1.7的HashMap數(shù)據(jù)結(jié)構(gòu)數(shù)組+鏈表

如圖所示

使用鏈地址方式解決hash沖突。

JDK1.8的HashMap數(shù)據(jù)結(jié)構(gòu)數(shù)組+鏈表+紅黑樹

如圖所示

對(duì)紅黑樹的學(xué)習(xí)可參考此博客。

鏈表和紅黑樹的轉(zhuǎn)換根據(jù)鏈表長度閾值判斷，閾值為8，即鏈表長度大于8時(shí)，由鏈表轉(zhuǎn)換為紅黑樹，小于6時(shí)，由紅黑樹轉(zhuǎn)換為鏈表。

紅黑樹的引入目的：在鏈表長度較長的情況下，優(yōu)化查找效率。

3. HashMap的重要變量3.1 常量DEFAULT_INITIAL_CAPACITY默認(rèn)的數(shù)組初始容量，值為2^4=16。如果沒有指定初始數(shù)組的容量的話，就會(huì)使用這個(gè)默認(rèn)值。MAXIMUM_CAPACITY最大的數(shù)組容量，值為2^30。在擴(kuò)容的時(shí)候，如果擴(kuò)容后的容量大于這個(gè)值，就會(huì)使用這個(gè)值作為新的容量。之后如果數(shù)據(jù)再增加，不再進(jìn)行擴(kuò)容，而是直接鏈表存儲(chǔ)或者轉(zhuǎn)為紅黑樹。DEFAULT_LOAD_FACTOR默認(rèn)負(fù)載因子，值為0.75。在HashMap中，擴(kuò)容的臨界值計(jì)算公式為：臨界值（threshold） = 負(fù)載因子（loadFactor） * 容量（capacity）負(fù)載因子可以設(shè)置為任意值，但是需要注意的是：負(fù)載因子變大，hash沖突的概率就會(huì)變大，查找效率就會(huì)降低?！緺奚鼤r(shí)間】負(fù)載因子過小，會(huì)導(dǎo)致數(shù)組空間利用率低，浪費(fèi)內(nèi)存空間?！緺奚臻g】TREEIFY_THRESHOLD鏈表轉(zhuǎn)化為紅黑樹的閾值，值為8。當(dāng)一個(gè)數(shù)組節(jié)點(diǎn)所帶著的鏈表長度大于8時(shí)，鏈表會(huì)轉(zhuǎn)化為紅黑樹。UNTREEIFY_THRESHOLD紅黑樹轉(zhuǎn)化為鏈表的閾值，值為6。當(dāng)一個(gè)數(shù)組節(jié)點(diǎn)的紅黑樹節(jié)點(diǎn)小于6時(shí)，紅黑樹會(huì)轉(zhuǎn)化為鏈表。MIN_TREEIFY_CAPACITY轉(zhuǎn)換為紅黑樹的最小容量，值為64。這個(gè)變量的意思是，在HashMap不斷增加新元素的過程中，如果此時(shí)數(shù)組中的元素個(gè)數(shù)小于64，那么就選擇擴(kuò)容。當(dāng)數(shù)組元素個(gè)數(shù)大于64的時(shí)候才會(huì)考慮樹化。3.2 變量sizeHashMap中存儲(chǔ)的鍵值對(duì)個(gè)數(shù)。modCount對(duì)HashMap進(jìn)行修改的次數(shù)記錄，每次增刪則加一。threshold擴(kuò)容的臨界值，計(jì)算公式為：threshold = loadFactor * capacity。其中capacity為數(shù)組總長度，通常為了提高閾值，會(huì)使用擴(kuò)容增加capacity，而對(duì)于負(fù)載因子loadFactor，一般不會(huì)修改。loadFactor負(fù)載因子，用戶可自行設(shè)置其值，否則等于默認(rèn)值0.75。3.3 辨析size、capacity、threshold

size:實(shí)際存儲(chǔ)的鍵值對(duì)個(gè)數(shù)capacity:數(shù)組的總長度threshold:擴(kuò)容的臨界值treeify_threshold/untreeify_threahold:鏈表和紅黑樹相互轉(zhuǎn)化的閾值

4. HashMap重要方法和源碼解析4.1 構(gòu)造方法HashMap()無參構(gòu)造，使用默認(rèn)的初始容量2^4和負(fù)載因子0.75，構(gòu)造一個(gè)空的HashMap。

// 構(gòu)造一個(gè)空的 HashMap，初始容量為 16，負(fù)載因子為默認(rèn)值 0.75public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR;  // all other fields defaulted}

HashMap(int initialCapacity)指定初始容量，使用默認(rèn)的負(fù)載因子0.75。

public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);//一次性實(shí)現(xiàn)容量和負(fù)載因子的賦值}

HashMap(int initialCapacity, float loadFactor)指定初始容量和負(fù)載因子，構(gòu)造一個(gè)空的HashMap。

public HashMap(int initialCapacity, float loadFactor) {    // 如果初始容量為負(fù)數(shù)，拋出非負(fù)異常    if (initialCapacity < 0)        throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity);    // 初始容量大于最大值時(shí)1<<30，則取最大值    if (initialCapacity > MAXIMUM_CAPACITY)        initialCapacity = MAXIMUM_CAPACITY;    // 負(fù)載因子不能小于 0，并且必須是數(shù)字，否則拋異常    if (loadFactor <= 0 || Float.isNaN(loadFactor))        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);    //數(shù)值判斷合法之后，賦值    this.loadFactor = loadFactor;    this.threshold = tableSizeFor(initialCapacity);//tableSizeFor() 方法返回一個(gè)值，比initialCapacity大的最小2的冪。}

HashMap(Map m)構(gòu)造一個(gè)非空的HashMap，將m中的鍵值對(duì)存入HashMap中，默認(rèn)的負(fù)載因子 0.75，使用默認(rèn)的初始容量2^4。

public HashMap(Map m) {    this.loadFactor = DEFAULT_LOAD_FACTOR;    // 將 Map 中的 key-value 賦值到新的 Map 中去    putMapEntries(m, false);}

4.2 resize方法

當(dāng)HashMap中數(shù)組的使用量超過閾值的時(shí)候，就需要進(jìn)行擴(kuò)容。JDK1.8的源碼如下所示：

final Node[] resize() {    Node[] oldTab = table;// 當(dāng)前 table    int oldCap = (oldTab == null) ? 0 : oldTab.length;// 當(dāng)前table的大小    int oldThr = threshold;// 當(dāng)前 table 的 threshold    int newCap, newThr = 0;// 新的 table 的大小和閥值暫時(shí)初始化為 0    // 下面就是開始計(jì)算新的 table 的大小和閥值    // 第一種情況：當(dāng)前 table 的大小大于 0，則意味著當(dāng)前的 table 肯定是有數(shù)據(jù)的    if (oldCap > 0) {//        if (oldCap >= MAXIMUM_CAPACITY) {//原始容量大于最大容量，不再擴(kuò)容，直接返回原始table            threshold = Integer.MAX_VALUE;            return oldTab;        }        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)//翻倍之后不超過最大容量，原始容量小于最大容量，且大于默認(rèn)容量，那么容量翻倍，閾值也對(duì)應(yīng)翻倍            newThr = oldThr << 1;    }    // 第二種情況：當(dāng)前的 table 中無數(shù)據(jù)，但是閥值不為零，說明初始化的時(shí)候指定過容量或者閥值，但是沒有被 put 過數(shù)據(jù)，    else if (oldThr > 0)         newCap = oldThr;//此時(shí)的閥值就是數(shù)組的大小，所以直接把當(dāng)前的閥值當(dāng)做新 table 的數(shù)組大小即可。threshold = tableSizeFor(t);    // 第三種情況，這種情況就代表當(dāng)前的 table 是調(diào)用的空參構(gòu)造來初始化的，所有的數(shù)據(jù)都是默認(rèn)值。    else {//初始閾值為0，表示使用默認(rèn)值，新的 table 也只要使用默認(rèn)值即可        newCap = DEFAULT_INITIAL_CAPACITY;        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    }    // 如果新的閥值是 0，那么就簡單計(jì)算一遍就行了    if (newThr == 0) {        float ft = (float)newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                  (int)ft : Integer.MAX_VALUE);    }    threshold = newThr;    // 根據(jù)上文中計(jì)算的新表容量和閾值，初始化新的 table    // 這個(gè) newTab 就是新的 table，數(shù)組大小就是上面這一堆邏輯所計(jì)算出來的    @SuppressWarnings({"rawtypes","unchecked"})    Node[] newTab = (Node[])new Node[newCap];    table = newTab;    if (oldTab != null) {        // 遍歷當(dāng)前 table，處理每個(gè)下標(biāo)處的 bucket，將其處理到新的 table 中去        for (int j = 0; j < oldCap; ++j) {            Node e;            if ((e = oldTab[j]) != null) {                // 釋放當(dāng)前 table 數(shù)組的對(duì)象引用（for循環(huán)后，當(dāng)前 table 數(shù)組不再引用任何對(duì)象）                oldTab[j] = null;                // a、只有一個(gè) Node，則直接 rehash 賦值即可                if (e.next == null)                    newTab[e.hash & (newCap - 1)] = e;                // b、當(dāng)前的 bucket 是紅黑樹，直接進(jìn)行紅黑樹的 rehash 即可                else if (e instanceof TreeNode)                    ((TreeNode)e).split(this, newTab, j, oldCap);                // c、當(dāng)前的 bucket 是鏈表                else { // preserve order                    Node loHead = null, loTail = null;                    Node hiHead = null, hiTail = null;                    Node next;                    // 遍歷鏈表中的每個(gè) Node，分別判斷是否需要進(jìn)行 rehash 操作                    // (e.hash & oldCap) == 0 算法是精髓，充分運(yùn)用了上文提到的 table 大小為 2 的冪次方這一優(yōu)勢，下文會(huì)細(xì)講                    do {                        next = e.next;                        // 根據(jù) e.hash & oldCap 算法來判斷節(jié)點(diǎn)位置是否需要變更                        // 索引不變                        if ((e.hash & oldCap) == 0) {                            if (loTail == null)                                loHead = e;                            else                                loTail.next = e;                            loTail = e;                        }                        // 原索引 + oldCap                        else {                            if (hiTail == null)                                hiHead = e;                            else                                hiTail.next = e;                            hiTail = e;                        }                    } while ((e = next) != null);                    // 原 bucket 位置的尾指針不為空(即還有 node )                    if (loTail != null) {                        // 鏈表末尾必須置為 null                        loTail.next = null;                        newTab[j] = loHead;                    }                    if (hiTail != null) {                        // 鏈表末尾必須置為 null                        hiTail.next = null;                        newTab[j + oldCap] = hiHead;                    }                }            }        }    }    return newTab;}

為什么要*2擴(kuò)容？或者說，為什么HashMap的數(shù)組大小為2的冪在理論學(xué)習(xí)中，Hash表的大小最好是素?cái)?shù)，因?yàn)樗財(cái)?shù)能夠有效降低hash碰撞。但是HashMap并沒有采用這種做法。在上面的源碼中，我們可以看到，HashMap在擴(kuò)容的時(shí)候，數(shù)組的大小都是原來的兩倍，這是因?yàn)樵谟?jì)算索引的時(shí)候，我們使用的是size-1的n個(gè)全1二進(jìn)制串和hash值進(jìn)行與運(yùn)算，這樣可以保證計(jì)算出來的索引值一定在0~size-1之間，不會(huì)越界。如圖所示：

當(dāng)HashMap值為2的冪的時(shí)候，size-1為全1二進(jìn)制字符串，且擴(kuò)容之后，原本有沖突的兩個(gè)元素會(huì)找到各自的新索引位置。如圖所示：

在代碼中，這個(gè)步驟被進(jìn)一步簡化。如代碼片段所示：

if ((e.hash & oldCap) == 0) {  if (loTail == null)      loHead = e;  else      loTail.next = e;  loTail = e;}// 原索引 + oldCapelse {  if (hiTail == null)      hiHead = e;  else      hiTail.next = e;  hiTail = e;}

因?yàn)閔ash值是一個(gè)整數(shù)，所以hash & oldCap的結(jié)果要么是0，要么是oldCap。所以，hashMap的擴(kuò)容，實(shí)際上是將原來的數(shù)組分成兩部分，一部分的索引不變，一部分的索引變?yōu)樵饕?oldCap。這樣就保證了原來的兩個(gè)元素，擴(kuò)容之后，一定不會(huì)在同一個(gè)索引位置上。具體解釋如圖所示：

4.3 hash方法

也就是之前在理論部分所說的hash函數(shù)部分，將關(guān)鍵字key的值轉(zhuǎn)換為唯一hash值，JDK1.8源碼如下:

static final int hash(Object key) {    int h;    // 高 16 位與低 16 位進(jìn)行異或運(yùn)算    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

hashCode()函數(shù)通常和equals()函數(shù)進(jìn)行比較，hashCode()函數(shù)是根據(jù)對(duì)象的內(nèi)存地址生成一個(gè)特定的數(shù)，因此，hashCode值相同的對(duì)象不一定相同，hashCode值不同的對(duì)象一定不相同。一般判斷兩個(gè)對(duì)象是否相等，先使用hashCode()函數(shù)判斷內(nèi)存地址，如果hashCode()函數(shù)值相同，再使用equals()函數(shù)判斷內(nèi)存中的內(nèi)容，如果hashCode()函數(shù)值不同，就不需要再使用equals()函數(shù)判斷了。

這里h先設(shè)置成key值的hashCode，然后右移16位，再和原來的h進(jìn)行異或運(yùn)算，這樣做的目的是為了減少hash碰撞，提高查找效率。

之后如何從hash值映射到數(shù)組下標(biāo)，在JDK1.7的源碼如下所示:

static int indexFor(int h, int length) {    return h & (length-1);}

這里也解釋了為什么HashMap的數(shù)組大小為2的冪，因?yàn)檫@樣可以保證length-1為全1的二進(jìn)制串，與操作之后計(jì)算出來的索引值一定在0~size-1之間，不會(huì)越界，具體操作如圖所示：

4.4 put方法

put方法主要是在HashMap中存儲(chǔ)鍵值對(duì)，JDK1.8源碼如下所示：

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);//重點(diǎn)在于putVal方法}// 參數(shù) onlyIfAbsent,針對(duì)已經(jīng)存在的value，值為true表示不修改；否則表示會(huì)替換原本的value值final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {    Node[] tab; Node p; int n, i;    // ① 如果當(dāng)前 table 為空則進(jìn)行初始化    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // (n - 1) & hash 計(jì)算得到索引 i，算法在上文有提到，然后查看索引處是否有數(shù)據(jù)    // ② 如果沒有數(shù)據(jù)，則新建一個(gè)新的 Node    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    // 索引處有數(shù)據(jù)    else {        Node e; K k;        // ③ 索引處的第一個(gè) Node 的  key 和參數(shù) key 是一致的，所以直接修改 value 值即可（修改的動(dòng)作放在下面）        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;        // ④ 索引處的 bucket 是紅黑樹，按照紅黑樹的邏輯進(jìn)行插入或修改        else if (p instanceof TreeNode)            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);        // ⑤ 索引處的 bucket 是鏈表        else {            // 遍歷鏈表上面的所有 Node            for (int binCount = 0; ; ++binCount) {                // 索引處的 Node 為尾鏈                if ((e = p.next) == null) {                    // 直接新建一個(gè) Node 插在尾鏈處                    p.next = newNode(hash, key, value, null);                    // 判斷是否需要轉(zhuǎn)換為紅黑樹                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        // 鏈表轉(zhuǎn)換為紅黑樹，此方法在上文中也有介紹                        treeifyBin(tab, hash);                    break;                }                // 當(dāng)前 Node 的 key 值和參數(shù) key 是一致的，即直接修改 value 值即可（修改的動(dòng)作放在下面）                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    break;                p = e;            }        }        // 找到了相同 key 的 Node，所以進(jìn)行修改 vlaue 值即可        if (e != null) { // existing mapping for key            V oldValue = e.value;            // 修改 value 值            if (!onlyIfAbsent || oldValue == null)                e.value = value;            afterNodeAccess(e);            // 修改操作，直接 return 結(jié)束掉代碼邏輯            return oldValue;        }    }    // 記錄結(jié)構(gòu)發(fā)生變化的次數(shù)    ++modCount;    // ⑥ 判斷是否需要擴(kuò)容    if (++size > threshold)        resize();    afterNodeInsertion(evict);    // 新增的 Node，返回 null    return null;}

源代碼所抽象出來的具體的put流程可如下圖所示：

在JDK1.7中，鏈表插入使用頭插法，而在JDK1.8中，鏈表插入使用尾插法，

JDK1.7 使用頭插法的原因：考慮到熱點(diǎn)數(shù)據(jù)，后面插入的元素更有可能被最近使用，因此使用頭插法。頭插法會(huì)使鏈表上 Node 的順序調(diào)轉(zhuǎn)，而尾插法則不會(huì)，另外，頭插法也會(huì)造成環(huán)形鏈死循環(huán)等問題，參考文獻(xiàn)知乎專欄-HashMap原理詳解，看不懂算我輸（附面試題）掘金社區(qū)-詳解 HashMap 數(shù)據(jù)結(jié)構(gòu)美團(tuán)技術(shù)團(tuán)隊(duì)-Java 8系列之重新認(rèn)識(shí)HashMap

關(guān)鍵詞：