天天看點
傳回

讀源碼了解jdk8 HashMapHashMap

目錄

HashMap

1、内部結構

2、HashMap構造器

3、HashMap put操作

4、hashMap 擴容

5、get操作

HashMap

讀源碼了解jdk8 HashMapHashMap

HashMap 繼承于AbstractMap，實作了Map,Cloneable,Serializable接口。

1、内部結構

JDK7的HashMap内部結構是數組+連結清單。

JDK8的HashMap内部結構是數組+ 連結清單+ 紅黑樹。

  • 連結清單節點結構： 
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) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    ............
 }
  • 樹節點結構： 
//LinkedHashMap.Entry<K,V>繼承于 HashMap.Node<K,V>
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    .........
 }
讀源碼了解jdk8 HashMapHashMap
  • 一些重要的預設字段： 
//如果建立一個HashMap未指定大小，HashMap初始化大小預設為16。
static final float DEFAULT_INITIAL_CAPACITY = 1 << 4;

//HashMap允許的最大容量為2^30。
static final float MAXIMUM_CAPACITY = 1 << 30; 

//負載因子，代表了HashTable的填充度，當HashTable内已經存在的元素個數超過HashTable容量*DEFAULT_LOAD_FACTOR時，
//進行擴容。預設為0.75 例如：HashTable的容量為32(32 * 0.75 = 14.4)，當已經存在14個元素時（不隻是主幹數組的元素，包括連結清單和樹的節點），
//如果要再添加一個元素，需要先進行擴容操作。擴容後的HashMap容量是之前的2倍
// 這樣做的原因是為了減少hash沖突。
static final float DEFAULT_LOAD_FACTOR = 0.75f;  

// 連結清單轉樹形的門檻值
static final int TREEIFY_THRESHOLD = 8;
// 容器可以樹化的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
// 結合以上兩個字段，在HashMap的容量大于等于64的前提下（小于64或者為空時，進行擴容操作），
//當某個連結清單的節點個數為大于等于8時，需要将連結清單轉為樹形
// 這樣做為了避免連結清單過長，紅黑樹查詢某個節點最差為O（logN）相比于連結清單的最差O（N），效率會更好。

// 樹形轉為連結清單的門檻值
// 當紅黑樹的節點個數小于等于6時，需要将紅黑樹轉為連結清單
static final int UNTREEIFY_THRESHOLD = 6;

 問題：為什麼不直接使用紅黑樹，而是要先使用連結清單，到一定條件下再轉紅黑樹呢？

Because TreeNodes are about twice the size of regular nodes,

we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD).

And when they become too small (due to removal or resizing) they are converted back to plain bins. 

“因為樹節點的大小是連結清單節點大小的兩倍，是以隻有在容器中包含足夠的節點保證使用才用它”，顯然盡管轉為樹使得查找的速度更快，但是在節點數比較少的時候，此時對于紅黑樹來說記憶體上的劣勢會超過查找等操作的優勢，自然使用連結清單更加好，但是在節點數比較多的時候，綜合考慮，紅黑樹比連結清單要好。

問題：為什麼在節點數為8時進行連結清單轉紅黑樹操作，而不是節點數為9？或者10？

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution

with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although

with a large variance because of resizing granularity. Ignoring variance, the expected

occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)).

The first values are:

0: 0.60653066

1: 0.30326533

2: 0.07581633

3: 0.01263606

4: 0.00157952

5: 0.00015795

6: 0.00001316

7: 0.00000094

8: 0.00000006

more: less than 1 in ten million

理想情況下，在随機哈希碼下，哈希表中節點的頻率遵循泊松分布，而根據統計，忽略方差，清單長度為K的期望出現的次數是以上的結果，可以看到其實在為8的時候機率就已經很小了，再往後調整并沒有很大意義。

2、HashMap構造器

HashMap有以下四個構造器

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
}
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

除了入參指定為Map的構造器外，其他構造器并不會為數組Node<K,V>[] table配置設定記憶體空間，隻是初始化一些成員變量。

threshold ：HashMap進行擴容的門檻值，構造初始化為 HashMap容量大小，總是2的指數。（注意：雖然在構造時，threshold 為 HashMap容量大小，但是在put操作為table配置設定記憶體空間時，會把threshold 修改為HashMap容量大小 * loadFactor ，這個後面會講）

來看一下threshold 計算方法tableSizeFor（）：

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

這個方法巧妙地利用了無符号位移和按位或，得到一個比入參cap大但是最接近cap或者等于cap的2的次幂。比如如果給定cap是10，那麼應該傳回2^3=16。

舉個例子：

cap = 259;
cap - 1 = 258;
258用二進制表示為0000 0001 0000 0010
n |= n >>> 1  // n等于n與n向無符号右位移1位的值做按位或（按位或：即二進制位有一個1，結果位就為1）
n >>> 1 = 0000 0000 1000 0001
  0000 0001 0000 0010
  0000 0000 1000 0001
 ------------------------
= 0000 0001 1000 0011
是以 n |= n >>> 1, n= 0000 0001 1000 0011;
n >>> 2 = 0000 0000 0110 0000
   0000 0001 1000 0011
   0000 0000 0110 0000
  ------------------------
 = 0000 0001 1110 0011
 是以 n |= n >>> 2, n= 0000 0001 1110 0011;
 n >>> 4 = 0000 0000 0001 1110
   0000 0001 1110 0011
   0000 0000 0001 1110
  ------------------------
 = 0000 0001 1111 1111
 是以 n |= n >>> 4, n= 0000 0001 1111 1111;
 ..............
 n |= n >>> 16, n= 0000 0001 1111 1111;
 此時 n + 1  = 0000 0010 0000 0000 = 512；
 
 對比下每一次計算前後n的值，可以發現每一次計算都是把二進制位為1的右邊的x位置為1，
 直到最後，最初始時n的最高位1後面的所有二進制位都被置為1，再加1後就得到比n大且最接近n的2的次幂方。
 0000 0001 0000 0010
 0000 0001 1000 0011
 
 0000 0001 1000 0011
 0000 0001 1110 0011

3、HashMap put操作

put操作會建構table數組，為其配置設定記憶體空間。

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;
    // 判斷table是否為空，如果是，通過擴容resize（）來建立
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // table不為空，key的hash值與 （length -1）做按位與運算後得到index，
    // 判斷 table[index]是否存在節點，如果沒有，直接添加一個新的node到table[index]
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //判斷 table[index]不為null
        Node<K,V> e; K k;
        // 判斷下table[index]上的node的key的hash與所要添加的節點的key的hash是否相等，
        // key是否與所要添加的節點的key相等，如果是，直接将要添加的節點覆寫原來的節點
        // 為什麼要判斷hash是否相等？因為17 & 15 和 33 & 15 相等，也就是
        // 不同的key的hash可能得到相同的index，而key的hash值與key的hashCode值相關，
        // 正常情況下，兩個key equals傳回true,他們的HashCode也應該相同。
        // 如果hashMap的key重寫了equals但沒有重寫HashCode，此時equals傳回true，兩個HashCode卻不同
        // 這種情況下就不是覆寫原來的節點，而是不斷添加本應該是相同節點的節點到連結清單中，
        // 利用get取節點或者根據containsKey判斷節點是否存在都不會得到預期的結果。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
        //如果與table[index]的目前節點不一樣，判斷一下是否是樹形節點，是的話就
        // 通過樹的特性去添加節點
            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);
                    // 檢測是否該從連結清單變成樹（注意：這裡是先插入節點，沒有增加binCount,是以判斷條件是大于等于門檻值-1）
                    // 門檻值預設為8
                    //treeifyBin（）方法還會判斷，在table容量小于MIN_TREEIFY_CAPACITY  = 64時，
                    //不會樹形化，會進行擴容
                    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;
            }
        }
        // e != null,說明新添加的節點已經存在table中，
        //這次操作沒有新增節點，隻是覆寫了原來的節點
        // 如果原來節點的value不為空，傳回原來節點的value，否則傳回新的節點的value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // e == null,新增了一個節點，size增加1，
    // 判斷size增加1後是否大于hashTable的容量,是的話進行擴容。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
  • put操作總結
  1. 如果tabel為空，通過擴容來建立table。

  2. 根據key的hashCode計算hash，與（length -1）做按位與運算得到index；

     2.1、如果table[index] == null，那麼直接添加新的節點；

     2.2、如果table[index] ！= null，并且新的節點與舊的節點相同（判斷hash和key是否相等），覆寫舊的節點；

     2.3、如果table[index] ！= null，并且新的節點與舊的節點不相同；

             2.3.1、判斷是不是樹節點，是的話就就根據樹的特性去添加節點；

             2.3.2、是連結清單節點，周遊連結清單，如果找得到與新節點相等的舊節點，覆寫舊節點，否 則就在連結清單尾部添加新的節點，添加新節點後還需要判斷是否需要把連結清單轉為樹形。

  3. 如果是新節點覆寫舊節點，table中的節點個數未變，傳回節點的value；
  4. 如果是新增節點，判斷新增後節點後table中的節點個數是否超過了擴容的門檻值，如果超過，需要進行擴容，擴容後的table容量是之前的2倍。

問題：HashMap的key需要注意什麼？

自定義類作為key，必須重寫equals()和hashCode()方法。

4、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;
    // table不為空
    if (oldCap > 0) {
        // 如果原table容量已經達到最大容量限制，把threshold設定為整數的最大值2^31 - 1（之後就不會再觸發調用resize()）
        // 不做擴容操作，直接傳回原table
        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
    }
    // 如果table為空，并且構造table時有初始化table容量，那麼就用這個初始化的值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 否則，table容量為預設的16，threshold（table進行擴容的門檻值）為預設的（16 * 0.75）
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // // 如果新的門檻值是 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;
    // 如果原來的table不為空，那就要把原來table的節點轉移到新的table中
    if (oldTab != null) {
        // 周遊每個節點
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 節點不為空,将值賦給e
            if ((e = oldTab[j]) != null) {
                //置空原來元素，友善GC回收
                oldTab[j] = null;
                // 是個單節點
                if (e.next == null)
                // 直接定位到新的table的index位置
                    newTab[e.hash & (newCap - 1)] = e;
                // 是樹形節點    
                else if (e instanceof TreeNode)
                // 根據樹的特性去拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                 // 是連結清單節點，且節點個數>1   
                else { // preserve order
                    // 高效之處
                    // 利用哈希值的高低位去區分存儲位置，如果高位是0，則存儲在原來的位置；如果是1則存儲在原來位置+oldCap。
                    // 低位連結清單的頭結點、尾節點
                    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;
                    }
                    // 高位連結清單放在（原來的索引+oldCap）處
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

問題：HashMap的實作中要求容量n的長度為2的n次幂

因為在hashMap上進行存取操作都要根據key的hash定位到hashMap的某個位置上，而求餘效率不如位移運算，如果n的長度為2的n次幂，那麼就可以利用按位與操作來計算出位置index的值。

  • 總結：
  1. 如果原table為空，那就為其配置設定記憶體，如果構造時有傳入table的容量，就使用該值，否則使用預設的16，更新擴容門檻值為容量 * 負載因子（預設為0.75）；
  2. table不為空

        2.1、如果table的容量已經超過或者等于最大容量設定，不再擴容，直接傳回舊的table；

        2.2、table的容量的2倍小于最大容量設定，那就把容量擴成原來的2倍

        2.3、把原來table中的節點轉移到新的table中

                2.3.1、如果目前位置隻有一個節點，那麼根據key的hash & （新容量 -1）得到新的index，把元素添加到新的table的index位置上

               2.3.2、如果是個樹形節點，根據樹的特性進行拆分節點

               2.3.3、如果是個連結清單節點，則根據key的hash值與原容量進行高位判斷，如果為0，就在新的table上将元素添加到原索引位置上，否則添加到（原索引 + 原容量大小）的位置上。

舉例：

舊table容量為64，在33位置上一個有着兩個節點的連結清單，兩節點對應的hash分别為33和97,擴容後容量為128，33 & 127 = 33, 定位到原來的位置，97 & 127 = 97 = 33 + 64，定位到（原索引 + 原容量）的位置上。

(e.hash & oldCap) == 0操作，因為oldCap二進制有且隻有一個位置上為1，設為x，如果e.hash對應x位置上為1，定位到（原索引 + 原容量）的位置上，否則定位到原索引位置上。

5、get操作 

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;
    // table不為空，根據key的hash計算定位到table的index位置（index = (n - 1) & hash）
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 如果index位置上的節點的key的hash等于所要找的key的hash以及
        //index位置上的節點的key等于所要找的key，直接傳回這個節點
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
       // 如果index上的節點不是所要找的，且它的nextNode不為null     
        if ((e = first.next) != null) {
            // 判斷index上的節點是不是樹節點，是的話根據樹的特性擷取節點
            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);
        }
    }
    // table為空，或者在連結清單中找不到所要找的節點，傳回null
    return null;
}
  • key的hash計算 
static final int hash(Object key) {
    int h;
    // 這裡做了一個處理，如果key為null的話，hash = 0，也就是強制第 0 個桶存放鍵為 null 的鍵值對
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// h >>> 16 将key的hashCode的二進制向右移動16位
// ^ 異或操作，二進制位對應都為1或者都為0時，結果位為0，隻有當二進制位對于位不相同時結果位才為1

問題：(h = key.hashCode()) ^ (h >>> 16)操作的意義或者說作用？

因為在将key定位到hashMap的index位置上時，如果直接采用key.hashCode() & （n -1）的話，當不同的key.hashCode()的低位相等，但是高位不同時，他們會計算出相同的index，這樣就會引起hash沖突，如果hash沖突太多，hashMap的效率就會低下。

n = 64, n - 1 = 63 =0011 1111;
key1.hashCode()= 33=0010 0001;
key2.hashCode()= 97=0110 0001;
key2.hashCode()=161=1010 0001;

// 這三個key根據key.hashCode() & （n -1）計算出的index都是33，
//也就是高位的變化對index的計算沒有影響。

// h >>> 16
// 為了友善，假設hashCode是8位的，那麼就向右位移4位
(h = key.hashCode()) ^ (h >>> 4)= 0010 0001 ^ 0000 0010 = 0010 0011;
(h = key.hashCode()) ^ (h >>> 4)= 0110 0001 ^ 0000 0110 = 0110 0111;
(h = key.hashCode()) ^ (h >>> 4)= 1010 0001 ^ 0000 1010 = 1010 1011;

// 此時再與（n -1）進行按位與
key1: 0010 0011 & 0011 1111 = 0010 0011 = 35;
key2: 0110 0111 & 0011 1111 = 0010 0111 = 39;
key1: 1010 1011 & 0011 1111 = 0010 1011 = 43;

通過(h = key.hashCode()) ^ (h >>> 16)讓高位的變化影響到低位，這樣可以減少hash沖突，提高效率。

比較jdk7 和jdk 8 的hashMap的差別：

1、jdk8 hash的計算比jdk7的hash計算更簡化

2、底層資料結構發生變化：

  • JDK7：數組+連結清單。在極端的情況下會形成一條單連結清單，那麼它的查找時間複雜度會達到O(n)。
  • JDK8: 數組+連結清單+紅黑樹。 當容量超過最小樹化容量64時，如果存在連結清單節點大于等于8時就會樹化，形成紅黑樹（類似平衡查找二叉樹）。是以最壞的情況下的查找時間複雜度為O(logN). 比JDK7效率要好。

3、擴容的具體操作不一樣，JDK8要優于JDK7。 JDK7需要重新進行索引下标 的計算，而 JDK8 不需要，通過判斷高位（與原容量比較）是 0 還是 1，要麼依舊是原 index，要麼是 oldCap + 原 index。

java java學習 日常學習積累 hashmap 連結清單 資料結構
上一篇: 基于FPGA的2ASK調制仿真
下一篇: JDK8 HashMap源碼了解前言一、資料結構二、源碼分析三、常見問題

繼續閱讀