Java集合2-HashMap詳解（含源碼分析）

Java集合系列

Java集合1-Map總結

Java集合2-HashMap詳解（含源碼分析）

1、資料結構

從上圖可以看到，HashMap是由數組、連結清單和紅黑樹（JDK1.8）實作的。

- Node

/**
     * 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

是一個

Node

數組，

Node

是HashMap的内部類，實作了

Map.Entry<K, V>

，也就是說，Node可以了解為是一個包含Key, Value組合的桶。

沖突解決

常見的Hash沖突解決的方法有：開放位址法（線性探查法、線性補償探測法、僞随機探測）、拉鍊法、再散列（雙重散列，多重散列）等。JDK中的HashMap采用了拉鍊法解決沖突。

2、HashMap的幾個重要字段

static final int DEFAULT_INITIAL_CAPACITY =  << ; 
static final int MAXIMUM_CAPACITY =  << ; 
static final float DEFAULT_LOAD_FACTOR = f;
static final int TREEIFY_THRESHOLD = ; 
static final int UNTREEIFY_THRESHOLD = ; 
static final int MIN_TREEIFY_CAPACITY = ; 

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 : 初始容量，也就是預設會建立 16 個桶，桶的個數不能太多或太少。如果太少，很容易觸發擴容，如果太多，周遊哈希表會比較慢。
MAXIMUM_CAPACITY : 哈希表最大容量，一般情況下隻要記憶體夠用，哈希表不會出現問題。
DEFAULT_LOAD_FACTOR : 預設的填充因子。
TREEIFY_THRESHOLD : 這個值表示當某個桶中，連結清單長度大于 8 時，會轉化成紅黑樹。
UNTREEIFY_THRESHOLD : 在哈希表擴容時，如果發現連結清單長度小于 6，則會由紅黑樹重新退化為連結清單。
MIN_TREEIFY_CAPACITY : 在轉變成紅黑樹之前，還會有一次判斷，隻有鍵值對數量大于 64 才會發生轉換。這是為了避免在哈希表建立初期，多個鍵值對恰好被放入了同一個連結清單中而導緻不必要的轉化。
table ：存儲元素的數組（桶），總是2的倍數。
entrySet : HashMap的視圖。HashMap的entrySet()方法傳回一個特殊的Set，這個Set使用EntryIterator周遊，而這個Iterator則直接操作于HashMap的内部存儲結構table上。通過這種方式實作了“視圖”的功能。整個過程不需要任何輔助存儲空間。從這一點也可以看出為什麼entrySet()是周遊HashMap最高效的方法，原因很簡單，因為這種方式和HashMap内部的存儲方式是一緻的。
size ：此HashMap中 K-V 對的個數。
modCount : 每次修改或者擴容map結構的計數器，主要用于fail-fast。
我們知道java.util.HashMap不是線程安全的，是以如果在使用疊代器的過程中有其他線程修改了map，那麼将抛出ConcurrentModificationException，這就是所謂fail-fast政策。這一政策在源碼中的實作是通過modCount域，modCount顧名思義就是修改次數，對HashMap内容的修改都将增加這個值，那麼在疊代器初始化過程中會将這個值賦給疊代器的expectedModCount。
threshold ：門檻值。即該HashMap所能容納的最大Node的個數。其大小為 this.threshold = tableSizeFor(initialCapacity); ，也就是初始容量的向上一個 2^n
。舉個栗子，如果初始值為16，則該門檻值為16；如果初始值為17-32則該門檻值為32。但是在執行一次put後，該值的大小則變成(capacity × loadFactor )，有待考證。

而在Java7中，該值的初始化大小為
threshold = (int)(capacity * loadFactor) ，是由初始容量和填充因子共同決定的，當實際大小超過臨界值時，HashMap會進行擴容。也就是說，預設情況下，當實際大小 size 大于 threshold （16 * 0.75=12）時，會進行擴容。
loadFactor
：填充因子。預設值0.75是時間和空間的一個權衡。極端情況下，若對時間要求很高，對記憶體要求相對較低，可以降低此值；若記憶體要求很高，對時間要求相對較低，可以增加此值，甚至可以大于1。

本質上講，這個參數主要是調整table大小與連結清單大小的關系。

下面通過一個例子分析下 loadFactor和 threshold的關系：

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

        /* 列印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(, );
        map.put(, );
        map.put(, );

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

**從上述代碼可以看出：** - 首先生成了一個初始容量為4，填充因子為0.75f的hashMap，此時，tableSize=4，threshold=4； - 執行一次put操作，tableSize = 4, threshold=（4 × 0.75=3）；這時hashMap的最大容量為3； - 再次執行3次put操作，超出了門檻值(3)，是以會進行一次擴容，此時tableSize=8，threshold=(8 × 0.75=6)

3、方法

3.1 構造方法

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < )  // 容量判斷
            throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <=  || 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) ?  : (h = key.hashCode()) ^ (h >>> );
}

可以看出，要确定具體桶的位置，需要三步運算： - 第一步：取得key的hash碼。即取key的hashCode值。 - 第二步：高位運算，為了避免hash碰撞(hash collisons)将高位分散到低位上，這是綜合考慮了速度，性能等各方面因素之後做出的。 - 第三步：取模運算。**`h & (length - 1)`**，這一步在put和get方法中，即在使用時才進行取模運算。

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) == )
        n = (tab = resize()).length;
    if ((p = tab[i = (n - ) & 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 = ; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - ) // -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;
}

從代碼看，插入的邏輯還是比較清晰的。首先判斷表中沒有空間，其次是根據索引值找到具體的位置。存在該Key的話就覆寫，如果是紅黑樹就直接插入，否則插傳入連結表（判斷重複Key值和紅黑樹轉換）。具體的流程圖如下： ![HashMap Put流程](http://upload-images.jianshu.io/upload_images/4324380-22978b37a8124114.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

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) >  && (first = tab[(n - ) & 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流程](http://upload-images.jianshu.io/upload_images/4324380-c756151576dd151b.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

3.5 擴容方法

final HashMap.Node<K,V>[] resize() {
    HashMap.Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ?  : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = ;
    if (oldCap > ) {
        if (oldCap >= MAXIMUM_CAPACITY) {  // 容量超過最大值，不再擴容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 擴容為原來的兩倍
            newThr = oldThr << ; // double threshold
    }
    else if (oldThr > ) // 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 == ) { // 計算新的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 = ; j < oldCap; ++j) { // 将舊的bucket移動到新的bucket中
            HashMap.Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - )] = e; // 重新計算哈希值
                else if (e instanceof HashMap.TreeNode) // 紅黑樹分裂，如果高度<=6，會退化為連結清單
                    ((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) == ) {
                            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初始化的時候估算map大小并指定容量，這是因為頻繁的擴容是非常耗資源的。
HashMap線程不安全，并發環境下建議使用ConcurrentHashMap。
JDK1.8 采用數組、連結清單+紅黑樹的存儲結構，優化了HashMap的性能，具體對比不再闡釋。

Java集合2-HashMap詳解（含源碼分析）

1、資料結構

2、HashMap的幾個重要字段

3、方法

3.1 構造方法

3.2 索引方法

3.3 Put方法

3.4 Get方法

3.5 擴容方法

4、綜述

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method