面試官再問你 HashMap 底層原理壁拉,就把這篇文章甩給他看

前言

HashMap 源碼和底層原理在現(xiàn)在面試中是必問的谬俄。因此,我們非常有必要搞清楚它的底層實現(xiàn)和思想弃理,才能在面試中對答如流溃论,跟面試官大戰(zhàn)三百回合。文章較長痘昌,介紹了很多原理性的問題蔬芥,希望對你有所幫助~

目錄

本篇文章主要包括以下內(nèi)容:

  • HashMap 的存儲結(jié)構(gòu)
  • 常用變量說明梆靖,如加載因子等
  • HashMap 的四個構(gòu)造函數(shù)
  • tableSizeFor()方法及作用
  • put()方法詳解
  • hash()方法,以及避免哈希碰撞的原理
  • resize()擴(kuò)容機(jī)制及原理
  • get()方法
  • 為什么HashMap鏈表會形成死循環(huán)笔诵,JDK1.8做了哪些優(yōu)化

正文

說明:本篇主要以JDK1.8的源碼來分析返吻,順帶講下和JDK1.7的一些區(qū)別。

HashMap存儲結(jié)構(gòu)

這里需要區(qū)分一下乎婿,JDK1.7和 JDK1.8之后的 HashMap 存儲結(jié)構(gòu)测僵。在JDK1.7及之前,是用數(shù)組加鏈表的方式存儲的谢翎。

但是捍靠,眾所周知,當(dāng)鏈表的長度特別長的時候森逮,查詢效率將直線下降榨婆,查詢的時間復(fù)雜度為 O(n)。因此褒侧,JDK1.8 把它設(shè)計為達(dá)到一個特定的閾值之后良风,就將鏈表轉(zhuǎn)化為紅黑樹。

這里簡單說下紅黑樹的特點:

  1. 每個節(jié)點只有兩種顏色:紅色或者黑色
  2. 根節(jié)點必須是黑色
  3. 每個葉子節(jié)點(NIL)都是黑色的空節(jié)點
  4. 從根節(jié)點到葉子節(jié)點闷供,不能出現(xiàn)兩個連續(xù)的紅色節(jié)點
  5. 從任一節(jié)點出發(fā)烟央,到它下邊的子節(jié)點的路徑包含的黑色節(jié)點數(shù)目都相同

由于紅黑樹,是一個自平衡的二叉搜索樹歪脏,因此可以使查詢的時間復(fù)雜度降為O(logn)疑俭。(紅黑樹不是本文重點,不了解的童鞋可自行查閱相關(guān)資料哈)

HashMap 結(jié)構(gòu)示意圖:

常用的變量

在 HashMap源碼中婿失,比較重要的常用變量钞艇,主要有以下這些。還有兩個內(nèi)部類來表示普通鏈表的節(jié)點和紅黑樹節(jié)點豪硅。


//默認(rèn)的初始化容量為16香璃,必須是2的n次冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//最大容量為 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

//默認(rèn)的加載因子0.75,乘以數(shù)組容量得到的值舟误,用來表示元素個數(shù)達(dá)到多少時葡秒,需要擴(kuò)容。
//為什么設(shè)置 0.75 這個值呢嵌溢,簡單來說就是時間和空間的權(quán)衡眯牧。
//若小于0.75如0.5,則數(shù)組長度達(dá)到一半大小就需要擴(kuò)容赖草,空間使用率大大降低学少,
//若大于0.75如0.8,則會增大hash沖突的概率秧骑,影響查詢效率版确。
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//剛才提到了當(dāng)鏈表長度過長時扣囊,會有一個閾值,超過這個閾值8就會轉(zhuǎn)化為紅黑樹
static final int TREEIFY_THRESHOLD = 8;

//當(dāng)紅黑樹上的元素個數(shù)绒疗,減少到6個時侵歇,就退化為鏈表
static final int UNTREEIFY_THRESHOLD = 6;

//鏈表轉(zhuǎn)化為紅黑樹,除了有閾值的限制吓蘑,還有另外一個限制惕虑,需要數(shù)組容量至少達(dá)到64,才會樹化磨镶。
//這是為了避免溃蔫,數(shù)組擴(kuò)容和樹化閾值之間的沖突。
static final int MIN_TREEIFY_CAPACITY = 64;

//存放所有Node節(jié)點的數(shù)組
transient Node<K,V>[] table;

//存放所有的鍵值對
transient Set<Map.Entry<K,V>> entrySet;

//map中的實際鍵值對個數(shù)琳猫,即數(shù)組中元素個數(shù)
transient int size;

//每次結(jié)構(gòu)改變時伟叛,都會自增,fail-fast機(jī)制脐嫂,這是一種錯誤檢測機(jī)制统刮。
//當(dāng)?shù)系臅r候,如果結(jié)構(gòu)發(fā)生改變雹锣,則會發(fā)生 fail-fast网沾,拋出異常癞蚕。
transient int modCount;

//數(shù)組擴(kuò)容閾值
int threshold;

//加載因子
final float loadFactor;                 

//普通單向鏈表節(jié)點類
static class Node<K,V> implements Map.Entry<K,V> {
    //key的hash值蕊爵,put和get的時候都需要用到它來確定元素在數(shù)組中的位置
    final int hash;
    final K key;
    V value;
    //指向單鏈表的下一個節(jié)點
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

//轉(zhuǎn)化為紅黑樹的節(jié)點類
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    //當(dāng)前節(jié)點的父節(jié)點
    TreeNode<K,V> parent;  
    //左孩子節(jié)點
    TreeNode<K,V> left;
    //右孩子節(jié)點
    TreeNode<K,V> right;
    //指向前一個節(jié)點
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    //當(dāng)前節(jié)點是紅色或者黑色的標(biāo)識
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}   

HashMap 構(gòu)造函數(shù)

HashMap有四個構(gòu)造函數(shù)可供我們使用,一起來看下:

//默認(rèn)無參構(gòu)造桦山,指定一個默認(rèn)的加載因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

//可指定容量的有參構(gòu)造攒射,但是需要注意當(dāng)前我們指定的容量并不一定就是實際的容量,下面會說
public HashMap(int initialCapacity) {
    //同樣使用默認(rèn)加載因子
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//可指定容量和加載因子恒水,但是筆者不建議自己手動指定非0.75的加載因子
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;
    //這里就是把我們指定的容量改為一個大于它的的最小的2次冪值会放,如傳過來的容量是14,則返回16
    //注意這里钉凌,按理說返回的值應(yīng)該賦值給 capacity咧最,即保證數(shù)組容量總是2的n次冪,為什么這里賦值給了 threshold 呢御雕?
    //先賣個關(guān)子矢沿,等到 resize 的時候再說
    this.threshold = tableSizeFor(initialCapacity);
}

//可傳入一個已有的map
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

//把傳入的map里邊的元素都加載到當(dāng)前map
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : 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();
            //put方法的具體實現(xiàn),后邊講
            putVal(hash(key), key, value, false, evict);
        }
    }
}

tableSizeFor()

上邊的第三個構(gòu)造函數(shù)中酸纲,調(diào)用了 tableSizeFor 方法捣鲸,這個方法是怎么實現(xiàn)的呢?

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

我們以傳入?yún)?shù)為14 來舉例闽坡,計算這個過程栽惶。

首先愁溜,14傳進(jìn)去之后先減1,n此時為13外厂。然后是一系列的無符號右移運(yùn)算冕象。

//13的二進(jìn)制
0000 0000 0000 0000 0000 0000 0000 1101 
//無右移1位,高位補(bǔ)0
0000 0000 0000 0000 0000 0000 0000 0110 
//然后把它和原來的13做或運(yùn)算得到酣衷,此時的n值
0000 0000 0000 0000 0000 0000 0000 1111 
//再以上邊的值交惯,右移2位
0000 0000 0000 0000 0000 0000 0000 0011
//然后和第一次或運(yùn)算之后的 n 值再做或運(yùn)算,此時得到的n值
0000 0000 0000 0000 0000 0000 0000 1111
...
//我們會發(fā)現(xiàn)穿仪,再執(zhí)行右移 4,8,16位席爽,同樣n的值不變
//當(dāng)n小于0時,返回1啊片,否則判斷是否大于最大容量只锻,是的話返回最大容量,否則返回 n+1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
//很明顯我們這里返回的是 n+1 的值紫谷,
0000 0000 0000 0000 0000 0000 0000 1111
+                                     1
0000 0000 0000 0000 0000 0000 0001 0000

將它轉(zhuǎn)為十進(jìn)制齐饮,就是 2^4 = 16 。我們會發(fā)現(xiàn)一個規(guī)律笤昨,以上的右移運(yùn)算祖驱,最終會把最低位的值都轉(zhuǎn)化為 1111 這樣的結(jié)構(gòu),然后再加1瞒窒,就是1 0000 這樣的結(jié)構(gòu)捺僻,它一定是 2的n次冪。因此崇裁,這個方法返回的就是大于當(dāng)前傳入值的最胸芭鳌(最接近當(dāng)前值)的一個2的n次冪的值。

put()方法詳解

//put方法拔稳,會先調(diào)用一個hash()方法葛峻,得到當(dāng)前key的一個hash值,
//用于確定當(dāng)前key應(yīng)該存放在數(shù)組的哪個下標(biāo)位置
//這里的 hash方法巴比,我們姑且先認(rèn)為是key.hashCode()术奖,其實不是的,一會兒細(xì)講
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//把hash值和當(dāng)前的key轻绞,value傳入進(jìn)來
//這里onlyIfAbsent如果為true采记,表明不能修改已經(jīng)存在的值,因此我們傳入false
//evict只有在方法 afterNodeInsertion(boolean evict) { }用到铲球,可以看到它是一個空實現(xiàn)挺庞,因此不用關(guān)注這個參數(shù)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判斷table是否為空,如果空的話稼病,會先調(diào)用resize擴(kuò)容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根據(jù)當(dāng)前key的hash值找到它在數(shù)組中的下標(biāo)选侨,判斷當(dāng)前下標(biāo)位置是否已經(jīng)存在元素掖鱼,
    //若沒有,則把key援制、value包裝成Node節(jié)點戏挡,直接添加到此位置。
    // i = (n - 1) & hash 是計算下標(biāo)位置的晨仑,為什么這樣算褐墅,后邊講
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else { 
        //如果當(dāng)前位置已經(jīng)有元素了,分為三種情況洪己。
        Node<K,V> e; K k;
        //1.當(dāng)前位置元素的hash值等于傳過來的hash妥凳,并且他們的key值也相等,
        //則把p賦值給e答捕,跳轉(zhuǎn)到①處逝钥,后續(xù)需要做值的覆蓋處理
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //2.如果當(dāng)前是紅黑樹結(jié)構(gòu),則把它加入到紅黑樹 
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        //3.說明此位置已存在元素拱镐,并且是普通鏈表結(jié)構(gòu)艘款,則采用尾插法,把新節(jié)點加入到鏈表尾部
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //如果頭結(jié)點的下一個節(jié)點為空沃琅,則插入新節(jié)點
                    p.next = newNode(hash, key, value, null);
                    //如果在插入的過程中哗咆,鏈表長度超過了8,則轉(zhuǎn)化為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    //插入成功之后益眉,跳出循環(huán)晌柬,跳轉(zhuǎn)到①處
                    break;
                }
                //若在鏈表中找到了相同key的話,直接退出循環(huán)呜叫,跳轉(zhuǎn)到①處
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //① 此時e有兩種情況
        //1.說明發(fā)生了碰撞空繁,e代表的是舊值殿衰,因此節(jié)點位置不變朱庆,但是需要替換為新值
        //2.說明e是插入鏈表或者紅黑樹,成功后的新節(jié)點
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //用新值替換舊值闷祥,并返回舊值娱颊。
            //oldValue為空,說明e是新增的節(jié)點或者也有可能舊值本來就是空的凯砍,因為hashmap可存空值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //看方法名字即可知箱硕,這是在node被訪問之后需要做的操作。其實此處是一個空實現(xiàn)悟衩,
            //只有在 LinkedHashMap才會實現(xiàn)剧罩,用于實現(xiàn)根據(jù)訪問先后順序?qū)υ剡M(jìn)行排序,hashmap不提供排序功能
            // Callbacks to allow LinkedHashMap post-actions
            //void afterNodeAccess(Node<K,V> p) { }
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //fail-fast機(jī)制
    ++modCount;
    //如果當(dāng)前數(shù)組中的元素個數(shù)超過閾值座泳,則擴(kuò)容
    if (++size > threshold)
        resize();
    //同樣的空實現(xiàn)
    afterNodeInsertion(evict);
    return null;
}

hash()計算原理

前面 put 方法中說到惠昔,需要先把當(dāng)前key進(jìn)行哈希處理幕与,我們看下這個方法是怎么實現(xiàn)的。

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

這里镇防,會先判斷key是否為空啦鸣,若為空則返回0。這也說明了hashMap是支持key傳 null 的来氧。若非空诫给,則先計算key的hashCode值,賦值給h啦扬,然后把h右移16位中狂,并與原來的h進(jìn)行異或處理。為什么要這樣做扑毡,這樣做有什么好處呢吃型?

我們知道,hashCode()方法繼承自父類Object僚楞,它返回的是一個 int 類型的數(shù)值勤晚,可以保證同一個應(yīng)用單次執(zhí)行的每次調(diào)用,返回結(jié)果都是相同的(這個說明可以在hashCode源碼上找到)泉褐,這就保證了hash的確定性赐写。在此基礎(chǔ)上,再進(jìn)行某些固定的運(yùn)算膜赃,肯定結(jié)果也是可以確定的挺邀。

我隨便運(yùn)行一段程序,把它的 hashCode的二進(jìn)制打印出來跳座,如下端铛。

public static void main(String[] args) {
    Object o = new Object();
    int hash = o.hashCode();
    System.out.println(hash);
    System.out.println(Integer.toBinaryString(hash));

}
//1836019240
//1101101011011110110111000101000

然后,進(jìn)行 (h = key.hashCode()) ^ (h >>> 16) 這一段運(yùn)算疲眷。

//h原來的值
0110 1101 0110 1111 0110 1110 0010 1000
//無符號右移16位禾蚕,其實相當(dāng)于把低位16位舍去,只保留高16位
0000 0000 0000 0000 0110 1101 0110 1111
//然后高16位和原 h進(jìn)行異或運(yùn)算
0110 1101 0110 1111 0110 1110 0010 1000
^
0000 0000 0000 0000 0110 1101 0110 1111
=
0110 1101 0110 1111 0000 0011 0100 0111

可以看到狂丝,其實相當(dāng)于换淆,我們把高16位值和當(dāng)前h的低16位進(jìn)行了混合,這樣可以盡量保留高16位的特征几颜,從而降低哈希碰撞的概率倍试。

思考一下,為什么這樣做蛋哭,就可以降低哈希碰撞的概率呢县习?先別著急,我們需要結(jié)合 i = (n - 1) & hash 這一段運(yùn)算來理解。

** (n-1) & hash 作用**

//②
//這是 put 方法中用來根據(jù)hash()值尋找在數(shù)組中的下標(biāo)的邏輯躁愿,
//n為數(shù)組長度哈蝇, hash為調(diào)用 hash()方法混合處理之后的hash值。
i = (n - 1) & hash

我們知道攘已,如果給定某個數(shù)值炮赦,去找它在某個數(shù)組中的下標(biāo)位置時,直接用模運(yùn)算就可以了(假設(shè)數(shù)組值從0開始遞增)样勃。如吠勘,我找 14 在數(shù)組長度為16的數(shù)組中的下標(biāo),即為 14 % 16峡眶,等于14 剧防。 18的位置即為 18%16,等于2辫樱。

而②中峭拘,就是取模運(yùn)算的位運(yùn)算形式。以18%16為例

//18的二進(jìn)制
0001 0010
//16 -1 即 15的二進(jìn)制
0000 1111
//與運(yùn)算之后的結(jié)果為
0000 0010
// 可以看到狮暑,上邊的結(jié)果轉(zhuǎn)化為十進(jìn)制就是 2 鸡挠。
//其實我們會發(fā)現(xiàn)一個規(guī)律,因為n是2的n次冪搬男,因此它的二進(jìn)制表現(xiàn)形式肯定是類似于
0001 0000
//這樣的形式拣展,只有一個位是1,其他位都是0缔逛。而它減 1 之后的形式就是類似于
0000 1111 
//這樣的形式备埃,高位都是0,低位都是1褐奴,因此它和任意值進(jìn)行與運(yùn)算按脚,結(jié)果值肯定在這個區(qū)間內(nèi)
0000 0000  ~  0000 1111
//也就是0到15之間,(以n為16為例)
//因此敦冬,這個運(yùn)算就可以實現(xiàn)取模運(yùn)算辅搬,而且位運(yùn)算還有個好處,就是速度比較快匪补。

為什么高低位異或運(yùn)算可以減少哈希碰撞

我們想象一下伞辛,假如用 key 原來的hashCode值烂翰,直接和 (n-1) 進(jìn)行與運(yùn)算來求數(shù)組下標(biāo)夯缺,而不進(jìn)行高低位混合運(yùn)算,會產(chǎn)生什么樣的結(jié)果甘耿。

//例如我有另外一個h2踊兜,和原來的 h相比較,高16位有很大的不同佳恬,但是低16位相似度很高捏境,甚至相同的話于游。
//原h(huán)值
0110 1101 0110 1111 0110 1110 0010 1000
//另外一個h2值
0100 0101 1110 1011 0110 0110 0010 1000
// n -1 ,即 15 的二進(jìn)制
0000 0000 0000 0000 0000 0000 0000 1111
//可以發(fā)現(xiàn) h2 和 h 的高位不相同,但是低位相似度非常高垫言。
//他們分別和 n -1 進(jìn)行與運(yùn)算時贰剥,得到的結(jié)果卻是相同的。(此處n假設(shè)為16)
//因為 n-1 的高16位都是0筷频,不管 h 的高 16 位是什么蚌成,與運(yùn)算之后,都不影響最終結(jié)果凛捏,高位一定全是 0
//因此担忧,哈希碰撞的概率就大大增加了,并且 h 的高16 位特征全都丟失了坯癣。

愛思考的同學(xué)可能就會有疑問了瓶盛,我進(jìn)行高低16位混合運(yùn)算,是可以的示罗,這樣可以保證盡量減少高區(qū)位的特征惩猫。那么,為什么選擇用異或運(yùn)算呢蚜点,我用與帆锋、或、非運(yùn)算不行嗎禽额?

這是有一定的道理的锯厢。我們看一個表格,就能明白了脯倒。

可以看到兩個值進(jìn)行與運(yùn)算实辑,結(jié)果會趨向于0;或運(yùn)算藻丢,結(jié)果會趨向于1剪撬;而只有異或運(yùn)算,0和1的比例可以達(dá)到1:1的平衡狀態(tài)悠反。(非呢残黑?別扯犢子了,兩個值怎么做非運(yùn)算斋否。梨水。。)

所以茵臭,異或運(yùn)算之后疫诽,可以讓結(jié)果的隨機(jī)性更大,而隨機(jī)性大了之后,哈希碰撞的概率當(dāng)然就更小了奇徒。

以上雏亚,就是為什么要對一個hash值進(jìn)行高低位混合,并且選擇異或運(yùn)算來混合的原因摩钙。

resize() 擴(kuò)容機(jī)制

在上邊 put 方法中罢低,我們會發(fā)現(xiàn),當(dāng)數(shù)組為空的時候胖笛,會調(diào)用 resize 方法奕短,當(dāng)數(shù)組的 size 大于閾值的時候,也會調(diào)用 resize方法匀钧。 那么看下 resize 方法都做了哪些事情吧翎碑。

final Node<K,V>[] resize() {
    //舊數(shù)組
    Node<K,V>[] oldTab = table;
    //舊數(shù)組的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //舊數(shù)組的擴(kuò)容閾值,注意看之斯,這里取的是當(dāng)前對象的 threshold 值日杈,下邊的第2種情況會用到旗们。
    int oldThr = threshold;
    //初始化新數(shù)組的容量和閾值禀晓,分三種情況討論。
    int newCap, newThr = 0;
    //1.當(dāng)舊數(shù)組的容量大于0時恋博,說明在這之前肯定調(diào)用過 resize擴(kuò)容過一次瘫絮,才會導(dǎo)致舊容量不為0涨冀。
    //為什么這樣說呢,之前我在 tableSizeFor 賣了個關(guān)子麦萤,需要注意的是鹿鳖,它返回的值是賦給了 threshold 而不是 capacity。
    //我們在這之前壮莹,壓根就沒有在任何地方看到過翅帜,它給 capacity 賦初始值。
    if (oldCap > 0) {
        //容量達(dá)到了最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新數(shù)組的容量和閾值都擴(kuò)大原來的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //2.到這里命满,說明 oldCap <= 0涝滴,并且 oldThr(threshold) > 0,這就是 map 初始化的時候胶台,第一次調(diào)用 resize的情況
    //而 oldThr的值等于 threshold歼疮,此時的 threshold 是通過 tableSizeFor 方法得到的一個2的n次冪的值(我們以16為例)。
    //因此诈唬,需要把 oldThr 的值韩脏,也就是 threshold ,賦值給新數(shù)組的容量 newCap讯榕,以保證數(shù)組的容量是2的n次冪骤素。
    //所以我們可以得出結(jié)論匙睹,當(dāng)map第一次 put 元素的時候愚屁,就會走到這個分支济竹,把數(shù)組的容量設(shè)置為正確的值(2的n次冪)
    //但是,此時 threshold 的值也是2的n次冪霎槐,這不對啊送浊,它應(yīng)該是數(shù)組的容量乘以加載因子才對。別著急丘跌,這個會在③處理袭景。
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //3.到這里,說明 oldCap 和 oldThr 都是小于等于0的闭树。也說明我們的map是通過默認(rèn)無參構(gòu)造來創(chuàng)建的耸棒,
    //于是,數(shù)組的容量和閾值都取默認(rèn)值就可以了报辱,即 16 和 12与殃。
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //③ 這里就是處理第2種情況,因為只有這種情況 newThr 才為0碍现,
    //因此計算 newThr(用 newCap即16 乘以加載因子 0.75幅疼,得到 12) ,并把它賦值給 threshold
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //賦予 threshold 正確的值昼接,表示數(shù)組下次需要擴(kuò)容的閾值(此時就把原來的 16 修正為了 12)爽篷。
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //如果原來的數(shù)組不為空,那么我們就需要把原來數(shù)組中的元素重新分配到新的數(shù)組中
    //如果是第2種情況慢睡,由于是第一次調(diào)用resize逐工,此時數(shù)組肯定是空的,因此也就不需要重新分配元素漂辐。
    if (oldTab != null) {
        //遍歷舊數(shù)組
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //取到當(dāng)前下標(biāo)的第一個元素钻弄,如果存在,則分三種情況重新分配位置
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //1.如果當(dāng)前元素的下一個元素為空者吁,則說明此處只有一個元素
                //則直接用它的hash()值和新數(shù)組的容量取模就可以了窘俺,得到新的下標(biāo)位置。
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //2.如果是紅黑樹結(jié)構(gòu)复凳,則拆分紅黑樹瘤泪,必要時有可能退化為鏈表
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //3.到這里說明,這是一個長度大于 1 的普通鏈表育八,則需要計算并
                //判斷當(dāng)前位置的鏈表是否需要移動到新的位置
                else { // preserve order
                    // loHead 和 loTail 分別代表鏈表舊位置的頭尾節(jié)點
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead 和 hiTail 分別代表鏈表移動到新位置的頭尾節(jié)點
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //如果當(dāng)前元素的hash值和oldCap做與運(yùn)算為0对途,則原位置不變
                        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);
                    //原位置不變的一條鏈表髓棋,數(shù)組下標(biāo)不變
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //移動到新位置的一條鏈表实檀,數(shù)組下標(biāo)為原下標(biāo)加上舊數(shù)組的容量
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

上邊還有一個非常重要的運(yùn)算惶洲,我們沒有講解。就是下邊這個判斷膳犹,它用于把原來的普通鏈表拆分為兩條鏈表恬吕,位置不變或者放在新的位置。

if ((e.hash & oldCap) == 0) {} else {}

我們以原數(shù)組容量16為例须床,擴(kuò)容之后容量為32铐料。說明下為什么這樣計算。

還是用之前的hash值舉例豺旬。

//e.hash值
0110 1101 0110 1111 0110 1110 0010 1000
//oldCap值钠惩,即16
0000 0000 0000 0000 0000 0000 0001 0000 
//做與運(yùn)算,我們會發(fā)現(xiàn)結(jié)果不是0就是非0族阅,
//而且它取決于 e.hash 二進(jìn)制位的倒數(shù)第五位是 0 還是 1篓跛,
//若倒數(shù)第五位為0,則結(jié)果為0坦刀,若倒數(shù)第五位為1愧沟,則結(jié)果為非0。
//那這個和新數(shù)組有什么關(guān)系呢求泰?
//別著急央渣,我們看下新數(shù)組的容量是32,如果求當(dāng)前hash值在新數(shù)組中的下標(biāo)渴频,則為
// e.hash &( 32 - 1) 這樣的運(yùn)算 芽丹,即 hash 與 31 進(jìn)行與運(yùn)算,
0110 1101 0110 1111 0110 1110 0010 1000 
&
0000 0000 0000 0000 0000 0000 0001 1111 
=
0000 0000 0000 0000 0000 0000 0000 1000
//接下來卜朗,我們對比原來的下標(biāo)計算結(jié)果和新的下標(biāo)結(jié)果拔第,看圖

看下面的圖,我們觀察场钉,hash值和舊數(shù)組進(jìn)行與運(yùn)算的結(jié)果 蚊俺,跟新數(shù)組的與運(yùn)算結(jié)果有什么不同。

會發(fā)現(xiàn)一個規(guī)律:

若hash值的倒數(shù)第五位是0逛万,則新下標(biāo)與舊下標(biāo)結(jié)果相同泳猬,都為 0000 1000

若hash值的倒數(shù)第五位是1,則新下標(biāo)(0001 1000)與舊下標(biāo)(0000 1000)結(jié)果值相差了 16 宇植。

因此得封,我們就可以根據(jù) (e.hash & oldCap == 0) 這個判斷的真假來決定,當(dāng)前元素應(yīng)該在原來的位置不變指郁,還是在新的位置(原位置 + 16)忙上。

如果,上邊的推理還是不明白的話闲坎,我再舉個簡單的例子疫粥。

18%16=2     18%32=18
34%16=2     34%32=2
50%16=2     50%32=18

怎么樣茬斧,發(fā)現(xiàn)規(guī)律沒,有沒有那個感覺了梗逮?

計算中的18项秉,34 ,50 其實就相當(dāng)于 e.hash 值库糠,和新舊數(shù)組做取模運(yùn)算伙狐,得到的結(jié)果涮毫,要么就是原來的位置不變瞬欧,要么就是原來的位置加上舊數(shù)組的長度。

get()方法

有了前面的基礎(chǔ)罢防,get方法就比較簡單了艘虎。

public V get(Object key) {
    Node<K,V> e;
    //如果節(jié)點為空,則返回null咒吐,否則返回節(jié)點的value野建。這也說明,hashMap是支持value為null的恬叹。
    //因此候生,我們就明白了,為什么hashMap支持Key和value都為null
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //首先要確保數(shù)組不能為空绽昼,然后取到當(dāng)前hash值計算出來的下標(biāo)位置的第一個元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //若hash值和key都相等唯鸭,則說明我們要找的就是第一個元素,直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果不是的話硅确,就遍歷當(dāng)前鏈表(或紅黑樹)
        if ((e = first.next) != null) {
            //如果是紅黑樹結(jié)構(gòu)目溉,則找到當(dāng)前key所在的節(jié)點位置
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果是普通鏈表,則向后遍歷查找菱农,直到找到或者遍歷到鏈表末尾為止缭付。
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //否則,說明沒有找到循未,返回null
    return null;
}

為什么HashMap鏈表會形成死循環(huán)

準(zhǔn)確的講應(yīng)該是 JDK1.7 的 HashMap 鏈表會有死循環(huán)的可能陷猫,因為JDK1.7是采用的頭插法,在多線程環(huán)境下有可能會使鏈表形成環(huán)狀的妖,從而導(dǎo)致死循環(huán)绣檬。JDK1.8做了改進(jìn),用的是尾插法羔味,不會產(chǎn)生死循環(huán)河咽。

那么,鏈表是怎么形成環(huán)狀的呢赋元?

關(guān)于這一點的解釋忘蟹,我發(fā)現(xiàn)網(wǎng)上文章抄來抄去的飒房,而且都來自左耳朵耗子,更驚奇的是媚值,連配圖都是一模一樣的狠毯。(別問我為什么知道,因為我也看過耗子叔的文章褥芒,哈哈嚼松。然而,菜雞的我锰扶,那篇文章献酗,并沒有看懂。坷牛。罕偎。)

我實在看不下去了,于是一怒之下京闰,就有了這篇文章颜及。我會照著源碼一步一步的分析變量之間的關(guān)系怎么變化的,并有配圖哦蹂楣。

我們從 put()方法開始俏站,最終找到線程不安全的那個方法。這里省略中間不重要的過程痊土,我只把方法的跳轉(zhuǎn)流程貼出來:

//添加元素方法 -> 添加新節(jié)點方法 -> 擴(kuò)容方法 -> 把原數(shù)組元素重新分配到新數(shù)組中
put()  --> addEntry()  --> resize() -->  transfer()

問題就發(fā)生在 transfer 這個方法中肄扎。

圖1

我們假設(shè),原數(shù)組容量只有2施戴,其中一條鏈表上有兩個元素 A,B反浓,如下圖

現(xiàn)在,有兩個線程都執(zhí)行 transfer 方法赞哗。每個線程都會在它們自己的工作內(nèi)存生成一個newTable 的數(shù)組雷则,用于存儲變化后的鏈表,它們互不影響(這里互不影響肪笋,指的是兩個新數(shù)組本身互不影響)月劈。但是,需要注意的是藤乙,它們操作的數(shù)據(jù)卻是同一份猜揪。

因為,真正的數(shù)組中的內(nèi)容在堆中存儲坛梁,它們指向的是同一份數(shù)據(jù)內(nèi)容而姐。就相當(dāng)于,有兩個不同的引用 X划咐,Y拴念,但是它們都指向同一個對象 Z钧萍。這里 X、Y就是兩個線程不同的新數(shù)組政鼠,Z就是堆中的A风瘦,B 等元素對象。

假設(shè)線程一執(zhí)行到了上圖1中所指的代碼①處公般,恰好 CPU 時間片到了万搔,線程被掛起,不能繼續(xù)執(zhí)行了官帘。 記住此時瞬雹,線程一中記錄的 e = A , e.next = B遏佣。

然后線程二正常執(zhí)行挖炬,擴(kuò)容后的數(shù)組長度為 4揽浙, 假設(shè) A状婶,B兩個元素又碰撞到了同一個桶中。然后馅巷,通過幾次 while 循環(huán)后膛虫,采用頭插法,最終呈現(xiàn)的結(jié)構(gòu)如下:

此時钓猬,線程一解掛稍刀,繼續(xù)往下執(zhí)行。注意敞曹,此時線程一账月,記錄的還是 e = A,e.next = B澳迫,因為它還未感知到最新的變化局齿。

我們主要關(guān)注圖1中標(biāo)注的①②③④處的變量變化:

/**
* next = e.next
* e.next = newTable[i]
* newTable[i] = e;
* e = next;
*/

//第一次循環(huán),(偽代碼)
e=A;next=B;
e.next=null //此時線程一的新數(shù)組剛初始化完成,還沒有元素
newTab[i] = A->null //把A節(jié)點頭插到新數(shù)組中
e=B; //下次循環(huán)的e值

第一次循環(huán)結(jié)束后橄登,線程一新數(shù)組的結(jié)構(gòu)如下圖:

然后抓歼,由于 e=B,不為空拢锹,進(jìn)入第二次循環(huán)谣妻。

//第二次循環(huán)
e=B;next=A;  //此時A,B的內(nèi)容已經(jīng)被線程二修改為 B->A->null卒稳,然后被線程一讀到蹋半,所以B的下一個節(jié)點指向A
e.next=A->null  // A->null 為第一次循環(huán)后線程一新數(shù)組的結(jié)構(gòu)
newTab[i] = B->A->null //新節(jié)點B插入之后,線程一新數(shù)組的結(jié)構(gòu)
e=A;  //下次循環(huán)的 e 值

第二次循環(huán)結(jié)束后充坑,線程一新數(shù)組的結(jié)構(gòu)如下圖:

此時减江,由于 e=A闻蛀,不為空,繼續(xù)循環(huán)您市。

//第三次循環(huán)
e=A;next=null;  // A節(jié)點后邊已經(jīng)沒有節(jié)點了
e.next= B->A->null  // B->A->null 為第二次循環(huán)后線程一新數(shù)組的結(jié)構(gòu)
//我們把A插入后觉痛,抽象的表達(dá)為 A->B->A->null,但是茵休,A只能是一個薪棒,不能分身啊
//因此實際上是 e(A).next指向發(fā)生了變化,A的 next 由指向 null 改為指向了 B榕莺,
//而 B 本身又指向A俐芯,因此A和B互相指向,成環(huán)
newTab[i] = A->B 且 B->A 
e=next=null; //e此時為空钉鸯,結(jié)束循環(huán)

第三次循環(huán)結(jié)束后吧史,看下圖,A的指向由 null 唠雕,改為指向為 B贸营,因此 A 和 B 之間成環(huán)。

這時岩睁,有的同學(xué)可能就會問了钞脂,就算他們成環(huán)了,又怎樣捕儒,跟死循環(huán)有什么關(guān)系冰啃?

我們看下 get() 方法(最終調(diào)用 getEntry 方法),

可以看到查找元素時刘莹,只要 e 不為空阎毅,就會一直循環(huán)查找下去。若有某個元素 C 的 hash 值也落在了和 A点弯,B元素同一個桶中扇调,則會由于, A蒲拉,B互相指向肃拜,e.next 永遠(yuǎn)不為空,就會形成死循環(huán)雌团。

結(jié)語

如果本文對你有用燃领,歡迎關(guān)注我哦~

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市锦援,隨后出現(xiàn)的幾起案子猛蔽,更是在濱河造成了極大的恐慌,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,651評論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件曼库,死亡現(xiàn)場離奇詭異区岗,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)毁枯,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,468評論 3 392
  • 文/潘曉璐 我一進(jìn)店門慈缔,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人种玛,你說我怎么就攤上這事藐鹤。” “怎么了赂韵?”我有些...
    開封第一講書人閱讀 162,931評論 0 353
  • 文/不壞的土叔 我叫張陵娱节,是天一觀的道長。 經(jīng)常有香客問我祭示,道長肄满,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,218評論 1 292
  • 正文 為了忘掉前任质涛,我火速辦了婚禮稠歉,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘蹂窖。我一直安慰自己轧抗,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 67,234評論 6 388
  • 文/花漫 我一把揭開白布瞬测。 她就那樣靜靜地躺著,像睡著了一般纠炮。 火紅的嫁衣襯著肌膚如雪月趟。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,198評論 1 299
  • 那天恢口,我揣著相機(jī)與錄音孝宗,去河邊找鬼。 笑死耕肩,一個胖子當(dāng)著我的面吹牛因妇,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播猿诸,決...
    沈念sama閱讀 40,084評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼婚被,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了梳虽?” 一聲冷哼從身側(cè)響起址芯,我...
    開封第一講書人閱讀 38,926評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后谷炸,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體北专,經(jīng)...
    沈念sama閱讀 45,341評論 1 311
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,563評論 2 333
  • 正文 我和宋清朗相戀三年旬陡,在試婚紗的時候發(fā)現(xiàn)自己被綠了拓颓。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,731評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡描孟,死狀恐怖录粱,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情画拾,我是刑警寧澤啥繁,帶...
    沈念sama閱讀 35,430評論 5 343
  • 正文 年R本政府宣布,位于F島的核電站青抛,受9級特大地震影響旗闽,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜蜜另,卻給世界環(huán)境...
    茶點故事閱讀 41,036評論 3 326
  • 文/蒙蒙 一适室、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧举瑰,春花似錦捣辆、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,676評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至耸序,卻和暖如春忍些,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背坎怪。 一陣腳步聲響...
    開封第一講書人閱讀 32,829評論 1 269
  • 我被黑心中介騙來泰國打工罢坝, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人搅窿。 一個月前我還...
    沈念sama閱讀 47,743評論 2 368
  • 正文 我出身青樓嘁酿,卻偏偏與公主長得像,于是被迫代替她去往敵國和親男应。 傳聞我的和親對象是個殘疾皇子闹司,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,629評論 2 354

推薦閱讀更多精彩內(nèi)容