一直以來碳柱，HashMap就是Java面試過程中的彻共福客革答，不管是剛畢業(yè)的，還是工作了好多年的同學(xué)曙强，在Java面試過程中残拐，經(jīng)常會(huì)被問到HashMap相關(guān)的一些問題，而且每次面試都被問到一些自己平時(shí)沒有注意的問題旗扑。因?yàn)镠ashMap不管對(duì)于畢業(yè)生蹦骑，還是對(duì)于老司機(jī)來說，都非常熟悉臀防，熟悉到你經(jīng)常忽略它眠菇。

本著知其然，更要知其所以然的精神袱衷，本人對(duì)JDK 1.8版本的HashMap源碼進(jìn)行了仔細(xì)的學(xué)習(xí)捎废。大家知道，JDK 1.8中HashMap的實(shí)現(xiàn)有了一些改進(jìn)致燥，特別是數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)引進(jìn)了紅黑樹登疗，使得查詢更加的快捷，本文也會(huì)對(duì)相應(yīng)的內(nèi)容進(jìn)行分析，希望大家能有收獲辐益。

一断傲、HashMap基礎(chǔ)

1.1 HashMap的定義

話不多說，首先從HashMap的一些基礎(chǔ)開始智政。我們先看一下HashMap的定義：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

我們可以看出认罩，HashMap繼承了AbstractMap<K,V>抽象類，實(shí)現(xiàn)了Map<K,V>的方法续捂。

1.2 HashMap的屬性

接著垦垂，我們通過源碼看看HashMap的一些重要的常量屬性。

//默認(rèn)容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//鏈表轉(zhuǎn)成紅黑樹的閾值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹轉(zhuǎn)為鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
//存儲(chǔ)方式由鏈表轉(zhuǎn)成紅黑樹的容量的最小閾值
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap中存儲(chǔ)的鍵值對(duì)的數(shù)量
transient int size;
//擴(kuò)容閾值牙瓢，當(dāng)size>=threshold時(shí)劫拗，就會(huì)擴(kuò)容
int threshold;
//HashMap的加載因子
final float loadFactor;

這里我們要知道<<運(yùn)算符的意義，表示移位操作矾克，每次向左移動(dòng)一位(相對(duì)于二進(jìn)制來說)页慷，表示乘以2，此處1<<4表示00001中的1向左移動(dòng)了4位聂渊，變成了10000差购，換算成十進(jìn)制就是2^4=16，也就是HashMap的默認(rèn)容量就是16汉嗽。Java中還有一些位操作符欲逃，比如類似的>>(右移)，還有>>>(無符號(hào)右移)等饼暑，也是需要我們掌握的稳析。這些位操作符的計(jì)算速度很快，我們?cè)谄綍r(shí)的工作中可以使用它們來提升我們系統(tǒng)的性能弓叛。

這里我們需要加載因子(load_factor)彰居，加載因子默認(rèn)為0.75，當(dāng)HashMap中存儲(chǔ)的元素的數(shù)量大于(容量×加載因子)撰筷，也就是默認(rèn)大于16*0.75=12時(shí)陈惰，HashMap會(huì)進(jìn)行擴(kuò)容的操作。

二毕籽、初始化

一般來說抬闯，我們初始化的時(shí)候會(huì)這樣寫：

Map<K,V> map = new HashMap<K,V>();

這個(gè)過程發(fā)生了什么呢？我們看看源碼关筒。

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

我們debug跟蹤時(shí)溶握，會(huì)發(fā)現(xiàn)，這里的initialCapacity并不是我們想象的16蒸播，而是31睡榆，并且會(huì)變化幾次之后萍肆，initialCapacity最終變成了11，這是為什么呢胀屿？說實(shí)話塘揣，我也不清楚，希望有大神可以幫忙解答碉纳。

我們繼續(xù)勿负。初始化時(shí)馏艾，會(huì)首先判斷初始容量是否小于0劳曹，如果小于0，會(huì)拋出異常琅摩。接著铁孵，判斷初始容量是否大于最大的容量(即2^31)，如果大于房资，將初始容量設(shè)置為最大初始容量蜕劝。緊接著，判斷加載因子：如果小于等于0轰异，或者不是一個(gè)數(shù)字岖沛，都會(huì)拋出異常。等這些校驗(yàn)完成之后搭独，會(huì)將HashMap的加載因子和擴(kuò)容的閾值設(shè)置上婴削。這里需要注意一下，threshold(閾值)=capacity*loadFactor牙肝。而我們的閾值是怎么來的呢唉俗？我們看一下tableSizeFor()這個(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;
}

我們可以看到英文注釋：Returns a power of two size for the given target capacity.(返回目標(biāo)容量對(duì)應(yīng)的2的冪次方配椭。)我們可以想象一下虫溜，如果我們將初始值設(shè)置為非2的冪次方的數(shù)值，比如我們?cè)O(shè)置為19股缸，最終我們通過這個(gè)方法衡楞，得到的數(shù)組大小是多少呢？我們可以計(jì)算一下敦姻。

cap=19
int n=cap-1;//得到n=18瘾境，換算為二進(jìn)制為10010
n|=n>>>1;//表示n無符號(hào)右移一位后，與n按位或計(jì)算替劈，其中n>>>1=01001寄雀，按位或結(jié)果為11011
n|=n>>>2;//其中n>>>2=00110,按位或的結(jié)果為11111，下面幾步類似陨献，最終得到的結(jié)果是n=11111(二進(jìn)制盒犹，也就是2^5-1，31)

最終計(jì)算得到的結(jié)果是32

因?yàn)閏ap最大為2^31，我們可以知道急膀，這個(gè)方法的最終目的就是返回比cap大的最小的2的冪次方沮协。

三、put()

下面卓嫂，我們開始解析HashMap中最重要的一個(gè)方法:put()慷暂。

//如果原來存在相同的key-value，原來的value會(huì)被替換掉
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

下面我們首先看一下hash(key)晨雳，然后再看一下putVal()方法行瑞，這兩個(gè)方法是精髓。

3.1 hash(key)

先上源碼：

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

我們可以發(fā)現(xiàn)餐禁，當(dāng)key=null時(shí)血久，也是有hash值的，是0帮非，所以氧吐，HashMap的key是可以為null的，對(duì)比HashTable源碼我們可以知道末盔，HashTable的key直接進(jìn)行了hashCode筑舅，如果key為null時(shí)，會(huì)拋出異常陨舱，所以HashTable的key不可以是null翠拣。

我們還能發(fā)現(xiàn)hash值的計(jì)算，首先計(jì)算出key的hashCode()為h隅忿，然后與h無條件右移16位后的二進(jìn)制進(jìn)行按位異或(^)得到最終的hash值心剥，這個(gè)hash值就是鍵值對(duì)存儲(chǔ)在數(shù)組中的位置。

備注：異或的操作如下：0 ^ 0=0背桐，1 ^ 1 =0优烧，0 ^ 1=1，1 ^ 0=1链峭，也就是相同時(shí)返回0畦娄，不同時(shí)返回1。

我們目前不去深究為什么這么設(shè)計(jì)弊仪，我們只要知道熙卡，這樣設(shè)計(jì)的目的是為了讓hash值分布的更加均勻即可。

3.2 putVal()方法

3.2.1 源碼

我們直接看源碼励饵。

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;
    if ((p = tab[i = (n - 1) & hash]) == null)
        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))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    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;
            }
        }
        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)
        resize();
    afterNodeInsertion(evict);
    return null;
}

我們慢慢來分析驳癌。首先看入?yún)ⅲ?/p>

• hash：表示key的hash值
• key：待存儲(chǔ)的key值
• value：待存儲(chǔ)的value值，從這個(gè)方法可以知道，HashMap底層存儲(chǔ)的是key-value的鍵值對(duì)，不只是存儲(chǔ)了value
• onlyIfAbsent：這個(gè)參數(shù)表示，是否需要替換相同的value值堕油，如果為true甜滨，表示不替換已經(jīng)存在的value
• evict：如果為false乐严，表示數(shù)組是新增模式

我們看到put時(shí)所傳入的參數(shù)put(hash(key), key, value, false, true)，可以得到相應(yīng)的含義衣摩。

3.2.2 HashMap的數(shù)據(jù)結(jié)構(gòu)

在繼續(xù)下一步分析之前昂验，我們首先需要看一下HashMap底層的數(shù)據(jù)結(jié)構(gòu)。

HashMap的數(shù)據(jù)結(jié)構(gòu)

我們可以看到艾扮，HashMap底層是數(shù)組加單向鏈表或紅黑樹實(shí)現(xiàn)的(這是JDK 1.8里面的內(nèi)容既琴，之前的版本純粹是數(shù)組加單向鏈表實(shí)現(xiàn))。

下面我們看一下HashMap的一些重要的內(nèi)部類栏渺。首先最重要的就是Node類呛梆，即HashMap內(nèi)部定義的單向鏈表

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    
    //省略一些代碼

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

我們重點(diǎn)看一下數(shù)據(jù)結(jié)構(gòu)，Node中存儲(chǔ)了key的hash值磕诊，鍵值對(duì)，同時(shí)還有下一個(gè)鏈表元素纹腌。我們重點(diǎn)關(guān)注一些equals這個(gè)方法霎终，這個(gè)方法在什么時(shí)候會(huì)用到呢？當(dāng)我們算出的key的hash值相同時(shí)升薯，put方法并不會(huì)報(bào)錯(cuò)莱褒，而是繼續(xù)向這個(gè)hash值的鏈表中添加元素。我們會(huì)調(diào)用equals方法來比對(duì)key和value是否相同涎劈，如果equals方法返回false广凸，會(huì)繼續(xù)向鏈表的尾部添加一個(gè)鍵值對(duì)。

當(dāng)然蛛枚，在JDK 1.8中引入了紅黑樹的概念谅海，內(nèi)部定義為TreeNode，對(duì)紅黑樹感興趣的同學(xué)可以看看相關(guān)的文檔蹦浦，引入紅黑樹是為了提升查詢的效率扭吁。

3.2.3 繼續(xù)分析putVal()方法

首先判斷當(dāng)前HashMap的數(shù)組是否為空，如果為空盲镶，則調(diào)用resize()方法侥袜，對(duì)HashMap進(jìn)行擴(kuò)容，這次擴(kuò)容的結(jié)果就是HashMap的初始化一個(gè)長度為16的數(shù)組溉贿。獲取到數(shù)組的長度n枫吧。代碼如下：

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

接著，根據(jù)長度-1和hash值進(jìn)行按位與運(yùn)算宇色，算出hash值對(duì)應(yīng)于數(shù)組中的位置九杂，從tab中將這個(gè)位置上面的內(nèi)容取出闽寡，判斷為null時(shí)，在這個(gè)位置新增一個(gè)Node尼酿。代碼如下：

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
    
// Create a regular (non-tree) node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

如果同樣的位置取到了數(shù)據(jù)爷狈，也就是這個(gè)hash值對(duì)應(yīng)數(shù)組的位置上面已經(jīng)有了鍵值對(duì)存在，這時(shí)候我們就需要做一些動(dòng)作了裳擎。首先涎永，我們判斷這個(gè)Node，也就是p的hash值是否與傳入的hash相等鹿响，然后接著判斷key是否相等(這里判斷key是否相等羡微，用了一個(gè)或運(yùn)算)。如果判斷通過惶我，表示要傳入的key-val鍵值對(duì)就是tab[i]位置上面的鍵值對(duì)妈倔，直接替換即可，不用管后面是鏈表還是紅黑樹绸贡。代碼如下：

Node<K,V> e; K k;
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

如果tab[i]的key不是我們傳入的key盯蝴，下面我們首先要判斷p這個(gè)Node是不是紅黑樹，如果是紅黑樹听怕，直接向紅黑樹新增一個(gè)數(shù)據(jù)捧挺。向紅黑樹新增數(shù)據(jù)的代碼我們后續(xù)再解析，目前先不進(jìn)行分析尿瞭。代碼如下：

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

下面闽烙，當(dāng)p是單向鏈表時(shí)，我們遍歷鏈表進(jìn)行插入等操作声搁。找到鏈表的尾部黑竞，將節(jié)點(diǎn)新增到尾部。如果鏈表的長度大于等于紅黑樹化的閾值-1疏旨，就將桶(也就是鏈表)轉(zhuǎn)成紅黑樹存儲(chǔ)數(shù)據(jù)很魂。如果在鏈表中還存在相同的key，直接替換舊的value即可充石。

    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            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;
    }
    
if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

最后莫换，還有一個(gè)操作，大家千萬不要忽略骤铃，也就是判斷當(dāng)前的鍵值對(duì)數(shù)量是否即將超過閾值拉岁，如果即將超過，需要進(jìn)行resize()操作惰爬。

if (++size > threshold)
    resize();

下一篇文章我們將著重分析resize()和get()的源碼喊暖。