Java?源碼重讀系列之?HashMap

更新時(shí)間：2023年04月13日 08:37:14 作者：U2647

這篇文章主要為大家介紹了Java源碼重讀系列之HashMap示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

0. 成員變量

首先我們先看一下 HashMap 有哪些成員變量

    /**
     * 默認(rèn)的初始大小，16，值必須是 2 的冪值
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 &lt;&lt; 4; // aka 16

    /**
     * 最大值，必須是 2 冪值且 小于等于 2 的30 次冪
     */
    static final int MAXIMUM_CAPACITY = 1 &lt;&lt; 30;
    /**
     * 默認(rèn)加載因子，0.75，就是map里的元素值超過(guò) 75% 就會(huì)觸發(fā)擴(kuò)容
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //下面還有三個(gè)樹(shù)化的參數(shù)
    //如果哈希值相同的元素超過(guò) 8 個(gè)，則樹(shù)化
    static final int TREEIFY_THRESHOLD = 8;
    //樹(shù)的節(jié)點(diǎn)小于 6 個(gè)，則轉(zhuǎn)成鏈表
    static final int UNTREEIFY_THRESHOLD = 6;
    //如果 map 的元素小于 64，即便是 哈希值相同的元素超過(guò) 8 個(gè)了，也不樹(shù)化，會(huì)擴(kuò)容
    static final int MIN_TREEIFY_CAPACITY = 64;

下面還有一個(gè) Node 類，這個(gè)類就是 HashMap 存儲(chǔ)元素的容器，其實(shí)很簡(jiǎn)單

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        //... ... 

}

沒(méi)有多少?gòu)?fù)雜的內(nèi)容，類似于鏈表的Node節(jié)點(diǎn)，key、value、next，因?yàn)榇罅康牡胤蕉夹枰玫綄?duì)象的 hash 值，所以又記錄了下 key 的 hash 值。

1. hash()

繼續(xù)往下看

	//求 key 的哈希值
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

也沒(méi)什么好說(shuō)的，就是通過(guò)對(duì)象的 hashCode 計(jì)算出一個(gè) int 值。

2. comparableClassFor()

下面有個(gè) comparableClassFor 方法，這個(gè)方法的主要是判斷入?yún)?x 是否實(shí)現(xiàn)了 Comparable 接口。不過(guò)寫的格式有點(diǎn)緊湊，我們需要展開(kāi)以下。

	static Class<?> myComparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c = x.getClass();
            // 獲取 x 實(shí)現(xiàn)的所有接口
            Type[] ts = c.getGenericInterfaces();
            Type[] as;
            Type t;
            ParameterizedType p;
            //如果 x  是 String 類型 直接返回
            if (c == String.class) {
                return c;
            }
            if (ts != null) {
                // 遍歷實(shí)現(xiàn)的所有接口
                for (int i = 0; i < ts.length; ++i) {
                    t = ts[i];
                    // 如果接口有泛型
                    if (t instanceof ParameterizedType) {
                        p = (ParameterizedType) t;
                        // 如果泛型對(duì)象是 Comparable
                        if (p.getRawType() == Comparable.class) {
                            as = p.getActualTypeArguments();
                            // 只有一個(gè)泛型參數(shù)，且參數(shù)類型是 x.class
                            if (as != null && as.length == 1 && as[0] == c) {
                                return c;
                            }
                        }
                    }
                }
            }
        }
        return null;
    }

舉個(gè)例子:

class MyTest implements Comparable<MyTest> {}

會(huì)返回 MyTest.class

class MyTest implements Comparable<Integer> {}

會(huì)返回 null

這個(gè)方法就結(jié)束了，如果還是不能理解，可以將代碼復(fù)制出來(lái)，打個(gè)斷點(diǎn)跑一下。繼續(xù)往下看。

    @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

這個(gè)方法有意思，注釋是說(shuō)，如果 x 是 kc 的類型，返回 k.compareTo(x) （k 是篩選過(guò)的比較類）。如果你查找下這個(gè)方法的使用地方就會(huì)發(fā)現(xiàn)，kc 這個(gè)參數(shù)就是上面 comparableClassFor 返回的類型。

這么一看是不是就清晰了？ comparableClassFor(x) 拿到類型，然后傳入 compareComparables(kc,k,x) 去比較。

3. tableSizeFor()

下面又是一個(gè)方法：

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

這個(gè)方法也很有意思，看著很復(fù)雜，其實(shí)功能很簡(jiǎn)單，返回第一個(gè)大于等于 cap 的 2 的冪值。還是那句話， main 方法試試就知道了。不多說(shuō)。

4. table、threshold、loadFactor

再往下就是一些變量了。其中最核心的變量就是 table

    transient Node<K,V>[] table;

通過(guò)注釋我們就可以知道這個(gè)是存儲(chǔ) HashMap 元素的數(shù)組，在第一次使用時(shí)被初始化，并且根據(jù)需要調(diào)整大小，長(zhǎng)度適中是 2 的冪。

table 數(shù)組就是存儲(chǔ) HashMap 元素的底層結(jié)構(gòu)，具體怎么存儲(chǔ)我們后面再看。不過(guò)需要注意的是這個(gè)變量使用了一個(gè) transient 修飾符，這在我們平常的編碼中是很少見(jiàn)到的。這個(gè)修飾符的作用是在序列化時(shí)跳過(guò)該屬性。是跟 Serializable 相對(duì)應(yīng)的。其實(shí)就是當(dāng)一個(gè) HashMap 對(duì)象被序列化到文件中時(shí)，其中的元素是沒(méi)有寫到文件里的。所以通過(guò)反序列化也是拿不到元素的。

我們知道了它的功能，但是 HashMap 為什么要這么做呢？其實(shí)這個(gè)是跟 HashMap 的 put 方法有關(guān)系，我們稍后再說(shuō)。繼續(xù)往下看。

下面還有一些其他的屬性，其中有兩個(gè)比較重要。

    int threshold;

    final float loadFactor;

threshold 是下次擴(kuò)容時(shí) HashMap 的容量。 loadFactor 是加載因子，當(dāng) HashMap 的容量達(dá)到總?cè)萘康囊欢ū壤蜁?huì)觸發(fā)擴(kuò)容。這兩個(gè)字段都跟擴(kuò)容有關(guān)，等看到擴(kuò)容時(shí)再說(shuō)。

再往下就是幾個(gè)構(gòu)造方法了，前面三個(gè)構(gòu)造方法都只是在確定 threshold、loadFactor 這兩個(gè)屬性的默認(rèn)值。沒(méi)有什么好說(shuō)的

threshold 如果初始化時(shí)沒(méi)有傳值就是 0 ，loadFactor 默認(rèn)值是 DEFAULT_LOAD_FACTOR = 0.75f。也就是說(shuō)，如果 HashMap 的當(dāng)前容量達(dá)到總?cè)萘康?75% 就會(huì)觸發(fā)擴(kuò)容。

5. putMapEntries()

后面還有一個(gè)構(gòu)造方法是傳入了一個(gè) Map 集合，它會(huì)把入?yún)⒅屑侠锏脑?put 到當(dāng)前的 HashMap 集合中。

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

這個(gè)構(gòu)造方法首先初始化了 loadFactor 屬性，然后調(diào)了putMapEntries 方法，這個(gè)方法就在下面。同樣格式有點(diǎn)亂，沒(méi)關(guān)系，我們先調(diào)整下格式。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s <= 0){
            return;
        }
        if (table == null) {
            float ft = ((float)s / loadFactor) + 1.0F;
            int t;
            if (ft < (float)MAXIMUM_CAPACITY){
                t = (int)ft;
            }else {
                t = MAXIMUM_CAPACITY
            }
            if (t > threshold){
                threshold = tableSizeFor(t);
            }

        }
        else if (s > threshold){
            resize();
        }


        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }

如果 map 里沒(méi)有元素，直接結(jié)束。因?yàn)槲覀兪菢?gòu)造方法進(jìn)入到這個(gè)方法里的，所以 table 一定為 null，然后計(jì)算了一下 ft ，表示放入 m 個(gè)元素后，HashMap 的最大容量，（如果 s = 75,那 ft = 101）。

然后計(jì)算了一下 t 就是 map 需要的最大容量。并且判斷一下是否超限。然后判斷了一下是否要更新 threshold ，因?yàn)槲覀兪菢?gòu)造方法進(jìn)來(lái)的，所以一定是需要更新的。更新結(jié)束后就是 for 循環(huán)依次調(diào)用 putVal 將元素放入到當(dāng)前的 HashMap 里。

6. putVal()

然后我們跳到 putVal 方法。這個(gè)方法的格式依然不太好閱讀，我們需要修改下。

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> p;
        int n, i;

        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 {
            HashMap.Node<K, V> e;
            K k;
            if (p.hash == hash) {
                k = p.key;
                if (k == key || key != null && key.equals(k)) {
                    e = p;
                }
            } else {
                if (p instanceof HashMap.TreeNode) {
                    e = ((HashMap.TreeNode<K, V>) 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) {
                                treeifyBin(tab, hash);
                            }
                            break;
                        }
                        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                            break;

                        p = e;
                    }
                }
            }

            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

首先判斷了 table 是否進(jìn)行了初始化，沒(méi)有的話進(jìn)行 resize，這個(gè)方法我們一會(huì)再看。它的作用就是返回一個(gè) Node 數(shù)組，數(shù)組的長(zhǎng)度就是 threshold。初始化好之后就是判斷下這個(gè)數(shù)組的(n - 1) & hash 位置是否有值，沒(méi)有值的話直接創(chuàng)建一個(gè) Node 存到數(shù)組里就結(jié)束了。其實(shí) (n - 1) & hash 相當(dāng)于 hash % (n-1) 的作用，但是與操作的效率比取模的效率高。二者達(dá)到的效果是一樣的。

如果有值，并且 key 相等，說(shuō)明是同一個(gè)元素，這個(gè)時(shí)候 e 就是 HashMap 里的元素，后面對(duì) e 的判斷就會(huì)直接返回 e 對(duì)應(yīng)的 value。

如果 key 不相等，說(shuō)明發(fā)生了 hash 沖突。兩個(gè) hash 值不一樣的元素應(yīng)該存儲(chǔ)到數(shù)組的同一個(gè)位置。這個(gè)時(shí)候判斷了一下 Node 的類型。如果是 TreeNode 那么調(diào)用 putTreeVal 方法。

如果不是，則依次遍歷當(dāng)前位置節(jié)點(diǎn)的 next 指針，直到為空，插入新節(jié)點(diǎn)。其實(shí)就是講新節(jié)點(diǎn)掛到了已當(dāng)前節(jié)點(diǎn)為表頭的鏈表尾部。插入成功之后判斷了一下鏈表的長(zhǎng)度，如果需要?jiǎng)t進(jìn)行樹(shù)化。將當(dāng)前鏈表轉(zhuǎn)成一個(gè)紅黑樹(shù)。這個(gè)主要是解決鏈表太長(zhǎng)，查詢效率低的問(wèn)題。而且在遍歷鏈表期間依然判斷了 key 是否相等，相等則直接返回舊元素的 value。

好像也不是很難，這個(gè)就是 HashMap 最核心的方法之一了。從這個(gè)方法中也可以知道，HashMap 的底層存儲(chǔ)結(jié)構(gòu)是一個(gè)數(shù)組。如果發(fā)生 hash 沖突后，會(huì)采用鏈表的方式存儲(chǔ)，當(dāng)鏈表長(zhǎng)度過(guò)長(zhǎng)時(shí)，會(huì)將鏈表轉(zhuǎn)成紅黑樹(shù)結(jié)構(gòu)，提高查詢效率。

7. resize()

下面我們看一下resize() 方法

final HashMap.Node<K, V>[] resize() {
    HashMap.Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    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"})
    HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            HashMap.Node<K, V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof HashMap.TreeNode)
                    ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                else { // preserve order
                    HashMap.Node<K, V> loHead = null, loTail = null;
                    HashMap.Node<K, V> hiHead = null, hiTail = null;
                    HashMap.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;
}

resize() 方法的主要作用就是當(dāng) table 數(shù)組中的元素超過(guò)一定的數(shù)量后，對(duì) table 數(shù)組進(jìn)行擴(kuò)容，以便減少 hash 碰撞發(fā)生的概率。最前面一大串的 if 、else 判斷主要是為了確定兩個(gè)變量的值 newCap 和 newThr 。newCap 是指擴(kuò)容后新的 table 數(shù)組的長(zhǎng)度。newThr 是指新數(shù)組的元素超過(guò)多少時(shí)需要擴(kuò)容。

計(jì)算的方式分幾種場(chǎng)景。第一種 oldCap > 0: 這種是正常擴(kuò)容，oldTable 已經(jīng)有元素了，而且元素的數(shù)量也達(dá)到了擴(kuò)容的數(shù)量。這時(shí) newCap 和 newThr 是原來(lái)數(shù)值的 2 倍（<< 是右移操作）而且判斷了下是否超過(guò)了最大值。如果 oldCap 已經(jīng)大于等于最大值了，那直接把下次擴(kuò)容的閾值調(diào)整到最大就結(jié)束了，因?yàn)?table 數(shù)組已經(jīng)無(wú)法擴(kuò)容了。

(newCap = oldCap << 1) < MAXIMUM_CAPACITY 這一行代碼很有意思它的執(zhí)行邏輯是，先將 oldCap 右移一位后的數(shù)值賦值給 newCap，然后判斷 newCap 是否超過(guò)了 MAXIMUM_CAPACITY 。有意思的點(diǎn)在于，它沒(méi)有關(guān)注 newCap 的溢出情況?。∵@個(gè)其實(shí)也是 HashMap 的的容量永遠(yuǎn)都是 2 的整數(shù)次冪的原因。因?yàn)椋岩粋€(gè)2 的整數(shù)次冪的數(shù)值右移一位后，依然是一個(gè)2 的整數(shù)次冪，而 MAXIMUM_CAPACITY 就是允許的最大的 2的整數(shù)次冪。因?yàn)橹耙呀?jīng)判斷過(guò)是否等于 MAXIMUM_CAPACITY 了。所以，oldCap 右移后，最大只能是等于 MAXIMUM_CAPACITY ，不會(huì)溢出。而且，當(dāng) newCap 等于 MAXIMUM_CAPACITY 是沒(méi)有對(duì) newThr 賦值的，對(duì) newThr 賦值的邏輯是在下面的 if (newThr == 0) 的地方。

第二個(gè)場(chǎng)景 else if (oldThr > 0) 執(zhí)行到這個(gè) if 里的情況是，初始化的時(shí)候傳了 initialCapacity 這個(gè)參數(shù)。還記得之前初始化時(shí) threshold 的賦值邏輯么？

this.threshold = tableSizeFor(initialCapacity)

當(dāng)初始時(shí)傳了 initialCapacity 參數(shù)，在第一次 put 操作時(shí)，就會(huì)觸發(fā)首次擴(kuò)容（或者說(shuō)初始化 table 數(shù)組）。

這里有個(gè)小知識(shí)點(diǎn)：我們?cè)谄綍r(shí)寫代碼使用到 HashMap 時(shí)，為了提高效率，不讓 HashMap 觸發(fā)擴(kuò)容，都會(huì)指定 HashMap 的容量，比如：

Map<String, String> map = new HashMap<>(40);

這個(gè)時(shí)候我們往 Map 里放 5 個(gè)元素，應(yīng)該是只擴(kuò)容一次即初始化 table 那次。好像沒(méi)有什么問(wèn)題。這時(shí)因?yàn)樵诘谝淮纬跏蓟瘯r(shí) tableSizeFor 這個(gè)參數(shù)返回的是大于等于 initialCapacity 的最小的 2 的整數(shù)冪的值。比如你傳 50，初始化的結(jié)果是 64 。而默認(rèn)的 loadFactor 是 0.75，也就是在元素達(dá)到 48 時(shí)才會(huì)觸發(fā)擴(kuò)容。

但是，如果你給的值是 48 以上的呢? 或者說(shuō)恰好是 64 的時(shí)候。這個(gè)時(shí)候就會(huì)在插入第 49 個(gè)元素時(shí)再次觸發(fā)一次擴(kuò)容。所以，如果你明確的知道元素的容量的話，可以初始化 2 倍元素容量的 HashMap ，這樣就不會(huì)觸發(fā)兩次擴(kuò)容了。

繼續(xù)往下說(shuō)，計(jì)算好 newCap 和 newThr 的值后，就創(chuàng)建了一個(gè) newTab，然后就是遍歷 oldTab 不斷的將元素轉(zhuǎn)移到 newTab 里去。

首先將 oldTab 的引用置為 null，避免內(nèi)存泄露。然后當(dāng)前元素會(huì)有三種情況：第一種 e.next == null 就是當(dāng)前位置只有這一個(gè)元素，沒(méi)有發(fā)生 hash 沖突。這種最簡(jiǎn)單，直接放到 newTab 里就可以了。第二種 e instanceof TreeNode，就是發(fā)生了 hash 沖突，且已經(jīng)把鏈表轉(zhuǎn)成了紅黑樹(shù)的結(jié)構(gòu)了（還記的 putVal 方法么？）。這種就需要按照紅黑樹(shù)的操作，把 e 這個(gè)節(jié)點(diǎn)從 oldTab 上摘下來(lái)，掛到 newTab 上去（有點(diǎn)復(fù)雜，已經(jīng)超過(guò)了本文的內(nèi)容。需要了解的可以搜一下紅黑樹(shù)）。第三種，就是發(fā)生了 hash 沖突，但是存儲(chǔ)結(jié)構(gòu)還是鏈表的情況。這種情況如果按照正常的思路的話，無(wú)非就是遍歷鏈表，依次將鏈表的元素放入到 newTab 就好了。但是這樣就會(huì)有一個(gè)問(wèn)題，就是鏈表上的元素依然有可能出現(xiàn) hash 沖突，如果在遍歷鏈表期間多個(gè)元素發(fā)生了 hash 沖突怎么辦呢？

很顯然，從代碼上來(lái)看，并沒(méi)有按照我們的思路來(lái)。代碼邏輯是根據(jù)元素的 hash 值將一個(gè)鏈表分成了兩個(gè)鏈表。loHead 和 hiHead。等拆分完成后，直接將鏈表的表頭保存到了 newTab 的兩個(gè)元素里。是不是很神奇？？就好像是在說(shuō)，擴(kuò)容前發(fā)生了 hash 沖突的元素，那么擴(kuò)容后也有可能發(fā)生 hash 沖突，并且這些元素一定應(yīng)該放到 newTab[j] 或者是 newTab[j+oldCap] 這兩個(gè)位置。事實(shí)就是這樣?。?/p>

其實(shí)，你可以寫代驗(yàn)證下，擴(kuò)容前發(fā)生 hash 沖突的元素，如果 (e.hash & oldCap) == 0 那么它一定會(huì)落在 newTab[j]上，否則一定落在 newTab[j+oldCap] 上。數(shù)學(xué)就是這么完美~~

好了，resize()方法到這里就結(jié)束了。我們回到 putMapEntries() 方法這里繼續(xù)往下看。

再往下，szie() 和 isEmpty() 都沒(méi)有什么好說(shuō)的，下面是 get(Object key) 方法，這個(gè)是 HashMap 最常用的方法之一。

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

好像也沒(méi)有特別復(fù)雜，計(jì)算 key 的 hash 值，然后通過(guò) getNode 方法獲取 node 對(duì)象，找不到就返回 null，找到了就返回對(duì)應(yīng)的 value。getNode()方法就在下面。

8. getNode()

如果你對(duì) putVal() 方法已經(jīng)非常熟悉了，其實(shí) getNode() 就非常清晰了。首先判斷了 table 是否為空，不為空的話就通過(guò) hash 找對(duì)應(yīng)位置的元，如果對(duì)應(yīng)的位置有值，就判斷 key 是否相等。相等直接返回。

如果不相等，則判斷當(dāng)前位置是否有其他元素，如果是 TreeNode 則從紅黑樹(shù)里找，如果是鏈表則遍歷鏈表找。

這里需要注意下，還記得之前我們說(shuō)過(guò) table 這個(gè)變量加了 transient 修飾符么，就是為了不讓 table 元素進(jìn)行序列化。其實(shí)是跟hash(key) 這個(gè)方法有關(guān)系。你可以翻看下hash() 這個(gè)方法，里面有這樣一段 h = key.hashCode()。這里的 hashCode() 你找到它的定義會(huì)發(fā)現(xiàn)是下面這樣的,

 public native int hashCode();

這是一個(gè)本地方法。這個(gè)方法在不同的 JVM 上可能會(huì)有不同的實(shí)現(xiàn)，所以，就有可能出現(xiàn)，序列化前和序列化后的對(duì)象 hashCode() 方法返回的值不同。但是在序列化后，HashMap 保存在 table 中的位置沒(méi)有變，就會(huì)出現(xiàn)找不到的情況，這就是 HashMap 中的一些元素不能序列化的原因。

繼續(xù)往下就沒(méi)有什么好說(shuō)的了，剩下的除了像 clear()、remove() 這種比較簡(jiǎn)單的方法外，就剩一個(gè)最復(fù)雜的treeify和untreeify。這個(gè)是 HashMap 里最復(fù)雜的部分，都是 TreeNode 里的方法，已經(jīng)超出了本文的內(nèi)容。

以上就是Java 源碼重讀系列之 HashMap的詳細(xì)內(nèi)容，更多關(guān)于Java HashMap源碼重讀的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: