HashMap

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

背景引入

陣列

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

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

連結串列

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

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

拓展知識點：

陣列和連結串列迭代的方式不同 ArrayList實現了RandomAccess介面這是一個標記介面，標註是否可以隨機存取 ArrayList使用陣列實現，可以隨機存取經過測試使用for迴圈遍歷ArrayList更快而LinkedList沒有實現這個RandomAccess介面不支援隨機存取，使用迭代器遍歷更快 RandomAccess介面的作用。

正是陣列和連結串列各有各的優勢，所以引入了雜湊表，結合了兩者的優勢儘可能的降低劣勢帶來的影響。

簡介

Hash

雜湊：英文是Hash，也稱為雜湊 基本原理就是把任意長度輸入，轉化為固定長度輸出這個對映的規則就是Hash演演算法，而原始資料對映的二進位制串就是Hash值

Hash特點：

從Hash值不可以反向推匯出原始資料（因為互斥或的緣故無法反推）
輸入資料的微小變化會得到完全不同的Hash值相同的資料一定可以得到相同的值
雜湊演演算法的執行效率要高效，長的文字也能快速計算Hash值
Hash演演算法的衝突概率要小

HashMap

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

類圖

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

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

(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時 【二者滿足其一即可】

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衝突方法：

開放定址法
連結串列法（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長度

路由演演算法

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

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

PUT方法

put過程圖

putVal程式碼邏輯圖：

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對應的雜湊與高位運算結果。

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

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

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

HashMap原始碼分析 (基於JDK1.8)

HashMap

背景引入

陣列

連結串列

簡介

Hash

HashMap

類圖

儲存結構

Hash儲存過程

Hash衝突

Hash演演算法

Hash擾動函數

路由演演算法

HashMap擴容

Hash原始碼

建構函式

PUT方法

Resize方法

GET方法

Remove方法

Replace方法