HashMap源碼分析 (基於JDK1.8)

来源:https://www.cnblogs.com/buchizicai/archive/2023/02/07/17099246.html
-Advertisement-
Play Games

基於哈希表的 Map 介面的實現。此實現提供所有可選的映射操作，並允許使用 null 值和 null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恆久不變。 此實現假定哈希函數將元素適當地分佈在各桶之間，... ...


HashMap

本文講解的HashMap以及源代碼都是基於JDK1.8


背景引入

數組

優：讀取修改快 劣：增加刪除慢

原因：數組可以根據下標直接定位到指定位置的數據進行讀取和修改，但增加和刪除需要開闢一個新數組並移動增加和刪除後的數據到新數組並返回。


鏈表

優：增加刪除快 劣：讀取修改慢

原因：鏈表增加和刪除只需斷開指定位置的兩端節點，但讀取的時候只能從頭/尾開始往另一方向讀取。

拓展知識點：

數組和鏈表迭代的方式不同 ArrayList實現了RandomAccess介面 這是一個標記介面，標註是否可以隨機訪問 ArrayList使用數組實現，可以隨機訪問 經過測試 使用for迴圈遍歷ArrayList更快 而LinkedList沒有實現這個RandomAccess介面 不支持隨機訪問，使用迭代器遍歷更快 RandomAccess介面的作用。

正是數組和鏈表各有各的優勢，所以引入了散列表，結合了兩者的優勢儘可能的降低劣勢帶來的影響。


簡介

Hash

哈希：英文是Hash，也稱為散列 基本原理就是把任意長度輸入，轉化為固定長度輸出 這個映射的規則就是Hash演算法，而原始數據映射的二進位串就是Hash值

Hash特點：

  1. 從Hash值不可以反向推導出原始數據 （因為異或的緣故無法反推）

  2. 輸入數據的微小變化會得到完全不同的Hash值相同的數據一定可以得到相同的值

  3. 哈希演算法的執行效率要高效，長的文本也能快速計算Hash值

  4. Hash演算法的衝突概率要小


HashMap

HashMap ，是一種散列表，用於存儲 key-value 鍵值對的數據結構，每一個鍵值對也叫做Entry，一般翻譯為“哈希表”，提供平均時間複雜度為 O(1) 的、基於 key 級別的 get/put 等操作。


類圖

雙列集合定義了一個介面java.util.Map，此介面主要有四個常用的實現類，分別是HashMap、Hashtable、LinkedHashMap和TreeMap

image

下麵針對各個實現類的特點做一些說明：

(1) HashMap：它根據鍵的hashCode值存儲數據，大多數情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。 HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導致數據的不一致。如果需要滿足線程安全，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap。

(2) Hashtable：Hashtable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，並且是線程安全的，任一時間只有一個線程能寫Hashtable，併發性不如ConcurrentHashMap，因為ConcurrentHashMap引入了分段鎖。Hashtable不建議在新代碼中使用，不需要線程安全的場合可以用HashMap替換，需要線程安全的場合可以用ConcurrentHashMap替換。

(3) LinkedHashMap：LinkedHashMap是HashMap的一個子類，保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的，也可以在構造時帶參數，按照訪問次序排序。

(4) TreeMap：TreeMap實現SortedMap介面，能夠把它保存的記錄根據鍵排序，預設是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator遍歷TreeMap時，得到的記錄是排過序的。如果使用排序的映射，建議使用TreeMap。在使用TreeMap時，key必須實現Comparable介面或者在構造TreeMap傳入自定義的Comparator，否則會在運行時拋出java.lang.ClassCastException類型的異常。

對於上述四種Map類型的類，要求映射中的key是不可變對象。不可變對象是該對象在創建後它的哈希值不會被改變。如果對象的哈希值發生變化，Map對象很可能就定位不到映射的位置了。


存儲結構

HashMap是數組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現的

改變鏈表結構的預設條件：1. 單鏈表中的元素個數大於8時 2. 桶數組中的元素個數大於64時 【二者滿足其一即可】

image

table數組是一個Node [] table的數組，存放node節點（Node是HashMap的一個內部類）

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    //當前節點經過hash擾動函數和路由演算法後的值（存放位置的下標）
    final K key;
    V value;
    Node<K,V> next;   //下一個node節點

    Node(int hash, K key, V value, Node<K,V> next) { ... }
    public final K getKey(){ ... }
    public final V getValue() { ... }
    public final String toString() { ... }
    public final int hashCode() { ... }
    public final V setValue(V newValue) { ... }
    public final boolean equals(Object o) { ... }
}

Hash存儲過程

比較簡單的描述，詳細的可以看put方法流程圖

以存儲該鍵值對為例

 map.put("偵探","conan");

① 系統將調用”偵探”這個key的hashCode()方法得到其hashCode 值（該方法適用於每個Java對象），

② 然後再通過Hash演算法的後兩步運算（高位運算 (擾動函數) 和取模運算 (路由演算法) ）來定位該鍵值對的存儲位置


Hash衝突

由來：不同的數據經過hash擾動函數hash( )、路由演算法 ( hash(x) & (n-1) ) 後得到的值可能相同，此時就會存到同一個桶位，這就叫hash衝突。

解決hash衝突方法：

  1. 開放定址法

  2. 鏈表法（JDK1.8使用鏈表+紅黑樹）

    當不同的數據經過hash演算法後到達同一個桶位，該桶內的數據就會鏈化。拉鏈法的鏈子就會很長，那麼就會降低查找速度。

此時桶數組小了容易發生hash衝突，hash演算法要是區分數據不明顯也會導致hash衝突，所以僅僅時靠鏈表法來緩解hash衝突是不夠的，也需要號的hash演算法以及擴容機制來預防hash衝突。


Hash演算法

hash演算法包括hash擾動函數以及路由演算法。Hash演算法本質上就是三步：取key的hashCode值、高位運算、取模運算。

Hash擾動函數

作用：分散hashcode，使相似的數據有著截然不同的hash值

//hash擾動函數：加入了對高16位的特征，更見分散hash值
//(h = key.hashCode()) ^ (h >>> 16)：拿自己本身和本身右進位16位後的數組做異或運算，得到的數字就帶有高16位的特征
//疑問：為什麼不直接使用整個hash而是要得到前16位為0的數字？（整合hash就包括本身的高低16位數的特征）
//答案：因為hashcode的數據類型是int，有符號位所以int在正數範圍內是16位。所以需要hash得到一個16的數字
static final int hash(Object key) {
    int h;	//key對於的hashcode值
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

代碼中的h>>>16就是jdk1.8新引入的高位運算演算法，作用：使hashcode的高位數字特征也能一併體現再hashcode中，更加分散hash值。通過hashCode()的高16位異或低16位實現的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質量來考慮的，這麼做可以在數組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。

n為table長度

image

路由演算法

jdk1.8沒有封裝成方法，而是直接使用以下公式

h & (table.length-1); //h是前面hash擾動得到的值

HashMap擴容

註意點：JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候，如果在新表的數組索引位置相同，則鏈表元素會倒置，但是JDK1.8不會倒置 （具體可以看下文的Resize方法講解）

先瞭解幾個源碼變數：

//當前hash表中實際存在的元素個數
transient int size;

//當前hash表的結構修改次數（註意：改查不算結構修改，增刪才算結構修改）
transient int modCount;

//擴容閾值：當hash表中的元素超過該值時，觸發擴容【通過賦值因數計算得來：threshold=loadFactor * capacity】 capacity是桶數組長度
int threshold;

//負載因數【預設0.75】
final float loadFactor;

Node[] table的初始化長度length(預設值是16)，Load factor為負載因數(預設值是0.75)，threshold是HashMap所能容納的最大數據量的Node(鍵值對)個數。threshold = length * Load factor。

threshold擴容閾值就是在此Load factor和length(數組長度)對應下允許的最大元素數目，超過這個數目就重新resize(擴容)，擴容後的HashMap容量是之前容量的兩倍。預設的負載因數0.75是對空間和時間效率的一個平衡選擇。（一般情況不修改，如果記憶體空間很多而又對時間效率要求很高，可以降低負載因數Load factor的值；相反，如果記憶體空間緊張而對時間效率要求不高，可以增加負載因數loadFactor的值，這個值可以大於1）

在HashMap中，哈希桶數組table的長度length大小必須為2的n次方(一定是合數)（如何保證為2的n次方下麵構造方法有講），這是一種非常規的設計，常規的設計是把桶的大小設計為素數。相對來說素數導致衝突的概率要小於合數，Hashtable初始化桶大小為11，就是桶大小設計為素數的應用（Hashtable擴容後不能保證還是素數）。

必須為2的n次方的HashMap非常規設計目的：為了在取模 (路由演算法) 和擴容時做優化，同時為了減少衝突，HashMap定位哈希桶索引位置時，也加入了 (擾動函數) 高位參與運算的過程。

路由演算法優化：因為要提升性能 &比%快，所以只有當容量n為2的n次方時，(n - 1) & hash == hash % (n - 1) 才成立！

擴容優化：擴容的時候方便數據遷移。（具體如何方便後文有講）


Hash源碼

構造函數

小結：擴容是一個特別耗性能的操作，所以在創建hashmap的時候儘量估算capacity容量

先認識以下變數（和前面擴容認識的變數一樣）

//桶數組
transient Node<K,V>[] table;

//鍵值對對象
transient Set<Entry<K,V>> entrySet;

//當前hash表中實際存在的元素個數
transient int size;

//當前hash表的結構修改次數（改查不算結構修改，增刪才算結構修改）
transient int modCount;

//擴容閾值：當hash表中的元素超過該值時，觸發擴容【通過賦值因數計算得來：threshold=loadFactor * capacity】 capacity是桶數組長度
int threshold;

//負載因數
final float loadFactor;

四種構造方法

//指定容量和負載因數構造
public HashMap(int initialCapacity, float loadFactor) {
    //1. 做校驗：
    //1.1 容量合法 容量要在0~最大值內
    //1.2 負載因數必須大於0
    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);

    //2. 處理輸入的capacity，保證最後的capacity為2的n次方
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity); //轉為capacity為2的n次方
}

//指定容量構造
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//無參構造
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//傳map參數構造
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

保證capacity為2的n次方的演算法：

//將capacity轉化為大於capacity的最小的2的n次方
//原理：進來16結果是16 進來15結果是16
//0001 1101 1100 => 0001 1111 1111 => 0010 0000 0000
//解釋：
// 1. 先將進來的數字-1（保證邊緣不出錯，如：邊緣的16出去也是16）
// 2. 如何通過或運算，將最高位以下的0都轉成1
// 3. 最後再+1，就可以得到capacity最小的2的n次方
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;
}

image

在以上構造方法中並沒有看到 table 數組的初始化，只對靜態變數capacity、loadFactor賦值了，因為它是延遲初始化。只有在插入第一條數據的時候才會初始化（後面put方法中有體現）


PUT方法

put過程圖

image

putVal代碼邏輯圖：

image

put代碼：put調用putVal

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) {
    //tab:引用當前hashMap的散列表
    //p：表示當前散列表的元素
    //n：表示散列表數組的長度
    //i：表示路由定址結果
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    //1.前面創建時延遲初始化，節約記憶體。在第一次插入數據調用putVal的時候才初始化hashmap中最消耗記憶體的散列表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    //2.該桶位為空時直接插入：通過路由演算法（tab.length-1）& hash 得到桶位並插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //3.該桶位有元素時（鏈表/紅黑樹）：
    else {
        //e：不為null的話，找到了一個與當前要插入的A元素的key一致的B元素（B元素是桶內的）
        //k：表示臨時的一個key
        Node<K,V> e; K k;

        //3.1 要插入的元素的key與桶內元素的key一致，則進行替換修改操作
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //3.2 遇到該桶位已經是紅黑樹的情況
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //3.3 遇到該桶位為鏈表的情況
        else {
            //3.3.1迴圈遍歷鏈表，比對key（要插入的key和桶內鏈表的all key）是修改數據還是插到尾部
            for (int binCount = 0; ; ++binCount) {
                //① 到了末尾都沒找到相同的key就插入到尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //② 添加數據後，鏈長度是否觸發數化操作。
                    //binCount >= TREEIFY_THRESHOLD - 1：當binCount=7時就是第九個元素，因為從0開始並且該桶已經有元素在了
                    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;
            }
        }

        //3.4 替換數據；當e！=null說明有需要替換的數據，就替換數據
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //參數允許替換
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    //4. 如果是增加操作，就增加修改結構的次數(如果是修改操作前面會return的）
    ++modCount;
    //5. 插入新元素長度加一，判斷是否觸發擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Resize方法

擴容方法resize ( )

代碼：

final Node<K,V>[] resize() {
    //oldTab：引用擴容前的哈希表
    Node<K,V>[] oldTab = table;
    //oldCap：表示擴容之前table數組的長度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //oldThr：表示擴容之前的擴容閾值，觸發本次擴容的閾值
    int oldThr = threshold;
    //newCap:擴容之後table數組的大小
    //newThr：擴容之後，下次再次觸發擴容的條件
    int newCap, newThr = 0;

    //條件成立，說明hashMap中的散列表已經初始化過了，是一次正常的擴容
    if (oldCap > 0) {
        //如果當前容量已經大於最大容量則不能擴容，並且修改擴容條件為int最大值，防止下次觸發擴容條件
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //正常擴容*2；條件是舊的容量大於16，並且擴容後的容量(*2後的)小於最大容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }

    // oldCap == 0 && oldThr > 0  說明散列函數未初始化，但創建的時候有指定容量
    // 1.new HashMap(initCap,loadFactor)
    // 2.new HashMap(intiCap)
    // 3.new HashMap(map) 並且Map有數據
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;

    //oldCap == 0，散列表未初始化過，且創建的時候沒指定容量。此時就需要設置預設值
    // 1.new HashMap();
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // newThr為0的時候，通過newCap和loadFactor計算出一個newThr
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }

    // 更新閾值為計算出來的 newThr
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //創建一個很大的數組（如果是預設初始化就是16，是擴容就是*2，是指定初始化就是大於capacity最小的2的n次方）
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //更新table的引用
    table = newTab;

    //原數組中有值，需要做數據遷移
    if (oldTab != null) {
        //遍歷原數組中的元素
        for (int j = 0; j < oldCap; ++j) {
            //e：暫存當前的node節點
            Node<K,V> e;
            //當前桶位有節點：單個數據、鏈表數據、紅黑樹數據
            if ((e = oldTab[j]) != null) {
                //前面e已經記錄了當前節點，所以當前節點置為null便於 GC回收
                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;
                    //低高位鏈表例子：x可能為0 1
                    //x1111在原數組的15，根據路由演算法到新數組中要麼在15要麼在31，因為x只有0 1變化

                    //存放當前鏈表的一個元素
                    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;
}

擴容時數據遷移演算法：

我們使用的是2次冪的擴展(指長度擴為原來2倍)，所以元素的位置要麼是在原位置，要麼是在原位置再移動2次冪的位置（看下圖可以明白這句話的意思）n為table的長度，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴容後key1和key2兩種key確定索引位置的示例，其中hash1是key1對應的哈希與高位運算結果。

image

元素在重新計算hash之後，因為n變為2倍，那麼n-1的mask範圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：

image

因此，我們在擴充HashMap的時候，不需要像JDK1.7的實現那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”。下圖以16擴容為32的resize示意圖：

image


GET方法

代碼：

//根據傳入的key，得到其hash然後去查是否有該值
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) {
    // tab：引用當前hashMap的散列表
    // first：桶位中的頭元素
    // e：臨時node元素
    // n：table數組元素
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //有數據可查的時候：桶hash存在並且hash路由演算法得到的桶不為空
    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) {
            //桶位里是紅黑樹，查找紅黑樹O(LogN)
            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;
}

Remove方法

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

//邏輯：先查到然後標記，再刪除標記的元素
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    // tab：引用當前hashMap的散列表
    // p：當前node元素
    // n：表示散列表數組長度
    // index：表示定址結果
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //查找：
    //有數據時：判斷hash桶是否為空，並且根據hash路由到的桶位是否存在
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        // node：查找到的結果
        // e：當前Node的下一個元素
        Node<K,V> node = null, e; K k; V v;
        //桶位節點就是要找到節點，直接標記
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        //桶位節點數據有多個，可能是紅黑樹or鏈表
        else if ((e = p.next) != null) {
            //紅黑樹查找
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            //鏈表迴圈查找
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }

        //判斷是否查到節點需要刪除
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            //刪紅黑樹節點
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //刪桶位節點
            else if (node == p)
                tab[index] = node.next;
            //刪鏈表節點
            else
                p.next = node.next;

            //刪除操作修改了結構所以++
            ++modCount;
            //刪除操作使數量--
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

Replace方法

//根據 k 和 v 替換
public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

//根據 k oldValue newValue 替換 
public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

本文來自博客園，作者：不吃紫菜，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接：https://www.cnblogs.com/buchizicai/p/17099246.html及本聲明。

本文版權歸作者所有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 《分散式技術原理與演算法解析》學習筆記Day04
    這篇文章主要描述分散式技術中的選舉演算法，分散式選舉是為選出一個主節點，由它來協調和管理其他節點，保證集群有序運行和節點間數據的一致性。涉及到的選舉演算法包括Bully演算法、Raft演算法和ZAB演算法。 ...
  • 高層次綜合器Vivado HLS的概念與特點[原創www.cnblogs.com/helesheng]
    最近在寫一本Xilinx的FPGA方面的書，現將HLS部分內容在這裡分享給大家，希望大家喜歡，也歡迎批評指正。[原創www.cnblogs.com/helesheng] 在可編程邏輯器件被用於電子系統設計的前期，由於所含的邏輯資源較少，絕大部分情況下，它們被用於實現數據的傳輸和介面電路。工程師們習慣 ...
  • Spring AOP與AspectJ的對比及應用
    1 簡介 AOP，即面向切麵編程是很常用的技術，特別是在Java Web開發中。而最流行的AOP框架分別是Spring AOP和AspectJ。 2 Spring AOP vs AspectJ Spring AOP是基於Spring IoC實現的，它解決大部分常見的需求，但它並不是一個完整的AOP解 ...
  • Python教程：高級特性
    原文地址：https://bysocket.com/openai-chatgpt-error-1020/ 最近打開 chat.openai.com/chat 地址，如下圖會提示錯誤碼：Access denied Error code 1020。這裡通過學習和排查，總結了 3 種方法區解決這個問題。 ...
  • VGA、TFT顯示模塊——verilog實現
    這次設計一個VGA、TFT顯示模塊，其特點如下： 行同步信號、場同步信號、數據有效信號的延遲數可調。（應用時方便與存儲模塊數據對齊） 解析度可以通過調整參數來改變。 數據格式為RGR565,可簡單修改位寬來修改成其他數據格式。 TFT的介面時序和VGA的時序相似，但是TFT介面比VGA多了數據有效信 ...
  • spi~在插件開發過程中的使用
    spi是原生java的組件，通過META-INF/services目錄進行註冊，通過ServiceLoader進行載入，一般可以用在組件開發中，你在公用組件中封裝好邏輯，將個性化的部分抽象出一個介面，介面通過spi的方式進行載入，在外部開發人員引用你的組件之後，通過實現介面來擴展個性化的功能，再通過 ...
  • 在 SpringBoot 項目中簡單實現 JWT 驗證
    使用 SpringBoot 提供 api 的時候，我更喜歡使用 jwt 的方式來做驗證。網上有會多 Spring Security 整合 jwt 的，也有 Shiro 整合 jwt 的，感覺有點複雜。這裡分享一下自己在項目中的簡單實現。 依賴包 除了 SpringBoot 基本的依賴，需要一個生成 ...
  • 京東一面：MySQL 中的 distinct 和 group by 哪個效率更高？問倒一大遍。。
    先說大致的結論（完整結論在文末）： 在語義相同，有索引的情況下：group by和distinct都能使用索引，效率相同。 在語義相同，無索引的情況下：distinct效率高於group by。原因是distinct 和 group by都會進行分組操作，但group by可能會進行排序，觸發fil ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類