一、先來熟悉一下我們常用的HashMap:

hashing(散列法或哈希法)的概念

散列法（Hashing）是一種將字符組成的字符串轉(zhuǎn)換為固定長度的數(shù)值來取索引值的方法，稱為散列法贬芥，也叫哈希法。由于通過更短的哈希值比用原始值進行數(shù)據(jù)庫搜索更快宣决，這種方法一般用來在數(shù)據(jù)庫中建立索引并進行搜索蘸劈，同時還用在各種解密算法中。

概述

1尊沸、HashMap繼承AbstractMap實現(xiàn)Map威沫，Cloneable，Serializable接口洼专，
2棒掠、HashMap的底層基于哈希表(散列表)，數(shù)據(jù)結(jié)構(gòu)是“鏈表散列”屁商，也就是數(shù)組+鏈表 ：通過對元素hash算法計算出元素的索引存放位置烟很，遇到多個元素的hash值相同就產(chǎn)生了hash沖突，也叫做哈希碰撞蜡镶，HashMap即是采用了鏈地址法雾袱，也就是數(shù)組+鏈表的方式將多個元素的地址關(guān)聯(lián)起來，JDK7對鏈表頭部插入方法官还，JDK8對鏈表尾部插入方法芹橡。
3、允許使用null 建和null值望伦，因為key不允許重復(fù)林说，因此只能有一個鍵為null,當鍵為null時會存到數(shù)組的第一個位置煎殷。
4、HashMap插入是無序的腿箩，線程不安全蝌数，效率高；

• HashMap 的優(yōu)化
  HashMap 在java7和java8上有所區(qū)別度秘，當然java8的效率要更好一些，主要是java8的HashMap在java7的基礎(chǔ)上增加了紅黑樹這種數(shù)據(jù)結(jié)構(gòu)饵撑，降低在桶里面查找數(shù)據(jù)的復(fù)雜度剑梳，當然還有一些其他的優(yōu)化，比如resize的優(yōu)化等滑潘。

哈希表

數(shù)組：一段連續(xù)控件存儲數(shù)據(jù)垢乙，指定下標的查找，時間復(fù)雜度O(1),通過給定值查找语卤，需要遍歷數(shù)組追逮，自已對比復(fù)雜度為O（n） 二分查找插值查找，復(fù)雜度為O(logn)
線性鏈表：增 刪除僅處理結(jié)點粹舵，時間復(fù)雜度O(1)查找需要遍歷也就是O(n)
二叉樹：對一顆相對平衡的有序二叉樹钮孵，對其進行插入，查找眼滤，刪除巴席，平均復(fù)雜度O(logn)
哈希表：哈希表中進行添加，刪除诅需，查找等操作漾唉，性能十分之高，不考慮哈希沖突的情況下堰塌，僅需一次定位即可完成赵刑，時間復(fù)雜度為O(1)哈希表的主干就是數(shù)組

hash沖突

如果兩個不同的元素，通過哈希函數(shù)得出的實際存儲地址相同怎么辦场刑？也就是說般此，當我們對某個元素進行哈希運算疮方，得到一個存儲地址寸宵，然后要進行插入的時候，發(fā)現(xiàn)已經(jīng)被其他元素占用了侄柔，其實這就是所謂的哈希沖突施籍，也叫哈希碰撞居扒。前面我們提到過，哈希函數(shù)的設(shè)計至關(guān)重要丑慎，好的哈希函數(shù)會盡可能地保證 計算簡單和散列地址分布均勻,但是喜喂，我們需要清楚的是瓤摧，數(shù)組是一塊連續(xù)的固定長度的內(nèi)存空間，再好的哈希函數(shù)也不能保證得到的存儲地址絕對不發(fā)生沖突玉吁。那么哈希沖突如何解決呢照弥？哈希沖突的解決方案有多種:開放定址法（發(fā)生沖突，繼續(xù)尋找下一塊未被占用的存儲地址）进副，再散列函數(shù)法这揣，鏈地址法，而HashMap即是采用了鏈地址法影斑，也就是數(shù)組+鏈表的方式

鏈表則是主要為了解決哈希沖突而存在的给赞，如果定位到的數(shù)組位置不含鏈表（當前entry的next指向null）,那么對于查找，添加等操作很快矫户，僅需一次尋址即可片迅；如果定位到的數(shù)組包含鏈表，對于添加操作皆辽，其時間復(fù)雜度為O(n)柑蛇，首先遍歷鏈表，存在即覆蓋驱闷，否則新增耻台；對于查找操作來講，仍需遍歷鏈表空另，然后通過key對象的equals方法逐一比對查找粘我。所以，性能考慮痹换，HashMap中的鏈表出現(xiàn)越少征字，性能才會越好

繼承關(guān)系

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

基本屬性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列號
    private static final long serialVersionUID = 362498820763181265L;    
    // 默認的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默認的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 當桶(bucket)上的結(jié)點數(shù)大于這個值時會轉(zhuǎn)成紅黑樹
    static final int TREEIFY_THRESHOLD = 8; 
    // 當桶(bucket)上的結(jié)點數(shù)小于這個值時樹轉(zhuǎn)鏈表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對應(yīng)的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存儲元素的數(shù)組，總是2的冪次倍
    transient Node<k,v>[] table; 
    // 存放具體元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的個數(shù)娇豫，注意這個不等于數(shù)組的長度匙姜。
    transient int size;
    // 每次擴容和更改map結(jié)構(gòu)的計數(shù)器
    transient int modCount;   
    // 臨界值 當實際大小(容量*填充因子)超過臨界值時，會進行擴容
    int threshold;
    // 加載因子
    final float loadFactor;
} 

loadFactor加載因子

• loadFactor加載因子是控制數(shù)組存放數(shù)據(jù)的疏密程度冯痢，loadFactor越趨近于1氮昧，那么 數(shù)組中存放的數(shù)據(jù)(entry)也就越多，也就越密浦楣，也就是會讓鏈表的長度增加袖肥，loadFactor越小，也就是趨近于0振劳，數(shù)組中存放的數(shù)據(jù)(entry)也就越少椎组，也就越稀疏。
• loadFactor太大導(dǎo)致查找元素效率低历恐，太小導(dǎo)致數(shù)組的利用率低寸癌，存放的數(shù)據(jù)會很分散专筷。loadFactor的默認值為0.75f是官方給出的一個比較好的臨界值。
• 給定的默認容量為 16蒸苇，負載因子為 0.75磷蛹。Map 在使用過程中不斷的往里面存放數(shù)據(jù)，當數(shù)量達到了 16 * 0.75 = 12 就需要將當前 16 的容量進行擴容溪烤，而擴容這個過程涉及到 rehash味咳、復(fù)制數(shù)據(jù)等操作，所以非常消耗性能檬嘀。

threshold

• threshold = capacity * loadFactor槽驶，當Size>=threshold的時候，那么就要考慮對數(shù)組的擴增了枪眉，也就是說，這個的意思就是 衡量數(shù)組是否需要擴增的一個標準再层。
• HashMap的初始桶的數(shù)量為16贸铜，loadFact為0.75,當桶里面的數(shù)據(jù)記錄超過閾值的時候，HashMap將會進行擴容則操作聂受，每次都會變?yōu)樵瓉泶笮〉?倍蒿秦，直到設(shè)定的最大值之后就無法再resize了。

HashMap的擴容操作是一項很耗時的任務(wù)蛋济，所以如果能估算Map的容量棍鳖，最好給它一個默認初始值，避免進行多次擴容碗旅。HashMap的線程是不安全的渡处，多線程環(huán)境中推薦是ConcurrentHashMap。

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

HashMap的底層就是一個數(shù)組祟辟，數(shù)組中每一項有事一個鏈表医瘫，當新建一個HashMap時候，就會初始化一個數(shù)組旧困，查看源碼如下醇份，直接看重點，table = new Entry[capacity]; 創(chuàng)建一個Entry數(shù)組吼具，也就是上面的table ,這個Entry結(jié)構(gòu)就是static的包含key value 還有一個next的指針僚纷，指向下一個元素的引用，也就構(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);

    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}

Node節(jié)點類源碼

// 繼承自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;// 哈希值拗盒，存放元素到hashmap中時用來與其他元素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; }
        // 重寫hashCode()方法
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        // 重寫 equals() 方法
        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;
        }
}
}

樹節(jié)點類源碼:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // 父
        TreeNode<K,V> left;    // 左
        TreeNode<K,V> right;   // 右
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;           // 判斷顏色
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        // 返回根節(jié)點
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
       }

構(gòu)造方法

// 默認構(gòu)造函數(shù)怖竭。
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
     }
     
     // //指定初始容量的構(gòu)造方法
     public HashMap(int initialCapacity) {
         this(initialCapacity, DEFAULT_LOAD_FACTOR);
     }
     
     // //指定初始容量和負載因子
     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);
     }

     // 指定集合，轉(zhuǎn)化為HashMap
     public HashMap(Map<? extends K, ? extends V> m) {
         this.loadFactor = DEFAULT_LOAD_FACTOR;
         putMapEntries(m, false);
        //下面會分析到這個方法
     }

HashMap提供了四個構(gòu)造方法陡蝇，構(gòu)造方法中 侵状，依靠第三個方法來執(zhí)行的赞弥，但是前三個方法都沒有進行數(shù)組的初始化操作，即使調(diào)用了構(gòu)造方法此時存放HaspMap中數(shù)組元素的table表長度依舊為0 趣兄。在第四個構(gòu)造方法中調(diào)用了inflateTable()方法完成了table的初始化操作绽左，并將m中的元素添加到HashMap中。

• putMapEntries方法：

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
            // 未初始化艇潭，s為m的實際元素個數(shù)
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 計算得到的t大于閾值拼窥，則初始化閾值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素個數(shù)大于閾值蹋凝，進行擴容處理
        else if (s > threshold)
            resize();
        // 將m中的所有元素添加至HashMap中
        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);
        }
    }
}

主要方法

HashMap的put方法流程

下圖展示了java8中put方法的處理邏輯鲁纠，比java7多了紅黑樹部分，以及在一些細節(jié)上的優(yōu)化鳍寂，put邏輯和java7中是一致的改含。

image.png

HashMap只提供了put用于添加元素，putVal方法只是給put方法調(diào)用的一個方法迄汛，并沒有提供給用戶使用捍壤。

• 對putVal方法添加元素的分析如下：
  ①如果定位到的數(shù)組位置沒有元素 就直接插入。
  ②如果定位到的數(shù)組位置有元素就和要插入的key比較鞍爱，如果key相同就直接覆蓋鹃觉，如果key不相同，就判斷p是否是一個樹節(jié)點睹逃，如果是就調(diào)用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)將元素添加進入盗扇。如果不是就遍歷鏈表插入(插入的是鏈表尾部)。

JDK1.8 put方法的代碼

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
Node<K,V>[] tab; 
Node<K,V> p; 
int n, i;
    // table未初始化或者長度為0沉填，進行擴容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 確定元素存放在哪個桶中疗隶，桶為空，新生成結(jié)點放入桶中(此時翼闹，這個結(jié)點是放在數(shù)組中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已經(jīng)存在元素
    else {
        Node<K,V> e; K k;
        // 比較桶中第一個元素(數(shù)組中的結(jié)點)的hash值相等抽减，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 將第一個元素賦值給e，用e來記錄
                e = p;
        // hash值不相等橄碾，即key不相等卵沉；為紅黑樹結(jié)點
        else if (p instanceof TreeNode)
            // 放入樹中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 為鏈表結(jié)點
        else {
            // 在鏈表最末插入結(jié)點
            for (int binCount = 0; ; ++binCount) {
                // 到達鏈表的尾部
                if ((e = p.next) == null) {
                    // 在尾部插入新結(jié)點
                    p.next = newNode(hash, key, value, null);
                    // 結(jié)點數(shù)量達到閾值，轉(zhuǎn)化為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循環(huán)
                    break;
                }
                // 判斷鏈表中結(jié)點的key值與插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等法牲，跳出循環(huán)
                    break;
                // 用于遍歷桶中的鏈表史汗，與前面的e = p.next組合，可以遍歷鏈表
                p = e;
            }
        }
        // 表示在桶中找到key值拒垃、hash值與插入元素相等的結(jié)點
        if (e != null) { 
            // 記錄e的value
            V oldValue = e.value;
            // onlyIfAbsent為false或者舊值為null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替換舊值
                e.value = value;
            // 訪問后回調(diào)
            afterNodeAccess(e);
            // 返回舊值
            return oldValue;
        }
    }
    // 結(jié)構(gòu)性修改
    ++modCount;
    // 實際大小大于閾值則擴容
    if (++size > threshold)
        resize();
    // 插入后回調(diào)
    afterNodeInsertion(evict);
    return null;
} 

JDK1.7 put方法的代碼

對于put方法的分析如下：
①如果定位到的數(shù)組位置沒有元素 就直接插入停撞。
②如果定位到的數(shù)組位置有元素，遍歷以這個元素為頭結(jié)點的鏈表，依次和插入的key比較戈毒，如果key相同就直接覆蓋艰猬，不同就采用頭插法插入元素。

 //先看put方法
    public V put(K key, V value) {
    //table為空埋市，就先初始化
        if (table == EMPTY_TABLE) {
        //這個方法上面已經(jīng)分析過了冠桃，主要是在初始化HashMap,包括創(chuàng)建HashMap保存的元素的數(shù)組等操作
            inflateTable(threshold);
        }
    
    //key 為null的情況， 只允許有一個為null的key
        if (key == null)
            return putForNullKey(value);
    //計算hash
        int hash = hash(key);
    //根據(jù)指定hash道宅，找出在table中的位置
        int i = indexFor(hash, table.length);
    //table中食听，同一個位置（也就是同一個hash）可能出現(xiàn)多個元素（鏈表實現(xiàn)），故此處需要循環(huán)
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
         //如果key已經(jīng)存在污茵，那么直接設(shè)置新值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
    //key 不存在樱报，就在table指定位置之處新增Entry
        addEntry(hash, key, value, i);
        return null;
    }

在該方法中，添加鍵值對時泞当，首先進行table是否初始化的判斷迹蛤，如果沒有進行初始化（分配空間，Entry[]數(shù)組的長度）襟士。然后進行key是否為null的判斷盗飒，如果key==null ,放置在Entry[]的0號位置。計算在Entry[]數(shù)組的存儲位置敌蜂，判斷該位置上是否已有元素箩兽，如果已經(jīng)有元素存在津肛，則遍歷該Entry[]數(shù)組位置上的單鏈表章喉。判斷key是否存在，如果key已經(jīng)存在身坐，則用新的value值秸脱，替換點舊的value值，并將舊的value值返回部蛇。如果key不存在于HashMap中摊唇，程序繼續(xù)向下執(zhí)行。將key-vlaue, 生成Entry實體涯鲁，添加到HashMap中的Entry[]數(shù)組中巷查。

putForNullKey() :當key為null 的處理情況

 //當key為null 的處理情況
    private V putForNullKey(V value) {
    //先看有沒有key為null, 有就直接設(shè)置新值
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;、
    //當前沒有為null的key就新創(chuàng)建一個entry,其在table的位置為0（也就是第一個）
        addEntry(0, null, value, 0);
        return null;
    }

addEntry():在table指定位置新增Entry

 /*
*在table指定位置新增Entry, 這個方法很重要    
*/
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
        //table容量不夠, 該擴容了（兩倍table）抹腿，重點來了岛请，下面將會詳細分析
            resize(2 * table.length);
             //擴容操作，將數(shù)據(jù)元素重新計算位置后放入newTable中警绩，鏈表的順序與之前的順序相反

        //計算hash, null為0
            hash = (null != key) ? hash(key) : 0;
        //找出指定hash在table中的位置
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }
    }


    /**
     * 在鏈表中添加一個新的Entry對象在鏈表的表頭
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

添加到方法的具體操作崇败，在添加之前先進行容量的判斷，如果當前容量達到了閾值，并且需要存儲到Entry[]數(shù)組中后室，先進性擴容操作缩膝，空充的容量為table長度的2倍。重新計算hash值岸霹，和數(shù)組存儲的位置疾层，擴容后的鏈表順序與擴容前的鏈表順序相反。然后將新添加的Entry實體存放到當前Entry[]位置鏈表的頭部松申。在1.8之前云芦，新插入的元素都是放在了鏈表的頭部位置，但是這種操作在高并發(fā)的環(huán)境下容易導(dǎo)致死鎖贸桶，所以1.8之后舅逸，新插入的元素都放在了鏈表的尾部。

HashMap在擴容的時候皇筛，會重新計算hash值琉历，并對hash的位置進行重新排列， 因此水醋，為了效率旗笔，盡量給HashMap指定合適的容量，避免多次擴容

什么時候擴容：

當向容器添加元素的時候拄踪，會判斷當前容器的元素個數(shù)蝇恶，如果大于等于閾值(知道這個閾字怎么念嗎？不念fa值惶桐，念yu值四聲)---即當前數(shù)組的長度乘以加載因子的值的時候撮弧，就要自動擴容啦。

擴容(resize)介紹：

當HashMapde的長度超出了加載因子與當前容量的乘積（默認16*0.75=12）時姚糊，通過調(diào)用resize方法重新創(chuàng)建一個原來HashMap大小的兩倍的newTable數(shù)組贿衍，最大擴容到2^30+1，并transfer()方法救恨，重新計算hash值贸辈，然后再重新根據(jù)hash分配位置，將原先table的元素全部移到newTable里面肠槽。

分析下resize的源碼

鑒于JDK1.8融入了紅黑樹擎淤，較復(fù)雜，為了便于理解我們?nèi)匀皇褂肑DK1.7的代碼秸仙，好理解一些嘴拢，本質(zhì)上區(qū)別不大，具體區(qū)別后文再說筋栋。

//擴容之后炊汤，重新計算hash，然后再重新根據(jù)hash分配位置，
//由此可見抢腐，為了保證效率姑曙，如果能指定合適的HashMap的容量，會更合適
void resize(int newCapacity) {   //傳入新的容量
        Entry[] oldTable = table;    //引用擴容前的Entry數(shù)組
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {  //擴容前的數(shù)組大小如果已經(jīng)達到最大(2^30)了迈倍，那么就將臨界值threshold設(shè)置為最大的int值
            threshold = Integer.MAX_VALUE; //修改閾值為int的最大值(2^31-1)伤靠，這樣以后就不會擴容了
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];  //初始化一個新的Entry數(shù)組
        transfer(newTable);                         //！啼染！宴合，重新計算hash，然后再重新根據(jù)hash分配位置迹鹅，將原先table的元素全部移到newTable里面
        table = newTable;                           //再將newTable賦值給table
        threshold = (int) (newCapacity * loadFactor);
// 重新計算臨界值卦洽，擴容公式在這兒（newCapacity * loadFactor）

這里就是使用一個容量更大的數(shù)組來代替已有的容量小的數(shù)組，transfer()方法將原有Entry數(shù)組的元素拷貝到新的Entry數(shù)組里斜棚。

void transfer(Entry[] newTable) {
        Entry[] src = table;                   //src引用了舊的Entry數(shù)組
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) { //遍歷舊的Entry數(shù)組
            Entry<K, V> e = src[j];             //取得舊Entry數(shù)組的每個元素
            if (e != null) {
                src[j] = null;//釋放舊Entry數(shù)組的對象引用（for循環(huán)后阀蒂，舊的Entry數(shù)組不再引用任何對象）
                do {
                    Entry<K, V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); //！弟蚀！重新計算每個元素在數(shù)組中的位置
                    e.next = newTable[i]; //標記[1]
                    newTable[i] = e;      //將元素放在數(shù)組上
                    e = next;             //訪問下一個Entry鏈上的元素
                } while (e != null);
            }
        }
}

詳細介紹for循環(huán)內(nèi)部這個轉(zhuǎn)存的過程和怎么進行頭插入

Entry<K, V> e = src[j];
這句話蚤霞，就把原來數(shù)組上的那個鏈表的引用就給接手了，所以下面src[j] = null;可以放心大膽的置空义钉，釋放空間昧绣。告訴gc這個地方可以回收啦。
繼續(xù)到do while 循環(huán)里面捶闸，
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);計算出元素在新數(shù)組中的位置
下面就是單鏈表的頭插入方式轉(zhuǎn)存元素啦

擴容問題：

數(shù)組擴容之后夜畴，最消耗性能的點就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置，并放進去鉴嗤，這個操作是極其消耗性能的斩启。所以如果我們已經(jīng)預(yù)知HashMap中元素的個數(shù)序调，那么預(yù)設(shè)初始容量能夠有效的提高HashMap的性能醉锅。

重新調(diào)整HashMap大小，當多線程的情況下可能產(chǎn)生條件競爭发绢。因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了硬耍，它們會同時試著調(diào)整大小。在調(diào)整大小的過程中边酒，存儲在鏈表中的元素的次序會反過來经柴，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部墩朦，而是放在頭部坯认，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發(fā)生了，那么就死循環(huán)了牛哺。

newTable[i]的引用賦給了e.next陋气，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置引润；這樣先放在一個索引上的元素終會被放到Entry鏈的尾部(如果發(fā)生了hash沖突的話）巩趁，這一點和Jdk1.8有區(qū)別，下文詳解淳附。在舊數(shù)組中同一條Entry鏈上的元素议慰，通過重新計算索引位置后，有可能被放到了新數(shù)組的不同位置上奴曙。

死鏈過程分析

首先假設(shè)在擴容時别凹，hash表中有一個單鏈表，單鏈表中有兩個元素：元素1和元素2

如果該HashMap為單線程操作時

執(zhí)行過程：
首先 e = 元素1
執(zhí)行到 next = e.next 的時候 next =元素2
從 1 到 3 的過程會將 元素1 按照頭插法插入到newtable[i]所引用的單鏈表中
然后 e = next 會將 next 賦值給 e洽糟，所以就有 e = 元素2
判斷后 e != null番川，繼續(xù)循環(huán)，然后以同樣方式插入元素2
因為 元素2 的 next 為 null 所以最后 e = null
這時候循環(huán)就結(jié)束了脊框，原鏈表的順序由 元素1—>元素2 變成了 元素2—>元素1（結(jié)果如圖所示）颁督。

image.png

如果該HashMap為多線程操作時（假設(shè)有T1、T2兩個線程）

執(zhí)行過程：
T1執(zhí)行到 next = e.next浇雹；時掛起
T2開始執(zhí)行并且執(zhí)行完了整個流程沉御，也就是說T2把所有元素都插入了新數(shù)組之后，原來
的table引用現(xiàn)在指向了 newtable吠裆，即 table = newtable烂完；
這時T1回歸繼續(xù)執(zhí)行，這時就會有如下場景

image.png

當元素1正常插入后 next 是 元素2抠蚣，e = next = 元素2祝旷，繼續(xù)執(zhí)行插入
此時嘶窄，由于原表中 元素2 的 next 已經(jīng)被T2所修改，不再是T1掛起時的 next = null了柄冲，所以T1就會碰到如下情況吻谋，因為 next 永遠都不為空现横，所以就會一直循環(huán)執(zhí)行插入操作阁最，造成死循環(huán)骇两。（圖中這種狀態(tài)的鏈表稱為死鏈）

image.png

避免死循環(huán)

第一種方式：使用HashTable

HashTable和HashMap一樣都實現(xiàn)了Map接口脯颜，但是HashTable是一個線程安全的類，所以不會出現(xiàn)死循環(huán)問題栋操。

第二種方式：使用Collections.synchronizeMap(hashMap)

該方法是Collections類中的靜態(tài)方法，返回的是一個線程安全的HashMap

第三種方式：使用concurrentHashMap

concurrentHashMap也是一個線程安全類舍沙，他比HashTable更為高效剔宪。在HashTable中，使用的是同一個鎖感帅，所以當一個線程操作某一個功能時地淀，其他線程想要操作另外的功能就要等待鎖被讓出來。而concurrentHashMap采用了【鎖分段】技術(shù)实苞，不同的地方使用了不同的鎖烈疚，功能之間的鎖不一樣，操作不同功能時就不再需要等待猾浦，這樣就大大提高了執(zhí)行效率阶剑。

關(guān)于什么時候resize（）的說明：

• JDK1.7的是：
  if ((size >= threshold) && (null != table[bucketIndex])) {危号。。猪半。}
  其中
  size表示當前hashmap里面已經(jīng)包含的元素的個數(shù)。
  threshold：threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  一般是容量值X加載因子沽甥。
• JDK1.8的是：
  if (++size > threshold){}
  其中
  size：The number of key-value mappings contained in this map.和上面的是一樣的
  threshold：newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

remove移除方法

 //上面看了put方法乏奥，接下來就看看remove
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    //這就是remove的核心方法
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
    //老規(guī)矩，先計算hash,然后通過hash尋找在table中的位置
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
    
    //這兒又神奇地回到了怎么刪除鏈表的問題（上次介紹linkedList的時候恨诱，介紹過）
    //李四左手牽著張三骗炉，右手牽著王五句葵，要刪除李四，那么直接讓張三牽著王五的手就OK
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

get方法

如果兩個不同的key的hashcode相同剂碴，兩個值對象儲存在同一個bucket位置轻专，要獲取value，我們調(diào)用get()方法洪碳，HashMap會使用key的hashcode找到bucket位置叼屠，因為HashMap在鏈表中存儲的是Entry鍵值對，所以找到bucket位置之后嫂侍，會調(diào)用key的equals()方法荚坞，按順序遍歷鏈表的每個 Entry，直到找到想獲取的 Entry 為止——如果恰好要搜索的 Entry 位于該 Entry 鏈的最末端（該 Entry 是最早放入該 bucket 中）各淀，那HashMap必須循環(huán)到最后才能找到該元素诡挂。
get()方法源碼如下：

public V get(Object key) {
        // 若key為null临谱，遍歷table[0]處的鏈表（實際上要么沒有元素奴璃，要么只有一個Entry對象），取出key為null的value
        if (key == null)
            return getForNullKey();
        // 若key不為null抄课，用key獲取Entry對象
        Entry<K,V> entry = getEntry(key);
        // 若鏈表中找到的Entry不為null雳旅，返回該Entry中的value
        return null == entry ? null : entry.getValue();
    }

    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        // 計算key的hash值
        int hash = (key == null) ? 0 : hash(key);
        // 計算key在數(shù)組中對應(yīng)位置岭辣，遍歷該位置的鏈表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            // 若key完全相同，返回鏈表中對應(yīng)的Entry對象
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        // 鏈表中沒找到對應(yīng)的key仑濒，返回null
        return null;
    }

二偷遗、HashMap的數(shù)據(jù)存儲結(jié)構(gòu)

1、HashMap由數(shù)組和鏈表來實現(xiàn)對數(shù)據(jù)的存儲

HashMap采用Entry數(shù)組來存儲key-value對喉酌，每一個鍵值對組成了一個Entry實體泵喘，Entry類實際上是一個單向的鏈表結(jié)構(gòu)，它具有Next指針相速，可以連接下一個Entry實體鲜锚，以此來解決Hash沖突的問題。

數(shù)組存儲區(qū)間是連續(xù)的旺隙，占用內(nèi)存嚴重骏令，故空間復(fù)雜的很大。但數(shù)組的二分查找時間復(fù)雜度小抠刺，為O(1)摘昌；數(shù)組的特點是：尋址容易，插入和刪除困難罕容；

鏈表存儲區(qū)間離散稿饰，占用內(nèi)存比較寬松，故空間復(fù)雜度很小旅择，但時間復(fù)雜度很大侣姆，達O（N）捺宗。鏈表的特點是：尋址困難，插入和刪除容易蚜厉。

image.png

從上圖我們可以發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)由數(shù)組+鏈表組成昼牛，一個長度為16的數(shù)組中，每個元素存儲的是一個鏈表的頭結(jié)點斤斧。那么這些元素是按照什么樣的規(guī)則存儲到數(shù)組中呢霎烙。一般情況是通過hash(key.hashCode())%len獲得，也就是元素的key的哈希值對數(shù)組長度取模得到游昼。比如上述哈希表中尝蠕，12%16=12,28%16=12,108%16=12,140%16=12。所以12廊佩、28、108以及140都存儲在數(shù)組下標為12的位置顽铸。
HashMap里面實現(xiàn)一個靜態(tài)內(nèi)部類Entry料皇，其重要的屬性有 hash，key鬼譬，value逊脯，next。

HashMap里面用到鏈式數(shù)據(jù)結(jié)構(gòu)的一個概念巩螃。上面我們提到過Entry類里面有一個next屬性歉眷，作用是指向下一個Entry。打個比方淑际， 第一個鍵值對A進來扇住，通過計算其key的hash得到的index=0春缕，記做:Entry[0] = A锄贼。一會后又進來一個鍵值對B女阀，通過計算其index也等于0，現(xiàn)在怎么辦冯键？HashMap會這樣做:B.next = A,Entry[0] = B,如果又進來C,index也等于0,那么C.next = B,Entry[0] = C庸汗；這樣我們發(fā)現(xiàn)index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起。所以疑問不用擔心改化。也就是說數(shù)組中存儲的是最后插入的元素。到這里為止揍鸟，HashMap的大致實現(xiàn)燥爷，我們應(yīng)該已經(jīng)清楚了前翎。

根據(jù)key的hashCode來決定應(yīng)該將該記錄放在哪個桶里面畅涂，無論是插入、查找還是刪除立宜，這都是第一步臊岸，計算桶的位置。因為HashMap的length總是2的n次冪灯帮，所以可以使用下面的方法來做模運算：h&(length-1)
h是key的hashCode值逻住，計算好hashCode之后，使用上面的方法來對桶的數(shù)量取模舵抹，將這個數(shù)據(jù)記錄落到某一個桶里面。當然取模是java7中的做法沧烈，java8進行了優(yōu)化棘幸，做得更加巧妙，因為我們的length總是2的n次冪顶霞，所以在一次resize之后，當前位置的記錄要么保持當前位置不變蓝厌，要么就向前移動length就可以了古徒。所以java8中的HashMap的resize不需要重新計算hashCode隧膘。

為什么HashMap線程不安全

HashMap會進行resize操作，在resize操作的時候會造成線程不安全蹦疑。下面將舉兩個可能出現(xiàn)線程不安全的地方萨驶。
1、put的時候?qū)е碌亩嗑€程數(shù)據(jù)不一致叁温。
這個問題比較好想象核畴，比如有兩個線程A和B谤草，首先A希望插入一個key-value對到HashMap中，首先計算記錄所要落到的桶的索引坐標泳炉，然后獲取到該桶里面的鏈表頭結(jié)點嚎杨，此時線程A的時間片用完了，而此時線程B被調(diào)度得以執(zhí)行刨肃，和線程A一樣執(zhí)行箩帚，只不過線程B成功將記錄插到了桶里面紧帕，假設(shè)線程A插入的記錄計算出來的桶索引和線程B要插入的記錄計算出來的桶索引是一樣的桅打，那么當線程B成功插入之后愈案，線程A再次被調(diào)度運行時，它依然持有過期的鏈表頭但是它對此一無所知遭铺，以至于它認為它應(yīng)該這樣做魂挂，如此一來就覆蓋了線程B插入的記錄馁筐，這樣線程B插入的記錄就憑空消失了，造成了數(shù)據(jù)不一致的行為芹扭。

2赦抖、另外一個比較明顯的線程不安全的問題是HashMap的get操作可能因為resize而引起死循環(huán)（cpu100%）队萤，具體分析如下：
下面的代碼是resize的核心內(nèi)容：

void transfer(Entry[] newTable, boolean rehash) {  
        int newCapacity = newTable.length;  
        for (Entry<K,V> e : table) {  
  
            while(null != e) {  
                Entry<K,V> next = e.next;           
                if (rehash) {  
                    e.hash = null == e.key ? 0 : hash(e.key);  
                }  
                int i = indexFor(e.hash, newCapacity);   
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
            } 
        }  
    }  

這個方法的功能是將原來的記錄重新計算在新桶的位置矫钓，然后遷移過去。

image.png

我們假設(shè)有兩個線程同時需要執(zhí)行resize操作赵辕，我們原來的桶數(shù)量為2概龄，記錄數(shù)為3，需要resize桶到4蚕键，原來的記錄分別為：[3,A],[7,B],[5,C]衰粹，在原來的map里面铝耻，我們發(fā)現(xiàn)這三個entry都落到了第二個桶里面。
假設(shè)線程thread1執(zhí)行到了transfer方法的Entry next = e.next這一句频丘，然后時間片用完了，此時的e = [3,A], next = [7,B]诈火。線程thread2被調(diào)度執(zhí)行并且順利完成了resize操作状答，需要注意的是，此時的[7,B]的next為[3,A]拍摇。此時線程thread1重新被調(diào)度運行馆截，此時的thread1持有的引用是已經(jīng)被thread2 resize之后的結(jié)果蜡娶。線程thread1首先將[3,A]遷移到新的數(shù)組上，然后再處理[7,B]幕随，而[7,B]被鏈接到了[3,A]的后面宿接，處理完[7,B]之后睦霎，就需要處理[7,B]的next了啊，而通過thread2的resize之后蛤高，[7,B]的next變?yōu)榱薣3,A]肮塞，此時，[3,A]和[7,B]形成了環(huán)形鏈表猜欺，在get的時候拷窜，如果get的key的桶索引和[3,A]和[7,B]一樣，那么就會陷入死循環(huán)笋妥。

如果在取鏈表的時候從頭開始日丁（現(xiàn)在是從尾部開始取）的話月帝，則可以保證節(jié)點之間的順序幽污，那樣就不存在這樣的問題了距误。

最后總結(jié)一下：

就是這個map里面包含的元素，也就是size的值趁俊，大于等于這個閾值的時候惋鹅，才會resize（）闰集；
具體到實際情況就是：假設(shè)現(xiàn)在閾值是4般卑；在添加下一個假設(shè)是第5個元素的時候，這個時候的size還是原來的沐鼠，還沒加1叹谁，size=4焰檩，那么閾值也是4的時候，
當執(zhí)行put方法兜叨，添加第5個的時候，這個時候矛物，4 >= 4跪但。元素個數(shù)等于閾值屡久。就要resize（）啦。添加第4的時候雄卷，還是3 >= 4不成立蛤售，不需要resize（）悴能。
經(jīng)過這番解釋，可以發(fā)現(xiàn)下面的這個例子冯凹，不應(yīng)該是在添加第二個的時候resize（）炒嘲，而是在添加第三個的時候夫凸，才resize（）的。
這個也是我后來再細看的時候魔熏，發(fā)現(xiàn)的鸽扁。當然桶现，這個咱可以先忽略，重點看如何resize（）吏夯，以及如何將舊數(shù)據(jù)移動到新數(shù)組的

image.png

下面我們講解下JDK1.8做了哪些優(yōu)化噪生。經(jīng)過觀測可以發(fā)現(xiàn)，我們使用的是2次冪的擴展(指長度擴為原來2倍)战授，所以桨嫁，

經(jīng)過rehash之后璃吧，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置筒繁。對應(yīng)的就是下方的resize的注釋巴元。

/** 
 * Initializes or doubles table size.  If null, allocates in 
 * accord with initial capacity target held in field threshold. 
 * Otherwise, because we are using power-of-two expansion, the 
 * elements from each bin must either stay at same index, or move 
 * with a power of two offset in the new table. 
 * 
 * @return the table 
 */  
final Node<K,V>[] resize() {  }

看下圖可以明白這句話的意思逮刨，n為table的長度，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例恢总，圖（b）表示擴容后key1和key2兩種key確定索引位置的示例箩退，其中hash1是key1對應(yīng)的哈希值(也就是根據(jù)key1算出來的hashcode值)與高位與運算的結(jié)果戴涝。

image.png

元素在重新計算hash之后啥刻，因為n變?yōu)?倍咪笑，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：

image.png

JDK8的HashMap實現(xiàn)绍坝。

還需要能理解紅黑樹這種數(shù)據(jù)結(jié)構(gòu)

image.png

上面的圖片展示了我們的描述，其中有一個非常重要的數(shù)據(jù)結(jié)構(gòu)Node<K,V>椎咧，這就是實際保存我們的key-value對的數(shù)據(jù)結(jié)構(gòu)把介，下面是這個數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容：

final int hash;    
        final K key;
        V value;
        Node<K,V> next;

一個Node就是一個鏈表節(jié)點，也就是我們插入的一條記錄向臀，明白了HashMap使用鏈地址方法來解決哈希沖突之后莫矗，我們就不難理解上面的數(shù)據(jù)結(jié)構(gòu)作谚，hash字段用來定位桶的索引位置，key和value就是我們的數(shù)據(jù)內(nèi)容雀监，需要注意的是眨唬，我們的key是final的匾竿，也就是不允許更改，這也好理解临庇，因為HashMap使用key的hashCode來尋找桶的索引位置昵慌，一旦key被改變了斋攀，那么key的hashCode很可能就會改變了，所以隨意改變key會使得我們丟失記錄（無法找到記錄）侧蘸。next字段指向鏈表的下一個節(jié)點鹉梨。

小結(jié)
(1) 擴容是一個特別耗性能的操作俯画，所以當程序員在使用HashMap的時候司草，估算map的大小，初始化的時候給一個大致的數(shù)值娩怎，避免map進行頻繁的擴容胰柑。
(2) 負載因子是可以修改的柬讨，也可以大于1，但是建議不要輕易修改却桶，除非情況非常特殊蔗牡。
(3) HashMap是線程不安全的辩越，不要在并發(fā)的環(huán)境中同時操作HashMap，建議使用ConcurrentHashMap趁啸。
(4) JDK1.8引入紅黑樹大程度優(yōu)化了HashMap的性能莲绰。
(5) 還沒升級JDK1.8的姑丑，現(xiàn)在開始升級吧栅哀。HashMap的性能提升僅僅是JDK1.8的冰山