1. hash概念

把關(guān)鍵字通過(guò)某個(gè)函數(shù)映射到得到一個(gè)固定值，然后這個(gè)固定值來(lái)確定數(shù)組中的某個(gè)位置，通過(guò)數(shù)組下標(biāo)一次定位就可知道這個(gè)關(guān)鍵字的位置：
　　　　　　　　存儲(chǔ)位置 = hash(關(guān)鍵字)
　　其中明刷，這個(gè)函數(shù)就是hash算法映穗。

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

HashMap的底層實(shí)現(xiàn)是： 數(shù)組 + 鏈表+紅黑樹

2.1 結(jié)點(diǎn)
我們先來(lái)看看結(jié)點(diǎn)的結(jié)構(gòu)圖：

圖片.png

static class Node<K, V> implements Map.Entry<K, V> {

        final K key; // key值
        V value; // value值
        Node<K, V> next; // 鏈地址法解決hash沖突贼涩，單鏈表的每一個(gè)節(jié)點(diǎn)都含有指向下一個(gè)結(jié)點(diǎn)的引用
        int hash;

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

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        public final String toString() {
            return key + "=" + value;
        }

        @Override
        public V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

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

    }

Node類已經(jīng)重寫了hashCode()和equal()方法茅逮。

2.2 紅黑樹
講解之前璃赡，先來(lái)看看結(jié)點(diǎn)的定義：

圖片.png

• 左旋分析
  傳入的是p結(jié)點(diǎn)，root結(jié)點(diǎn)献雅。這里要求以p結(jié)點(diǎn)為中心的左旋這顆紅黑樹碉考。

  
  
  圖片.png
  
  

  第一步：數(shù)據(jù)項(xiàng)為10的結(jié)點(diǎn)將成為這棵樹的新的root結(jié)點(diǎn)：

  
  
  圖片.png
  
  第二步：r的左邊結(jié)點(diǎn)即將成為p的右結(jié)點(diǎn)，同時(shí)中間分成的結(jié)點(diǎn)也找到了父節(jié)點(diǎn)挺身。
  
  圖片.png

第三步：判斷新的根節(jié)點(diǎn)的父節(jié)點(diǎn)是否存在侯谁，然為將新的根節(jié)點(diǎn)r設(shè)置父節(jié)點(diǎn)。
如果p結(jié)點(diǎn)的父節(jié)點(diǎn)不存在：pp = p.parent;那就是說(shuō)這個(gè)新的結(jié)點(diǎn)r就成為根節(jié)點(diǎn)了章钾，由于不能違背根節(jié)點(diǎn)必須是黑色這一原則墙贱，還必須把根節(jié)點(diǎn)設(shè)置為黑色。如下所示：

圖片.png

如果p結(jié)點(diǎn)的父節(jié)點(diǎn)存在：pp = r.parent = p.parent;這個(gè)時(shí)候我們就要分為贱傀，p結(jié)點(diǎn)原來(lái)是父節(jié)點(diǎn)的左結(jié)點(diǎn)惨撇，還是右結(jié)點(diǎn)。
如果p原來(lái)是父節(jié)點(diǎn)的左結(jié)點(diǎn)府寒，如圖所示：

圖片.png

圖片.png

第四步：現(xiàn)在我們看到r結(jié)點(diǎn)有三個(gè)分支了纺棺，但是按照紅黑樹結(jié)點(diǎn)定義，應(yīng)該只有左結(jié)點(diǎn)邪狞，右結(jié)點(diǎn)的祷蝌。右結(jié)點(diǎn)沒(méi)有變化，那么主要看看左結(jié)點(diǎn)帆卓，左結(jié)點(diǎn)應(yīng)該就是p分支的節(jié)點(diǎn)了巨朦，就相當(dāng)于：r.left = p;

圖片.png

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

對(duì)比自己寫的：

        /**
         * 以p結(jié)點(diǎn)為中心左旋棚蓄，實(shí)際將以p結(jié)點(diǎn)右子樹結(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)
         * 這里需要考慮到p結(jié)點(diǎn)堕扶，p結(jié)點(diǎn)的右結(jié)點(diǎn)rootTemp，rootTemp的左結(jié)點(diǎn)rootTempLeft梭依，p的父節(jié)點(diǎn)四個(gè)結(jié)點(diǎn)的變化稍算，考慮的時(shí)候主要考慮這些結(jié)點(diǎn)的哪些屬性變化了。
         * 比如說(shuō)p結(jié)點(diǎn)役拴，左旋之后糊探，p結(jié)點(diǎn)的父節(jié)點(diǎn)變成了rootTemp,p結(jié)點(diǎn)的右結(jié)點(diǎn)發(fā)生了變化
         * rootTemp成為了新的結(jié)點(diǎn)，左結(jié)點(diǎn)河闰，父節(jié)點(diǎn)發(fā)生了變化
         * rootTempLeft的父節(jié)點(diǎn)變成了p
         * pParent的子節(jié)點(diǎn)發(fā)生了變化科平，這個(gè)主要是根據(jù)原來(lái)p結(jié)點(diǎn)是rootTemp的左結(jié)點(diǎn)還是右結(jié)點(diǎn)。
         * 
         * @param root
         * @param p
         * @return
         */
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {
            TreeNode<K, V> rootTemp,pRightLeftTemp,pParentTemp;//主要設(shè)置新的根節(jié)點(diǎn)姜性，p結(jié)點(diǎn)的右結(jié)點(diǎn)瞪慧，p結(jié)點(diǎn)父節(jié)點(diǎn)的屬性
            if (p != null) {
                rootTemp = p.right;
                if (rootTemp != null) {
                    //中間結(jié)點(diǎn)pRightLeftTemp設(shè)置給p結(jié)點(diǎn)的右結(jié)點(diǎn)，pRightLeftTemp結(jié)點(diǎn)的父節(jié)點(diǎn)有變化污抬，需要重新設(shè)置
                    pRightLeftTemp = p.right = rootTemp.left;
                    pRightLeftTemp.parent = p;
                    //重新設(shè)置新的根節(jié)點(diǎn)的父節(jié)點(diǎn)屬性
                    pParentTemp = p.parent;
                    if (pParentTemp == null) {
                        //當(dāng)前結(jié)點(diǎn)就是root結(jié)點(diǎn)汞贸，且遵循紅黑樹root結(jié)點(diǎn)必須是黑色
                        root = rootTemp;
                        root.red = false;
                    } else if (pParentTemp.left == p) {
                        //結(jié)點(diǎn)p是父節(jié)點(diǎn)的左結(jié)點(diǎn)
                        pParentTemp.left = rootTemp;
                    } else {
                        //結(jié)點(diǎn)p是父節(jié)點(diǎn)的右結(jié)點(diǎn)
                        pParentTemp.right = rootTemp;
                    }
                    
                    rootTemp.left = p;
                    rootTemp.parent = pParentTemp;
                    p.parent = rootTemp;
                }
            }
             return root;
        }
     }

• 插入結(jié)點(diǎn)
  紅黑樹特點(diǎn)：
  （1）每個(gè)結(jié)點(diǎn)都是黑色或者是紅色。
  （2）根節(jié)點(diǎn)是黑色印机。
  （3）每個(gè)葉子結(jié)點(diǎn)是黑色。
  （4）如果一個(gè)結(jié)點(diǎn)是紅色门驾，它的子節(jié)點(diǎn)必須是黑色的射赛。（如果一個(gè)結(jié)點(diǎn)是黑色的，并不能代表其子節(jié)點(diǎn)是紅色的奶是。）
  （5）從一個(gè)結(jié)點(diǎn)到該結(jié)點(diǎn)的子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)楣责。
  插入的時(shí)候由于需要保證紅黑樹上面5條規(guī)則，因此聂沙，插入的時(shí)候我們需要根據(jù)這些規(guī)則秆麸，對(duì)紅黑樹做一些調(diào)整或者旋轉(zhuǎn)操作。
  由于要滿足第5條規(guī)則及汉，因此我們統(tǒng)一規(guī)定插入的結(jié)點(diǎn)顏色必須是紅色沮趣。這樣最低程度減小其他操作對(duì)紅黑樹的影響。
  這里插入結(jié)點(diǎn)X有三種情況
  1.插入的是根節(jié)點(diǎn)（root）
  根據(jù)規(guī)則（2）坷随，只需要把該結(jié)點(diǎn)的顏色變?yōu)楹谏纯伞?br> 2.X結(jié)點(diǎn)的父節(jié)點(diǎn)是黑色
  滿足規(guī)則（5）弧腥，則不做處理屡久。
  3.X結(jié)點(diǎn)的父節(jié)點(diǎn)是紅色
  不滿足規(guī)則（4）需要做調(diào)整徽千，通常都是通過(guò)旋轉(zhuǎn)或者改變結(jié)點(diǎn)顏色來(lái)達(dá)到紅黑樹規(guī)則的平衡。
  我們知道如果x結(jié)點(diǎn)是紅色翁狐，父節(jié)點(diǎn)是紅色，則x祖父結(jié)點(diǎn)是黑色凌蔬。

a.父節(jié)點(diǎn)是紅色露懒，叔父結(jié)點(diǎn)是紅色

圖片.png

圖片.png

圖片.png

b. 叔父結(jié)點(diǎn)是黑色
如果叔父結(jié)點(diǎn)是黑色呢啦撮？如下圖所示：

圖片.png

圖片.png

圖片.png

圖片.png

圖片.png

X結(jié)點(diǎn)為左結(jié)點(diǎn)，父節(jié)點(diǎn)為左結(jié)點(diǎn)烦租。

X結(jié)點(diǎn)為左結(jié)點(diǎn)延赌，父節(jié)點(diǎn)為左結(jié)點(diǎn)情況如圖所示：

圖片.png

圖片.png

圖片.png

X結(jié)點(diǎn)為右結(jié)點(diǎn)窃祝，父節(jié)點(diǎn)為左結(jié)點(diǎn)掐松。

X結(jié)點(diǎn)為右結(jié)點(diǎn)，父節(jié)點(diǎn)為左結(jié)點(diǎn)情況如圖所示：

X結(jié)點(diǎn)為右結(jié)點(diǎn)粪小，父節(jié)點(diǎn)為左結(jié)點(diǎn).png

父節(jié)點(diǎn)XP為中心左旋.png

以X結(jié)點(diǎn)為中心右旋轉(zhuǎn).png

圖片.png

X結(jié)點(diǎn)為左結(jié)點(diǎn)流济，父節(jié)點(diǎn)為右結(jié)點(diǎn)。

結(jié)點(diǎn)為右結(jié)點(diǎn)腌闯，父節(jié)點(diǎn)為左結(jié)點(diǎn)

結(jié)點(diǎn)為右結(jié)點(diǎn)绳瘟，父節(jié)點(diǎn)為左結(jié)點(diǎn).png

父節(jié)點(diǎn)XP為中心右旋.png

X結(jié)點(diǎn)為中心左旋.png

圖片.png

X結(jié)點(diǎn)為右結(jié)點(diǎn)擅腰，父節(jié)點(diǎn)為右結(jié)點(diǎn)。

X結(jié)點(diǎn)為右結(jié)點(diǎn)翁潘，父節(jié)點(diǎn)為右結(jié)點(diǎn)的情況如圖所示：

圖片.png

圖片.png

圖片.png

/**
        /**
         * 插入結(jié)點(diǎn),必須保證紅黑樹的規(guī)則，所以要經(jīng)歷旋轉(zhuǎn)或者顏色調(diào)整 
         * 紅黑樹特點(diǎn)： 
         * （1）每個(gè)結(jié)點(diǎn)都是黑色或者是紅色取刃。 
         * （2）根節(jié)點(diǎn)是黑色蹋肮。
         * （3）每個(gè)葉子結(jié)點(diǎn)是黑色。 
         * （4）如果一個(gè)結(jié)點(diǎn)是紅色璧疗，它的子節(jié)點(diǎn)必須是黑色的坯辩。（如果一個(gè)結(jié)點(diǎn)是黑色的，并不能代表其子節(jié)點(diǎn)是紅色的崩侠。）
         * （5）從一個(gè)結(jié)點(diǎn)到該結(jié)點(diǎn)的子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)
         * 插入的是紅色結(jié)點(diǎn)漆魔，這樣避免違背規(guī)則(4)，簡(jiǎn)化了紅黑樹的插入操作
         * 插入需要分情況：
         * 1.插入的是根節(jié)點(diǎn)却音，結(jié)點(diǎn)顏色設(shè)置為黑色即可改抡。
         * 2.插入結(jié)點(diǎn)的父節(jié)點(diǎn)是黑色，不做改變僧家。
         * 3.插入父節(jié)點(diǎn)是紅色又分為兩種情況：3.1 叔父結(jié)點(diǎn)是紅色雀摘，只需要將插入結(jié)點(diǎn)x的父節(jié)點(diǎn)xp,叔父結(jié)點(diǎn)xpb設(shè)置為黑色，x的祖父結(jié)點(diǎn)xpp設(shè)置為紅色八拱。
         * 3.2 叔父結(jié)點(diǎn)是黑色阵赠，又分為四種情況：
         * 3.2.1 xp結(jié)點(diǎn)是左結(jié)點(diǎn)，x是左結(jié)點(diǎn)
         * 3.2.2 xp結(jié)點(diǎn)是左結(jié)點(diǎn)肌稻，x是右結(jié)點(diǎn)
         * 3.2.3 xp結(jié)點(diǎn)是右結(jié)點(diǎn)清蚀，x是左結(jié)點(diǎn)
         * 3.2.4 xp結(jié)點(diǎn)是右結(jié)點(diǎn)，x是右結(jié)點(diǎn)
         * @param root
         * @param x
         * @return
         */
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {
            //三種情況：1.插入的是根節(jié)點(diǎn)爹谭，直接插入枷邪，并保證規(guī)則（1）,將結(jié)點(diǎn)變?yōu)楹谏?            //2.插入的結(jié)點(diǎn)x的父節(jié)點(diǎn)是黑色，滿足規(guī)則（5）诺凡。直接插入东揣。
            //3.插入的結(jié)點(diǎn)x的父節(jié)點(diǎn)是紅色，不滿足規(guī)則（4）腹泌，需要經(jīng)過(guò)旋轉(zhuǎn)或者改變顏色進(jìn)行調(diào)整嘶卧。
            
            x.red = true;//默認(rèn)插入結(jié)點(diǎn)是紅色，保證規(guī)則(5),簡(jiǎn)化紅黑樹操作的復(fù)雜性
            for (TreeNode<K,V> xp,xpp,xppl,xppr;;) {
                if (x != null) {
                    xp = x.parent;
                    //第一種情況凉袱，插入根節(jié)點(diǎn)
                    if (xp == null) {
                        x.red = false;
                        return x;
                    } else if (!xp.red || (xpp = xp.parent) == null) {
                        //第二種情況芥吟，父節(jié)點(diǎn)是黑色結(jié)點(diǎn)侦铜，不做處理
                        return root;
                    }
                    
                    xppl = xpp.left;
                    if (xp == xppl) {
                        //xp為左結(jié)點(diǎn)
                        xppr = xpp.right;
                        //叔父結(jié)點(diǎn)為紅色，結(jié)點(diǎn)X的祖父結(jié)點(diǎn)XPP顏色設(shè)置為紅色钟鸵，XP和XPB設(shè)置為黑色
                        if (xppr != null && xppr.red) {
                            xp.red = false;
                            xpp.red = true;
                            xppr.red = false;
                            x = xpp;//繼續(xù)向上迭代
                        }
                        else {
                            //如果x為xp的右結(jié)點(diǎn)钉稍，需要先進(jìn)行xp為中心的左旋
                            if (x == xp.right) {
                                root = rotateLeft(root,xp);
                                x = xp;//xp結(jié)點(diǎn)與x結(jié)點(diǎn)位置交換
                                xp = x.parent;
                                xpp = xp == null?null : xp.parent;
                            }
                            
                            //XP設(shè)置成黑色，XPP設(shè)置成紅色棺耍，以XPP為中心右旋
                            if (xp != null) {
                                xp.red = false;
                                if (xpp != null) {
                                    xpp.red = true;
                                    root = rotateRight(root, xpp);
                                    
                                }
                            }
                        }
                    }
                    else {
                        //xp結(jié)點(diǎn)為右結(jié)點(diǎn)
                        
                        //結(jié)點(diǎn)X的祖父結(jié)點(diǎn)XPP顏色設(shè)置為紅色贡未，X和XPPL設(shè)置為黑色
                        if (xppl != null && xppl.red) {
                            xpp.red = true;
                            x.red = false;
                            xppl.red = false;
                            x = xpp;//繼續(xù)向上迭代
                        }
                        else {
                            if (x == xp.left) {
                                //如果是左結(jié)點(diǎn),先以XP為中心右旋
                                root = rotateRight(root, xp);
                                x = xp;
                                xp = x.parent;
                                xpp = xp == null?null:xp.parent;
                            }
                            
                            //XP設(shè)置成黑色，XPP設(shè)置成紅色烈掠，以XPP為中心左旋
                            if (xp != null) {
                                xp.red = false;
                                if (xpp != null) {
                                    xpp.red = true;
                                    root = rotateLeft(root, xpp);
                                }
                            }
                        }
                    }
                }
            }
        }
     }

為了更直觀的看這個(gè)源代碼羞秤，我們現(xiàn)在畫上流程圖：

條件結(jié)構(gòu)流程圖(1).png

2.3 具體的HashMap的數(shù)據(jù)結(jié)構(gòu)
具體的HashMap的數(shù)據(jù)結(jié)構(gòu)如下所示：

圖片.png

3. 如何解決hash沖突

我們知道這種通過(guò)函數(shù)得到的固定值，通過(guò)hash()算法之后左敌，有可能存在key1和key2得到的固定值一致瘾蛋，這樣定位到的數(shù)組地址一致了，引起了hash沖突矫限。那么如何解決這個(gè)hash沖突呢哺哼？
解決hash沖突有四種方法：開(kāi)放地址法，再hash法叼风，鏈地址法取董，建立公共溢出區(qū)。

• 開(kāi)放地址法
  這種方法也稱再散列法无宿，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時(shí)茵汰，以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址p1孽鸡，如果p1仍然沖突蹂午，再以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址p2彬碱，…豆胸，直到找出一個(gè)不沖突的哈希地址pi ，將相應(yīng)元素存入其中巷疼。這種方法有一個(gè)通用的再散列函數(shù)形式：

Hi=（H（key）+di）% m i=1晚胡，2，…嚼沿，n

其中H（key）為哈希函數(shù)估盘，m 為表長(zhǎng)，di稱為增量序列骡尽。增量序列的取值方式不同忿檩，相應(yīng)的再散列方式也不同。主要有以下三種：線性探測(cè)再散列爆阶，二次探測(cè)再散列，偽隨機(jī)探測(cè)再散列。
線性探測(cè)再散列：這種方法是線性的辨图，沖突發(fā)生時(shí)班套，在數(shù)組中查找下一個(gè)地址，一直找到一個(gè)為null的地址來(lái)存放這個(gè)元素故河。缺點(diǎn)是比較耗時(shí)吱韭。
二次探測(cè)再散列：沖突發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探測(cè)鱼的，比較靈活理盆。
偽隨機(jī)探測(cè)再散列：具體實(shí)現(xiàn)時(shí)，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器凑阶，（如i=(i+p) % m）猿规，并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)。然后隨機(jī)探測(cè)宙橱，一直找到不沖突的hash地址姨俩。

• 再hash法
  這種方法是同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)：
  Hi=RH1（key） i=1，2师郑，…环葵，k
  當(dāng)哈希地址Hi=RH1（key）發(fā)生沖突時(shí)，再計(jì)算Hi=RH2（key）……宝冕，直到?jīng)_突不再產(chǎn)生张遭。增加了計(jì)算時(shí)間。
• 鏈地址法
  這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個(gè)稱為同義詞鏈的單鏈表地梨，并將單鏈表的頭指針存在哈希表的第i個(gè)單元中菊卷，因而查找、插入和刪除主要在同義詞鏈中進(jìn)行湿刽。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況的烁。目前java實(shí)現(xiàn)HashMap,就是采用這種方法。
• 建立公共溢出區(qū)
  建立了一個(gè)公共溢出區(qū)诈闺，一旦發(fā)現(xiàn)hash沖突渴庆，將其放入到這個(gè)公共溢出區(qū)。增加了額外空間雅镊。

4. HashMap變量以及常量分析

常量：

    /*****************************************************常量*********************************************************/
    //默認(rèn)初始化容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  //16
    
    //最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    //默認(rèn)負(fù)載因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    //樹形結(jié)構(gòu)存儲(chǔ)的閾值襟雷，就是說(shuō)當(dāng)node結(jié)點(diǎn)樹超過(guò)這個(gè)閾值，則將鏈表轉(zhuǎn)為樹形結(jié)構(gòu)存儲(chǔ)仁烹，將查找元素的時(shí)間效率從O(n)降低到O（logN）
    static final int TREEIFY_THRESHOLD = 8;
    
    //由樹轉(zhuǎn)換成鏈表的閾值
    static final int UNTREEIFY_THRESHOLD = 6;
    
    //樹形結(jié)構(gòu)最小容量
    static final int MIN_TREEIFY_CAPACITY = 64;

變量：

/*****************************************************fileds*********************************************************/
    // 定義數(shù)組
    Node<K, V>[] table;
    //實(shí)際擁有的鍵值對(duì)
    transient Set<Map.Entry<K,V>> entrySet;
    
    //key-value對(duì)的數(shù)量
    transient int size;
    
    //被修改次數(shù) 
    transient int modCount;
    
    //HashMap的實(shí)際key-values對(duì)的數(shù)量size大于threshold(key-value對(duì)的臨界值)時(shí)會(huì)執(zhí)行resize（擴(kuò)容）操作
    int threshold;
    
    //裝載因子耸弄。裝載因子用來(lái)衡量HashMap滿的程度。loadFactor的默認(rèn)值為0.75f.計(jì)算HashMap的實(shí)時(shí)裝載因子的方法為：size/capacity卓缰，而不是占用桶的數(shù)量去除以capacity计呈。
    final float loadFactor;

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

/******************************************************構(gòu)造方法***************************************************/
    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);//根據(jù)初始化容量界定table的key-value對(duì)的臨界值砰诵，返回一個(gè)比給定整數(shù)大最接近的2的冪次方整數(shù)
    }
    /**
     * 空構(gòu)造器，默認(rèn)負(fù)載因子為0.75
     */
    public HashMap(){
         this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }
    /**
     * 
     * @param initialCapacity 初始容量
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

6. HashMap常用輔助方法

6.1 桶的下標(biāo)計(jì)算方法
HashMap中通過(guò)hash（）方法來(lái)定位key-values對(duì)在桶中的位置捌显。如下代碼所示:

tab[(n - 1) & hash]

而我們知道一個(gè)好的hash()方法茁彭，盡最大可能解決沖突問(wèn)題使得key-values鍵值對(duì)均勻的分散在桶中。
設(shè)計(jì)者想了一個(gè)顧全大局的方法(綜合考慮了速度扶歪、作用理肺、質(zhì)量)，就是把高16bit和低16bit異或了一下善镰。設(shè)計(jì)者還解釋到因?yàn)楝F(xiàn)在大多數(shù)的hashCode的分布已經(jīng)很不錯(cuò)了妹萨，就算是發(fā)生了碰撞也用O(logn)的tree去做了。僅僅異或一下炫欺，既減少了系統(tǒng)的開(kāi)銷乎完，也不會(huì)造成的因?yàn)楦呶粵](méi)有參與下標(biāo)的計(jì)算(table長(zhǎng)度比較小時(shí))，從而引起的碰撞竣稽。

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

可以看到這個(gè)函數(shù)大概的作用就是：高16bit不變囱怕，低16bit和高16bit做了一個(gè)異或，這樣使得高位也可以參與hash毫别，更大程度上減少了碰撞率娃弓。
下面舉例說(shuō)明下，n為table的長(zhǎng)度岛宦，這里假設(shè)n=16：

圖片.png

從上面結(jié)果我們可以看到台丛，index=5;
這個(gè)時(shí)候再高16位參與運(yùn)算下，減少碰撞的可能性砾肺。

6.2 擴(kuò)容方法resize（）

• 擴(kuò)容條件
  首先挽霉，我們必須知道hashmap在什么情況下需要擴(kuò)容呢文黎？esize方法是在hashmap中的鍵值對(duì)size大于閥值threshold時(shí)或者table初始化時(shí)秸应，就調(diào)用resize方法進(jìn)行擴(kuò)容歇攻。
• 擴(kuò)容倍數(shù)
  然后我們還要了解到具體擴(kuò)容之后做了些什么筷黔？每次擴(kuò)容后，容量為原來(lái)的 2 倍薯鼠，之后重新計(jì)算index叙甸，把節(jié)點(diǎn)再放到新的bucket中秧耗。
  然后我們來(lái)看下源代碼：

/**
     * 數(shù)組擴(kuò)容
     * @return
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//暫存原來(lái)的table
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            //如果原來(lái)的容量已經(jīng)超過(guò)最大值,不需要擴(kuò)容了,你去碰撞去吧.閥值為證書最大值
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } 
            //如果當(dāng)前hash桶數(shù)組的長(zhǎng)度在擴(kuò)容后仍然小于最大容量 并且oldCap大于默認(rèn)值16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY){
                newThr = oldThr << 1; //擴(kuò)充為原來(lái)的2倍
            }
        }
        
        else if (oldThr > 0){
            newCap = oldThr;
        }
        else {
             newCap = DEFAULT_INITIAL_CAPACITY;
             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //計(jì)算新的resie上線
        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" })
        //重新構(gòu)造一個(gè)新的table,并重新計(jì)算index番官，然后將原來(lái)的oldTab遷移到新的newTab中
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            //重新遷移
            for (int j = 0; j < oldCap; ++j) {
                 Node<K,V> e;
                 if (oldTab[j] != null) {
                    e = oldTab[j];
                    oldTab[j] = null;//釋放空間
                    if (e.next == null){
                        //如果桶中只有這一個(gè)元素e,重新計(jì)算index并將e賦值到newTab中
                        newTab[e.hash & (newCap - 1)] = e;
                    } 
                    //如果是一顆紅黑樹或者鏈表結(jié)構(gòu)
                    else if (e instanceof TreeNode) {
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    }
                    else {
                        //將這個(gè)桶中的鏈表賦值到新table中
                        Node<K, V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            //擴(kuò)容為原來(lái)的兩倍庐完，因此要么重新hash之后再原位置，是在原位置再移動(dòng)2次冪的位置徘熔。元素在重新計(jì)算hash之后门躯，因?yàn)閚變?yōu)?倍，那么n-1的mask范圍在高位多1bit酷师，
                            //因此新的index就會(huì)分為原位置和原索引+oldCap讶凉。因此只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好了染乌，是0的話索引沒(méi)變，是1的話索引變成“原索引+oldCap”缀遍。
                             next = e.next;//一個(gè)一個(gè)遍歷
                             //原索引
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 原索引+oldCap
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 原索引放到bucket里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 原索引+oldCap放到bucket里
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                    
                }
            }
        }
        
        return newTab;
    }

擴(kuò)容為原來(lái)的兩倍慕匠，因此要么重新hash之后再原位置，是在原位置再移動(dòng)2次冪的位置域醇。元素在重新計(jì)算hash之后，因?yàn)閚變?yōu)?倍蓉媳，那么n-1的mask范圍在高位多1bit譬挚，因此新的index就會(huì)分為原位置和原索引+oldCap。因此只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好了酪呻，是0的話索引沒(méi)變减宣，是1的話索引變成“原索引+oldCap”。這樣避免 了重新計(jì)算hash玩荠。
如圖所示：

jdk1.8 hashMap擴(kuò)容例圖.png

7. HashMap常用方法

常用方法無(wú)非是put（）和get()方法漆腌。

• put()方法

  
  
  HashMap之put(K key,V value)(1).png
  
  

  如上圖所示，已經(jīng)畫好了put(K key,V value)方法的流程圖阶冈，我們具體來(lái)分析一下執(zhí)行過(guò)程：

1. 第一次put(K key,V value)的時(shí)候闷尿，由于最開(kāi)始沒(méi)有初始化table，因此需要先進(jìn)行初始化女坑。
   當(dāng)(tab = table) == null || (n = tab.length) == 0時(shí)填具，表示我們的table未初始化，我們先對(duì)table進(jìn)行初始化匆骗，由于table實(shí)際是數(shù)組劳景，因此我們必須先知道數(shù)組的大小，這個(gè)時(shí)候需要第一次擴(kuò)容：n = (tab = resize()).length;
2. 如果我們的數(shù)組已經(jīng)初始化過(guò)了碉就，我們就要找到當(dāng)前key對(duì)應(yīng)table中的位置盟广，通過(guò)hash（）方法來(lái)獲取index,并定位到這個(gè)key對(duì)應(yīng)的值：p = tab[i = (n - 1) & hash]。
3. 如果定位到的這個(gè)tab[index]==null瓮钥，就說(shuō)明現(xiàn)在table里面還沒(méi)有任何的key-value筋量。此時(shí)我們直接插入即可。然后執(zhí)行步驟5.如果tab[index]!=null,表示我們table中現(xiàn)在有值骏庸，說(shuō)明這是鏈表或者紅黑樹的第一個(gè)元素毛甲，只需要先判斷tab[index]這個(gè)值的key是否等于插入的key值：
   p.hash == hash &&
   ((k = p.key) == key || (key != null && key.equals(k)))
   如果這些條件都滿足，就說(shuō)明tab[index]存放的就是這個(gè)key對(duì)應(yīng)的鍵值對(duì)具被，現(xiàn)在只需要覆蓋原來(lái)的key-value對(duì)就行了玻募。e = p;如果不相等則繼續(xù)執(zhí)行步驟4.
4. 現(xiàn)在我們知道tab[index]作為第一個(gè)元素，key不相等了一姿，那么我們需要遍歷紅黑樹或者鏈表來(lái)判斷如何插入七咧。如果tab[index]是紅黑樹結(jié)點(diǎn)跃惫，則我們只需要直接插入到紅黑樹即可。否則艾栋，表示我們需要遍歷鏈表爆存，如果鏈表的節(jié)點(diǎn)數(shù)超過(guò)8，則要將鏈表轉(zhuǎn)為紅黑樹蝗砾，再執(zhí)行紅黑樹的插入先较。如果沒(méi)有超過(guò)8，該結(jié)點(diǎn)又不存在鏈表中悼粮，我們需要將該結(jié)點(diǎn)插入到鏈表的頭結(jié)點(diǎn)闲勺。如果存在，則直接覆蓋即可扣猫。
5. 插入執(zhí)行完了菜循，我們需要進(jìn)行一次預(yù)擴(kuò)容。就是說(shuō)當(dāng)table中key-value對(duì)數(shù)量超過(guò)閾值申尤，我們需要進(jìn)行擴(kuò)容操作癌幕。
   源代碼實(shí)現(xiàn)如下：

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

java1.8實(shí)現(xiàn)的HashMap在代碼上盡量簡(jiǎn)潔了，但是可讀性不太好昧穿，為了能夠最大程度理解其思想勺远，我用自己的方式實(shí)現(xiàn)了下，其實(shí)思路一樣：

    /**
     * 
     * @param hash
     * @param key
     * @param value
     * @param onlyIfAbsent
     * @param evict
     * @return
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        tab = table;
        n = tab.length;
        //第一次插入粤咪，需要對(duì)table表初始化
        if (tab == null || n == 0) {
            //擴(kuò)容
            tab = resize();
            n = tab.length;
        }
        
        //計(jì)算index
        index = (n -1)& hash;
        //獲取inddex下標(biāo)的元素
        p = tab[index];
        //此時(shí)index處沒(méi)有key-value對(duì)谚中，直接插入
        if (p == null) {
            tab[index] = new Node<>(hash, key, value, null);
        }
        //此時(shí)index處有key-value對(duì)，先判斷作為首元素的tab[index]的hash和key是否相等來(lái)判斷寥枝，該key的元素是否存在宪塔，如果存在，直接覆蓋囊拜。
        else {
            Node<K, V> e;
            K k = p.key;
            //tab[index]就是給定key對(duì)應(yīng)的鍵值對(duì)某筐，只需要改變value值即可
            if (p.hash == hash && ( key == k || (key != null && key.equals(k)))) {
                e = p;
            }
            //接下來(lái)是首元素不是該key對(duì)應(yīng)的key-value對(duì)，就需要判斷tab[index]對(duì)應(yīng)的是鏈表還是樹形結(jié)構(gòu)
            else if (p instanceof TreeNode) {
                //1.是紅黑樹結(jié)點(diǎn)冠跷，直接插入到紅黑樹
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            }
            else {
                //2.是鏈表元素結(jié)點(diǎn)南誊，從鏈表第二個(gè)元素開(kāi)始遍歷。
                for (int binCount = 0; ; ++binCount){
                    e = p.next;//此時(shí)說(shuō)明tab[index]里面只有一個(gè)元素蜜托，直接插入到頭結(jié)點(diǎn)即可
                    if ((e = p.next) == null) {
                        p.next = new Node<>(hash, key, value, null);
                        //鏈表長(zhǎng)度大于8轉(zhuǎn)換為紅黑樹進(jìn)行處理
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果遍歷過(guò)程中發(fā)現(xiàn)key值對(duì)應(yīng)有key-value存在抄囚，則直接覆蓋
                    if (p.hash == hash && ( key == k || (key != null && key.equals(k)))) {
                        break;
                    }
                    p = e;
                }
            }
        }
        
        
        ++modCount;
        //如果容量超過(guò)閾值，需要擴(kuò)容
        if (++size > threshold){
            resize();
        }
        afterNodeInsertion(evict);
        return null;
    }

• get(K key)方法

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

 /**
     * 獲取key對(duì)應(yīng)的key-value對(duì)
     * @param hash
     * @param key
     * @return
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        tab = table;
        //table為空
        if (tab == null) {
            return null;
        }
        
        //否則查找的時(shí)候橄务，需要知道是紅黑樹查找還是鏈表查找
        int index = (n-1) & hash;
        first = tab[index];
        if (first != null) {
            //就是說(shuō)key定位到的位置元素是存在的
            k = first.key;
            if (first.hash == hash && (key == k || (k != null && k.equals(key))) ) {
                //如果首元素就是key對(duì)應(yīng)的key-value,直接返回
                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);
                
            }
        }
        //未找到key-value對(duì)幔托，返回null
        return null;
    }

HashMap的get(K key)方法分析.png

從我們的源碼分析知道，當(dāng)tab[index]下的元素超過(guò)8，則將鏈表轉(zhuǎn)為紅黑樹重挑，這樣查找效率就由O（n）降低為O(logN)了嗓化。

8. 特點(diǎn)

• HashMap允許null的value,null的key.
• HashMap大致和Hashtable實(shí)現(xiàn)和功能一致,除了HashMap不是線程安全的集合,允許為null的value和key.
• HahsMap不保證元素順序,特別是它不保證該順序恒久不變.
• HahsMap為get和put操作提供穩(wěn)定的性能,前提是hash()函數(shù)能夠在桶中適當(dāng)?shù)姆稚⒃?
• HashMap有兩個(gè)重要因素影響其性能：初始化容量initialCapacity和負(fù)載因子loadFactor.
• capacity代表table的桶的個(gè)數(shù)，initialCapacity僅僅在創(chuàng)建table的時(shí)候賦值.當(dāng)hash table中鍵值對(duì)超過(guò)了負(fù)載因子*當(dāng)前容量的時(shí)候谬哀，需要進(jìn)行rehashed（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)）刺覆。
• 此實(shí)現(xiàn)不是同步的,如果多個(gè)線程同時(shí)訪問(wèn)一個(gè)哈希映射，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了該映射史煎，則它必須 保持外部同步谦屑，比如：Map m = Collections.synchronizedMap(new HashMap(...)); .
• 迭代器的fast-fail僅用來(lái)檢測(cè)錯(cuò)誤.
• 引入紅黑樹，提升了查找效率.