聲明：原創(chuàng)文章，轉(zhuǎn)載請注明出處。http://www.itdecent.cn/u/e02df63eaa87

Java集合系列
Java集合1-Map總結(jié)
Java集合2-HashMap詳解（含源碼分析）

1、數(shù)據(jù)結(jié)構(gòu)

HashMap底層數(shù)據(jù)結(jié)構(gòu)

從上圖可以看到，HashMap是由數(shù)組、鏈表和紅黑樹（JDK1.8）實(shí)現(xiàn)的。

• Node<K, V> table

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, 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() { return Objects.hashCode(key) ^ Objects.hashCode(value); }

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

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

HashMap的table是一個(gè)Node數(shù)組，Node是HashMap的內(nèi)部類，實(shí)現(xiàn)了Map.Entry<K, V>，也就是說，Node可以理解為是一個(gè)包含Key, Value組合的桶。

• 沖突解決
  常見的Hash沖突解決的方法有：開放地址法（線性探查法、線性補(bǔ)償探測法、偽隨機(jī)探測）、拉鏈法、再散列（雙重散列，多重散列）等。JDK中的HashMap采用了拉鏈法解決沖突。

2、HashMap的幾個(gè)重要字段

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
static final int MAXIMUM_CAPACITY = 1 << 30; 
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8; 
static final int UNTREEIFY_THRESHOLD = 6; 
static final int MIN_TREEIFY_CAPACITY = 64; 

transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

• DEFAULT_INITIAL_CAPACITY : 初始容量，也就是默認(rèn)會(huì)創(chuàng)建 16 個(gè)桶，桶的個(gè)數(shù)不能太多或太少。如果太少，很容易觸發(fā)擴(kuò)容，如果太多，遍歷哈希表會(huì)比較慢。

• MAXIMUM_CAPACITY : 哈希表最大容量，一般情況下只要內(nèi)存夠用，哈希表不會(huì)出現(xiàn)問題。

• DEFAULT_LOAD_FACTOR : 默認(rèn)的填充因子。

• TREEIFY_THRESHOLD : 這個(gè)值表示當(dāng)某個(gè)桶中，鏈表長度大于 8 時(shí)，會(huì)轉(zhuǎn)化成紅黑樹。

• UNTREEIFY_THRESHOLD : 在哈希表擴(kuò)容時(shí)，如果發(fā)現(xiàn)鏈表長度小于 6，則會(huì)由紅黑樹重新退化為鏈表。

• MIN_TREEIFY_CAPACITY : 在轉(zhuǎn)變成紅黑樹之前，還會(huì)有一次判斷，只有鍵值對數(shù)量大于 64 才會(huì)發(fā)生轉(zhuǎn)換。這是為了避免在哈希表建立初期，多個(gè)鍵值對恰好被放入了同一個(gè)鏈表中而導(dǎo)致不必要的轉(zhuǎn)化。

• table：存儲(chǔ)元素的數(shù)組（桶），總是2的倍數(shù)。

• entrySet : HashMap的視圖。HashMap的entrySet()方法返回一個(gè)特殊的Set，這個(gè)Set使用EntryIterator遍歷，而這個(gè)Iterator則直接操作于HashMap的內(nèi)部存儲(chǔ)結(jié)構(gòu)table上。通過這種方式實(shí)現(xiàn)了“視圖”的功能。整個(gè)過程不需要任何輔助存儲(chǔ)空間。從這一點(diǎn)也可以看出為什么entrySet()是遍歷HashMap最高效的方法，原因很簡單，因?yàn)檫@種方式和HashMap內(nèi)部的存儲(chǔ)方式是一致的。

• size：此HashMap中 K-V 對的個(gè)數(shù)。

• modCount : 每次修改或者擴(kuò)容map結(jié)構(gòu)的計(jì)數(shù)器，主要用于fail-fast。

我們知道java.util.HashMap不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了map，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。這一策略在源碼中的實(shí)現(xiàn)是通過modCount域，modCount顧名思義就是修改次數(shù)，對HashMap內(nèi)容的修改都將增加這個(gè)值，那么在迭代器初始化過程中會(huì)將這個(gè)值賦給迭代器的expectedModCount。

• threshold：閾值。即該HashMap所能容納的最大Node的個(gè)數(shù)。其大小為this.threshold = tableSizeFor(initialCapacity);，也就是初始容量的向上一個(gè)2^n。舉個(gè)栗子，如果初始值為16，則該閾值為16；如果初始值為17-32則該閾值為32。但是在執(zhí)行一次put后，該值的大小則變成(capacity × loadFactor )，有待考證。
  而在Java7中，該值的初始化大小為 threshold = (int)(capacity * loadFactor)，是由初始容量和填充因子共同決定的，當(dāng)實(shí)際大小超過臨界值時(shí)，HashMap會(huì)進(jìn)行擴(kuò)容。也就是說，默認(rèn)情況下，當(dāng)實(shí)際大小size大于threshold （16 * 0.75=12）時(shí)，會(huì)進(jìn)行擴(kuò)容。

• loadFactor：填充因子。默認(rèn)值0.75是時(shí)間和空間的一個(gè)權(quán)衡。極端情況下，若對時(shí)間要求很高，對內(nèi)存要求相對較低，可以降低此值；若內(nèi)存要求很高，對時(shí)間要求相對較低，可以增加此值，甚至可以大于1。
  本質(zhì)上講，這個(gè)參數(shù)主要是調(diào)整table大小與鏈表大小的關(guān)系。

下面通過一個(gè)例子分析下loadFactor和threshold的關(guān)系：

public static void main(String[] args) throws Exception {
        Map<Integer, Integer> map = new HashMap<>(4, 0.75f);
        map.put(0, 1);

        /* 打印table的大小 */
        Field field = map.getClass().getDeclaredField("table");
        field.setAccessible(true);

        Object table = field.get(map);
        if (table!= null && table.getClass().isArray()) {
            Object[] tables = (Object[]) table;
            System.out.println(tables.length); // output: 4
        }
        /* 打印threshold的大小 */
        Field t = map.getClass().getDeclaredField("threshold");
        t.setAccessible(true);
        int threshold = t.getInt(map);
        System.out.println("threshold:" + threshold); // output: 3

        map.put(1, 2);
        map.put(2, 3);
        map.put(3, 4);

        /* 再次打印table的大小 */
        table = field.get(map);
        if (table!= null && table.getClass().isArray()) {
            Object[] tables = (Object[]) table;
            System.out.println(tables.length); // output: 8
        }
    }

從上述代碼可以看出：

• 首先生成了一個(gè)初始容量為4，填充因子為0.75f的hashMap，此時(shí)，tableSize=4，threshold=4；
• 執(zhí)行一次put操作，tableSize = 4, threshold=（4 × 0.75=3）；這時(shí)hashMap的最大容量為3；
• 再次執(zhí)行3次put操作，超出了閾值(3)，因此會(huì)進(jìn)行一次擴(kuò)容，此時(shí)tableSize=8，threshold=(8 × 0.75=6)

3、方法

3.1 構(gòu)造方法

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)  // 容量判斷
            throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 填充因子判斷
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);  // 不保留初始值，僅用來生成閾值
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

3.2 索引方法

對HashMap的操作，首先需要定位到哈希桶上。下面是具體的hash代碼：

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

可以看出，要確定具體桶的位置，需要三步運(yùn)算：

• 第一步：取得key的hash碼。即取key的hashCode值。
• 第二步：高位運(yùn)算，為了避免hash碰撞(hash collisons)將高位分散到低位上，這是綜合考慮了速度，性能等各方面因素之后做出的。
• 第三步：取模運(yùn)算。h & (length - 1)，這一步在put和get方法中，即在使用時(shí)才進(jìn)行取模運(yùn)算。

3.3 Put方法

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

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);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        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();
    afterNodeInsertion(evict);
    return null;
}

從代碼看，插入的邏輯還是比較清晰的。首先判斷表中沒有空間，其次是根據(jù)索引值找到具體的位置。存在該Key的話就覆蓋，如果是紅黑樹就直接插入，否則插入鏈表（判斷重復(fù)Key值和紅黑樹轉(zhuǎn)換）。具體的流程圖如下：

HashMap Put流程

3.4 Get方法

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

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;
}

從代碼來看，查找的邏輯同樣比較清晰。具體流程圖如下：

HashMap Get流程

3.5 擴(kuò)容方法

final HashMap.Node<K,V>[] resize() {
    HashMap.Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {  // 容量超過最大值，不再擴(kuò)容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 擴(kuò)容為原來的兩倍
            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) { // 計(jì)算新的threshold值
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) { // 將舊的bucket移動(dòng)到新的bucket中
            HashMap.Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e; // 重新計(jì)算哈希值
                else if (e instanceof HashMap.TreeNode) // 紅黑樹分裂，如果高度<=6，會(huì)退化為鏈表
                    ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order，鏈表處理hash沖突
                    HashMap.Node<K,V> loHead = null, loTail = null;
                    HashMap.Node<K,V> hiHead = null, hiTail = null;
                    HashMap.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;
}

4、綜述

• HashMap初始化的時(shí)候估算map大小并指定容量，這是因?yàn)轭l繁的擴(kuò)容是非常耗資源的。
• HashMap線程不安全，并發(fā)環(huán)境下建議使用ConcurrentHashMap。
• JDK1.8 采用數(shù)組、鏈表+紅黑樹的存儲(chǔ)結(jié)構(gòu)，優(yōu)化了HashMap的性能，具體對比不再闡釋。