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= https://www.cnblogs.com/liyuelian/archive/2022/08/23/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=https://www.cnblogs.com/liyuelian/archive/2022/08/23/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 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)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:剪枝--->如果有鏈表樹化之后，樹中的節點經過洗掉之后越來越少，當元素個數減少到一定程度，樹會轉變為了鏈表

標籤：其他

上一篇：行程

下一篇：說說用戶執行緒和守護執行緒