最近工作不是太忙，準(zhǔn)備再讀讀一些源碼踏烙，想來想去师骗，還是先從JDK的源碼讀起吧，畢竟很久不去讀了讨惩，很多東西都生疏了辟癌。當(dāng)然，還是先從炙手可熱的HashMap荐捻，每次讀都會(huì)有一些收獲黍少。當(dāng)然，JDK8對(duì)HashMap有一次優(yōu)化

一处面、一些參數(shù)

我們首先看到的厂置，應(yīng)該是它的一些基本參數(shù)，這對(duì)于我們了解HashMap有一定的作用魂角。他們分別是：

二、重要方法

我們知道挣惰，HashMap底層是通過數(shù)組+鏈表來實(shí)現(xiàn)的游添。具體的圖網(wǎng)上有很多系草，我們主要看看幾個(gè)重要的方法。

2.1 構(gòu)造方法

他的構(gòu)造方法唆涝，最本質(zhì)的構(gòu)造方法是：

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;
    this.threshold = tableSizeFor(initialCapacity);
}

前面幾行就是做一些基本的檢查找都，我們看到，HashMap的最大容量是<u>MAXIMUM_CAPACITY</u>廊酣，也就是2^30能耻，我們?nèi)粘Ｊ褂脮r(shí)可能達(dá)不到這樣的容量，但是如果真的需要在Map存儲(chǔ)這么多的數(shù)據(jù)亡驰，還是建議存在其他的地方吧晓猛。當(dāng)然，最后一行中時(shí)為了計(jì)算下一次resize的容量閾值凡辱，也就是計(jì)算出下一次resize的threshold戒职。

2.2 計(jì)算容量

這個(gè)方法較簡單，直接返回的是一個(gè)size的值透乾，這個(gè)參數(shù)的含義就是當(dāng)前Map中存儲(chǔ)的KV對(duì)的數(shù)量洪燥，而不是整個(gè)Map的容量。

public int size() {
    return size;
}

2.3 put(K,V)

這個(gè)方法是HashMap中比較重要的一個(gè)方法乳乌，我們仔細(xì)分析一下捧韵。

2.3.1 主入口

首先，方法的入口是這個(gè)汉操，也就是我們經(jīng)常使用的就是這個(gè)方法：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

我們主要看的再来，就是put的整個(gè)過程。

2.3.2 hash(key)

首先就是對(duì)我們傳入的key磷瘤，進(jìn)行hash計(jì)算芒篷。

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

從這個(gè)方法，我們可以看到采缚，HashMap的key是可以為null的针炉，如果是null的話，那么我們的hash方法返回的hash值是0仰担。

如果key不是null糊识，那么調(diào)用的是HashMap本身的hashCode方法绩社，也就是我們的bean中自定義的hashCode()摔蓝。不要以為這樣就結(jié)束了。我們一般來說愉耙，一個(gè)key的hash值的范圍也就是int的范圍（從-2147483648到2147483648）贮尉，但是HashMap的容量是有限的，必須把hash值能夠分散到HashMap的數(shù)組中去朴沿。HashMap為了key在數(shù)組中更加分散猜谚，還會(huì)進(jìn)行一次計(jì)算败砂，也就是我們看到的第二行的方法。具體這塊是如何分配均勻的魏铅，可以參考這篇文章昌犹。

2.3.3 putVal()

這個(gè)方法就是將KV放到對(duì)應(yīng)的桶中。這個(gè)方法的過程览芳，比較清晰斜姥。

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)
        //如果之前的數(shù)組為空，那么新建一個(gè)默認(rèn)的數(shù)組
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果hash值計(jì)算出來在數(shù)組中的位置上沧竟，沒有元素铸敏，那么直接插入到數(shù)組中
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //如果算出的hash存在，而且kv完全一致的話悟泵，那么目前什么也不做
            e = p;
        else if (p instanceof TreeNode)
            //如果數(shù)組中的元素是紅黑樹杈笔，那么將kv插入到紅黑樹中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //如果hash的桶中，已經(jīng)存在了一個(gè)鏈表糕非，那么新增一個(gè)節(jié)點(diǎn)蒙具，放到鏈表的尾部
                    p.next = newNode(hash, key, value, null);
                    //如果鏈表的長度大于樹化的閾值，那么將鏈表轉(zhuǎn)為紅黑樹
                    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;
            }
        }
        //如果當(dāng)前數(shù)組中存在相同的kv峰弹，那么根據(jù)是否替換來判斷店量，如果不替換，那么就不替換
        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)
        //如果空間需要進(jìn)行擴(kuò)容鞠呈，那么進(jìn)行resize操作
        resize();
    afterNodeInsertion(evict);
    return null;
}

至此融师，putVal的方法過程基本上清楚了，但是里面有個(gè)非常重要的方法蚁吝，就是resize旱爆，我們下面就進(jìn)入resize方法，看看到底是如何擴(kuò)容的窘茁。

2.4 resize()

這個(gè)過程是HashMap擴(kuò)容的過程怀伦，也是需要重點(diǎn)理解的一塊。
我們首先看下第一部分山林。

2.4.1 確定容量和擴(kuò)容閾值

Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
    //如果目前容量已經(jīng)是最大容量房待，那么擴(kuò)容閾值為int的最大值，所有的節(jié)點(diǎn)都不需要移動(dòng)
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    //如果oldCap*2小于最大容量驼抹，并且oldCap>=16桑孩，擴(kuò)容為2倍，擴(kuò)容閾值也*2
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1;
}
else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
else {// 默認(rèn)值
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//計(jì)算新的擴(kuò)容閾值
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;

這個(gè)過程框冀，主要是確定新的容量和擴(kuò)容閾值流椒。

2.4.2 節(jié)點(diǎn)移動(dòng)

if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {//遍歷老的數(shù)組
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            if (e.next == null)//如果老的鏈表，只有一個(gè)KV明也，直接將這個(gè)KV放到新的數(shù)組鏈表中
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)//如果老的是紅黑樹宣虾，需要將紅黑樹中的每個(gè)元素都拆分到新的數(shù)組和鏈表/紅黑樹中
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            else { // 如果節(jié)點(diǎn)是鏈表惯裕，而且不止一個(gè)KV的情況下，需要對(duì)鏈表進(jìn)行處理绣硝，處理的過程蜻势，光看代碼理解起來較困難，需要通過例子來理解
                Node<K,V> loHead = null, loTail = null;
                Node<K,V> hiHead = null, hiTail = null;
                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;
                }
            }
        }
    }
}

我們需要知道鹉胖，坐標(biāo)點(diǎn)的計(jì)算方法是e.hash & (cap-1)咙边。

沒有進(jìn)行擴(kuò)容時(shí)，假設(shè)原來的cap=16次员，也就是默認(rèn)值败许，擴(kuò)容后容量為32。對(duì)于hash值為5（二進(jìn)制為0000 0101）和21（二進(jìn)制為0001 0101）的元素來講淑蔚，計(jì)算坐標(biāo)市殷，也就是和15（二進(jìn)制為0000 1111）計(jì)算后的坐標(biāo)點(diǎn)都是5，會(huì)落到同一個(gè)鏈表中刹衫。

但是擴(kuò)容后醋寝，需要求與的變成了31（二進(jìn)制為0001 1111），算出來的坐標(biāo)點(diǎn)分別為5和21带迟，第二個(gè)坐標(biāo)點(diǎn)增加了oldCap的長度音羞。

此時(shí)再看e.hash & oldCap的計(jì)算結(jié)果，也就是將5和21和16（二進(jìn)制為0001 0000）求與仓犬，得到的結(jié)果分別是0和16（!=0）嗅绰。可以看到搀继，當(dāng)e.hash & oldCap得到0時(shí)窘面，坐標(biāo)不需要進(jìn)行變動(dòng)，也就是不需要在數(shù)組中的位置不需要移動(dòng)叽躯。如果結(jié)果不為0财边，需要在原來坐標(biāo)的位置，增加oldCap点骑。

這里的lo和hi也就是兩個(gè)鏈表酣难，表示的是低位和高位的兩條鏈表。

三黑滴、線程不安全的問題

我們都知道憨募，HashMap不是線程安全的。這塊主要體現(xiàn)在兩塊：

3.1 get和put

這兩塊都沒有加鎖跷跪，所以可能會(huì)導(dǎo)致多線程執(zhí)行時(shí)馋嗜，出現(xiàn)數(shù)據(jù)被覆蓋的問題齐板。

3.2 死循環(huán)的問題

這個(gè)問題主要出現(xiàn)在resize的過程中吵瞻，多線程都探測到需要resize時(shí)葛菇，將鏈表元素rehash過程中，可能會(huì)導(dǎo)致死循環(huán)橡羞。這個(gè)問題參考這篇文章眯停。

至此，源碼分析基本結(jié)束卿泽，我們還可以思考莺债，為什么cap必須是2的冪次，我們應(yīng)該如何正確的初始化HashMap等签夭。

歡迎大家關(guān)注我的公眾號(hào)齐邦，有各種一線分享。

qrcode_for_gh_2e415bdf9b4e_258.jpg