天天看點
傳回

JDK8 HashMap源碼了解前言一、資料結構二、源碼分析三、常見問題

HashMap

  • 前言
  • 一、資料結構
    • 1.1 Node
    • 1.2 重要參數
  • 二、源碼分析
    • 2.1 擾動函數
    • 2.2 插入
    • 2.3 查找
    • 2.4 樹形化
    • 2.5 擴容
  • 三、常見問題
    • 3.1 桶數組長度為什麼總是2的n次方
    • 3.2 HashMap的參數loadFactor，它的作用是什麼？
    • 3.3 HashMap從JDK7到JDK8的變化。

前言

最近本翔再次認真閱讀了HashMap的源碼，總結一下自己的一些了解，希望對大家能有點幫助。

一、資料結構

HashMap的資料結構是數組+連結清單，數組裡面是一個個Node，在JDK8中加入了紅黑樹。HashMap根據存入的對象的hash跟數組長度取模得出下标，如果發生了哈希沖突，則新插入的鍵值對會放到上一個節點的後面，形成連結清單。當連結清單長度超過8且數組長度也不小于64時會轉為紅黑樹，同理，連結清單長度小于6時會再次變回連結清單。數組裡的每個存儲空間，我們稱為桶(bucket)。

JDK8 HashMap源碼了解前言一、資料結構二、源碼分析三、常見問題

1.1 Node

Node封裝了key和value，我們使用put方法塞進去key和value其實都存到了Node裡面，看看Node裡面的成員變量有哪些。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        // ………………略
    }

可以看到裡面有四個成員

hash值：即鍵的散列值

key：就是我們put進去的那個鍵了

value：就是我們put進去的那個值了

next：下一個節點

1.2 重要參數

HashMap裡面定義了一些比較重要的參數

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;    //初始容量
static final int MAXIMUM_CAPACITY = 1 << 30;    //最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;    //負載因子，當map裡面的node數量大于 threshold = loadFactor * capacity時，就會擴容
static final int TREEIFY_THRESHOLD = 8;    //桶的樹化門檻值，轉為紅黑樹的哈希沖突數量門檻值
static final int UNTREEIFY_THRESHOLD = 6;    //桶的連結清單還原門檻值，轉為連結清單的哈希沖突數量門檻值
static final int MIN_TREEIFY_CAPACITY = 64;    //最小樹形化容量門檻值，當哈希表中的容量即數組長度不小于該值時，樹形化連結清單

1.初始容量和加載因子我們在執行個體化HashMap的時候是可以定義的。當 元素數量 > 容量*加載因子 時，數組就會擴容。

2.當桶裡面的 連結清單長度 > TREEIFY_THRESHOLD 且 桶數組長度 > MIN_TREEIFY_CAPACITY 時，連結清單就會轉換為紅黑樹。

二、源碼分析

2.1 擾動函數

沒仔細看源碼前，我一直以為計算桶下标的時候值直接用鍵的hashCode跟數組容量相與得出的下标，現在仔細一看才發現事情沒那麼簡單。

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

可以看到擾動函數裡面把hashCode右移了16位再與原hashCode進行了異或操作，即用自己的高16位和低16位進行了異或。這樣能增加随機性，讓資料元素更散列，減少碰撞。

2.2 插入

簡單來說，插入鍵值對的時候，先通過鍵的哈希值計算出下标，然後再把資料存放到數組中。不多BB，直接放源碼。

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;
        //如果桶裡沒資料，直接建立一個Node，并把桶指向這個Node
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //桶裡有資料再做處理
        else {
            Node<K,V> e; K k;
            //鍵值和鍵散列值都和桶裡的第一個Node鍵值和鍵hashCode一樣，直接把e指向這個Node，準備後面直接替換值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果是TreeNode對象，則調用紅黑樹插入值的方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //即不是樹節點，且第一個Node也不是要找的Node，那就準備周遊連結清單
            else {
            	//周遊連結清單且統計連結清單長度
                for (int binCount = 0; ; ++binCount) {
                	//周遊完連結清單都沒有這個key，那就在連結清單後面插入新節點吧
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //連結清單長度大于門檻值的話就轉為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //找到key，結束周遊
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //e不為空則表示連結清單裡包含有要插入的鍵值對，直接替換值就好了
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //元素數量超過threshold時就擴容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

主要步驟如下：

1.檢查桶數組是否為空，為空則resize()初始化

2.計算下标，用桶數組長度 - 1跟鍵的哈希值相與，即(length - 1) & hash 計算下标，看桶是否為空，為空就直接把Node存進桶中

3.如果桶裡第一個Node的key和目前的key一樣，直接将桶指向現在的Node

4.如果Node是樹節點，就調用紅黑樹的插入方法

5.如果以上兩種情況都不是，則需要周遊該連結清單，找到對應的key替換值或者沒有key就往連結清單尾部插入新Node

6.所有元素處理完成後，判斷size是否超過門檻值 threshold，是則resize()擴容

2.3 查找

查找就比較簡單，就計算出數組下标，到桶裡面看看是紅黑樹還是連結清單還是null，再拿資料。

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

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; 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 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;
    }

2.4 樹形化

由于從連結清單中查找資料的時間複雜度是O(n)，是以如果插入的鍵值對，發生哈希碰撞太多而導緻連結清單過長的時候，那性能是非常差的。是以在JDK8中，連結清單長度大于8且桶容量不小于64時，連結清單會樹形化，即轉為紅黑樹。

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //可以看到，如果桶數組容量小于64時，就算連結清單長度大于8，也隻會擴容而不會把連結清單轉為紅黑樹
        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);
        }
    }

2.5 擴容

擴容可以有效避免有太多的哈希碰撞而導緻的桶内資料過多的情況。桶數組容量 * 負載因子大于元素數量時，HashMap就會擴容，把數組容量擴大一倍。

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)
                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;
        //初始化新的桶數組
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
        	//周遊舊的桶數組
            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;
                            //這裡用哈希跟舊數組長度相與，計算出該節點是放在高位桶還是低位桶
                            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;
    }

總結擴容操作步驟，其實主要就以下幾個步驟：

1.沒初始化就初始化，容量達到MAXIMUM_CAPACITY即2^30就不擴容了

2.建立桶數組，容量為舊的桶數組的2倍

3.周遊舊數組的所有桶，桶裡連結清單隻有一個資料就直接遷移，是樹節點就調用紅黑樹的拆分方法，連結清單不止一個資料就周遊連結清單

4.由于新桶數組容量是原來的兩倍，是以原本在同一個桶中的資料遷移到新數組中時，是有可能放在不同的兩個桶中的。一個是低位桶，下标值和原來的一樣，一個是高位桶，下标值和原來的內插補點為舊桶數組的容量，通過 hash&oldCap 是否等于0可以判斷這個節點是在高位桶還是低位桶

為什麼 (hash&oldCap==0) 可以判斷一個節點是在高位桶還是低位桶呢？

一個節點的數組下标，是通過它的鍵的hash跟數組容量取模計算得來的，是以同一個桶上的資料，要麼它們的hash相等，要麼它們的hash相差 2^n 個數組容量。

比如兩個哈希值分别為13和5的鍵，插進數組長度為8的桶數組裡，1101&0111 和 0101&0111 計算得到的下标都是0101，即5。當擴容後，數組長度為16，而這時再計算下标時， 就變成了 1101&1111和0101&1111，最終的結果分别為13和5，它們相差8。哈希值為5的節點擴容後仍然在下标值為5的桶上，而哈希值為13的節點已經遷移到了下标值為8的桶上了。

其實不難發現，通過位于運算計算下标時，擴容前的0111和擴容後的1111隻相差第四位的那個1，由于哈希值為13的第四位原本是1，而哈希值為5的第四位原本是0，當位于運算的值有0111變成1111時，第四位也參與了運算，才導緻了擴容後的它們得出的下标值會不同。是以我們可以直接用1000跟hash進行相與，看看它的第四位是1還是0就可以知道它是在高位桶還是低位桶了。

三、常見問題

3.1 桶數組長度為什麼總是2的n次方

計算效率更高，計算更友善。

取模(%)操作中如果除數是2的幂次，則等價于與其除數減一的與(&)操作（前提是length是2的n次方）。是以可以從源碼中看到，計算數組下标是通過 hash & (length - 1) 來計算的。而且這樣使擴容後計算新位置會更友善，從擴容源碼中可以看到判斷一個節點擴容後的數組下标是在高位桶還是低位桶時，直接用hash跟舊桶數組容量相與即可判斷，并在如果是高位桶，直接用下标加上舊數組長度即可拿到高位桶的下标。

3.2 HashMap的參數loadFactor，它的作用是什麼？

其實從源碼中可以看得很清楚了，它其實是表示HashMap裡面數組所能承受的擁擠程度，影響hash操作到同一個數組位置的機率。預設的loadFactor是0.75，當HashMap裡面容納的元素已經達到HashMap數組長度的75%時，表示HashMap太擠了，需要擴容，在HashMap的構造器中可以定制loadFactor。

3.3 HashMap從JDK7到JDK8的變化。

1.樹形化

首先肯定就是新增了紅黑樹啦，JDK7及之前桶中隻有連結清單一種資料結構，JDK8中桶内元素大于8且數組容量不小于64時便會把桶内連結清單轉為紅黑樹。

2.hash計算方式不同

JDK7的擾動函數，前前後後進行了四次擾動。而JDK8簡化了這一操作，隻是對高低位做了異或。

3.擴容操作中，下标的計算方法不一樣。

可以從JDK8源碼中看到resize()裡面，判斷節點是高位桶還是低位桶，是高位桶的話，直接用舊的下标加上舊的數組容量即可。但是JDK7中不是這樣的，JDK7的擴容操作需要對節點重新計算下标。

4.發生哈希碰撞時，插傳入連結表中的方法不一樣。

JDK8裡的HashMap插入元素時，用的是尾插法，但是JDK7裡用的是頭插法。在進行擴容操作遷移元素時也是如此，這就導緻JDK7的HashMap在多線程進行擴容操作時，有可能會出現死鎖問題！這裡就不較長的描述JDK7HashMap的死鎖問題了，後面會專門出篇部落格翔談該問題。（不要問我為什麼是“翔談”不是詳談，請看看我的名字）

java hashmap 資料結構 哈希表 連結清單
上一篇: 讀源碼了解jdk8 HashMapHashMap
下一篇: centos7.2下安裝python3.6.2 以及 centos下安裝pipcentos7.2下安裝python3.6.2 以及 centos下安裝pip時：安裝pip 2出現問題： zlib

繼續閱讀