HashMap（get和put）jdk8

get邏輯：

HashMap數據結構為數組加鏈表加紅黑樹、只有當鏈表數量大於8時、才將鏈表轉換為紅黑樹、時間複雜度由鏈表的O(N)轉換為紅黑樹的O(logN)

// 主要看getNode下的方法、傳入key的hash值和key
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

// 返回一個Node對象、包含了key和value、在get方法中在返回value值
final Node<K,V> getNode(int hash, Object key) {
    // tab：Node<K, V>對象數組
    Node<K,V>[] tab;
    // first: 指向key hash值對應的數組值 e: first對應Node對象的下一個節點
    Node<K,V> first, e; 
    // n: 指向當前HashMpa的數組長度
    int n;
    // k: 臨時變數、指向 key
    K k;
    // 這裡檢測HashMap對象的數組是否存在、長度是否大於0、((n - 1) & hash)根據此表達式算出key對應的數組位置、在檢查是否存在對象。
    if (
        (tab = table) != null && 
        (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null
    ) {
        // first當前值為一個Node節點
        // 這個if是檢測當前的first指向的Node是否是要獲取的對象
        // 直接判斷first的hash值和要獲取的hash值是否一直、並且key的值是否一直、通過 ==判斷地址!=null和equals判斷、key賦值為first的key
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            // 判斷一致後直接返回要獲取的Node節點給get、get在返回Node的value值
            return first;
        // 由於上面查找都查找不到、所以要查找Node的下一個節點、即查詢鏈表或者紅黑樹
        if ((e = first.next) != null) {
            // 檢查first對象是否是TreeNode（紅黑樹）
            if (first instanceof TreeNode)
                // 當前first為紅黑樹對象、直接根據key調用內部的檢索方法獲取對應的value
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 鏈表查詢、由於first上面判斷過不是要查找的對象、e在上面語句已經指向first下一個節點、所以直接開始判斷
                // 和上面的判斷一樣、檢查hash值和key、qeuals判斷、如果有則返回對應的Node對象、沒有則最終執行下麵的return null;語句。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 表示當前對象並沒有存儲相關的key值、返回null
    return null;
}

put邏輯

public V put(K key, V value) {
    // 內部調用putVal設置值、參數如下int hash, K key, V value, boolean onlyIfAbsent（如果為 true，則不更改現有值）,boolean evict（如果為 false，則表處於創建模式）
    return putVal(hash(key), key, value, false, true);
}

// 參數如下int hash, K key, V value, boolean onlyIfAbsent（如果為 true，則不更改現有值）,boolean evict（如果為 false，則表處於創建模式）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab指向當前HashMap對象數組
    Node<K,V>[] tab; 
    // p指向key的hash值所在的數組Node對象
    Node<K,V> p;
    // n：HashMap數組的長度、i：key的hash值對應的索引（index）
    int n, i;
    // 判斷當前HashMap的數組對象是否為空、並且長度是否為0
    if ((tab = table) == null || (n = tab.length) == 0)
        // 分配數組空間並把長度返回給n
        n = (tab = resize()).length;
    // 計算hash對應的索引是否有對象存在、沒有的話則創建Node對象、並將要put的值寫入Node對象、在返回給數組
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 要將Node對象寫入到鏈表或者紅黑樹中
    else {
        // e: 代表最終你要寫入的Node對象
        Node<K,V> e; 
        // k: 指向hash值對象的Node節點的key
        K k;
        // 檢查是否是同一個hash值、key是否相對或者進行equals判斷
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 代表同一個對象、賦值給e、最後在寫入值
            e = p;
        // 檢測是否是紅黑樹節點
        else if (p instanceof TreeNode)
            // 檢測是紅黑樹對象、直接調用內部的寫入方法、在返回一個Node<K, V>節點對象、最後在寫入值、putTreeVal裡面其實已經寫入value了、後面在寫入一次。
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 鏈表操作、binCount檢測有多少個鏈表節點、根據TREEIFY_THRESHOLD常量設定的值8、超過8個鏈表節點、則將該鏈表轉換為紅黑樹
            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;
                }
                // 檢測當前插入的對象是否一致、一致的話直接返回e、下麵在將要寫入的值賦值給變數e對象
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 檢測e對象是否不為空、不為空則下麵寫入對應的value值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent為true表示不更新對象
            if (!onlyIfAbsent || oldValue == null)
                // 將值寫入
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 當前數組長度自增1大於上次擴容長度後、重新擴容並且把重新擴容的大小賦值給threshold
    if (++size > threshold)
        // 重新調整數組長度
        resize();
    // LinkedHashMap中重寫了、HashMap中沒有具體實現
    afterNodeInsertion(evict);
    // 對應的key無法寫入、返回null       
    return null;
}