109      阿裏雲  技術社區[雲棲]

由阿裏巴巴Java開發規約HashMap條目引發的故事

大熱的《阿裏巴巴Java開發規約》中有提到：

【推薦】集合初始化時，指定集合初始值大小。
說明：HashMap使用如下構造方法進行初始化，如果暫時無法確定集合大小，那麼指定默認值（16）即可：

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

看到代碼規約這一條的時候，我覺得是不是有點太 low 了，身為開發，大家都知道 HashMap 的原理。

什麼？這個要通過插件監測？沒必要吧，哪個開發不知道默認大小，何時 resize 啊，然後我和孤盡打賭隨機谘詢幾位同學以下幾個問題：

1. HashMap 默認bucket數組多大？
2. 如果new HashMap<>(19)，bucket數組多大？
3. HashMap 什麼時候開辟bucket數組占用內存？
4. HashMap 何時擴容？

抽樣調查的結果出乎我的意料：

1. HashMap 默認bucket數組多大？（答案是16，大概一半的同學答錯）
2. 如果new HashMap<>(19)，bucket數組多大？（答案是32，大多被谘詢同學都不太了解這個點）
3. HashMap 什麼時候開辟bucket數組占用內存？（答案是第一次 put 時，一半同學認為是 new 的時候）
4. HashMap 何時擴容？（答案是put的元素達到容量乘負載因子的時候，默認16*0.75，有1/4同學中槍）

HashMap 是寫代碼時最常用的集合類之一，看來大家也不是全都很了解。孤盡乘勝追擊又拋出問題：JDK8中 HashMap 和之前 HashMap 有什麼不同？

我知道 JDK8 中 HashMap 引入了紅黑樹來處理哈希碰撞，具體細節和源代碼並沒有仔細翻過，看來是時候對比翻看下 JDK8 和 JDK7 的 HashMap 源碼了。

通過對比翻看源碼，先說下結論：

1. HashMap 在 new 後並不會立即分配bucket數組，而是第一次 put 時初始化，類似 ArrayList 在第一次 add 時分配空間。
2. HashMap 的 bucket 數組大小一定是2的冪，如果 new 的時候指定了容量且不是2的冪，實際容量會是最接近(大於)指定容量的2的冪，比如 new HashMap<>(19)，比19大且最接近的2的冪是32，實際容量就是32。
3. HashMap 在 put 的元素數量大於 Capacity * LoadFactor（默認16 * 0.75） 之後會進行擴容。
4. JDK8在哈希碰撞的鏈表長度達到TREEIFY_THRESHOLD（默認8)後，會把該鏈表轉變成樹結構，提高了性能。
5. JDK8在 resize 的時候，通過巧妙的設計，減少了 rehash 的性能消耗。

存儲結構

JDK7 中的 HashMap 還是采用大家所熟悉的數組+鏈表的結構來存儲數據。

JDK8 中的 HashMap 采用了數組+鏈表或樹的結構來存儲數據。

重要參數

HashMap中有兩個重要的參數，容量(Capacity) 和 負載因子(Load factor)

• Initial capacity The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.
• Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

Initial capacity 決定 bucket 的大小，Load factor 決定 bucket 內數據填充比例，基於這兩個參數的乘積，HashMap 內部由 threshold 這個變量來表示 HashMap 能放入的元素個數。

• Capacity 就是 HashMap 中數組的 length
• loadFactor 一般都是使用默認的0.75
• threshold 決定能放入的數據量，一般情況下等於 Capacity * LoadFactor

以上參數在 JDK7 和 JDK8中是一致的，接下來會根據實際代碼分析。

JDK8 中的 HashMap 實現

new

HashMap 的bucket數組並不會在new 的時候分配，而是在第一次 put 的時候通過 resize() 函數進行分配。

JDK8中 HashMap 的bucket數組大小肯定是2的冪，對於2的冪大小的 bucket，計算下標隻需要 hash 後按位與 n-1，比%模運算取餘要快。如果你通過 HashMap(int initialCapacity) 構造器傳入initialCapacity，會先計算出比initialCapacity大的 2的冪存入 threshold，在第一次 put 的 resize() 初始化中會按照這個2的冪初始化數組大小，此後 resize 擴容也都是每次乘2，這麼設計的原因後麵會詳細講。

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;
    // 比initialCapacity大的2的 N 次方，先存在threshold中，resize() 中會處理
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

hash

JKD8 中put 和 get 時，對 key 的 hashCode 先用 hash 函數散列下，再計算下標：

具體 hash 代碼如下：

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

由於 h>>>16，高16bit 補0，一個數和0異或不變，所以 hash 函數大概的作用就是：高16bit不變，低16bit和高16bit做了一個異或，目的是減少碰撞。

按照函數注釋，因為bucket數組大小是2的冪，計算下標index = (table.length - 1) & hash，如果不做 hash 處理，相當於散列生效的隻有幾個低 bit 位，為了減少散列的碰撞，設計者綜合考慮了速度、作用、質量之後，使用高16bit和低16bit異或來簡單處理減少碰撞，而且 JDK8中用了複雜度 O（logn）的樹結構來提升碰撞下的性能。具體性能提升可以參考Java 8：HashMap的性能提升

put

put函數的思路大致分以下幾步：

1. 對key的hashCode()進行hash後計算數組下標index;
2. 如果當前數組table為null，進行resize()初始化；
3. 如果沒碰撞直接放到對應下標的bucket裏；
4. 如果碰撞了，且節點已經存在，就替換掉 value；
5. 如果碰撞後發現為樹結構，掛載到樹上。
6. 如果碰撞後為鏈表，添加到鏈表尾，並判斷鏈表如果過長(大於等於TREEIFY_THRESHOLD，默認8)，就把鏈表轉換成樹結構；
7. 數據 put 後，如果數據量超過threshold，就要resize。

具體代碼如下：

public V put(K key, V value) {
    // 對key的hashCode()做hash
    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;
    // 初始 tab 為 null，resize 初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 計算下標index，沒碰撞，直接放
    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;
            }
        }
        // 節點已存在，替換value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 超過threshold，進行resize擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 數量大於 64 才會發生轉換，避免初期，多個鍵值對恰好放入同一個鏈表中而導致不必要的轉化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

resize

resize()用來第一次初始化，或者 put 之後數據超過了threshold後擴容，resize的注釋如下：

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

數組下標計算： index = (table.length - 1) & hash ，由於 table.length 也就是capacity 肯定是2的N次方，使用 & 位運算意味著隻是多了最高位，這樣就不用重新計算 index，元素要麼在原位置，要麼在原位置+ oldCapacity。

如果增加的高位為0，resize 後 index 不變，如圖所示：

如果增加的高位為1，resize 後 index 增加 oldCap，如圖所示：

這個設計的巧妙之處在於，節省了一部分重新計算hash的時間，同時新增的一位為0或1的概率可以認為是均等的，所以在resize 的過程中就將原來碰撞的節點又均勻分布到了兩個bucket裏。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // oldCap > 0，是擴容而不是初始化
    if (oldCap > 0) {
        // 超過最大值就不再擴充了，並且把閾值增大到Integer.MAX_VALUE
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 沒超過最大值，就擴充為原來的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // oldCap 為0，oldThr 不為0，第一次初始化 table，一般是通過帶參數的構造器
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // oldCap 和 oldThr 都為0的初始化，一般是通過無參構造器生成，用默認值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果到這裏 newThr 還沒計算，則計算新的閾值threshold
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 把每個bucket都移動到新的buckets中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 原索引（e.hash 和類似 0010000 按位與，結果為0，說明原高位為0）
                        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裏
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket裏
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

JDK7 中的 HashMap 實現

new

JDK7 裏 HashMap的bucket數組也不會在new 的時候分配，也是在第一次 put 的時候通過 inflateTable() 函數進行分配。

JDK7中 HashMap 的bucket數組大小也一定是2的冪，同樣有計算下標簡便的優點。如果你通過 HashMap(int initialCapacity) 構造器傳入initialCapacity，會先存入 threshold，在第一次 put 時調用 inflateTable() 初始化，會計算出比initialCapacity大的2的冪作為初始化數組的大小，此後 resize 擴容也都是每次乘2。

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;
    threshold = initialCapacity;
    init();
}

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // ···省略代碼
}

// 第一次 put 時，初始化 table
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    // threshold 在不超過限製最大值的前提下等於 capacity * loadFactor
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    // 接下來hash 部分分析
    initHashSeedAsNeeded(capacity);
}

hash

JKD7 中，bucket數組下標也是按位與計算，但是 hash 函數與 JDK8稍有不同，代碼注釋如下：

Retrieve object hash code and applies a supplemental hash function to the result hash, which defends against poor quality hash functions. This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits. Note: Null keys always map to hash 0, thus index 0.

• hash為了防止隻有 hashCode() 的低 bit 位參與散列容易碰撞，也采用了位移異或，隻不過不是高低16bit，而是如下代碼中多次位移異或。
• JKD7的 hash 中存在一個開關：hashSeed。開關打開(hashSeed不為0)的時候，對 String 類型的key 采用sun.misc.Hashing.stringHash32的 hash 算法；對非 String 類型的 key，多一次和hashSeed的異或，也可以一定程度上減少碰撞的概率。
• JDK 7u40以後，hashSeed 被移除，在 JDK8中也沒有再采用，因為stringHash32()的算法基於MurMur哈希，其中hashSeed的產生使用了Romdum.nextInt()實現。Rondom.nextInt()使用AtomicLong，它的操作是CAS的（Compare And Swap）。這個CAS操作當有多個CPU核心時，會存在許多性能問題。因此，這個替代函數在多核處理器中表現出了糟糕的性能。

具體hash 代碼如下所示：

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

/**
 * 下標計算依然是使用按位與
 */
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

hashSeed 默認值是0，也就是默認關閉，任何數字與0異或不變。hashSeed 會在capacity發生變化的時候，通過initHashSeedAsNeeded()函數進行計算。當capacity大於設置值Holder.ALTERNATIVE_HASHING_THRESHOLD後，會通過sun.misc.Hashing.randomHashSeed產生hashSeed 值，這個設定值是通過 JVM的jdk.map.althashing.threshold參數來設置的，具體代碼如下：

final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

/**
 * holds values which can't be initialized until after VM is booted.
 */
private static class Holder {

    /**
     * Table capacity above which to switch to use alternative hashing.
     */
    static final int ALTERNATIVE_HASHING_THRESHOLD;

    static {
        String altThreshold = java.security.AccessController.doPrivileged(
            new sun.security.action.GetPropertyAction(
                "jdk.map.althashing.threshold"));

        int threshold;
        try {
            threshold = (null != altThreshold)
                    ? Integer.parseInt(altThreshold)
                    : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;// ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE
            // disable alternative hashing if -1
            if (threshold == -1) {
                threshold = Integer.MAX_VALUE;
            }
            if (threshold < 0) {
                throw new IllegalArgumentException("value must be positive integer.");
            }
        } catch(IllegalArgumentException failed) {
            throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
        }
        ALTERNATIVE_HASHING_THRESHOLD = threshold;
    }
}

put

JKD7 的put相比於 JDK8就要簡單一些，碰撞以後隻有鏈表結構。具體代碼如下：

public V put(K key, V value) {
    // 初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    // 計算 hash 和下標
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 查到相同 key，替換 value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    // 添加數據
    addEntry(hash, key, value, i);
    return null;
}


void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果數據量達到threshold，需要 resize 擴容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    //在鏈表頭部添加新元素
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

resize

JDK7的 resize() 也是擴容兩倍，不過擴容過程相對JDK8就要簡單許多，由於默認initHashSeedAsNeeded內開關都是關閉狀態，所以一般情況下transfer 不需要進行 rehash，能減少一部分開銷。代碼如下所示：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    // 擴容後轉移數據，根據initHashSeedAsNeeded判斷是否 rehash
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}


void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            // 根據之前的分析，默認情況是不需要 rehash 的
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

總結

1. HashMap 在 new 後並不會立即分配bucket數組，而是第一次 put 時初始化，類似 ArrayList 在第一次 add 時分配空間。
2. HashMap 的 bucket 數組大小一定是2的冪，如果 new 的時候指定了容量且不是2的冪，實際容量會是最接近(大於)指定容量的2的冪，比如 new HashMap<>(19)，比19大且最接近的2的冪是32，實際容量就是32。
3. HashMap 在 put 的元素數量大於 Capacity * LoadFactor（默認16 * 0.75） 之後會進行擴容。
4. JDK8處於提升性能的考慮，在哈希碰撞的鏈表長度達到TREEIFY_THRESHOLD（默認8)後，會把該鏈表轉變成樹結構。
5. JDK8在 resize 的時候，通過巧妙的設計，減少了 rehash 的性能消耗。

相對於 JDK7的1000餘行代碼，JDK8代碼量達到了2000餘行，對於這個大家最常用的數據結構增加了不少的性能優化。
仔細看完上麵的分析和源碼，對 HashMap 內部的細節又多了些了解，有空的時候還是多翻翻源碼，^_^

《阿裏巴巴Java開發規約》自誕生以來，一直處於挑戰漩渦的最中心，從這一個規約的小條目，看出來規約也是冰凍三尺，非一日之寒，研讀規約，其實能夠發現很多看似簡單的知識點背後，其實隱藏著非常深的邏輯知識點。

參考

• Java HashMap工作原理及實現
• Java 8：HashMap的性能提升
• 疫苗：JAVA HASHMAP的死循環

最後更新：2017-10-19 16:33:22

  上一篇：  HybridDB for PostgreSQL上手指南

  下一篇：  深度學習入門指南