1 概述
本文將從幾個(gè)常用方法下手业稼，來閱讀HashMap的源碼伏钠。
按照從構(gòu)造方法->常用API（增横漏、刪、改熟掂、查）的順序來閱讀源碼缎浇，并會(huì)講解閱讀方法中涉及的一些變量的意義。了解HashMap的特點(diǎn)赴肚、適用場(chǎng)景素跺。

如果本文中有不正確的結(jié)論、說法誉券，請(qǐng)大家提出和我討論指厌，共同進(jìn)步，謝謝踊跟。

2 概要
概括的說踩验，HashMap 是一個(gè)關(guān)聯(lián)數(shù)組、哈希表琴锭，它是線程不安全的晰甚，允許key為null,value為null。遍歷時(shí)無序决帖。
其底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組稱之為哈希桶厕九，每個(gè)桶里面放的是鏈表，鏈表中的每個(gè)節(jié)點(diǎn)地回，就是哈希表中的每個(gè)元素扁远。
在JDK8中俊鱼，當(dāng)鏈表長度達(dá)到8，會(huì)轉(zhuǎn)化成紅黑樹畅买，以提升它的查詢并闲、插入效率，它實(shí)現(xiàn)了Map<K,V>, Cloneable, Serializable接口谷羞。

因其底層哈希桶的數(shù)據(jù)結(jié)構(gòu)是數(shù)組帝火，所以也會(huì)涉及到擴(kuò)容的問題。

當(dāng)HashMap的容量達(dá)到threshold域值時(shí)湃缎，就會(huì)觸發(fā)擴(kuò)容犀填。擴(kuò)容前后，哈希桶的長度一定會(huì)是2的次方嗓违。
這樣在根據(jù)key的hash值尋找對(duì)應(yīng)的哈希桶時(shí)九巡，可以用位運(yùn)算替代取余操作，更加高效蹂季。

而key的hash值冕广，并不僅僅只是key對(duì)象的hashCode()方法的返回值，還會(huì)經(jīng)過擾動(dòng)函數(shù)的擾動(dòng)偿洁，以使hash值更加均衡撒汉。
因?yàn)閔ashCode()是int類型，取值范圍是40多億父能，只要哈希函數(shù)映射的比較均勻松散神凑，碰撞幾率是很小的。
但就算原本的hashCode()取得很好何吝，每個(gè)key的hashCode()不同溉委，但是由于HashMap的哈希桶的長度遠(yuǎn)比hash取值范圍小，默認(rèn)是16爱榕，所以當(dāng)對(duì)hash值以桶的長度取余瓣喊，以找到存放該key的桶的下標(biāo)時(shí)，由于取余是通過與操作完成的黔酥，會(huì)忽略hash值的高位藻三。因此只有hashCode()的低位參加運(yùn)算，發(fā)生不同的hash值跪者，但是得到的index相同的情況的幾率會(huì)大大增加棵帽，這種情況稱之為hash碰撞。 即渣玲，碰撞率會(huì)增大逗概。

擾動(dòng)函數(shù)就是為了解決hash碰撞的。它會(huì)綜合hash值高位和低位的特征忘衍，并存放在低位逾苫，因此在與運(yùn)算時(shí)卿城，相當(dāng)于高低位一起參與了運(yùn)算，以減少hash碰撞的概率铅搓。（在JDK8之前瑟押，擾動(dòng)函數(shù)會(huì)擾動(dòng)四次，JDK8簡(jiǎn)化了這個(gè)操作）

擴(kuò)容操作時(shí)星掰，會(huì)new一個(gè)新的Node數(shù)組作為哈希桶多望，然后將原哈希表中的所有數(shù)據(jù)(Node節(jié)點(diǎn))移動(dòng)到新的哈希桶中，相當(dāng)于對(duì)原哈希表中所有的數(shù)據(jù)重新做了一個(gè)put操作氢烘。所以性能消耗很大便斥，可想而知，在哈希表的容量越大時(shí)威始，性能消耗越明顯。

擴(kuò)容時(shí)像街，如果發(fā)生過哈希碰撞黎棠，節(jié)點(diǎn)數(shù)小于8個(gè)。則要根據(jù)鏈表上每個(gè)節(jié)點(diǎn)的哈希值镰绎，依次放入新哈希桶對(duì)應(yīng)下標(biāo)位置脓斩。
因?yàn)閿U(kuò)容是容量翻倍，所以原鏈表上的每個(gè)節(jié)點(diǎn)畴栖，現(xiàn)在可能存放在原來的下標(biāo)随静，即low位， 或者擴(kuò)容后的下標(biāo)吗讶，即high位燎猛。 high位= low位+原哈希桶容量
如果追加節(jié)點(diǎn)后，鏈表數(shù)量》=8照皆，則轉(zhuǎn)化為紅黑樹

由迭代器的實(shí)現(xiàn)可以看出重绷，遍歷HashMap時(shí)，順序是按照哈希桶從低到高膜毁，鏈表從前往后昭卓，依次遍歷的。屬于無序集合瘟滨。

整個(gè)HashMap示意圖：圖片來源于網(wǎng)絡(luò)候醒，侵刪：

HashMap的源碼中，充斥個(gè)各種位運(yùn)算代替常規(guī)運(yùn)算的地方杂瘸，以提升效率：

• 與運(yùn)算替代模運(yùn)算倒淫。用 hash & (table.length-1) 替代 hash % (table.length)
• 用if ((e.hash & oldCap) == 0)判斷擴(kuò)容后，節(jié)點(diǎn)e處于低區(qū)還是高區(qū)胧沫。

3 鏈表節(jié)點(diǎn)Node
在開始之前昌简，我們先看一下掛載在哈希表上的元素占业，鏈表的結(jié)構(gòu)：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;//哈希值
    final K key;//key
    V value;//value
    Node<K,V> next;//鏈表后置節(jié)點(diǎn)

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

    //每一個(gè)節(jié)點(diǎn)的hash值，是將key的hashCode 和 value的hashCode 亦或得到的纯赎。
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    //設(shè)置新的value 同時(shí)返回舊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;
    }
}

由此可知谦疾，這是一個(gè)單鏈表~。
每一個(gè)節(jié)點(diǎn)的hash值犬金，是將key的hashCode 和 value的hashCode 亦或得到的念恍。

4 構(gòu)造函數(shù)
//最大容量 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)的加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//哈希桶，存放鏈表晚顷。 長度是2的N次方峰伙，或者初始化時(shí)為0.
transient Node<K,V>[] table;

//加載因子，用于計(jì)算哈希表元素?cái)?shù)量的閾值该默。  threshold = 哈希桶.length * loadFactor;
final float loadFactor;
//哈希表內(nèi)元素?cái)?shù)量的閾值瞳氓，當(dāng)哈希表內(nèi)元素?cái)?shù)量超過閾值時(shí)，會(huì)發(fā)生擴(kuò)容resize()栓袖。
int threshold;

public HashMap() {
    //默認(rèn)構(gòu)造函數(shù)匣摘，賦值加載因子為默認(rèn)的0.75f
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
    //指定初始化容量的構(gòu)造函數(shù)
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//同時(shí)指定初始化容量 以及 加載因子， 用的很少裹刮，一般不會(huì)修改loadFactor
public HashMap(int initialCapacity, float loadFactor) {
    //邊界處理
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //初始容量最大不能超過2的30次方
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //顯然加載因子不能為負(fù)數(shù)
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //設(shè)置閾值為  》=初始化容量的 2的n次方的值
    this.threshold = tableSizeFor(initialCapacity);
}
//新建一個(gè)哈希表音榜，同時(shí)將另一個(gè)map m 里的所有元素加入表中
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

//根據(jù)期望容量cap，返回2的n次方形式的 哈希桶的實(shí)際容量 length捧弃。 返回值一般會(huì)>=cap 
static final int tableSizeFor(int cap) {
//經(jīng)過下面的 或 和位移 運(yùn)算赠叼， n最終各位都是1。
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    //判斷n是否越界违霞，返回 2的n次方作為 table（哈希桶）的閾值
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

//將另一個(gè)Map的所有元素加入表中嘴办，參數(shù)evict初始化時(shí)為false，其他情況為true
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    //拿到m的元素?cái)?shù)量
    int s = m.size();
    //如果數(shù)量大于0
    if (s > 0) {
        //如果當(dāng)前表是空的
        if (table == null) { // pre-size
            //根據(jù)m的元素?cái)?shù)量和當(dāng)前表的加載因子买鸽，計(jì)算出閾值
            float ft = ((float)s / loadFactor) + 1.0F;
            //修正閾值的邊界 不能超過MAXIMUM_CAPACITY
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            //如果新的閾值大于當(dāng)前閾值
            if (t > threshold)
                //返回一個(gè) 》=新的閾值的 滿足2的n次方的閾值
                threshold = tableSizeFor(t);
        }
        //如果當(dāng)前元素表不是空的户辞，但是 m的元素?cái)?shù)量大于閾值，說明一定要擴(kuò)容癞谒。
        else if (s > threshold)
            resize();
        //遍歷 m 依次將元素加入當(dāng)前表中底燎。
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

先看一下擴(kuò)容函數(shù)： 這是一個(gè)重點(diǎn)！重點(diǎn)弹砚！重點(diǎn)双仍！
初始化或加倍哈希桶大小。如果是當(dāng)前哈希桶是null,分配符合當(dāng)前閾值的初始容量目標(biāo)桌吃。
否則朱沃，因?yàn)槲覀償U(kuò)容成以前的兩倍。
在擴(kuò)容時(shí)，要注意區(qū)分以前在哈希桶相同index的節(jié)點(diǎn)逗物，現(xiàn)在是在以前的index里搬卒，還是index+oldlength 里

final Node<K,V>[] resize() {
//oldTab 為當(dāng)前表的哈希桶
Node<K,V>[] oldTab = table;
//當(dāng)前哈希桶的容量 length
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//當(dāng)前的閾值
int oldThr = threshold;
//初始化新的容量和閾值為0
int newCap, newThr = 0;
//如果當(dāng)前容量大于0
if (oldCap > 0) {
//如果當(dāng)前容量已經(jīng)到達(dá)上限
if (oldCap >= MAXIMUM_CAPACITY) {
//則設(shè)置閾值是2的31次方-1
threshold = Integer.MAX_VALUE;
//同時(shí)返回當(dāng)前的哈希桶，不再擴(kuò)容
return oldTab;
}//否則新的容量為舊的容量的兩倍翎卓。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)//如果舊的容量大于等于默認(rèn)初始容量16
//那么新的閾值也等于舊的閾值的兩倍
newThr = oldThr << 1; // double threshold
}//如果當(dāng)前表是空的契邀，但是有閾值。代表是初始化時(shí)指定了容量失暴、閾值的情況
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;//那么新表的容量就等于舊的閾值
else {}//如果當(dāng)前表是空的坯门，而且也沒有閾值。代表是初始化時(shí)沒有任何容量/閾值參數(shù)的情況 // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//此時(shí)新表的容量為默認(rèn)的容量 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的閾值為默認(rèn)容量16 * 默認(rèn)加載因子0.75f = 12
}
if (newThr == 0) {//如果新的閾值是0逗扒，對(duì)應(yīng)的是 當(dāng)前表是空的古戴，但是有閾值的情況
float ft = (float)newCap * loadFactor;//根據(jù)新表容量 和 加載因子 求出新的閾值
//進(jìn)行越界修復(fù)
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新閾值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//根據(jù)新的容量 構(gòu)建新的哈希桶
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//更新哈希桶引用
table = newTab;
//如果以前的哈希桶中有元素
//下面開始將當(dāng)前哈希桶中的所有節(jié)點(diǎn)轉(zhuǎn)移到新的哈希桶中
if (oldTab != null) {
//遍歷老的哈希桶
for (int j = 0; j < oldCap; ++j) {
//取出當(dāng)前的節(jié)點(diǎn) e
Node<K,V> e;
//如果當(dāng)前桶中有元素,則將鏈表賦值給e
if ((e = oldTab[j]) != null) {
//將原哈希桶置空以便GC
oldTab[j] = null;
//如果當(dāng)前鏈表中就一個(gè)元素，（沒有發(fā)生哈希碰撞）
if (e.next == null)
//直接將這個(gè)元素放置在新的哈希桶里矩肩。
//注意這里取下標(biāo) 是用 哈希值 與 桶的長度-1 现恼。 由于桶的長度是2的n次方，這么做其實(shí)是等于 一個(gè)模運(yùn)算黍檩。但是效率更高
newTab[e.hash & (newCap - 1)] = e;
//如果發(fā)生過哈希碰撞 ,而且是節(jié)點(diǎn)數(shù)超過8個(gè)述暂，轉(zhuǎn)化成了紅黑樹（暫且不談 避免過于復(fù)雜， 后續(xù)專門研究一下紅黑樹）
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果發(fā)生過哈希碰撞建炫，節(jié)點(diǎn)數(shù)小于8個(gè)。則要根據(jù)鏈表上每個(gè)節(jié)點(diǎn)的哈希值疼蛾，依次放入新哈希桶對(duì)應(yīng)下標(biāo)位置肛跌。
else { // preserve order
//因?yàn)閿U(kuò)容是容量翻倍，所以原鏈表上的每個(gè)節(jié)點(diǎn)察郁，現(xiàn)在可能存放在原來的下標(biāo)衍慎，即low位， 或者擴(kuò)容后的下標(biāo)皮钠，即high位稳捆。 high位= low位+原哈希桶容量
//低位鏈表的頭結(jié)點(diǎn)、尾節(jié)點(diǎn)
Node<K,V> loHead = null, loTail = null;
//高位鏈表的頭節(jié)點(diǎn)麦轰、尾節(jié)點(diǎn)
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//臨時(shí)節(jié)點(diǎn) 存放e的下一個(gè)節(jié)點(diǎn)
do {
next = e.next;
//這里又是一個(gè)利用位運(yùn)算 代替常規(guī)運(yùn)算的高效點(diǎn)： 利用哈希值 與 舊的容量乔夯，可以得到哈希值去模后，是大于等于oldCap還是小于oldCap款侵，等于0代表小于oldCap末荐，應(yīng)該存放在低位，否則存放在高位
if ((e.hash & oldCap) == 0) {
//給頭尾節(jié)點(diǎn)指針賦值
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}//高位也是相同的邏輯
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}//循環(huán)直到鏈表結(jié)束
} while ((e = next) != null);
//將低位鏈表存放在原index處新锈，
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//將高位鏈表存放在新index處
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

再看一下 往哈希表里插入一個(gè)節(jié)點(diǎn)的putVal函數(shù),如果參數(shù)onlyIfAbsent是true甲脏，那么不會(huì)覆蓋相同key的值value。如果evict是false。那么表示是在初始化時(shí)調(diào)用的

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //tab存放 當(dāng)前的哈希桶块请， p用作臨時(shí)鏈表節(jié)點(diǎn)  
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果當(dāng)前哈希表是空的娜氏，代表是初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        //那么直接去擴(kuò)容哈希表，并且將擴(kuò)容后的哈希桶長度賦值給n
        n = (tab = resize()).length;
    //如果當(dāng)前index的節(jié)點(diǎn)是空的墩新，表示沒有發(fā)生哈希碰撞贸弥。 直接構(gòu)建一個(gè)新節(jié)點(diǎn)Node，掛載在index處即可抖棘。
    //這里再啰嗦一下茂腥，index 是利用 哈希值 & 哈希桶的長度-1，替代模運(yùn)算
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//否則 發(fā)生了哈希沖突切省。
        //e
        Node<K,V> e; K k;
        //如果哈希值相等最岗，key也相等，則是覆蓋value操作
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;//將當(dāng)前節(jié)點(diǎn)引用賦值給e
        else if (p instanceof TreeNode)//紅黑樹暫且不談
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//不是覆蓋操作朝捆，則插入一個(gè)普通鏈表節(jié)點(diǎn)
            //遍歷鏈表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {//遍歷到尾部般渡，追加新節(jié)點(diǎn)到尾部
                    p.next = newNode(hash, key, value, null);
                    //如果追加節(jié)點(diǎn)后，鏈表數(shù)量》=8芙盘，則轉(zhuǎn)化為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果找到了要覆蓋的節(jié)點(diǎn)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果e不是null驯用，說明有需要覆蓋的節(jié)點(diǎn)，
        if (e != null) { // existing mapping for key
            //則覆蓋節(jié)點(diǎn)值儒老，并返回原oldValue
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //這是一個(gè)空實(shí)現(xiàn)的函數(shù)蝴乔，用作LinkedHashMap重寫使用。
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //如果執(zhí)行到了這里驮樊，說明插入了一個(gè)新的節(jié)點(diǎn)薇正，所以會(huì)修改modCount，以及返回null囚衔。

    //修改modCount
    ++modCount;
    //更新size挖腰，并判斷是否需要擴(kuò)容。
    if (++size > threshold)
        resize();
    //這是一個(gè)空實(shí)現(xiàn)的函數(shù)练湿，用作LinkedHashMap重寫使用猴仑。
    afterNodeInsertion(evict);
    return null;
}

newNode如下：構(gòu)建一個(gè)鏈表節(jié)點(diǎn)

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

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

小結(jié)：

• 運(yùn)算盡量都用位運(yùn)算代替，更高效肥哎。
• 對(duì)于擴(kuò)容導(dǎo)致需要新建數(shù)組存放更多元素時(shí)辽俗，除了要將老數(shù)組中的元素遷移過來，也記得將老數(shù)組中的引用置null篡诽，以便GC
• 取下標(biāo) 是用 哈希值 與運(yùn)算 （桶的長度-1） i = (n - 1) & hash榆苞。 由于桶的長度是2的n次方，這么做其實(shí)是等于 一個(gè)模運(yùn)算霞捡。但是效率更高
• 擴(kuò)容時(shí)坐漏，如果發(fā)生過哈希碰撞，節(jié)點(diǎn)數(shù)小于8個(gè)。則要根據(jù)鏈表上每個(gè)節(jié)點(diǎn)的哈希值赊琳，依次放入新哈希桶對(duì)應(yīng)下標(biāo)位置街夭。
• 因?yàn)閿U(kuò)容是容量翻倍，所以原鏈表上的每個(gè)節(jié)點(diǎn)躏筏，現(xiàn)在可能存放在原來的下標(biāo)板丽，即low位， 或者擴(kuò)容后的下標(biāo)趁尼，即high位埃碱。 high位= low位+原哈希桶容量
• 利用哈希值 與運(yùn)算 舊的容量 ，if ((e.hash & oldCap) == 0),可以得到哈希值去模后酥泞，是大于等于oldCap還是小于oldCap砚殿，等于0代表小于oldCap，應(yīng)該存放在低位芝囤，否則存放在高位似炎。這里又是一個(gè)利用位運(yùn)算 代替常規(guī)運(yùn)算的高效點(diǎn)
• 如果追加節(jié)點(diǎn)后，鏈表數(shù)量》=8悯姊，則轉(zhuǎn)化為紅黑樹
• 插入節(jié)點(diǎn)操作時(shí)羡藐，有一些空實(shí)現(xiàn)的函數(shù)，用作LinkedHashMap重寫使用悯许。

5 增仆嗦、改
1往表中插入或覆蓋一個(gè)key-value
public V put(K key, V value) {
//先根據(jù)key，取得hash值先壕。 再調(diào)用上一節(jié)的方法插入節(jié)點(diǎn)
return putVal(hash(key), key, value, false, true);
}

這個(gè)根據(jù)key取hash值的函數(shù)也要關(guān)注一下瘩扼，它稱之為“擾動(dòng)函數(shù)”，關(guān)于這個(gè)函數(shù)的用處 開頭已經(jīng)總結(jié)過了：

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

而key的hash值启上，并不僅僅只是key對(duì)象的hashCode()方法的返回值，還會(huì)經(jīng)過擾動(dòng)函數(shù)的擾動(dòng)店印，以使hash值更加均衡冈在。
因?yàn)閔ashCode()是int類型，取值范圍是40多億按摘，只要哈希函數(shù)映射的比較均勻松散包券，碰撞幾率是很小的。
但就算原本的hashCode()取得很好炫贤，每個(gè)key的hashCode()不同溅固，但是由于HashMap的哈希桶的長度遠(yuǎn)比hash取值范圍小，默認(rèn)是16兰珍，所以當(dāng)對(duì)hash值以桶的長度取余侍郭，以找到存放該key的桶的下標(biāo)時(shí)，由于取余是通過與操作完成的，會(huì)忽略hash值的高位亮元。因此只有hashCode()的低位參加運(yùn)算猛计，發(fā)生不同的hash值，但是得到的index相同的情況的幾率會(huì)大大增加爆捞，這種情況稱之為hash碰撞奉瘤。 即，碰撞率會(huì)增大煮甥。

擾動(dòng)函數(shù)就是為了解決hash碰撞的盗温。它會(huì)綜合hash值高位和低位的特征，并存放在低位成肘，因此在與運(yùn)算時(shí)卖局，相當(dāng)于高低位一起參與了運(yùn)算，以減少hash碰撞的概率艇劫。（在JDK8之前吼驶，擾動(dòng)函數(shù)會(huì)擾動(dòng)四次，JDK8簡(jiǎn)化了這個(gè)操作）

2往表中批量增加數(shù)據(jù)
public void putAll(Map<? extends K, ? extends V> m) {
//這個(gè)函數(shù)上一節(jié)也已經(jīng)分析過店煞。//將另一個(gè)Map的所有元素加入表中蟹演，參數(shù)evict初始化時(shí)為false，其他情況為true
putMapEntries(m, true);
}

3 只會(huì)往表中插入 key-value, 若key對(duì)應(yīng)的value之前存在顷蟀，不會(huì)覆蓋酒请。（jdk8增加的方法）
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}

6 刪
以key為條件刪除
如果key對(duì)應(yīng)的value存在，則刪除這個(gè)鍵值對(duì)鸣个。 并返回value羞反。如果不存在 返回null。

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

//從哈希表中刪除某個(gè)節(jié)點(diǎn)囤萤， 如果參數(shù)matchValue是true昼窗，則必須key 、value都相等才刪除涛舍。
//如果movable參數(shù)是false澄惊，在刪除節(jié)點(diǎn)時(shí)，不移動(dòng)其他節(jié)點(diǎn)

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    // p 是待刪除節(jié)點(diǎn)的前置節(jié)點(diǎn)
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //如果哈希表不為空富雅，則根據(jù)hash值算出的index下 有節(jié)點(diǎn)的話掸驱。
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        //node是待刪除節(jié)點(diǎn)
        Node<K,V> node = null, e; K k; V v;
        //如果鏈表頭的就是需要?jiǎng)h除的節(jié)點(diǎn)
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;//將待刪除節(jié)點(diǎn)引用賦給node
        else if ((e = p.next) != null) {//否則循環(huán)遍歷 找到待刪除節(jié)點(diǎn)，賦值給node
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //如果有待刪除節(jié)點(diǎn)node没佑，  且 matchValue為false毕贼，或者值也相等
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)//如果node ==  p，說明是鏈表頭是待刪除節(jié)點(diǎn)
                tab[index] = node.next;
            else//否則待刪除節(jié)點(diǎn)在表中間
                p.next = node.next;
            ++modCount;//修改modCount
            --size;//修改size
            afterNodeRemoval(node);//LinkedHashMap回調(diào)函數(shù)
            return node;
        }
    }
    return null;
}

void afterNodeRemoval(Node<K,V> p) { }

1
以key value 為條件刪除
@Override
public boolean remove(Object key, Object value) {
//這里傳入了value 同時(shí)matchValue為true
return removeNode(hash(key), key, value, true, true) != null;
}

7 查
以key為條件蛤奢，找到返回value鬼癣。沒找到返回null
public V get(Object key) {
Node<K,V> e;
//傳入擾動(dòng)后的哈希值 和 key 找到目標(biāo)節(jié)點(diǎn)Node
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

//傳入擾動(dòng)后的哈希值 和 key 找到目標(biāo)節(jié)點(diǎn)Node
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //查找過程和刪除基本差不多陶贼， 找到返回節(jié)點(diǎn)，否則返回null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            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);
        }
    }
    return null;
}

判斷是否包含該key
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}

判斷是否包含value
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
//遍歷哈希桶上的每一個(gè)鏈表
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
//如果找到value一致的返回true
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}

java8新增扣溺，帶默認(rèn)值的get方法
以key為條件骇窍，找到了返回value。否則返回defaultValue

@Override
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

遍歷
//緩存 entrySet
transient Set<Map.Entry<K,V>> entrySet;
*/
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    //一般我們用到EntrySet锥余，都是為了獲取iterator
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();
    }
    //最終還是調(diào)用getNode方法
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    //最終還是調(diào)用removeNode方法
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    //腹纳。。驱犹。
}

//EntryIterator的實(shí)現(xiàn)：

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        //因?yàn)閔ashmap也是線程不安全的嘲恍，所以要保存modCount。用于fail-fast策略
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        //next 初始時(shí)雄驹，指向 哈希桶上第一個(gè)不為null的鏈表頭
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    //由這個(gè)方法可以看出佃牛，遍歷HashMap時(shí)，順序是按照哈希桶從低到高医舆，鏈表從前往后俘侠，依次遍歷的。屬于無序集合蔬将。
    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        //fail-fast策略
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        //依次取鏈表下一個(gè)節(jié)點(diǎn)爷速，
        if ((next = (current = e).next) == null && (t = table) != null) {
            //如果當(dāng)前鏈表節(jié)點(diǎn)遍歷完了，則取哈希桶下一個(gè)不為null的鏈表頭
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        ////fail-fast策略
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        //最終還是利用removeNode 刪除節(jié)點(diǎn)
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

8 總結(jié)
HashMap特點(diǎn)和精髓可以參看本文第二章【概要】 和第四章的【小結(jié)】部分霞怀。

后續(xù)會(huì)另開新篇聊一聊紅黑樹惫东。

20170920 add,從網(wǎng)上轉(zhuǎn)了一張圖，據(jù)說來自美團(tuán)毙石，侵刪：

9 與HashTable的區(qū)別
與之相比HashTable是線程安全的廉沮，且不允許key、value是null徐矩。
HashTable默認(rèn)容量是11滞时。
HashTable是直接使用key的hashCode(key.hashCode())作為hash值，不像HashMap內(nèi)部使用static final int hash(Object key)擾動(dòng)函數(shù)對(duì)key的hashCode進(jìn)行擾動(dòng)后作為hash值滤灯。
HashTable取哈希桶下標(biāo)是直接用模運(yùn)算%.（因?yàn)槠淠J(rèn)容量也不是2的n次方坪稽。所以也無法用位運(yùn)算替代模運(yùn)算）
擴(kuò)容時(shí)，新容量是原來的2倍+1力喷。int newCapacity = (oldCapacity << 1) + 1;
Hashtable是Dictionary的子類同時(shí)也實(shí)現(xiàn)了Map接口刽漂，HashMap是Map接口的一個(gè)實(shí)現(xiàn)類演训；
————————————————
原文鏈接：https://blog.csdn.net/zxt0601/article/details/77413921