HashMap是一個(gè)常用的集合，日常使用可能我們并不關(guān)心它是如何實(shí)現(xiàn)的，不過(guò)它是面試中的?？?。所以為了弄懂它，不妨看一看源碼，同時(shí)也可以學(xué)習(xí)一下大牛的編程思想。

歡迎大家關(guān)注我的公眾號(hào) javawebkf，目前正在慢慢地將簡(jiǎn)書(shū)文章搬到公眾號(hào)，以后簡(jiǎn)書(shū)和公眾號(hào)文章將同步更新，且簡(jiǎn)書(shū)上的付費(fèi)文章在公眾號(hào)上將免費(fèi)。

一、HashMap的宏觀實(shí)現(xiàn)

1、HashMap數(shù)據(jù)結(jié)構(gòu):
HashMap采用數(shù)組 + 鏈表的方式來(lái)實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)。為什么使用這種方式呢？鏈表什么時(shí)候產(chǎn)生呢？

首先HashMap主要還是用數(shù)組來(lái)存儲(chǔ)元素的。它通過(guò)key的hash來(lái)計(jì)算元素應(yīng)該放在數(shù)組中的哪個(gè)位置。如果有兩個(gè)key的hash都一樣，該怎么處理呢？這時(shí)候會(huì)去判斷這兩個(gè)key是否相等，如果相等，那就直接用新的value覆蓋舊的value；如果這兩個(gè)key不相等，那么就連接在第一個(gè)key的后面，用頭插法形成鏈表(JDK1.8開(kāi)始用尾插法)。由此鏈表就誕生了。

JDK1.8開(kāi)始，又對(duì)HashMap進(jìn)行了優(yōu)化。我們知道鏈表讀取數(shù)據(jù)不方便，所以為了避免鏈表太長(zhǎng)，又加入了紅黑樹(shù)結(jié)構(gòu)。當(dāng)鏈表長(zhǎng)度達(dá)到閾值時(shí)，就會(huì)將鏈表轉(zhuǎn)成紅黑樹(shù)。

所以宏觀的來(lái)說(shuō)，JDK1.8開(kāi)始，HashMap是由(數(shù)組 + 鏈表 + 紅黑樹(shù))實(shí)現(xiàn)的。首先是用hash去判斷元素應(yīng)該放到數(shù)組中的哪個(gè)位置，如果該位置已有元素，就判斷這兩個(gè)元素的key是否相同，相同就覆蓋，不同就生成鏈表，接在后面。當(dāng)鏈表達(dá)到一定長(zhǎng)度時(shí)，就轉(zhuǎn)成紅黑樹(shù)。同時(shí)數(shù)組的元素個(gè)數(shù)達(dá)到一定值時(shí)，就會(huì)進(jìn)行擴(kuò)容。擴(kuò)容之后再將數(shù)據(jù)轉(zhuǎn)移到新的數(shù)組。

二、HashMap實(shí)現(xiàn)細(xì)節(jié)

1、用什么存儲(chǔ)元素？
根據(jù)上面的宏觀描述，可以知道，我們需要一個(gè)Node類，里面有四個(gè)屬性，分別是 key、value、hash、next。其中next是Node類型，表示下一個(gè)節(jié)點(diǎn)，用于生成鏈表。同時(shí)需要一個(gè)Node[ ] 數(shù)組，用來(lái)存儲(chǔ)每個(gè)節(jié)點(diǎn)。如下代碼所示：

// 這是源碼中的節(jié)點(diǎn)內(nèi)部類。
 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
}
// 源碼中的節(jié)點(diǎn)數(shù)組
 transient Node<K,V>[] table;

2、數(shù)組如何初始化？
從上面我們可以看到，這個(gè)數(shù)組并沒(méi)有初始化，那么當(dāng)我們put元素的時(shí)候，這個(gè)數(shù)組是如何初始化的呢？
通過(guò)源碼可以發(fā)現(xiàn)，put方法里面調(diào)用了一個(gè)putVal方法，在putVal方法中，首先判斷數(shù)組長(zhǎng)度是不是沒(méi)有初始化，如果是，就調(diào)用resize方法進(jìn)行初始化。

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        ...
}

接下來(lái)看看resize方法是怎么初始化數(shù)組的。

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

這個(gè)是數(shù)組初始化默認(rèn)的大小。

 ...
 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 table = newTab;
 ...
 return newTab;

在這個(gè)方法中，其他的先不用看，就看這幾行代碼，其中newCap的值就是與上面數(shù)組默認(rèn)初始化大小值一樣，也就是16。也就是說(shuō)，使用HashMap的時(shí)候，首先會(huì)初始化一個(gè)長(zhǎng)度為16的數(shù)組，用來(lái)存儲(chǔ)元素。

3、如何將元素放入數(shù)組？
初始化了一個(gè)長(zhǎng)度為16的數(shù)組，那么索引就是 0 ~ 15，當(dāng)put元素的時(shí)候，如何知曉元素是放入哪個(gè)位置呢？Node內(nèi)部類的hash屬性就起作用了。首先來(lái)看看這個(gè)hash屬性是怎么來(lái)的。

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

在HasnMap中有一個(gè)hash方法，該方法返回key的hashCode值的高16與低16位進(jìn)行異或運(yùn)算(科普一下：異或運(yùn)算，將運(yùn)算數(shù)轉(zhuǎn)成二進(jìn)制，1^1=0，1^0=1，0^0=0 ，0^1=1，也就是說(shuō)，相等為0，不等為1；與運(yùn)算，將運(yùn)算數(shù)轉(zhuǎn)成二進(jìn)制，1&1=1，1&0=0，0&1=0，0&0=0；或運(yùn)算，將運(yùn)算數(shù)轉(zhuǎn)成二進(jìn)制，1|1=1，1|0=1，0|1=1，0|0=0)，該值就是hash。為什么要這樣計(jì)算hash的值，而不直接使用hashCode方法計(jì)算的值？hashCode方法返回值是一個(gè)32位的二進(jìn)制數(shù)，等下在計(jì)算元素索引的時(shí)候，這32位并沒(méi)有都參與運(yùn)算，這樣的話，兩個(gè)key計(jì)算出來(lái)的索引一致的概率就更大，所以要讓這32位充分利用起來(lái)，都參與計(jì)算，所以先用hashCode值的高16位與低16位進(jìn)行異或運(yùn)算。那么為什么是異或，而不是其他運(yùn)算呢？從上面括號(hào)內(nèi)的說(shuō)明可以知道，只有異或運(yùn)算，得到1和0的概率都是0.5。為了不影響計(jì)算結(jié)果，所以選擇了異或。

有了hash后，如何計(jì)算出索引？

...
 if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

...
}

在putVal方法中，有這樣一段代碼。索引 i 就是 hash 和 n ( n是數(shù)組長(zhǎng)度 - 1) 進(jìn)行與運(yùn)算得來(lái)的。為什么這樣算呢？上面說(shuō)了，數(shù)組默認(rèn)初始化長(zhǎng)度為16，二進(jìn)制就是 10000，減一后結(jié)果就是 01111。再用 hash 和 01111 進(jìn)行與運(yùn)算，其結(jié)果一定是在 0 到 01111 這個(gè)范圍的，也就是 0 到 15 之間。而數(shù)組索引也是 0 到 15，這樣便達(dá)到了目的。計(jì)算出來(lái)的結(jié)果是 n，那就放入數(shù)組索引為 n 的位置。

問(wèn)題來(lái)了，因?yàn)閿?shù)組默認(rèn)初始化長(zhǎng)度是16，是2的n次冪。(length - 1) 就是奇數(shù)，最后一位是1。這樣就保證了 hash & (length - 1) 的計(jì)算結(jié)果可能為奇數(shù)也可能為偶數(shù)，保證了散列的均勻性。

4、如果我們給的初始化大小不是2的n次冪怎么辦？
HashMap還有個(gè)構(gòu)造方法，我們可以自己傳入一個(gè)數(shù)組初始化容量。如下：

HashMap<Integer,String> map = new HashMap<>(20);

根據(jù)上面的分析，我們知道數(shù)組的大小一定得是2的n次冪，才能保證散列均勻分布。如果我傳入不是2的n次冪，比如是20，那么如何處理？

通過(guò)源碼我們可以發(fā)現(xiàn)如下的一個(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è)方法的作用就是，如果用戶傳入的不是2的n次冪，那么就會(huì)return一個(gè)大于和用戶傳入的數(shù)最接近的2的n次冪的數(shù)。比如傳入20，那么實(shí)際上數(shù)組的大小將會(huì)是32。

5、數(shù)組何時(shí)進(jìn)行擴(kuò)容？如何擴(kuò)容？
resize方法不僅是用來(lái)初始化的，也是用來(lái)擴(kuò)容的。那么什么時(shí)候進(jìn)行擴(kuò)容？是數(shù)組中的元素滿了才擴(kuò)容的嗎？當(dāng)然不是。

 static final float DEFAULT_LOAD_FACTOR = 0.75f;

在源碼中有這么一個(gè)常量，暫且稱作擴(kuò)容因子。當(dāng)數(shù)組中元素個(gè)數(shù)達(dá)到了數(shù)組長(zhǎng)度的四分之三的時(shí)候，就會(huì)進(jìn)行擴(kuò)容。上面也說(shuō)了，數(shù)組長(zhǎng)度必須是2的n次冪，所以擴(kuò)容就會(huì)擴(kuò)成兩倍。原來(lái)長(zhǎng)度為16，當(dāng)數(shù)組中有12個(gè)元素了，就會(huì)進(jìn)行擴(kuò)容，擴(kuò)成32。那么舊數(shù)組的數(shù)據(jù)如何移動(dòng)到新數(shù)組呢？有三種情況：

如果是單個(gè)元素，那就用 hash & (newLength - 1 )；
如果是鏈表，那么就用看 hash & oldLength 的計(jì)算結(jié)果是否為0(oldLength表示舊數(shù)組的容量)，如果為0，放在原位置，如果不為0，放在 (原來(lái)的index + 舊數(shù)組容量) 的位置。
如果是紅黑樹(shù)，那么將樹(shù)打散，根據(jù) hash & (newLength - 1 ) 重新分配位置。

所以總結(jié)起來(lái)就是，要么在原來(lái)的位置，要么在原來(lái)索引加上原數(shù)組容量的位置。

6、什么時(shí)候會(huì)生成鏈表？
上面說(shuō)了HashMap通過(guò)計(jì)算 hash & (數(shù)組長(zhǎng)度 - 1 ) 的值來(lái)確定元素放入數(shù)組中哪個(gè)位置。當(dāng)兩個(gè)元素計(jì)算出來(lái)的值一樣時(shí)，如何處理？那么就會(huì)繼續(xù)通過(guò)equals方法方法判斷這兩個(gè)元素的key是否一樣，如果一樣，那么新的value就會(huì)覆蓋舊的value；如果不一樣，就會(huì)生成鏈表。在jdk 1.7的時(shí)候，用頭插法生成鏈表，jdk1.8開(kāi)始，用尾插法生成鏈表。

7、為什么要有紅黑樹(shù)？什么時(shí)候生成紅黑樹(shù)？
上面說(shuō)了什么時(shí)候生成鏈表，我們知道鏈表讀取數(shù)據(jù)很慢，如果鏈表太長(zhǎng)，會(huì)導(dǎo)致讀取性能不好。所以就出現(xiàn)了紅黑樹(shù)。在源碼中，有如下常量：

 static final int TREEIFY_THRESHOLD = 8;

也就是說(shuō)，當(dāng)鏈表的長(zhǎng)度達(dá)到了8，就會(huì)將鏈表轉(zhuǎn)成紅黑樹(shù)，以提高讀取效率。還有一個(gè)常量：

static final int UNTREEIFY_THRESHOLD = 6;

也就是說(shuō)，當(dāng)樹(shù)中元素個(gè)數(shù)少于6個(gè)時(shí)，那就將樹(shù)變回鏈表。

紅黑樹(shù)的平均查找長(zhǎng)度為log(n)，鏈表的平均查找長(zhǎng)度為 n/2。當(dāng)元素個(gè)數(shù)為8時(shí)，使用鏈表平均查找長(zhǎng)度為4，而使用紅黑樹(shù)的話平均查找長(zhǎng)度為3，所以有必要轉(zhuǎn)成紅黑樹(shù)。當(dāng)元素個(gè)數(shù)小于等于6時(shí)，用鏈表平均查找長(zhǎng)度是3，速度已經(jīng)很快了，所以沒(méi)必要轉(zhuǎn)紅黑樹(shù)。

小結(jié)：往HashMap中put元素主要分為以下幾個(gè)步驟：

1. hash(key)，計(jì)算key的hash，用key的hashCode值的高16位和低16位進(jìn)行異或運(yùn)算；
1. 調(diào)用resize方法初始化數(shù)組，默認(rèn)初始化大小為 16 ，如果自定義的初始化大小x不是2的n次冪，就會(huì)轉(zhuǎn)成比x大的最接近x的2的n次冪；
1. hash和數(shù)組長(zhǎng)度減一的值進(jìn)行與運(yùn)算，判斷元素在數(shù)組中的存儲(chǔ)位置，如果這個(gè)位置沒(méi)有其他key，直接存入該位置，如果有其他的key，那么又有三種情況：
  --- ：如果key相等，直接替換
  --- ：如果key不等，生成鏈表
  --- ：如果鏈表長(zhǎng)度達(dá)到 8 了，那就轉(zhuǎn)成紅黑樹(shù)
1. 當(dāng)數(shù)組中元素個(gè)數(shù)達(dá)到容量的 0.75 時(shí)，調(diào)用resize方法將容量擴(kuò)為當(dāng)前的兩倍。
1. 擴(kuò)容后數(shù)據(jù)的轉(zhuǎn)移有兩種情況：
  --- ：如果是單個(gè)元素或者是紅黑樹(shù)，根據(jù) hash ^ （newLength - 1）的方式存儲(chǔ)；
  ---：如果是鏈表，判斷 hash ^ oldLength 的值是否為0，如果是，放在原位置，不為0，放在 (原index + 舊數(shù)組容量) 的位置。

三、ConcurrentHashMap

1、為什么要有ConcurrentHashMap？
看了HashMap的源碼之后，可以發(fā)現(xiàn)HashMap并不是同步的。如果在多線程環(huán)境中同時(shí)對(duì)一個(gè)HashMap進(jìn)行讀寫(xiě)操作，肯定是會(huì)出問(wèn)題的。那么如何保證在多線程中的安全問(wèn)題呢？加鎖！沒(méi)錯(cuò)，最熟悉的就是 synchronized 了。只要在HashMap的每個(gè)方法中都加上 synchronized 關(guān)鍵字，就安全了。確實(shí)可以，HashTable就是這樣做的，所以它被淘汰了，因?yàn)檫@樣性能很低。接下來(lái)就該ConcurrentHashMap上場(chǎng)表演了。

2、ConcurrentHashMap如何保證線程安全？
說(shuō)這個(gè)問(wèn)題之前，先回到HashMap的小結(jié)中的5個(gè)過(guò)程，看看5個(gè)過(guò)程哪幾個(gè)過(guò)程在多線程環(huán)境中可能出現(xiàn)線程安全問(wèn)題。

1. hash(key)，這個(gè)過(guò)程不管多少個(gè)線程同時(shí)操作，計(jì)算出的hash都是一樣的，不會(huì)有線程安全問(wèn)題。所以ConcurrentHashMap中這個(gè)過(guò)程沒(méi)做處理。
1. 初始化數(shù)組，這個(gè)過(guò)程肯定會(huì)有問(wèn)題。比如一個(gè)線程要初始化容量為16，另一個(gè)線程要初始化容量為32，那么怎么辦？ConcurrentHashMap采用了CAS算法來(lái)保證線程的安全性。當(dāng)有線程初始化map了，其他線程就yield，禮讓一下。初始化數(shù)組的 initTable 方法如下：

private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

關(guān)于CAS算法的工作原理，它如何保證線程安全，以后再寫(xiě)個(gè)文章詳細(xì)說(shuō)明，此處不多說(shuō)。

3、存放元素，這個(gè)過(guò)程肯定也會(huì)有線程安全問(wèn)題。

 if (tab == null || (n = tab.length) == 0)
         tab = initTable();
 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
         if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
               break;                   // no lock when adding to empty bin
 }

先看這段代碼，首先判斷數(shù)組是否為空，為空，那么就調(diào)用initTable進(jìn)行初始化。如果不為空，并且要插入的位置沒(méi)有元素，就執(zhí)行casTabAt方法。下面來(lái)看一個(gè)這個(gè)方法：

 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
 }

這個(gè)方法也是使用了CAS算法，也就是說(shuō)，當(dāng)要插入的位置沒(méi)有其他key時(shí)，也是用CAS保證線程的安全性的。如果要插入的位置有key存在呢，看接下來(lái)的代碼：

 else {
       synchronized (f) {
       ......
       }
}

如果要插入的位置有key了，那么要判斷是替換還是生成鏈表還是生成紅黑樹(shù)，情況比較復(fù)雜。所以直接用synchronized代碼塊。鎖對(duì)象是當(dāng)前操作的node節(jié)點(diǎn)，縮小了鎖的粒度也就是說(shuō)，其他線程只是不能對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行操作，但可以對(duì)其他節(jié)點(diǎn)進(jìn)行操作。

4、擴(kuò)容和轉(zhuǎn)移數(shù)據(jù)：這個(gè)過(guò)程也會(huì)有線程安全問(wèn)題。只能有一個(gè)線程進(jìn)行擴(kuò)容，當(dāng)一個(gè)線程進(jìn)行擴(kuò)容的時(shí)候，其他線程也別閑著，其他線程就幫忙將舊數(shù)組的數(shù)據(jù)轉(zhuǎn)移到新數(shù)組。擴(kuò)容的addCount方法也是通過(guò)CAS來(lái)保證線程安全的。在putVal方法中，好友一個(gè)判斷條件如下：

else if ((fh = f.hash) == MOVED) // -1
        tab = helpTransfer(tab, f);

當(dāng)那個(gè)值等于-1時(shí)，那么就調(diào)用helpTransfer方法去幫忙進(jìn)行數(shù)據(jù)的轉(zhuǎn)移。

小結(jié)：ConcurrentHashMap在put元素時(shí)主要邏輯如下：

 if (tab == null || (n = tab.length) == 0) // 數(shù)組為空
         tab = initTable(); // 初始化，CAS保證線程安全
 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { // 要插入的位置key為null 
         // casTabAt 方法用CAS保證線程安全
         if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) { 
             delta = 1;
             val = value;
             break;
          }
 }
 else if ((fh = f.hash) == MOVED) // f.hash == MOVED(-1)
          tab = helpTransfer(tab, f); // 幫忙轉(zhuǎn)移元素到擴(kuò)容后的數(shù)組，CAS保證安全性
 else { // 要插入的位置key不為null 
          synchronized (f) { // 同步代碼塊保證線程安全
                   ......
          }
 }
 if (delta != 0) 
          addCount((long)delta, binCount); // 擴(kuò)容，CAS保證安全性

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Java源碼解讀 --- HashMap&ConcurrentHashMap

Java源碼解讀 --- HashMap&ConcurrentHashMap

一、HashMap的宏觀實(shí)現(xiàn)

二、HashMap實(shí)現(xiàn)細(xì)節(jié)

三、ConcurrentHashMap

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Java源碼解讀 --- HashMap&ConcurrentHashMap

一、HashMap的宏觀實(shí)現(xiàn)

二、HashMap實(shí)現(xiàn)細(xì)節(jié)

三、ConcurrentHashMap

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一、HashMap的宏觀實(shí)現(xiàn)

二、HashMap實(shí)現(xiàn)細(xì)節(jié)

三、ConcurrentHashMap