HashMap源碼及常見面試題

HashMap 底層是如何實(shí)現(xiàn)的摔认？

在 JDK 1.7 中 HashMap 是以數(shù)組加鏈表的形式組成的，JDK 1.8 之后新增了紅黑樹的組成結(jié)構(gòu)轻腺，當(dāng)鏈表大于 8 并且容量大于 64 時(shí)歉甚，鏈表結(jié)構(gòu)會轉(zhuǎn)換成紅黑樹結(jié)構(gòu)。

img

數(shù)組中的元素我們稱之為哈希桶戒傻，它的定義如下：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    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;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

JDK 1.8 之所以添加紅黑樹是因?yàn)橐坏╂湵磉^長税手，會嚴(yán)重影響 HashMap 的性能蜂筹，而紅黑樹具有快速增刪改查的特點(diǎn)，這樣就可以有效的解決鏈表過長時(shí)操作比較慢的問題芦倒。

HashMap 源碼中包含了以下幾個(gè)屬性：

// HashMap 初始化長度,使用位運(yùn)算艺挪，長度一定是2的N次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap 最大長度
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824
// 默認(rèn)的加載因子 (擴(kuò)容因子)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 當(dāng)鏈表長度大于此值且容量大于 64 時(shí)
static final int TREEIFY_THRESHOLD = 8;
// 轉(zhuǎn)換鏈表的臨界值，當(dāng)元素小于此值時(shí)，會將紅黑樹結(jié)構(gòu)轉(zhuǎn)換成鏈表結(jié)構(gòu)
static final int UNTREEIFY_THRESHOLD = 6;
// 最小樹容量
static final int MIN_TREEIFY_CAPACITY =

HashMap 源碼中三個(gè)重要方法：查詢麻裳、新增和數(shù)據(jù)擴(kuò)容口蝠。

先來看查詢源碼：

public V get(Object key) {
    Node<K,V> e;
    // 對 key 進(jìn)行哈希操作
    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;
    // 非空判斷
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判斷第一個(gè)元素是否是要查詢的元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 下一個(gè)節(jié)點(diǎn)非空判斷
        if ((e = first.next) != null) {
            // 如果第一節(jié)點(diǎn)是樹結(jié)構(gòu)，則使用 getTreeNode 直接獲取相應(yīng)的數(shù)據(jù)(紅黑樹的搜索方法就不放源碼了)
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do { // 非樹結(jié)構(gòu)津坑，循環(huán)節(jié)點(diǎn)判斷
                // hash 相等并且 key 相同妙蔗，則返回此節(jié)點(diǎn)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

從以上源碼可以看出，當(dāng)哈希沖突時(shí)我們需要通過判斷 key 值是否相等疆瑰，才能確認(rèn)此元素是不是我們想要的元素眉反。這里計(jì)算key的下標(biāo)使用了first = tab[(n - 1) & hash]，當(dāng)length總是2的n次方時(shí)穆役，tab[(n - 1) & hash運(yùn)算等價(jià)于對n取模寸五，也就是hash%n，但是&比%具有更高的效率耿币。

  1. 保證不會發(fā)生數(shù)組越界

    數(shù)組的長度按規(guī)定一定是2的冪（2的n次方）因此，數(shù)組的長度的二進(jìn)制形式是：10000…000, 1后面有一堆0。tab.length - 1 的二進(jìn)制形式就是01111…111, 0后面有一堆1楼眷。最高位是0, 和hash值相“與”限佩，結(jié)果值一定不會比數(shù)組的長度值大，因此也就不會發(fā)生數(shù)組越界蹈集。

  2. 保證元素盡可能的均勻分布

    tab.length一定是一個(gè)偶數(shù)烁试，tab.length - 1一定是一個(gè)奇數(shù)。

    假設(shè)現(xiàn)在數(shù)組的長度（tab.length）為16拢肆，減去1后（tab.length - 1）就是15减响，15對應(yīng)的二進(jìn)制是：1111。

    現(xiàn)在假設(shè)有兩個(gè)元素需要插入郭怪，一個(gè)哈希值是8支示，二進(jìn)制是1000，一個(gè)哈希值是9鄙才，二進(jìn)制是1001颂鸿。和1111“與”運(yùn)算后，結(jié)果分別是1000和1001攒庵，它們被分配在了數(shù)組的不同位置嘴纺，這樣，哈希的分布非常均勻浓冒。

    那么栽渴，如果數(shù)組長度是奇數(shù)呢？減去1后（tab.length - 1）就是偶數(shù)了稳懒，偶數(shù)對應(yīng)的二進(jìn)制最低位一定是 0闲擦，例如14二進(jìn)制1110。對上面兩個(gè)數(shù)子分別“與”運(yùn)算，得到1000和1000墅冷。結(jié)果都是一樣的值纯路。那么，哈希值8和9的元素都被存儲在數(shù)組同一個(gè)index位置的鏈表中寞忿。在操作的時(shí)候驰唬，鏈表中的元素越多，效率越低腔彰，因?yàn)橐煌５膶︽湵硌h(huán)比較定嗓。

HashMap 第二個(gè)重要方法：新增方法，源碼如下：

public V put(K key, V value) {
    // 對 key 進(jìn)行哈希操作
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 哈希表為空則創(chuàng)建表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 根據(jù) key 的哈希值計(jì)算出要插入的數(shù)組索引 i
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果 table[i] 等于 null萍桌，則直接插入
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果 key 已經(jīng)存在了宵溅，直接覆蓋 value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果 key 不存在，判斷是否為紅黑樹
        else if (p instanceof TreeNode)
            // 紅黑樹直接插入鍵值對
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 為鏈表結(jié)構(gòu)上炎，循環(huán)準(zhǔn)備插入
            for (int binCount = 0; ; ++binCount) {
                // 下一個(gè)元素為空時(shí)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 轉(zhuǎn)換為紅黑樹進(jìn)行處理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //  key 已經(jīng)存在直接覆蓋 value
                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;
    // 超過最大容量恃逻，擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

新增方法的執(zhí)行流程，如下圖所示：
image.png

HashMap 第三個(gè)重要的方法是擴(kuò)容方法藕施，源碼如下：

final Node<K,V>[] resize() {
    // 擴(kuò)容前的數(shù)組
    Node<K,V>[] oldTab = table;
    // 擴(kuò)容前的數(shù)組的大小和閾值
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    // 預(yù)定義新數(shù)組的大小和閾值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 超過最大值就不再擴(kuò)容了
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 擴(kuò)大容量為當(dāng)前容量的兩倍寇损，但不能超過 MAXIMUM_CAPACITY
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 當(dāng)前數(shù)組沒有數(shù)據(jù)，使用初始化的值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 如果初始化的值為 0裳食，則使用默認(rèn)的初始化容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新的容量等于 0
    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"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 開始擴(kuò)容矛市，將新的容量賦值給 table
    table = newTab;
    // 原數(shù)據(jù)不為空，將原數(shù)據(jù)復(fù)制到新 table 中
    if (oldTab != null) {
        // 根據(jù)容量循環(huán)數(shù)組诲祸，復(fù)制非空元素到新 table
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果鏈表只有一個(gè)浊吏，則進(jìn)行直接賦值
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 紅黑樹相關(guān)的操作
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 鏈表復(fù)制，JDK 1.8 擴(kuò)容優(yōu)化部分
                    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;
                        }
                        // 原索引 + oldCap
                        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;
                    }
                    // 將原索引 + oldCap 放到哈希桶中
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

從以上源碼可以看出救氯，JDK 1.8 在擴(kuò)容時(shí)并沒有像 JDK 1.7 那樣找田，重新計(jì)算每個(gè)元素的哈希值，而是通過高位運(yùn)算（e.hash & oldCap）來確定元素是否需要移動着憨，比如 key1 的信息如下：

  • key1.hash = 10 0000 1010
  • oldCap = 16 0001 0000

使用 e.hash & oldCap 得到的結(jié)果墩衙，高一位為 0，當(dāng)結(jié)果為 0 時(shí)表示元素在擴(kuò)容時(shí)位置不會發(fā)生任何變化甲抖，而 key 2 信息如下：

  • key2.hash = 10 0001 0001
  • oldCap = 16 0001 0000

還是看不懂為什么的話看看下面的圖漆改，a表示擴(kuò)容hash前后hash的值不變的情況，b表示擴(kuò)容前后hash的值變化了的情況准谚。

image.png

這時(shí)候得到的結(jié)果挫剑，高一位為 1，當(dāng)結(jié)果為 1 時(shí)氛魁，表示元素在擴(kuò)容時(shí)位置發(fā)生了變化暮顺，新的下標(biāo)位置等于原下標(biāo)位置 + 原數(shù)組長度，如下圖所示：

image.png

HashMap 死循環(huán)分析

以 JDK 1.7 為例秀存，假設(shè) HashMap 默認(rèn)大小為 2捶码，原本 HashMap 中有一個(gè)元素 key(5)，我們再使用兩個(gè)線程：t1 添加元素 key(3)或链，t2 添加元素 key(7)惫恼，當(dāng)元素 key(3) 和 key(7) 都添加到 HashMap 中之后，線程 t1 在執(zhí)行到 Entry<K,V> next = e.next; 時(shí)澳盐，交出了 CPU 的使用權(quán)祈纯，源碼如下：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next; // 線程一執(zhí)行此處
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

那么此時(shí)線程 t1 中的 e 指向了 key(3)，而 next 指向了 key(7) 叼耙；之后線程 t2 重新 rehash 之后鏈表的順序被反轉(zhuǎn)腕窥，鏈表的位置變成了 key(5) → key(7) → key(3)，其中 “→” 用來表示下一個(gè)元素筛婉。

當(dāng) t1 重新獲得執(zhí)行權(quán)之后簇爆，先執(zhí)行 newTalbe[i] = e 把 key(3) 的 next 設(shè)置為 key(7)，而下次循環(huán)時(shí)查詢到 key(7) 的 next 元素為 key(3)爽撒，于是就形成了 key(3) 和 key(7) 的循環(huán)引用入蛆，因此就導(dǎo)致了死循環(huán)的發(fā)生，如下圖所示：

image.png

當(dāng)然發(fā)生死循環(huán)的原因是 JDK 1.7 鏈表插入方式為首部倒序插入硕勿，這個(gè)問題在 JDK 1.8 得到了改善哨毁，變成了尾部正序插入。

什么是加載因子源武？加載因子為什么是 0.75扼褪？

加載因子也叫擴(kuò)容因子或負(fù)載因子，用來判斷什么時(shí)候進(jìn)行擴(kuò)容的粱栖，假如加載因子是 0.5迎捺，HashMap 的初始化容量是 16，那么當(dāng) HashMap 中有 16*0.5=8 個(gè)元素時(shí)查排，HashMap 就會進(jìn)行擴(kuò)容凳枝。

那加載因子為什么是 0.75 而不是 0.5 或者 1.0 呢？

這其實(shí)是出于容量和性能之間平衡的結(jié)果：

  • 當(dāng)加載因子設(shè)置比較大的時(shí)候跋核，擴(kuò)容的門檻就被提高了岖瑰，擴(kuò)容發(fā)生的頻率比較低，占用的空間會比較小砂代，但此時(shí)發(fā)生 Hash 沖突的幾率就會提升蹋订，因此需要更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來存儲元素，這樣對元素的操作時(shí)間就會增加刻伊，運(yùn)行效率也會因此降低露戒；
  • 而當(dāng)加載因子值比較小的時(shí)候椒功，擴(kuò)容的門檻會比較低，因此會占用更多的空間智什，此時(shí)元素的存儲就比較稀疏动漾，發(fā)生哈希沖突的可能性就比較小，因此操作性能會比較高荠锭。

所以綜合了以上情況就取了一個(gè) 0.5 到 1.0 的平均數(shù) 0.75 作為加載因子旱眯。

總結(jié)

本文過后應(yīng)該能回答如下問題：

  • JDK 1.8 HashMap 擴(kuò)容時(shí)做了哪些優(yōu)化？
  • 加載因子為什么是 0.75证九？
  • 當(dāng)有哈希沖突時(shí)删豺，HashMap 是如何查找并確認(rèn)元素的？
  • HashMap 源碼中有哪些重要的方法愧怜？
  • HashMap 是如何導(dǎo)致死循環(huán)的
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末呀页，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子拥坛，更是在濱河造成了極大的恐慌赔桌，老刑警劉巖，帶你破解...
    沈念sama閱讀 216,402評論 6贊 499
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件渴逻，死亡現(xiàn)場離奇詭異疾党，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)惨奕，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,377評論 3贊 392
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門雪位，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人梨撞，你說我怎么就攤上這事雹洗。” “怎么了卧波？”我有些...
    開封第一講書人閱讀 162,483評論 0贊 353
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵时肿，是天一觀的道長。 經(jīng)常有香客問我港粱，道長螃成，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,165評論 1贊 292
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任查坪，我火速辦了婚禮寸宏，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘偿曙。我一直安慰自己氮凝，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,176評論 6贊 388
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布望忆。 她就那樣靜靜地躺著罩阵，像睡著了一般竿秆。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上稿壁，一...
    開封第一講書人閱讀 51,146評論 1贊 297
  • 城市分裂傳說
    那天幽钢，我揣著相機(jī)與錄音，去河邊找鬼常摧。 笑死，一個(gè)胖子當(dāng)著我的面吹牛威创，可吹牛的內(nèi)容都是我干的落午。 我是一名探鬼主播，決...
    沈念sama閱讀 40,032評論 3贊 417
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼肚豺，長吁一口氣：“原來是場噩夢啊……” “哼溃斋！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起吸申，我...
    開封第一講書人閱讀 38,896評論 0贊 274
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對情侶失蹤梗劫，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后截碴，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體梳侨，經(jīng)...
    沈念sama閱讀 45,311評論 1贊 310
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,536評論 2贊 332
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年日丹，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了走哺。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,696評論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡哲虾，死狀恐怖丙躏，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情束凑，我是刑警寧澤晒旅，帶...
    沈念sama閱讀 35,413評論 5贊 343
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站汪诉，受9級特大地震影響废恋，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜扒寄，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,008評論 3贊 325
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一拴签、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧旗们，春花似錦蚓哩、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評論 0贊 22
  • 一樁弒父案岸梨，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽喜颁。三九已至，卻和暖如春曹阔，著一層夾襖步出監(jiān)牢的瞬間半开，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,815評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工赃份， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留寂拆，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,698評論 2贊 368
  • 代替公主和親
    正文 我出身青樓抓韩，卻偏偏與公主長得像纠永，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子谒拴，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,592評論 2贊 353