摘要：的值是在上述方法中處理過(guò)的值，通過(guò)與當(dāng)前容量進(jìn)行，直接獲取到哈希表的位置。策略二，如果已經(jīng)很大了，擴(kuò)容已經(jīng)不可取，那么就采用紅黑樹(shù)結(jié)構(gòu)轉(zhuǎn)化鏈表。紅黑樹(shù)的創(chuàng)建不再詳述。紅黑樹(shù)的根就是中第一個(gè)節(jié)點(diǎn)。

java.util.Map

需要小心用易變的對(duì)象作為Map的key，這會(huì)導(dǎo)致Map的行為無(wú)法預(yù)測(cè)。Map也不可以將自己作為key，可以作為value，但是會(huì)導(dǎo)致equals和hashCode方法不是well defined.

Map中有些操作涉及遞歸的遍歷，如果Map自我引用，則有可能出現(xiàn)異常。這些方法包括：clone，equals，hashCode和toString。

這是Map接口自己默認(rèn)實(shí)現(xiàn)的一個(gè)獲取指定key的value，當(dāng)沒(méi)有該key時(shí)可以獲取一個(gè)默認(rèn)值得方法。這就給用戶提供了更靈活的選擇來(lái)處理map中沒(méi)有存這個(gè)key的情況。這里比較有意思的一點(diǎn)是在用v = get(key)判斷一次后，為什么又用containsKey(key)再判斷一次，因?yàn)橛械膍ap中是允許存null作為value的，所以有key在Map中，但是value為null的情況。

    default V getOrDefault(Object key, V defaultValue) {
        V v;
        return (((v = get(key)) != null) || containsKey(key))
            ? v
            : defaultValue;
    }

HashMap中，用戶可以初始化容量，但是HashMap中容量皆為2的次冪，所以會(huì)把用戶預(yù)設(shè)的值先轉(zhuǎn)為最近的2的次冪。tableSizeFor方法求出的結(jié)果總是大于或等于cap，且最接近c(diǎn)ap的一個(gè)2的次冪。當(dāng)然，對(duì)于大于2^30的數(shù)，會(huì)返回-2147483648，所以這里會(huì)判斷n為負(fù)數(shù)的情況，同時(shí)，設(shè)置了HashMap的最大容量應(yīng)該為2^30（MAXIMUM_CAPACITY）。

有意思的是經(jīng)過(guò)如下幾步就能求得一個(gè)2的次冪，下面方法所做的是先求得一個(gè)2^n-1，然后+1。獲得一個(gè)2^n-1的過(guò)程也很巧妙，就是不停的拷貝1。n |= n >>> x;將前x位的1拷貝到了接著的x位。通過(guò)幾步位操作就獲得了目標(biāo)值，不得不贊嘆開(kāi)發(fā)者的聰明。

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

HashMap的table就是一個(gè)Node的數(shù)組，大小一致保持2的次冪。Node就是HashMap中存儲(chǔ)的元素，它有哈希值、key、value和存儲(chǔ)下一個(gè)Node的next屬性。處理沖突的方法是閉哈希方法，也就是有相同的hash值的Node會(huì)用鏈表串起來(lái)。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

將key的hashCode的高位和低位部分通過(guò)異或合并，使得低位和高位的值都能在hash時(shí)發(fā)揮作用。因?yàn)楣１頃?huì)用一個(gè)掩碼來(lái)取hashCode的后面一段，如不采用上述方法，前面一部分的hashCode就被忽略了。如果一組key恰巧只在前段的hash值有所差異，而后段都是相同的，則會(huì)出現(xiàn)大量的沖突，這種情況在實(shí)際中是很可能存在的。

公式如：table[node.hash & (capacity - 1)] = node。node的hash值是key在上述hash()方法中處理過(guò)的值，通過(guò)與當(dāng)前容量-1進(jìn)行mask，直接獲取到哈希表的位置。

如上所述，table大小保持2的次冪，擴(kuò)張的步驟：

申請(qǐng)一個(gè)容量乘以2的新Node數(shù)組。

遍歷table，將原來(lái)的元素依次copy到新數(shù)組上，這里原來(lái)的鏈表會(huì)進(jìn)行分裂。因?yàn)閠able的擴(kuò)大，Node的hash值會(huì)被多mask一位，所以Node被Hash到的位置也會(huì)變化，Node要么保持原位置，要么就是在相對(duì)于原位置有一個(gè)舊容量大小的偏移。

這里不會(huì)將原來(lái)的元素重新進(jìn)行一次hash的過(guò)程，重建原來(lái)的hash table，這樣代價(jià)是比較大的。這里就利用了Node位置變化的規(guī)律，直接將原來(lái)的鏈表分裂為兩個(gè)。

雖然已經(jīng)進(jìn)行了優(yōu)化，但是該過(guò)程代價(jià)還是比較高的，時(shí)間復(fù)雜度為原table大小+元素?cái)?shù)量，

當(dāng)Node發(fā)生多次沖突，在一個(gè)hash值下建了一個(gè)很長(zhǎng)的鏈表，這會(huì)導(dǎo)致查詢的代價(jià)越來(lái)越大，這里采用了樹(shù)結(jié)構(gòu)來(lái)減輕這種問(wèn)題。

具體過(guò)程是，當(dāng)某個(gè)hash值下的鏈表超過(guò)了閾值，則會(huì)采取策略對(duì)其長(zhǎng)度進(jìn)行消解。

如果table還不算大，那么直接對(duì)table擴(kuò)容，鏈表自然會(huì)被分裂到兩地。

策略二，如果table已經(jīng)很大了，擴(kuò)容table已經(jīng)不可取，那么就采用紅黑樹(shù)結(jié)構(gòu)轉(zhuǎn)化鏈表。

紅黑樹(shù)的創(chuàng)建不再詳述。需要知道，這里采用的是二叉搜索樹(shù)，進(jìn)行比較的是每個(gè)hash值，不是key的直接比較。紅黑樹(shù)的根就是table中第一個(gè)節(jié)點(diǎn)。原始鏈表會(huì)先變成雙向鏈表，以保存前后關(guān)系，然后再變成樹(shù)結(jié)構(gòu)。雖然由鏈表轉(zhuǎn)化成了樹(shù)結(jié)構(gòu)，但是每個(gè)節(jié)點(diǎn)仍然保存了鏈表的前后關(guān)系，所以可以迅速的從樹(shù)結(jié)構(gòu)退化為鏈表結(jié)構(gòu)。從TreeNode的屬性中可以看出其既有樹(shù)結(jié)構(gòu)的left、right、parent關(guān)系，又有prev、next（繼承）的雙向鏈表關(guān)系。

        TreeNode parent;  // red-black tree links
        TreeNode left;
        TreeNode right;
        TreeNode prev;    // needed to unlink next upon deletion

HashMap用KeySet來(lái)提供一個(gè)key的集合視角，KeySet并沒(méi)有再申請(qǐng)一個(gè)空間來(lái)存儲(chǔ)這些key，而是將所有的方法建立于HashMap的方法之上。KeySet提供了刪除key的操作，該操作會(huì)映射到其HashMap之上，最后就是在HashMap中刪除了該元素。KeySet沒(méi)有提供添加元素的方法，因?yàn)镠ashMap需要的是key和value，而KeySet只能添加key，方法不能映射到HashMap上。

同樣，HashMap提供了value的集合視角Values，EntrySet提供了Node集合的視角，原理類似。

在HashMap中，分為key、value和node三種Spliterator，實(shí)現(xiàn)原理都是類似的。HashMap的Spliterator的劃分不是針對(duì)元素的直接劃分，而是對(duì)table這個(gè)數(shù)組的劃分，這樣更為簡(jiǎn)單。劃分的策略也很簡(jiǎn)單，采用的二分法。