歡迎光臨
每天分享高質量文章

Map 大家族的那點事兒 ( 4 ) :HashMap

(點擊上方公眾號,可快速關註)


來源:SylvanasSun’s Blog ,

sylvanassun.github.io/2018/03/16/2018-03-16-map_family/

HashMap

光從名字上應該也能猜到,HashMap肯定是基於hash演算法實現的,這種基於hash實現的map叫做散串列(hash table)。

散串列中維護了一個陣列,陣列的每一個元素被稱為一個桶(bucket),當你傳入一個key = “a”進行查詢時,散串列會先把key傳入散列(hash)函式中進行尋址,得到的結果就是陣列的下標,然後再通過這個下標訪問陣列即可得到相關聯的值。

我們都知道陣列中資料的組織方式是線性的,它會直接分配一串連續的記憶體地址序列,要找到一個元素只需要根據下標來計算地址的偏移量即可(查找一個元素的起始地址為:陣列的起始地址加上下標乘以該元素型別占用的地址大小)。因此散串列在理想的情況下,各種操作的時間複雜度只有O(1),這甚至超過了二叉查找樹,雖然理想的情況並不總是滿足的,關於這點之後我們還會提及。

為什麼是hash?

hash演算法是一種可以從任何資料中提取出其“指紋”的資料摘要演算法,它將任意大小的資料(輸入)映射到一個固定大小的序列(輸出)上,這個序列被稱為hash code、資料摘要或者指紋。比較出名的hash演算法有MD5、SHA。

hash是具有唯一性且不可逆的,唯一性指的是相同的輸入產生的hash code永遠是一樣的,而不可逆也比較容易理解,資料摘要演算法並不是壓縮演算法,它只是生成了一個該資料的摘要,沒有將資料進行壓縮。壓縮演算法一般都是使用一種更節省空間的編碼規則將資料重新編碼,解壓縮只需要按著編碼規則解碼就是了,試想一下,一個幾百MB甚至幾GB的資料生成的hash code都只是一個擁有固定長度的序列,如果再能逆向解壓縮,那麼其他壓縮演算法該情何以堪?

我們上述討論的僅僅是在密碼學中的hash演算法,而在散串列中所需要的散列函式是要能夠將key尋址到buckets中的一個位置,散列函式的實現影響到整個散串列的性能。

一個完美的散列函式要能夠做到均勻地將key分佈到buckets中,每一個key分配到一個bucket,但這是不可能的。雖然hash演算法具有唯一性,但同時它還具有重覆性,唯一性保證了相同輸入的輸出是一致的,卻沒有保證不同輸入的輸出是不一致的,也就是說,完全有可能兩個不同的key被分配到了同一個bucket(因為它們的hash code可能是相同的),這叫做碰撞衝突。總之,理想很豐滿,現實很骨感,散列函式只能盡可能地減少衝突,沒有辦法完全消除衝突。

散列函式的實現方法非常多,一個優秀的散列函式要看它能不能將key分佈均勻。首先介紹一種最簡單的方法:除留餘數法,先對key進行hash得到它的hash code,然後再用該hash code對buckets陣列的元素數量取餘,得到的結果就是bucket的下標,這種方法簡單高效,也可以當做對集群進行負載均衡的路由演算法。

private int hash(Key key) {

   // & 0x7fffffff 是為了屏蔽符號位,M為bucket陣列的長度

   return (key.hashCode() & 0x7fffffff) % M;

}

要註意一點,只有整數才能進行取餘運算,如果hash code是一個字串或別的型別,那麼你需要將它轉換為整數才能使用除留餘數法,不過Java在Object物件中提供了hashCode()函式,該函式傳回了一個int值,所以任何你想要放入HashMap的自定義的抽象資料型別,都必須實現該函式和equals()函式,這兩個函式之間也遵守著一種約定:如果a.equals(b) == true,那麼a與b的hashCode()也必須是相同的。

下麵為String類的hashCode()函式,它先遍歷了內部的字符陣列,然後在每一次迴圈中計算hash code(將hash code乘以一個素數並加上當前迴圈項的字符):

/** The value is used for character storage. */

private final char value[];

/** Cache the hash code for the string */

private int hash; // Default to 0

public int hashCode() {

    int h = hash;

    if (h == 0 && value.length > 0) {

        char val[] = value;

        for (int i = 0; i < value.length; i++) {

            h = 31 * h + val[i];

        }

        hash = h;

    }

    return h;

}

HashMap沒有採用這麼簡單的方法,有一個原因是HashMap中的buckets陣列的長度永遠為一個2的冪,而不是一個素數,如果長度為素數,那麼可能會更適合簡單暴力的除留餘數法(當然除留餘數法雖然簡單卻並不是那麼高效的),順便一提,時代的眼淚Hashtable就使用了除留餘數法,它沒有強制約束buckets陣列的長度。

HashMap在內部實現了一個hash()函式,首先要對hashCode()的傳回值進行處理:

static final int hash(Object key) {

    int h;

    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

該函式將key.hashCode()的低16位和高16位做了個異或運算,其目的是為了擾亂低位的信息以實現減少碰撞衝突。之後還需要把hash()的傳回值與table.length – 1做與運算(table為buckets陣列),得到的結果即是陣列的下標。

table.length – 1就像是一個低位掩碼(這個設計也優化了擴容操作的性能),它和hash()做與操作時必然會將高位屏蔽(因為一個HashMap不可能有特別大的buckets陣列,至少在不斷自動擴容之前是不可能的,所以table.length – 1的大部分高位都為0),只保留低位,看似沒什麼毛病,但這其實暗藏玄機,它會導致總是只有最低的幾位是有效的,這樣就算你的hashCode()實現得再好也難以避免發生碰撞。這時,hash()函式的價值就體現出來了,它對hash code的低位添加了隨機性並且混合了高位的部分特征,顯著減少了碰撞衝突的發生(關於hash()函式的效果如何,可以參考這篇文章An introduction to optimising a hashing strategy)。

HashMap的散列函式具體流程如下圖:

解決衝突

在上文中我們已經多次提到碰撞衝突,但是散列函式不可能是完美的,key分佈完全均勻的情況是不存在的,所以碰撞衝突總是難以避免。

那麼發生碰撞衝突時怎麼辦?總不能丟棄資料吧?必須要有一種合理的方法來解決這個問題,HashMap使用了叫做分離鏈接(Separate chaining,也有人翻譯成拉鏈法)的策略來解決衝突。它的主要思想是每個bucket都應當是一個互相獨立的資料結構,當發生衝突時,只需要把資料放入bucket中(因為bucket本身也是一個可以存放資料的資料結構),這樣查詢一個key所消耗的時間為訪問bucket所消耗的時間加上在bucket中查找的時間。

HashMap的buckets陣列其實就是一個鏈表陣列,在發生衝突時只需要把Entry(還記得Entry嗎?HashMap的Entry實現就是一個簡單的鏈表節點,它包含了key和value以及hash code)放到鏈表的尾部,如果未發生衝突(位於該下標的bucket為null),那麼就把該Entry做為鏈表的頭部。而且HashMap還使用了Lazy策略,buckets陣列只會在第一次呼叫put()函式時進行初始化,這是一種防止記憶體浪費的做法,像ArrayList也是Lazy的,它在第一次呼叫add()時才會初始化內部的陣列。

不過鏈表雖然實現簡單,但是在查找的效率上只有O(n),而且我們大部分的操作都是在進行查找,在hashCode()設計的不是非常良好的情況下,碰撞衝突可能會頻繁發生,鏈表也會變得越來越長,這個效率是非常差的。Java 8對其實現了優化,鏈表的節點數量在到達閾值時會轉化為紅黑樹,這樣查找所需的時間就只有O(log n)了,閾值的定義如下:

/**

 * The bin count threshold for using a tree rather than list for a

 * bin.  Bins are converted to trees when adding an element to a

 * bin with at least this many nodes. The value must be greater

 * than 2 and should be at least 8 to mesh with assumptions in

 * tree removal about conversion back to plain bins upon

 * shrinkage.

 */

static final int TREEIFY_THRESHOLD = 8;

如果在插入Entry時發現一條鏈表超過閾值,就會執行以下的操作,對該鏈表進行樹化;相對的,如果在刪除Entry(或進行擴容)時發現紅黑樹的節點太少(根據閾值UNTREEIFY_THRESHOLD),也會把紅黑樹退化成鏈表。

/**

 * 替換指定hash所處位置的鏈表中的所有節點為TreeNode,

 * 如果buckets陣列太小,就進行擴容。

 */

final void treeifyBin(Node[] tab, int hash) {

    int n, index; Node e;

    // MIN_TREEIFY_CAPACITY = 64,小於該值代表陣列中的節點並不是很多

    // 所以選擇進行擴容,只有陣列長度大於該值時才會進行樹化。

    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

        resize();

    else if ((e = tab[index = (n – 1) & hash]) != null) {

        TreeNode hd = null, tl = null;

        // 轉換鏈表節點為樹節點,註意要處理好連接關係

        do {

            TreeNode p = replacementTreeNode(e, null);

            if (tl == null)

                hd = p;

            else {

                p.prev = tl;

                tl.next = p;

            }

            tl = p;

        } while ((e = e.next) != null);

        if ((tab[index] = hd) != null)

            hd.treeify(tab); // 從頭部開始構造樹

    }

}

    // 該函式定義在TreeNode中

    final void treeify(Node[] tab) {

        TreeNode root = null;

        for (TreeNode x = this, next; x != null; x = next) {

            next = (TreeNode)x.next;

            x.left = x.right = null;

            if (root == null) { // 初始化root節點

                x.parent = null;

                x.red = false;

                root = x;

            }

            else {

                K k = x.key;

                int h = x.hash;

                Class > kc = null;

                for (TreeNode p = root;;) {

                    int dir, ph;

                    K pk = p.key;

                    // 確定節點的方向

                    if ((ph = p.hash) > h)

                        dir = -1;

                    else if (ph < h)

                        dir = 1;

                    // 如果kc == null

                    // 並且k沒有實現Comparable接口

                    // 或者k與pk是沒有可比較性的(型別不同)

                    // 或者k與pk是相等的(傳回0也有可能是相等)

                    else if ((kc == null &&

                              (kc = comparableClassFor(k)) == null) ||

                             (dir = compareComparables(kc, k, pk)) == 0)

                        dir = tieBreakOrder(k, pk);

                    // 確定方向後插入節點,修正紅黑樹的平衡

                    TreeNode xp = p;

                    if ((p = (dir <= 0) ? p.left : p.right) == null) {

                        x.parent = xp;

                        if (dir <= 0)

                            xp.left = x;

                        else

                            xp.right = x;

                        root = balanceInsertion(root, x);

                        break;

                    }

                }

            }

        }

        // 確保給定的root是該bucket中的第一個節點

        moveRootToFront(tab, root);

    }

    static int tieBreakOrder(Object a, Object b) {

        int d;

        if (a == null || b == null ||

            (d = a.getClass().getName().

             compareTo(b.getClass().getName())) == 0)

            // System.identityHashCode()將呼叫並傳回傳入物件的預設hashCode()

            // 也就是說,無論是否重寫了hashCode(),都將呼叫Object.hashCode()。

            // 如果傳入的物件是null,那麼就傳回0

            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?

                 -1 : 1);

        return d;

    }

解決碰撞衝突的另一種策略叫做開放尋址法(Open addressing),它與分離鏈接法的思想截然不同。在開放尋址法中,所有Entry都會儲存在buckets陣列,一個明顯的區別是,分離鏈接法中的每個bucket都是一個鏈表或其他的資料結構,而開放尋址法中的每個bucket就僅僅只是Entry本身。

開放尋址法是基於陣列中的空位來解決衝突的,它的想法很簡單,與其使用鏈表等資料結構,不如直接在陣列中留出空位來當做一個標記,反正都要占用額外的記憶體。

當你查找一個key的時候,首先會從起始位置(通過散列函式計算出的陣列索引)開始,不斷檢查當前bucket是否為標的Entry(通過比較key來判斷),如果當前bucket不是標的Entry,那麼就向後查找(查找的間隔取決於實現),直到碰見一個空位(null),這代表你想要找的key不存在。

如果你想要put一個全新的Entry(Map中沒有這個key存在),依然會從起始位置開始進行查找,如果起始位置不是空的,則代表發生了碰撞衝突,只好不斷向後查找,直到發現一個空位。

開放尋址法的名字也是來源於此,一個Entry的位置並不是完全由hash值決定的,所以也叫做Closed hashing,相對的,分離鏈接法也被稱為Open hashing或Closed addressing。

根據向後探測(查找)的演算法不同,開放尋址法有多種不同的實現,我們介紹一種最簡單的演算法:線性探測法(Linear probing),在發生碰撞時,簡單地將索引加一,如果到達了陣列的尾部就折回到陣列的頭部,直到找到標的或一個空位。

基於線性探測法的查找操作如下:

private K[] keys; // 儲存key的陣列

private V[] vals; // 儲存值的陣列 

public V get(K key) {

    // m是buckets陣列的長度,即keys和vals的長度。

    // 當i等於m時,取模運算會得0(折回陣列頭部)

    for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {

        if (keys[i].equals(key))

            return vals[i];

    }

    return null;

}

插入操作稍微麻煩一些,需要在插入之前判斷當前陣列的剩餘容量,然後決定是否擴容。陣列的剩餘容量越多,代表Entry之間的間隔越大以及越早碰見空位(向後探測的次數就越少),效率自然就會變高。代價就是額外消耗的記憶體較多,這也是在用空間換取時間。

public void put(K key, V value) {

    // n是Entry的數量,如果n超過了陣列長度的一半,就擴容一倍

    if (n >= m / 2) resize(2 * m);

    int i;

    for (i = hash(key); keys[i] != null; i = (i + 1) % m) {

        if (keys[i].equals(key)) {

            vals[i] = value;

            return;

        }

    }

    // 沒有找到標的,那麼就插入一對新的Entry

    keys[i] = key;

    vals[i] = value;

    n++;

}

接下來是刪除操作,需要註意一點,我們不能簡單地把標的key所在的位置(keys和vals陣列)設置為null,這樣會導致此位置之後的Entry無法被探測到,所以需要將標的右側的所有Entry重新插入到散串列中:

public V delete(K key) {

    int i = hash(key);

    // 先找到標的的索引

    while (!key.equals(keys[i])) {

        i = (i + 1) % m;

    }

    V oldValue = vals[i];

    // 刪除標的key和value

    keys[i] = null;

    vals[i] = null;

    // 指標移動到下一個索引

    i = (i + 1) % m;

    while (keys[i] != null) {

        // 先刪除然後重新插入

        K keyToRehash = keys[i];

        V valToRehash = vals[i];

        keys[i] = null;

        vals[i] = null;

        n–;

        put(keyToRehash, valToRehash);

        i = (i + 1) % m;

    }

    n–;

    // 當前Entry小於等於陣列長度的八分之一時,進行縮容

    if (n > 0 && n <= m / 8) resize(m / 2);

    return oldValue;

}

動態擴容

散串列以陣列的形式組織bucket,問題在於陣列是靜態分配的,為了保證查找的性能,需要在Entry數量大於一個臨界值時進行擴容,否則就算散列函式的效果再好,也難免產生碰撞。

所謂擴容,其實就是用一個容量更大(在原容量上乘以二)的陣列來替換掉當前的陣列,這個過程需要把舊陣列中的資料重新hash到新陣列,所以擴容也能在一定程度上減緩碰撞。

HashMap通過負載因子(Load Factor)乘以buckets陣列的長度來計算出臨界值,演算法:threshold = load_factor * capacity。比如,HashMap的預設初始容量為16(capacity = 16),預設負載因子為0.75(load_factor = 0.75),那麼臨界值就為threshold = 0.75 * 16 = 12,只要Entry的數量大於12,就會觸發擴容操作。

還可以通過下列的建構式來自定義負載因子,負載因子越小查找的性能就會越高,但同時額外占用的記憶體就會越多,如果沒有特殊需要不建議修改預設值。

/**

 * 可以發現建構式中根本就沒初始化buckets陣列。

 * (之前說過buckets陣列會推遲到第一次呼叫put()時進行初始化)

 */

public HashMap(int initialCapacity, float loadFactor) {

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

    this.loadFactor = loadFactor;

    // tableSizeFor()確保initialCapacity必須為一個2的N次方

    this.threshold = tableSizeFor(initialCapacity);

}

 buckets陣列的大小約束對於整個HashMap都至關重要,為了防止傳入一個不是2次冪的整數,必須要有所防範。tableSizeFor()函式會嘗試修正一個整數,並轉換為離該整數最近的2次冪。

/**

 * Returns a power of two size for the given target capacity.

 */

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;

}

還記得陣列索引的計算方法嗎?index = (table.length – 1) & hash,這其實是一種優化手段,由於陣列的大小永遠是一個2次冪,在擴容之後,一個元素的新索引要麼是在原位置,要麼就是在原位置加上擴容前的容量。這個方法的巧妙之處全在於&運算,之前提到過&運算只會關註n – 1(n = 陣列長度)的有效位,當擴容之後,n的有效位相比之前會多增加一位(n會變成之前的二倍,所以確保陣列長度永遠是2次冪很重要),然後只需要判斷hash在新增的有效位的位置是0還是1就可以算出新的索引位置,如果是0,那麼索引沒有發生變化,如果是1,索引就為原索引加上擴容前的容量。

這樣在每次擴容時都不用重新計算hash,省去了不少時間,而且新增有效位是0還是1是帶有隨機性的,之前兩個碰撞的Entry又有可能在擴容時再次均勻地散佈開。下麵是resize()的原始碼:

final Node[] resize() {

    Node[] oldTab = table; // table就是buckets陣列

    int oldCap = (oldTab == null) ? 0 : oldTab.length;

    int oldThr = threshold;

    int newCap, newThr = 0;

    // oldCap大於0,進行擴容,設置閾值與新的容量

    if (oldCap > 0) {

        // 超過最大值不會進行擴容,並且把閾值設置成Interger.MAX_VALUE

        if (oldCap >= MAXIMUM_CAPACITY) {

            threshold = Integer.MAX_VALUE;

            return oldTab;

        }

        // 沒超過最大值,擴容為原來的2倍

        // 向左移1位等價於乘2

        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

                 oldCap >= DEFAULT_INITIAL_CAPACITY)

            newThr = oldThr << 1; // double threshold

    }

    // oldCap = 0,oldThr大於0,那麼就把閾值做為新容量以進行初始化

    // 這種情況發生在用戶呼叫了帶有引數的建構式(會對threshold進行初始化)

    else if (oldThr > 0) // initial capacity was placed in threshold

        newCap = oldThr;

    // oldCap與oldThr都為0,這種情況發生在用戶呼叫了無參建構式

    // 採用預設值進行初始化

    else {               // zero initial threshold signifies using defaults

        newCap = DEFAULT_INITIAL_CAPACITY;

        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

    }

    // 如果newThr還沒有被賦值,那麼就根據newCap計算出閾值

    if (newThr == 0) {

        float ft = (float)newCap * loadFactor;

        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

                  (int)ft : Integer.MAX_VALUE);

    }

    threshold = newThr;

    @SuppressWarnings({“rawtypes”,”unchecked”})

        Node[] newTab = (Node[])new Node[newCap];

    table = newTab;

    // 如果oldTab != null,代表這是擴容操作

    // 需要將擴容前的陣列資料遷移到新陣列

    if (oldTab != null) {

        // 遍歷oldTab的每一個bucket,然後移動到newTab

        for (int j = 0; j < oldCap; ++j) {

            Node e;

            if ((e = oldTab[j]) != null) {

                oldTab[j] = null;

                // 索引j的bucket只有一個Entry(未發生過碰撞)

                // 直接移動到newTab

                if (e.next == null)

                    newTab[e.hash & (newCap – 1)] = e;

                // 如果是一個樹節點(代表已經轉換成紅黑樹了)

                // 那麼就將這個節點拆分為lower和upper兩棵樹

                // 首先會對這個節點進行遍歷

                // 只要當前節點的hash & oldCap == 0就鏈接到lower樹

                // 註意這裡是與oldCap進行與運算,而不是oldCap – 1(n – 1)

                // oldCap就是擴容後新增有效位的掩碼

                // 比如oldCap=16,二進制10000,n-1 = 1111,擴容後的n-1 = 11111

                // 只要hash & oldCap == 0,就代表hash的新增有效位為0

                // 否則就鏈接到upper樹(新增有效位為1)

                // lower會被放入newTab[原索引j],upper樹會被放到newTab[原索引j + oldCap]

                // 如果lower或者upper樹的節點少於閾值,會被退化成鏈表

                else if (e instanceof TreeNode)

                    ((TreeNode)e).split(this, newTab, j, oldCap);

                else { // preserve order

                    // 下麵操作的邏輯與分裂樹節點基本一致

                    // 只不過split()操作的是TreeNode

                    // 而且會將兩條TreeNode鏈表組織成紅黑樹

                    Node loHead = null, loTail = null;

                    Node hiHead = null, hiTail = null;

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

}

使用HashMap時還需要註意一點,它不會動態地進行縮容,也就是說,你不應該保留一個已經刪除過大量Entry的HashMap(如果不打算繼續添加元素的話),此時它的buckets陣列經過多次擴容已經變得非常大了,這會占用非常多的無用記憶體,這樣做的好處是不用多次對陣列進行擴容或縮容操作。不過一般也不會出現這種情況,如果遇見了,請毫不猶豫地丟掉它,或者把資料轉移到一個新的HashMap。

添加元素

我們已經瞭解了HashMap的內部實現與工作原理,它在內部維護了一個陣列,每一個key都會經過散列函式得出在陣列的索引,如果兩個key的索引相同,那麼就使用分離鏈接法解決碰撞衝突,當Entry的數量大於臨界值時,對陣列進行擴容。

接下來以一個添加元素(put())的過程為例來梳理一下知識,下圖是put()函式的流程圖:

然後是原始碼:

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) {

    Node[] tab; Node p; int n, i;

    // table == null or table.length == 0

    // 第一次呼叫put(),初始化table

    if ((tab = table) == null || (n = tab.length) == 0)

        n = (tab = resize()).length;

    // 沒有發生碰撞,直接放入到陣列

    if ((p = tab[i = (n – 1) & hash]) == null)

        tab[i] = newNode(hash, key, value, null);

    else {

        Node e; K k;

        // 發生碰撞(頭節點就是標的節點)

        if (p.hash == hash &&

            ((k = p.key) == key || (key != null && key.equals(k))))

            e = p;

        // 節點為紅黑樹

        else if (p instanceof TreeNode)

            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

        // 節點為鏈表

        else {

            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;

                }

                // 找到標的節點,退出迴圈

                if (e.hash == hash &&

                    ((k = e.key) == key || (key != null && key.equals(k))))

                    break;

                p = e;

            }

        }

        // 節點已存在,替換value

        if (e != null) { // existing mapping for key

            V oldValue = e.value;

            if (!onlyIfAbsent || oldValue == null)

                e.value = value;

            // afterNodeXXXXX是提供給LinkedHashMap重寫的函式

            // 在HashMap中沒有意義

            afterNodeAccess(e);

            return oldValue;

        }

    }

    ++modCount;

    // 超過臨界值,進行擴容

    if (++size > threshold)

        resize();

    afterNodeInsertion(evict);

    return null;

}

系列


【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】《不要自稱是程式員,我十多年的 IT 職場總結》:http://blog.jobbole.com/94148/

③ 最後請附上您的個人簡介哈~



看完本文有收穫?請轉發分享給更多人

關註「ImportNew」,提升Java技能

赞(0)

分享創造快樂