Java集合07

14.HashMap底層機制

1. （k,v）是一個Node，實現了Map.Entry<K,V>，查看HashMap的源碼可以看到
2. jdk7.0 的HashMap底層實現[數組+鏈表]，jdk8.0底層[數組+鏈表+紅黑樹]

14.1HashMap擴容機制（和HashSet完全相同）

詳見10.2HashSet的底層擴容機制

1. HashMap底層維護了Node類型的數組table，預設為null
2. 當創建對象時，將載入因數（loadfactor）初始化為0.75
3. 當添加key-value時，通過key的哈希值得到在table的索引。然後判斷該索引處是否有元素，如果沒有元素則直接添加；如果該索引處有元素，繼續判斷該元素的key是否和準備加入的key相等。若相等，則直接替換value；若不相等，需要判斷是樹結構還是鏈表結構，作出相應處理。如果添加是發現容量還不夠，則需要擴容。
4. 第一次添加，則需要擴容table容量為16，臨界值（threshold）為（0.75*16=）12
5. 以後再擴容，則需要擴容為table的容量為之前的兩倍，臨界值也為原來的兩倍，即24.以此類推
6. 在Java8中，如果一條鏈表的元素個數超過TREEIFY_THRESHOLD（預設為8），並且table的大小>=MIN_TREEIFY_CAPACITY（預設64），就會進行樹化（紅黑樹）。

例子：

package li.map.hashmap;

import java.util.HashMap;

@SuppressWarnings("all")
public class HashMapSource {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("java",10);//ok
        map.put("php",10);//ok
        map.put("java",20);//替換value

        System.out.println(map);//{java=20, php=10}
    }
}

執行過程如下：

1. 執行構造器 newHashMap();

   初始化載入因數 loadfactor = 0.75

   HashMap$Node[ ] = null

2. 執行put（），調用hash（）方法計算key的值

   可以看到，如果傳入的參數key為空的話，就返回0；如果不為空，則求出 key 的 hashCode 值，然後將hashCode 值右移16位並且與原來的 hashCode 值進行 ^(按位異或) 操作，並返回這個哈希值

public V put(K key, V value) {//K="java" value= 10
    return putVal(hash(key), key, value, false, true);
}

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

3.調用putVal方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {//
    Node<K,V>[] tab; Node<K,V> p; int n, i;//定義了輔助變數
    //這裡定義的tablejiushi HashMap的一個數組，類型是Node[]數組
    if ((tab = table) == null || (n = tab.length) == 0)//if 語句表示，如果當前table是null，或者大小=0，則進行第一次擴容，擴容到16個空間
        n = (tab = resize()).length;//如果為第一次擴容，此時初始的table已經變成容量為16的數組
    
    /*
    1.根據key，得到hash 去計算key應該放到table表的哪個索引位置，並且把這個未知的對象賦給賦值變數p  	     2.再判斷p是否為空 
    	2.1如果p為空，表示該位置還沒存放元素，就創建一個Node (key="java", value=PRESENT)並把數         據放在該位置--table[i]=newNode(hash, key, value, null);
    */
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    
    else {
      //2.2如果不為空，就會進入else語句
        Node<K,V> e; K k;//定義輔助變數
       /*這裡的p指向當前索引所在的對象（由上面的p = tab[i = (n - 1) & hash])計算出索引位置），如          果當前索引位置對應鏈表的第一個元素的哈希值 和 準備添加的key的哈希值 一樣，
       並且 滿足下麵兩個條件之一：
        1.準備加入的key 和 p指向的Node節點 的key 是同一個對象：(k = p.key) == key
        2.p指向的Node節點的key 的equals()和準備加入的key比較後相同 並且key不等於null：(key !=               null && key.equals(k))
       就不加入  只是換原來的元素（不插入新結點只是替換值）
        */
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        //再判斷p是否是一顆紅黑樹
        //如果是紅黑樹，就調用putTreeVal（）方法來進行添加
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        else { //如果table對應索引位置已經是一個鏈表了，就使用for迴圈依次比較
               //（1）依次和該鏈表的每個元素都比較後 都不相同，就則將數據加入到該鏈表的最後
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {//先賦值再判斷
                    p.next = newNode(hash, key, value, null);
                    //註意：把元素添加到鏈表之後立即 判斷該鏈表是否已經達到8個節點，如果已經達到則                         //調用 treeifyBin()對當前鏈表進行樹化（轉成紅黑樹）
                    //在轉成紅黑樹時 還要進行一個判斷：
                    //如果該table數組的為空或者大小小於64，則對table數組進行擴容
                    //如果上麵條件不成立，即數組大小大於等於64且鏈表數量達到8個，就轉成紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                 //（2）如果在依次和該鏈表的每個元素比較的過程中發現如果有相同情況，就直接break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;//在上面for迴圈條件已經把p.next賦值給e了，這裡e又賦值給p 其實就是將p指針指                         //向p.next，然後再進行新一輪的判斷，如此迴圈，直到有滿足上面if語句的條件為止
            }
     }
        
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;//替換，key對應value
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    
    ++modCount;//每增加一個Node，就size++
    if (++size > threshold)//當使用的容量 > 臨界值時，就擴容
        resize();
    afterNodeInsertion(evict);
    return null;
}

PS:關於樹化

        for (int binCount = 0; ; ++binCount) {
            //（1）依次和該鏈表的每個元素都比較後 都不相同，就則將數據加入到該鏈表的最後
                if ((e = p.next) == null) {//先賦值再判斷
                    p.next = newNode(hash, key, value, null);
                    
                    //註意：把元素添加到鏈表之後立即 判斷該鏈表是否已經達到8個節點，如果已經達到則                         //調用 treeifyBin()對當前鏈表進行樹化（轉成紅黑樹）
                    //在轉成紅黑樹時 還要進行一個判斷：
                    //如果該table數組的為空或者大小小於64，則對table數組進行擴容
                    //如果上麵條件不成立，即數組大小大於等於64且鏈表數量達到8個，就轉成紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                 //（2）如果在依次和該鏈表的每個元素比較的過程中發現如果有相同情況，就直接break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;//在上面for迴圈條件已經把p.next賦值給e了，這裡e又賦值給p 其實就是將p指針指                         //向p.next，然後再進行新一輪的判斷，如此迴圈，直到有滿足上面if語句的條件為止
            }

遍歷過程中p從第一個節點遍歷到最後一個節點，但由於binCount是從0開始計數，所以在做樹化判斷時binCount

的值等於 鏈表長度 - 1（註意此時的鏈表長度沒有算新插入的節點）

判斷條件為 binCount >= TREEIFY_THRESHOLD - 1 ==> binCount+1(鏈表長度) >= TREEIFY_THRESHOLD

但此時鏈表新插入了一個節點

 p.next = newNode(hash, key, value, null);

所以鏈表樹化的那一刻，它的真實長度應該時binCount+1+1 => 鏈表長度>TREEIFY_THRESHOLD(8)

即：

鏈表長度大於8時，treeifyBin()方法被調用

（在做樹化判斷時，鏈表長度 = binCount+1（從零計數）+1（新插入節點） = bincount +2）

（判斷條件： (bincount >= 8-1) => (bincount>=7) => (bincount+2>=9) => (鏈表長度>=9) 長度是整數 大於等於9也就是大於8）

ps:剪枝--->如果有鏈表樹化之後，樹中的節點經過刪除之後越來越少，當元素個數減少到一定程度，樹會轉變為了鏈表