HashMap繼承AbstractMap<K,V>抽象類秘车，實現(xiàn)了 Map<K,V>, Cloneable, Serializable接口。

• Map<K,V>接口：定義了一組通用的操作規(guī)范
• Cloneable接口：可以克隆對象（淺拷貝）
• Serializable接口： 對象序列化

HashMap結(jié)構(gòu)圖

HashMap結(jié)構(gòu)圖

1. HashMap的屬性

1.1 HashMap的重要屬性

其中有些屬性是有transient關(guān)鍵字修飾的

1.1.1 transient Node<K,V>[] table;

存儲元素（位桶--Node<K,V>節(jié)點）的數(shù)組蹦玫，總是2的冪次倍

1.1.2 transient Set<Map.Entry<K,V>> entrySet;

由hashMap 中 Node<K,V>節(jié)點構(gòu)成的 set集合

1.1.3 transient int size;

存放元素（鍵-值對）的個數(shù)烟馅，注意這個不等于數(shù)組的長度

1.1.4 transient int modCount;

每次擴(kuò)容和更改map結(jié)構(gòu)的計數(shù)器涛浙，fail-fast機(jī)制

1.1.5 int threshold;

臨界值 當(dāng)實際大小size(容量*填充因子)超過臨界值時康辑，會進(jìn)行擴(kuò)容

1.1.6 final float loadFactor;

記錄 hashMap 裝載因子

1.2 HashMap的靜態(tài)屬性

    // 序列號
    private static final long serialVersionUID = 362498820763181265L;    
    // 默認(rèn)的初始table大小是1<<4(16)
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // table的最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默認(rèn)的填充因子（loadFactor）大小
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 當(dāng)桶(*bucket*)上的結(jié)點數(shù)大于這個值時會轉(zhuǎn)成紅黑樹
    static final int TREEIFY_THRESHOLD = 8;
    // 當(dāng)桶(*bucket*)上的結(jié)點數(shù)小于這個值時樹轉(zhuǎn)鏈表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶(*bucket*)中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對應(yīng)的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;    

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

2.1 HashMap(int, float)型構(gòu)造函數(shù)

    /**
     * 指定初始容量及裝載因子
     */
    public HashMap(int initialCapacity, float loadFactor) {
        // 初始容量不能小于0，否則報錯
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 初始容量不能大于最大值轿亮，否則為最大值
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 填充因子不能小于或等于0疮薇，不能為非數(shù)字
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // 初始化填充因子 
        this.loadFactor = loadFactor;
        // 初始化threshold大小
        this.threshold = tableSizeFor(initialCapacity);
    }

注：此處調(diào)用了static final int tableSizeFor(int cap);方法。返回的值是大于等于initialCapacity 的最小2的冪數(shù)值

• static final int tableSizeFor(int cap)

    /**
     * 返回的值是大于等于initialCapacity 的最小2的冪數(shù)值
     * 若指定初始容量為９我注，則實際 hashMap 容量為16
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
       /** 
        * 先移位再或運算按咒，最終保證返回值是2的整數(shù)冪
        * >>> 代表無符號右移，高位取0
        */
        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;
    }

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

    /**
     * 僅指定初始容量但骨，裝載因子的值采用默認(rèn)的　0.75
     */
    public HashMap(int initialCapacity) {
        // 調(diào)用HashMap(int, float)型構(gòu)造函數(shù)
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

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

    /**
     * 所有參數(shù)均采用默認(rèn)值
     */
    public HashMap() {
        // 初始化填充因子
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

2.4 HashMap(Map<? extends K>)型構(gòu)造函數(shù)

    /**
     *   直接將map放入HashMap中
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        // 初始化填充因子
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        // 將m中的所有元素添加至HashMap中
        putMapEntries(m, false);
    }

注：此處調(diào)用 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)函數(shù)將m的所有元素存入本HashMap實例中励七，此函數(shù)在put函數(shù)中介紹

3 HashMap的重要函數(shù)

3.1 put函數(shù)及相關(guān)方法

• public V put(K key, V value)

    /**
     * 指定節(jié)點 key,value智袭，向 hashMap 中插入節(jié)點
     */
    public V put(K key, V value) {
        // 注意待插入節(jié)點hash值的計算，調(diào)用了hash(key) 函數(shù)
        // 實際調(diào)用 putVal() 進(jìn)行節(jié)點的插入
        return putVal(hash(key), key, value, false, true);
    }

• public void putAll(Map<? extends K, ? extends V> m)

    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }

• final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

    /**
     * 將m的所有元素存入本HashMap實例中
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            // 判斷table是否已經(jīng)初始化
            if (table == null) { // pre-size
                // 根據(jù)待插入的map 的 size 計算要創(chuàng)建的　hashMap 的容量掠抬。
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                // 把要創(chuàng)建的　hashMap 的容量存在　threshold　中
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            // 判斷待插入的　map 的 size,若　size 大于　threshold吼野，則先進(jìn)行　resize()
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                // 實際也是調(diào)用　putVal　函數(shù)進(jìn)行元素的插入
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

注：該方法中調(diào)用了final Node<K,V>[] resize();函數(shù)，此函數(shù)為擴(kuò)容函數(shù)具體細(xì)節(jié)下面介紹两波；除此之外還調(diào)用了static final int tableSizeFor(int cap);上面已經(jīng)介紹瞳步；還有就是static final int hash(Object key) 函數(shù)。

• static final int hash(Object key)

    /**
     * key 的 hash值的計算是通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)
     * 主要是從速度雨女、功效谚攒、質(zhì)量來考慮的阳准，這么做可以在數(shù)組table的length比較小的時候
     * 也能保證考慮到高低Bit都參與到Hash的計算中氛堕，同時不會有太大的開銷
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

通過上面的put方法看到最后都是調(diào)用putVal函數(shù)進(jìn)行插入下面看一下該函數(shù)：

• final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  boolean evict)

    /**
     * 核心方法
     */
    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未初始化或者長度為0，調(diào)用resize函數(shù)進(jìn)行擴(kuò)容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;     
        /* 根據(jù) hash 值確定節(jié)點在數(shù)組中的插入位置野蝇，若此位置沒有元素則進(jìn)行插入讼稚，
           注意確定插入位置所用的計算方法為　(n - 1) & hash,由于　n 一定是２的冪次，這個操作相當(dāng)于hash % n  位運算更快*/
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 空桶绕沈，創(chuàng)建新的鍵值對節(jié)點锐想，放入table數(shù)組中
            tab[i] = newNode(hash, key, value, null);
        else {  
            // 說明待插入位置存在元素 即tab[i]不為空，需要組成單鏈表或紅黑樹
            Node<K,V> e; K k;
            // 與桶（*bucket*）中首元素相比乍狐，如果 hash赠摇、key 均等，說明待插入元素和第一個元素相等浅蚪，直接更新
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 此時p指的是table[i]中存儲的那個Node藕帜，如果待插入的節(jié)點中hash值和key值在p中已經(jīng)存在，則將p賦給e
                e = p;
            // 當(dāng)前桶（*bucket*）中無該鍵值對惜傲，且桶是紅黑樹結(jié)構(gòu)洽故，按照紅黑樹結(jié)構(gòu)插入
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {// 當(dāng)前桶（*bucket*）中無該鍵值對，且桶（*bucket*）是鏈表結(jié)構(gòu)盗誊，按照鏈表結(jié)構(gòu)插入到尾部
                // 在鏈表最末插入結(jié)點
                for (int binCount = 0; ; ++binCount) {
                    // 遍歷到鏈表的尾部
                    if ((e = p.next) == null) {
                        // 創(chuàng)建鏈表節(jié)點并插入尾部
                        p.next = newNode(hash, key, value, null);
                        // 結(jié)點數(shù)量達(dá)到閾值时甚，轉(zhuǎn)化為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 判斷鏈表中結(jié)點的 key 值與插入的元素的 key 值是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 用于遍歷桶中的鏈表，與前面的e = p.next組合哈踱，可以遍歷鏈表將荒适；即p調(diào)整為下一個節(jié)點 
                    p = e;
                }
            }
            // 表示在桶（*bucket*）中找到key值、hash值與插入元素相等的結(jié)點
            if (e != null) { // existing mapping for key
                // 記錄e的value
                V oldValue = e.value;
                // 判斷是否修改已插入節(jié)點的value
                if (!onlyIfAbsent || oldValue == null)
                    // 用新值替換舊值
                    e.value = value;
                // 訪問后回調(diào)
                afterNodeAccess(e);// 空函數(shù)开镣，由用戶根據(jù)需要覆蓋
                return oldValue;
            }
        }
        // 結(jié)構(gòu)性修改
        ++modCount;
        // 鍵值對數(shù)目超過閾值時刀诬，進(jìn)行 resize 擴(kuò)容
        if (++size > threshold)
            resize();
        // 插入后回調(diào)
        afterNodeInsertion(evict);// 空函數(shù)，由用戶根據(jù)需要覆蓋
        return null;
    }

注：hash 沖突發(fā)生的幾種情況：
1.兩節(jié)點　key 值相同（hash值一定相同）哑子，導(dǎo)致沖突舅列；
2.兩節(jié)點　key 值不同肌割，由于 hash 函數(shù)的局限性導(dǎo)致hash 值相同，沖突帐要；
3.兩節(jié)點　key 值不同把敞，hash 值不同，但 hash 值對數(shù)組長度取模后相同榨惠，沖突奋早；

其中有紅黑樹插入方式和鏈表插入方式，下面先看鏈表插入：

• final void treeifyBin(Node<K,V>[] tab, int hash)

    /**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

紅黑樹插入方式：

• final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)

        /**
         * 該函數(shù)是HashMap靜態(tài)內(nèi)部類
         * static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>中的方法赠橙。
         * 主要功能就是以紅黑樹的方式添加一個鍵值對
         */
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            TreeNode<K,V> root = (parent != null) ? root() : this;
            // 從根節(jié)點開始查找合適的插入位置（與二叉搜索樹查找過程相同）
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if ((ph = p.hash) > h)
                    dir = -1;  //　dir小于０耽装，接下來查找當(dāng)前節(jié)點左孩子
                else if (ph < h)
                    dir = 1;  //　dir大于０，接下來查找當(dāng)前節(jié)點右孩子
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                //進(jìn)入這個else if 代表　hash 值相同期揪，key　相同
                    return p;
                /*要進(jìn)入下面這個else if,代表有以下幾個含義:
                  1.當(dāng)前節(jié)點與待插入節(jié)點　key　不同,　hash 值相同
                  2.k是不可比較的掉奄，即ｋ并未實現(xiàn)　comparable<K>　接口（若 k 實現(xiàn)了comparable<K>　接口，comparableClassFor（k）返回的是ｋ的　class,而不是　null）或 者　
                    compareComparables(kc, k, pk)　返回值為 0(pk 為空　或者　按照 k.compareTo(pk) 返回值為０凤薛，返回值為０可能是由于⌒战āｋ的compareTo 方法實現(xiàn)不當(dāng)引起的，compareTo 判定相等缤苫，而上個 else if　中　equals 判定不等)*/
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    // 在以當(dāng)前節(jié)點為根的整個樹上搜索是否存在待插入節(jié)點（只會搜索一次）
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            // 若樹中存在待插入節(jié)點速兔，直接返回
                            return q;
                    }
                    // 既然ｋ是不可比較的，那我自己指定一個比較方式
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // 找到了待插入的位置活玲，xp 為待插入節(jié)點的父節(jié)點
                    // 注意TreeNode節(jié)點中既存在樹狀關(guān)系涣狗，也存在鏈?zhǔn)疥P(guān)系，k是不可比較的舒憾，即ｋ并未實現(xiàn)　comparable<K>　接口（若 k 實現(xiàn)了comparable<K>　接口镀钓，comparableClassFor（k）返回的是ｋ的　class,而并且是雙端鏈表
                    Node<K,V> xpn = xp.next;
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    // 插入節(jié)點后進(jìn)行二叉樹的平衡操作
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

3.2 get函數(shù)及相關(guān)方法

• public V get(Object key)

    /**
     * 實際上是根據(jù)輸入節(jié)點的 hash 值和 key 值利用getNode 方法進(jìn)行查找
     */
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

• final Node<K,V> getNode(int hash, Object key)

    /**
     * HashMap并沒有直接提供getNode接口給用戶調(diào)用，而是提供的get函數(shù)珍剑，而get函數(shù)就是通過getNode來取得元素的掸宛。
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // table已經(jīng)初始化，長度大于0招拙，根據(jù)hash尋找table中的項也不為空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 桶中第一項(數(shù)組元素)相等
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 桶中不止一個結(jié)點
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    // 若定位到的節(jié)點是　TreeNode 節(jié)點唧瘾，則在樹中進(jìn)行查找
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {  // 否則在鏈表中進(jìn)行查找
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

getNode方法中調(diào)用 getTreeNode 函數(shù)

• final TreeNode<K,V> getTreeNode(int h, Object k)

        /**
         * 從根節(jié)點開始，調(diào)用 find 方法進(jìn)行查找
         */
        final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
        }

getTreeNode 函數(shù)最終調(diào)用 find函數(shù)進(jìn)行紅黑樹查找别凤。

• final TreeNode<K,V> find(int h, Object k, Class<?> kc)

        /**
         * Finds the node starting at root p with the given hash and key.
         * The kc argument caches comparableClassFor(key) upon first use
         * comparing keys.
         */
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                // 首先進(jìn)行hash 值的比較饰序，若不同令當(dāng)前節(jié)點變?yōu)樗淖蠛⒆踊蛘哂液⒆?                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                // hash 值相同，進(jìn)行 key　值的比較 
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                // 若k 是可比較的并且k.compareTo(pk) 返回結(jié)果不為０可進(jìn)入下面else if 
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                // 若 k 是不可比較的　或者　k.compareTo(pk) 返回結(jié)果為０則在整棵樹中進(jìn)行查找规哪，先找右子樹求豫，右子樹沒有再找左子樹 
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
        }

3.3 remove函數(shù)

• public V remove(Object key)

    /**
     * 實際上是根據(jù)輸入節(jié)點的key 值利用removeNode方法進(jìn)行刪除
     */
    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

• final Node<K,V> removeNode(int hash, Object key, Object value,
  boolean matchValue, boolean movable)

    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            // 待刪除元素在桶（*bucket*）中，但不是桶中首元素
            else if ((e = p.next) != null) {
                // 判斷待刪除元素是否在紅黑樹結(jié)構(gòu)的桶中
                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保存待刪除節(jié)點的前一個節(jié)點蝠嘉，用于鏈表刪除操
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 1. matchValue為true：表示必須value相等才進(jìn)行刪除操作
            // 2. matchValue為false：表示無須判斷value最疆，直接根據(jù)key進(jìn)行刪除操作
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                // 桶為紅黑數(shù)結(jié)構(gòu)，刪除節(jié)點
                if (node instanceof TreeNode)
                    // movable參數(shù)用于紅黑樹操作
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                // 待刪除節(jié)點是桶鏈表表頭蚤告，將子節(jié)點放進(jìn)桶位
                else if (node == p)
                    tab[index] = node.next;
                // 待刪除節(jié)點在桶鏈表中間
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        // 待刪除元素不存在努酸，返回null
        return null;
    }

3.4 replace 函數(shù)

進(jìn)行replace有兩種方案：

• 一種是采用 putVal 的方法，因為很明顯 putVal 是能夠替換的杜恰，但是這里就涉及到了 size 获诈，和 modCount 這兩個 field 的變化了，也是要注意的心褐。
• 另一種是 getNode 得到節(jié)點舔涎，然后替換，所以采用了 getNode 這個方法逗爹。

    /**
     * 根據(jù)key和舊的value查找匹配進(jìn)行替換value
     */
    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            afterNodeAccess(e);
            return true;
        }
        return false;
    }

    /**
     * 根據(jù)key查詢匹配進(jìn)行替換value
     */
    @Override
    public V replace(K key, V value) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) != null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
        return null;
    }

3.5 擴(kuò)容函數(shù) resize() 之再哈希法

先來看一下resize() 函數(shù)

        // 保存當(dāng)前table
        Node<K,V>[] oldTab = table;
        // 保存當(dāng)前table的容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 保存當(dāng)前閾值
        int oldThr = threshold;
        // 初始化新的table容量和閾值 
        int newCap, newThr = 0;
        /*
        1. resize（）函數(shù)在size　> threshold時被調(diào)用亡嫌。oldCap大于 0 代表原來的 table 表非空，
           oldCap 為原表的大小桶至，oldThr（threshold） 為 oldCap × load_factor
        */
        if (oldCap > 0) {
            // 若舊table容量已超過最大容量昼伴，更新閾值為Integer.MAX_VALUE（最大整形值）
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
             // 容量翻倍匾旭，使用左移镣屹，效率更高
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 閾值翻倍
                newThr = oldThr << 1; // double threshold
        }
        /*
        2. resize（）函數(shù)在table為空被調(diào)用。oldCap 小于等于 0 且 oldThr 大于0价涝，代表用戶創(chuàng)建了一個 HashMap女蜈，但是使用的構(gòu)造函數(shù)為      
           HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
           或 HashMap(Map<? extends K, ? extends V> m)，導(dǎo)致 oldTab 為 null色瘩，oldCap 為0伪窖， oldThr 為用戶指定的 HashMap的初始容量。
    　　*/
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        /*
        3. resize（）函數(shù)在table為空被調(diào)用居兆。oldCap 小于等于 0 且 oldThr 等于0覆山，用戶調(diào)用 HashMap()構(gòu)造函數(shù)創(chuàng)建的　HashMap，所有值均采用默認(rèn)值泥栖，oldTab（Table）表為空簇宽，oldCap為0，oldThr等于0吧享，
        */
        else {               // zero initial threshold signifies using defaults
            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"})
        // 初始化table
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            // 把 oldTab 中的節(jié)點　reHash 到　newTab 中去
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 若節(jié)點是單個節(jié)點魏割，直接在 newTab　中進(jìn)行重定位
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    // 若節(jié)點是　TreeNode 節(jié)點，要進(jìn)行 紅黑樹的 rehash　操作
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 若是鏈表钢颂，進(jìn)行鏈表的 rehash　操作
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 將同一桶中的元素根據(jù)(e.hash & oldCap)是否為0進(jìn)行分割钞它，分成兩個不同的鏈表，完成rehash
                        do {
                            next = e.next;
                            // 根據(jù)算法　e.hash & oldCap　判斷節(jié)點位置rehash　后是否發(fā)生改變
                            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) {  // 原bucket位置的尾指針不為空(即還有node)  
                            loTail.next = null; // 鏈表最后得有個null
                            newTab[j] = loHead; // 鏈表頭指針放在新桶的相同下標(biāo)(j)處
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            // rehash　后節(jié)點新的位置一定為原來基礎(chǔ)上加上　oldCap
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

1. 什么時候擴(kuò)容：通過HashMap源碼可以看到是在put操作時，即向容器中添加元素時遭垛，判斷當(dāng)前容器中元素的個數(shù)是否達(dá)到閾值（當(dāng)前數(shù)組長度乘以加載因子的值）的時候尼桶，就要自動擴(kuò)容了。
2. 擴(kuò)容(resize)：其實就是重新計算容量锯仪；而這個擴(kuò)容是計算出所需容器的大小之后重新定義一個新的容器疯汁，將原來容器中的元素放入其中。
   經(jīng)過rehash之后卵酪，元素的位置要么是在原位置幌蚊，要么是在原位置再移動2次冪的位置

下面根據(jù)圖來解釋一下再哈希法

6.png

2.png

• （a）表示擴(kuò)容前的key1和key2兩種key確定索引位置的示例
• （b）表示擴(kuò)容后的key1和key2兩種key確定索引位置的示例
• hash1是key1對應(yīng)的哈希與高位運算結(jié)果
• 元素在重新計算hash之后溃卡，因為n變?yōu)?倍溢豆，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化瘸羡，如下圖

3.png

1.png

3.6 Serializable方法

3.6.1 writeObject方法

    /**
     * 將HashMap的“總的容量，實際容量峻村，所有的Entry”都寫入到輸出流對象中
     */根據(jù)寫入方式讀出,將HashMap的“總的容量麸折，實際容量，所有的Entry”依次讀出
    private void writeObject(java.io.ObjectOutputStream s)
        throws IOException {
        int buckets = capacity();
        // Write out the threshold, loadfactor, and any hidden stuff
        s.defaultWriteObject();
        s.writeInt(buckets);
        s.writeInt(size);
        internalWriteEntries(s);
    }

3.6.2 readObject方法

    /**
     * 根據(jù)寫入方式讀出,將HashMap的“總的容量粘昨，實際容量垢啼，所有的Entry”依次讀出
     */
    private void readObject(java.io.ObjectInputStream s)
        throws IOException, ClassNotFoundException {
        // Read in the threshold (ignored), loadfactor, and any hidden stuff
        s.defaultReadObject();
        reinitialize();
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        s.readInt();                // Read and ignore number of buckets
        int mappings = s.readInt(); // Read number of mappings (size)
        if (mappings < 0)
            throw new InvalidObjectException("Illegal mappings count: " +
                                             mappings);
        else if (mappings > 0) { // (if zero, use defaults)
            // Size the table using given load factor only if within
            // range of 0.25...4.0
            float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
            float fc = (float)mappings / lf + 1.0f;
            int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                       DEFAULT_INITIAL_CAPACITY :
                       (fc >= MAXIMUM_CAPACITY) ?
                       MAXIMUM_CAPACITY :
                       tableSizeFor((int)fc));
            float ft = (float)cap * lf;
            threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                         (int)ft : Integer.MAX_VALUE);
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
            table = tab;

            // Read the keys and values, and put the mappings in the HashMap
            for (int i = 0; i < mappings; i++) {
                @SuppressWarnings("unchecked")
                    K key = (K) s.readObject();
                @SuppressWarnings("unchecked")
                    V value = (V) s.readObject();
                putVal(hash(key), key, value, false, false);
            }
        }
    }

3.6.3 internalWriteEntries方法

    /**
     * 僅被writeObject調(diào)用，確保HashMap的鍵和值被序列化的存儲順序 
     */
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        Node<K,V>[] tab;
        if (size > 0 && (tab = table) != null) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    s.writeObject(e.key);
                    s.writeObject(e.value);
                }
            }
        }
    }

3.7 其他方法

• public void clear()

    /**
     * 刪除此Map的所有映射
     */
    public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

• public Object clone()

    /**
     * 返回此 HashMap實例的淺拷貝：鍵和值本身不被克隆
     */
    @SuppressWarnings("unchecked")
    @Override
    public Object clone() {
        HashMap<K,V> result;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
        result.reinitialize();
        result.putMapEntries(this, false);
        return result;
    }

• public boolean containsKey(Object key)

    /**
     * 如果此映射包含指定鍵的映射张肾，則返回 true 
     */
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

• public boolean containsValue(Object value)

    /**
     * 如果此Map將一個或多個鍵映射到指定的值芭析，則返回 true 。
     */
    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        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) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

• public Set<Map.Entry<K,V>> entrySet()

    /**
     * 返回此Map中包含的映射的Set視圖
     */
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

• public Set<Map.Entry<K,V>> entrySet()

    /**
     * 返回到指定鍵所映射的值吞瞪，或 defaultValue如果此映射包含該鍵的映射 
     */
    @Override
    public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }

4. HashMap的內(nèi)部類

4.1 Node內(nèi)部類

    /**
     * 繼承自 Map.Entry這個內(nèi)部接口馁启，它就是存儲一對映射關(guān)系的最小單元，也就是說key芍秆，value實際存儲在Node中
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        // 結(jié)點的哈希值惯疙，不可變 
        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;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
        // 由直接實現(xiàn) 變?yōu)?調(diào)用Object的HashCode，實際是一樣的
        public final int hashCode() {
            //按位異或^不同為真,數(shù)a兩次異或同一個數(shù)b(a=a^b^b)仍然為原值a
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        // 調(diào)用Object的equals 
        public final boolean equals(Object o) {
            // 內(nèi)存地址
            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;
        }
    }

4.2 TreeNode內(nèi)部類

    /**
     * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
     * extends Node) so can be used as extension of either regular or
     * linked node.
     */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // 節(jié)點的前一個節(jié)點 
        boolean red;  //true表示紅節(jié)點，false表示黑節(jié)點
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * 獲取紅黑樹的根
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

        /**
         * 確保root是桶中的第一個元素，將root移到桶中的第一個【平衡思想】
         */
        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
            int n;
            if (root != null && tab != null && (n = tab.length) > 0) {
                int index = (n - 1) & root.hash;
                TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
                if (root != first) {
                    Node<K,V> rn;
                    tab[index] = root;
                    TreeNode<K,V> rp = root.prev;
                    if ((rn = root.next) != null)
                        ((TreeNode<K,V>)rn).prev = rp;
                    if (rp != null)
                        rp.next = rn;
                    if (first != null)
                        first.prev = root;
                    root.next = first;
                    root.prev = null;
                }
                assert checkInvariants(root);
            }
        }

        /**
         * 查找hash為h正压，key為k的節(jié)點 
         */
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
        }

        /**
         * 獲取樹節(jié)點边苹，通過根節(jié)點查找 .
         */
        final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
        }

        /**
         * 比較2個對象的大小
         */
        static int tieBreakOrder(Object a, Object b) {
            int d;
            if (a == null || b == null ||
                (d = a.getClass().getName().
                 compareTo(b.getClass().getName())) == 0)
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                     -1 : 1);
            return d;
        }

        /**
         * 將鏈表轉(zhuǎn)為二叉樹 
         */
        final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
                next = (TreeNode<K,V>)x.next;
                x.left = x.right = null;
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);

                        TreeNode<K,V> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }

        /**
         * 將二叉樹轉(zhuǎn)為鏈表 
         */
        final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
                Node<K,V> p = map.replacementNode(q, null);
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }

        /**
         * 添加一個鍵值對
         */
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            TreeNode<K,V> root = (parent != null) ? root() : this;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    Node<K,V> xpn = xp.next;
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

        /**
         * 刪除指定節(jié)點
         */
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
            int index = (n - 1) & hash;
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
            TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
            if (pred == null)
                tab[index] = first = succ;
            else
                pred.next = succ;
            if (succ != null)
                succ.prev = pred;
            if (first == null)
                return;
            if (root.parent != null)
                root = root.root();
            if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            TreeNode<K,V> p = this, pl = left, pr = right, replacement;
            if (pl != null && pr != null) {
                TreeNode<K,V> s = pr, sl;
                while ((sl = s.left) != null) // find successor
                    s = sl;
                boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                TreeNode<K,V> sr = s.right;
                TreeNode<K,V> pp = p.parent;
                if (s == pr) { // p was s's direct parent
                    p.parent = s;
                    s.right = p;
                }
                else {
                    TreeNode<K,V> sp = s.parent;
                    if ((p.parent = sp) != null) {
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                p.left = null;
                if ((p.right = sr) != null)
                    sr.parent = p;
                if ((s.left = pl) != null)
                    pl.parent = s;
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }
            else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            if (replacement != p) {
                TreeNode<K,V> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }

            TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

            if (replacement == p) {  // detach
                TreeNode<K,V> pp = p.parent;
                p.parent = null;
                if (pp != null) {
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            if (movable)
                moveRootToFront(tab, r);
        }

        /**
         * 這個函數(shù)的功能是對紅黑樹進(jìn)行　rehash 操作 即將結(jié)點太多的桶分割
         */
        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            // Relink into lo and hi lists, preserving order
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            // 由于　TreeNode 節(jié)點之間存在雙端鏈表的關(guān)系，可以利用鏈表關(guān)系進(jìn)行 rehash
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }
            //rehash 操作之后注意對根據(jù)鏈表長度進(jìn)行　untreeify　或　treeify　操作
            if (loHead != null) {
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

        /* ------------------------------------------------------------ */
        // Red-black tree methods, all adapted from CLR
        // 左旋轉(zhuǎn) 
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            TreeNode<K,V> r, pp, rl;
            if (p != null && (r = p.right) != null) {
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
        }
        // 右旋轉(zhuǎn)
        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }
        // 保證插入后平衡，共5種插入情況  
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
        }
        // 刪除后調(diào)整平衡 聋溜，共6種刪除情況  
        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {
            for (TreeNode<K,V> xp, xpl, xpr;;)  {
                if (x == null || x == root)
                    return root;
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (x.red) {
                    x.red = false;
                    return root;
                }
                else if ((xpl = xp.left) == x) {
                    if ((xpr = xp.right) != null && xpr.red) {
                        xpr.red = false;
                        xp.red = true;
                        root = rotateLeft(root, xp);
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {
                            xpr.red = true;
                            x = xp;
                        }
                        else {
                            if (sr == null || !sr.red) {
                                if (sl != null)
                                    sl.red = false;
                                xpr.red = true;
                                root = rotateRight(root, xpr);
                                xpr = (xp = x.parent) == null ?
                                    null : xp.right;
                            }
                            if (xpr != null) {
                                xpr.red = (xp == null) ? false : xp.red;
                                if ((sr = xpr.right) != null)
                                    sr.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateLeft(root, xp);
                            }
                            x = root;
                        }
                    }
                }
                else { // symmetric
                    if (xpl != null && xpl.red) {
                        xpl.red = false;
                        xp.red = true;
                        root = rotateRight(root, xp);
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    if (xpl == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                        if ((sl == null || !sl.red) &&
                            (sr == null || !sr.red)) {
                            xpl.red = true;
                            x = xp;
                        }
                        else {
                            if (sl == null || !sl.red) {
                                if (sr != null)
                                    sr.red = false;
                                xpl.red = true;
                                root = rotateLeft(root, xpl);
                                xpl = (xp = x.parent) == null ?
                                    null : xp.left;
                            }
                            if (xpl != null) {
                                xpl.red = (xp == null) ? false : xp.red;
                                if ((sl = xpl.left) != null)
                                    sl.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateRight(root, xp);
                            }
                            x = root;
                        }
                    }
                }
            }
        }

        /**
         * 檢測是否符合紅黑樹 
         */
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
            TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (TreeNode<K,V>)t.next;
            if (tb != null && tb.next != t)
                return false;
            if (tn != null && tn.prev != t)
                return false;
            if (tp != null && t != tp.left && t != tp.right)
                return false;
            if (tl != null && (tl.parent != t || tl.hash > t.hash))
                return false;
            if (tr != null && (tr.parent != t || tr.hash < t.hash))
                return false;
            if (t.red && tl != null && tl.red && tr != null && tr.red)
                return false;
            if (tl != null && !checkInvariants(tl))
                return false;
            if (tr != null && !checkInvariants(tr))
                return false;
            return true;
        }
    }

注：將樹節(jié)點插入單獨提出來進(jìn)行分析

        // 保證插入后平衡捏浊，共5種插入情況  
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            x.red = true;
            // 死循環(huán)加變量定義
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                // xp X父節(jié)點酥郭， XPP X的祖父節(jié)點华坦，  XPPL 祖父左節(jié)點  XXPR 祖父右節(jié)點 
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                // 如果父節(jié)點是黑色， 或者XP父節(jié)點是空不从，直接返回
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                // 下面的代碼就和上面的很treeMap像了惜姐，
                if (xp == (xppl = xpp.left)) {
                    /* 第一種情況, 賦值xppl,父節(jié)點是左節(jié)點的情況,下面這種
                                    G
                      P(RED)                   U
                    */
                    if ((xppr = xpp.right) != null && xppr.red) {
                        // 如果紅樹的情況，這種情況椿息，對應(yīng)下面 圖：情況一
                        /*                        
                                                       G
                                         P(RED)              U(RED)
                                X
                       */         
                        // 改變其顏色
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        // 黑樹的情況
                        /*
                                        G
                           P(RED)              U(BLACK)
                        */
                        if (x == xp.right) {
                            // 如果插入節(jié)點在右邊 這種對應(yīng)下面 圖：情況二
                            /*
                                            G
                              P(RED)                U(BLACK)
                                      X
                            */
                            // 需要進(jìn)行左旋
                            root = rotateLeft(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        // 左旋后情況都是這種了歹袁，對應(yīng)下面 圖：情況三
                        /*
                                          G
                              P(RED)               U(BLACK)
                          X
                        */
                        // 到這，X只能是左節(jié)點了寝优，而且P是紅色条舔，U是黑色的情況
                        if (xp != null) {
                            // 把P改成黑色，G改成紅色, 以G為節(jié)點進(jìn)行右旋
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                else {
                    /* 父節(jié)點在右邊的
                               G
                       U              P(RED)
                    */
                    // 獲取U
                    if (xppl != null && xppl.red) {
                          // 紅父紅樹的情況
                         /*
                                             G
                               U(RED)               P(RED)
                        */ 
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                            // 如果插入的X是右節(jié)點
                            /*
                                                   G
                               U(BLACK)                        P(RED)
                                            X              
                            */
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        // 右旋后
                        /*
                                           G
                            U(BLACK)                 P(RED)
                                                                  X
                        */
                        if (xp != null) {
                            // 把P改成黑色乏矾，G改成紅色
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                // 以G節(jié)點左旋
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }

情況1.png

情況2.png

情況3.png

紅黑樹插入流程圖

紅黑插入流程圖.png

5.HashMap的迭代器

5.1 基礎(chǔ)迭代器--HashIterator

HashIterator是一個抽象類孟抗，封裝了迭代器內(nèi)部工作的一些操作。

    /**
     * HashIterator是HashMap的一個內(nèi)部抽象類钻心，為HashMap的迭代器
     */
    abstract class HashIterator {
        // 下一個結(jié)點
        Node<K,V> next;        // next entry to return
        // 當(dāng)前結(jié)點
        Node<K,V> current;     // current entry
        // 期望的修改次數(shù) fast-fail機(jī)制
        int expectedModCount;  // for fast-fail
        // 當(dāng)前桶索引
        int index;             // current slot
        /**
         * next將表示第一個非空桶中的第一個結(jié)點凄硼，index將表示下一個桶。
         */
        HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            // table不為空并且大小大于0
            if (t != null && size > 0) { // advance to first entry
                 // 找到table數(shù)組中第一個存在的結(jié)點捷沸，即找到第一個具有元素的桶
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }
        // 是否存在下一個結(jié)點
        public final boolean hasNext() {
            return next != null;
        }
        /**
          * nextNode函數(shù)屏蔽掉了桶的不同所帶來的差異摊沉，就好像所有元素在同一個桶中，依次進(jìn)行遍歷亿胸。
          */
        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            // 記錄next結(jié)點
            Node<K,V> e = next;
            // 若在遍歷時對HashMap進(jìn)行結(jié)構(gòu)性的修改則會拋出異常
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 下一個結(jié)點為空坯钦，拋出異常
            if (e == null)
                throw new NoSuchElementException();
            // 如果下一個結(jié)點為空，并且table表不為空侈玄；表示桶中所有結(jié)點已經(jīng)遍歷完，需尋找下一個不為空的桶
            if ((next = (current = e).next) == null && (t = table) != null) {
                // 找到下一個不為空的桶
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        public final void remove() {
            Node<K,V> p = current;
            // 當(dāng)前結(jié)點為空吟温，拋出異常
            if (p == null)
                throw new IllegalStateException();
            // 若在遍歷時對HashMap進(jìn)行結(jié)構(gòu)性的修改則會拋出異常
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 當(dāng)前結(jié)點為空
            current = null;
            K key = p.key;
            // 移除結(jié)點
            removeNode(hash(key), key, null, false, false);  
            // 賦最新值
            expectedModCount = modCount;
        }
    }

5.2 鍵迭代器--KeyIterator

    /**
     * KeyIterator類是鍵迭代器序仙，繼承自HashIterator，實現(xiàn)了Iterator接口鲁豪，可以對HashMap中的鍵進(jìn)行遍歷潘悼。
     */
    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

5.3 值迭代器--ValueIterator

    /**
     * ValueIterator類是值迭代器，繼承自HashIterator爬橡，實現(xiàn)了Iterator接口治唤，與KeyIterator類似，對值進(jìn)行遍歷
     */
    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

5.4 結(jié)點迭代器--EntryIterator

    /**
     * EntryIterator類是結(jié)點迭代器糙申，繼承自HashIterator宾添，實現(xiàn)了Iterator接口，與KeyIterator、ValueIterator類似缕陕，對結(jié)點進(jìn)行遍歷粱锐。
     */
    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

致謝：
JAVA中的數(shù)據(jù)結(jié)構(gòu) - 真正的去理解紅黑樹
HashMap的擴(kuò)容機(jī)制---resize()