3 Map

昨晚去了鳥巢季蚂，膜拜了5位40多歲的大爺們。算上這次琅束，已是第三回了扭屁，每一次都有不同的感受、體驗狰闪。期待疯搅，下一次的相遇。

今天，筆者要介紹的是Java集合框架中的Map集合丽声，在日常工作中Map的運用也十分廣泛礁蔗。

與List集合、Set集合隸屬于Collection不同雁社，Map是一個獨立的接口浴井，與Collection相同級別的接口。

重要的是霉撵，Map集合提供了一個不一樣的元素存儲方法磺浙，利用“key--value”的形式進行存儲。其中徒坡，每個鍵映射一個值撕氧。而在Set集合中，元素的存儲就是利用Map的這一特性來實現(xiàn)喇完。

簡單的介紹了下Map集合伦泥，接下來，就讓筆者對其主要實現(xiàn)類HashMap锦溪、TreeMap不脯、HashTable進行詳細的說明。

3.1 Map常用方法

在具體介紹之前刻诊，我們先了解下Map接口本身防楷，以便了解所有實現(xiàn)的共同點。

public interface Map<K,V> {

    //返回Map中的key--value的數(shù)目
    int size();

    //如果Map不包含任何key--value则涯，則返回 true
    boolean isEmpty();

    //如果Map中包含指定key的映射域帐，則返回true
    boolean containsKey(Object key);

    //如果此Map將一個或多個鍵映射到指定值赘被，則返回 true
    boolean containsValue(Object value);

    //返回與指定鍵關(guān)聯(lián)的值
    V get(Object key);

    //將指定值與指定鍵相關(guān)聯(lián)
    V put(K key, V value);

    //從Map中刪除鍵和關(guān)聯(lián)的值
    V remove(Object key);

    //將指定Map中的所有映射復(fù)制到此map
    void putAll(java.util.Map<? extends K, ? extends V> m);

    //從Map中刪除所有映射
    void clear();

    //返回Map中所包含鍵的Set集合
    Set<K> keySet();

    //返回 map 中所包含值的 Collection集合。
    Collection<V> values();

    //返回Map中所包含映射的Set視圖肖揣。Set中的每個元素都是一個 Map.Entry 對象
    Set<java.util.Map.Entry<K, V>> entrySet();

    //比較指定對象與此 Map 的等價性
    boolean equals(Object o);

    //返回此 Map 的哈希碼
    int hashCode();

    //Map集合中存儲key--value的對象Entry民假，在Map集合內(nèi)形成數(shù)組結(jié)構(gòu)
    interface Entry<K,V> {

        V getValue();

        V setValue(V value);

        boolean equals(Object o);

        int hashCode();
    }
}

3.2 HashMap

HashMap，我們工作中經(jīng)常使用的集合之一龙优，也是面試中最常被問到的集合羊异。想必，你一定聽到過：“來彤断，說說HashMap的實現(xiàn)”等之類的問題野舶！

下面，來做具體介紹：

HashMap基于哈希表宰衙，底層結(jié)構(gòu)由數(shù)組來實現(xiàn)平道，添加到集合中的元素以“key--value”形式保存到數(shù)組中，在數(shù)組中key--value被包裝成一個實體來處理---也就是上面Map接口中的Entry供炼。

在HashMap中一屋，Entry[]保存了集合中所有的鍵值對，當我們需要快速存儲袋哼、獲取冀墨、刪除集合中的元素時，HashMap會根據(jù)hash算法來獲得“鍵值對”在數(shù)組中存在的位置涛贯，以來實現(xiàn)對應(yīng)的操作方法诽嘉。

此時，細心的朋友可能會問弟翘，既然是基于哈希表的實現(xiàn)虫腋，那么當新增的元素出現(xiàn)了hash值重復(fù)了怎么辦，怎么插入呢稀余？

專業(yè)上來說岔乔，hash值重復(fù)的情況，我們稱之為哈希碰撞（又或者哈希沖突）滚躯。在HashMap中，是通過鏈表的形式來解決的嘿歌，在hash值重復(fù)的數(shù)組角標下掸掏，通過鏈表將新插入的元素依次排列，當然如果插入的key相同宙帝，那么我們會將新插入的value覆蓋掉原有的value丧凤；

像上圖所示，當產(chǎn)生了hash沖突后步脓，會在產(chǎn)生沖突的角標下愿待，生成鏈表浩螺，依次排列。

HashMap繼承于AbstractMap仍侥，實現(xiàn)了Map, Cloneable, Serializable接口要出。
(1)HashMap繼承AbstractMap，得到了Map接口中定義方法的實現(xiàn)农渊，減少實現(xiàn)Map接口所需的工作患蹂；
(2)HashMap實現(xiàn)Map，得到了Map接口定義的所有方法砸紊，其中一部分AbstractMap已實現(xiàn)传于；
(3)HashMap實現(xiàn)Cloneable，得到了clone()方法醉顽，可以實現(xiàn)克隆功能沼溜；
(4)HashMap實現(xiàn)Serializable，表示可以被序列化游添，通過序列化去傳輸系草，典型的應(yīng)用就是hessian協(xié)議。

它具有如下特點：

• 允許存入null鍵否淤，null值（null值只有一個悄但，并存于數(shù)組第一個位置）
• 無序集合，而且順序會隨著元素的添加而隨時改變（添加順序石抡，迭代順序不一致）
• 隨著元素的增加而動態(tài)擴容（與ArrayList原理一致）
• 不存在重復(fù)元素（得益于hashCode算法和equals方法）
• 線程不安全

3.2 HashMap基本操作

下面檐嚣，我們來看下HashMap的常用方法：

 public static void main(String[] agrs){
    //創(chuàng)建HashMap集合：
    Map<String,String> map = new HashMap<String,String>();
    System.out.println("HashMap元素大小:"+map.size());

    //元素添加:
    map.put("hi","hello");
    map.put("my","hello");
    map.put("name","hello");
    map.put("is","hello");
    map.put("jiaboyan","hello");

    //遍歷1：獲取key的Set集合
    for(String key:map.keySet()){
        System.out.println("map的key是:"+key);
        System.out.println("map的value是:"+map.get(key));
    }

    //遍歷2:得到Set集合迭代器
    Set<Map.Entry<String,String>> mapSet1 = map.entrySet();
    Iterator<Map.Entry<String,String>> iterator = mapSet1.iterator();
    while(iterator.hasNext()){
        Map.Entry<String,String> mapEntry = iterator.next();
        System.out.println("map的key是:" + mapEntry.getKey());
        System.out.println("map的value是:" + mapEntry.getValue());
    }

    //遍歷3:轉(zhuǎn)換成Set集合，增強for循環(huán)
    Set<Map.Entry<String,String>> mapSet2 = map.entrySet();
    for(Map.Entry<String,String> mapEntry : mapSet2){
        System.out.println("map的key是:" + mapEntry.getKey());
        System.out.println("map的value是:" + mapEntry.getValue());
    }

    //元素獲葐浮：通過key獲取value
    String keyValue = map.get("jiaboyan");
    System.out.println("HashMap的key對應(yīng)的value:" + keyValue);

    //元素替換：map沒有提供直接set方法嚎京，而是使用新增來完成更新操作
    map.put("jiaboyan","helloworld");
    System.out.println("HashMap的key對應(yīng)的value:" + map.get("jiaboyan"));

    //元素刪除：
    String value = map.remove("jiaboyan");
    System.out.println("HashMap集合中被刪除元素的value" + value);
    //清空所有元素：
    map.clear();

    //hashMap是否包含某個key：
    boolean isContain = map.containsKey("hello");
    //hashMap是否為空：
    boolean isEmpty = map.isEmpty();
}

3.4 HashMap源碼講解（基于JDK1.7.0_45）

接下來，我們對HashMap源碼進行分析隐解。

同理鞍帝，我們還是帶著問題去理解HashMap的實現(xiàn)！

1.HashMap底層數(shù)據(jù)結(jié)構(gòu)如何煞茫？

2.HashMap如何保存數(shù)據(jù)帕涌，增刪改咋實現(xiàn)？

3.HashMap如何擴容续徽？

4.為什么擴容的大小一定要是2的整數(shù)次冪蚓曼，也就是2的N次方.

• HashMap成員變量

我們先了解下HashMap中有哪些成員變量：table、DEFAULT_INITIAL_CAPACITY钦扭、DEFAULT_LOAD_FACTOR等纫版；

其中，table就是HashMap底層保存元素的數(shù)組客情，默認情況下先賦值為空數(shù)組EMPTY_TABLE其弊；

DEFAULT_INITIAL_CAPACITY是HashMap中數(shù)組的默認初始化大小癞己。在JDK1.7.0_45版本中，當首次put(新增)元素時梭伐，會新建一個容量為16的Entry[]數(shù)組賦值給table屬性痹雅；

DEFAULT_LOAD_FACTOR是HashMap擴容的關(guān)鍵參數(shù)，當HashMap中存儲的元素個數(shù)達到一定的數(shù)量時籽御，Entry[]會進行擴容练慕。這個一定數(shù)量的值就是根據(jù)DEFAULT_LOAD_FACTOR計算得來，主要是數(shù)組大小*DEFAULT_LOAD_FACTOR技掏；

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

    //hashMap中的數(shù)組初始化大辛褰：1 << 4=2^4=16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    //1<<30 表示1左移30位，每左移一位乘以2哑梳，所以就是1*2^30=1073741824劲阎。
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //默認裝載因子：
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //HashMap默認初始化的空數(shù)組：
    static final java.util.HashMap.Entry<?,?>[] EMPTY_TABLE = {};

    //HashMap中底層保存數(shù)據(jù)的數(shù)組：HashMap其實就是一個Entry數(shù)組
    transient java.util.HashMap.Entry<K,V>[] table = (java.util.HashMap.Entry<K,V>[]) EMPTY_TABLE;

    //Hashmap中元素的個數(shù)：
    transient int size;

    //threshold：等于capacity * loadFactory，決定了HashMap能夠放進去的數(shù)據(jù)量
    int threshold;

    //loadFactor：裝載因子鸠真，默認值為0.75悯仙，它決定了bucket填充程度；
    final float loadFactor;

    //HashMap被操作的次數(shù)：
    transient int modCount;

}

• HashMap的最終實現(xiàn)

在HashMap中吠卷，存儲元素的是Entry[]數(shù)組锡垄，而其中的元素也就是Entry對象：

static class Entry<K,V> implements Map.Entry<K,V> {
    //Entry屬性-也就是HashMap的key
    final K key;

    //Entry屬性-也就是HashMap的value
    V value;

    //指向下一個節(jié)點的引用：實現(xiàn)單向鏈表結(jié)構(gòu)
    java.util.HashMap.Entry<K,V> next;

    //此Entry的hash值：也就是key的hash值
    int hash;

    // 構(gòu)造函數(shù)：
    Entry(int h, K k, V v, java.util.HashMap.Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    public final K getKey() { return key;}
    public final V getValue() { return value; }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {

        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }
    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }
    public final String toString() {
        return getKey() + "=" + getValue();
    }
    void recordAccess(java.util.HashMap<K,V> m) {
    }
    void recordRemoval(java.util.HashMap<K,V> m) {
    }
}

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

我們來看下，HashMap具體的構(gòu)造是如何實現(xiàn)祭隔？

最終都指定到了public HashMap(int initialCapacity, float loadFactor)方法中货岭，對一些成員變量進行賦值。傳入的初始容量疾渴，并沒有改變Entry[]容量大星Ч帷；

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

    //構(gòu)造方法：初始化容量  指定裝載因子
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        //指定初始化容量大于 HashMap規(guī)定最大容量的話搞坝，就將其設(shè)置為最大容量搔谴；
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //不能小于0，判斷參數(shù)float的值是否是數(shù)字
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        //裝載因子賦值：
        this.loadFactor = loadFactor;
        //初始容量賦值給 臨界值屬性
        threshold = initialCapacity;
        //空方法：沒有任何實現(xiàn)
        init();
    }

    //構(gòu)造方法：初始化容量
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    //無參構(gòu)造：默認初始化容量16桩撮、默認裝載因子0.75
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        inflateTable(threshold);

        putAllForCreate(m);
    }
}

• HashMap新增元素

對于HashMap來說敦第，新增操作可謂是一個重要的方法，其中包括了最核心的擴容實現(xiàn)店量；

首先芜果，直接來看put(K key, V value)方法：

public V put(K key, V value) {
    //如果調(diào)用put方法時(第一次調(diào)用put方法)，還是空數(shù)組垫桂，則進行初始化操作
    if (table == EMPTY_TABLE) {
        //進行初始化HashMap的table屬性，進行容量大小設(shè)置
        inflateTable(threshold);
    }
    //如果新增的key為null:
    if (key == null)
        //調(diào)用key為null的新增方法：
        return putForNullKey(value);

    //計算新增元素的hash值：
    int hash = hash(key);

    //根據(jù)hash值和數(shù)組長度粟按，計算出新增的元素應(yīng)該位于數(shù)組的哪個角標下：
    int i = indexFor(hash, table.length);

    //判斷計算出的角標下诬滩，是否有相同的key霹粥，可以理解遍歷該角標下的鏈表
    for (java.util.HashMap.Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //根據(jù)計算出的hash值，以及 equals方法 / == 來判斷key是否相同：
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            //key相同疼鸟，則替換原有key下的value：
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            //返回被替換的值：
            return oldValue;
        }
    }
    modCount++;
    //向HashMap中增加元素：
    addEntry(hash, key, value, i);
    return null;
}

補充：在進行key一致性判斷時后控，首先通過hash值判斷，再通過equals()或者==進行判斷空镜；為什么要做這么多操作浩淘？

因為每一個對象的hashCode()可以進行重寫，既然可以重寫吴攒，那么就可能會出現(xiàn)相同的hash值张抄。退一步說，哪怕使用JDK默認的計算方式洼怔，也會出現(xiàn)重復(fù)的可能署惯。所以在進行完hash值比較后，還進行了equals()或者==的判斷镣隶；

那么极谊，既然使用了equals()方法，為什么還要進行==判斷呢安岂？（艸轻猖，就你問題最多，哪來的這么多為什么域那？）

說白了咙边，主要是為了解決字符串的原因，才做的妥協(xié)琉雳！

對于字符串來說样眠，“==”比較兩個變量本身的值，即兩個對象在內(nèi)存中的首地址翠肘。而“equals()”比較字符串中所包含的內(nèi)容是否相同檐束。

但是對于非字符串的對象來說，"=="和"equals"都是用來比較對象在堆內(nèi)存的首地址束倍，即用來比較兩個引用變量是否指向同一個對象被丧。

這下你明白了吧！Ｐ髅谩甥桂！

接下來，我們就對上面的方法進行逐一講解：

當table還是一個空數(shù)組的時候邮旷，對數(shù)組進行初始化：

//初始化Entry數(shù)組黄选，默認16個大小：
private void inflateTable(int toSize) {
    //獲取要創(chuàng)建的數(shù)組容量大小：計算大于等于toSize的2的次冪（2的幾次方）
    int capacity = roundUpToPowerOf2(toSize);
    //計算HashMap的閥值：
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    //創(chuàng)建Entry數(shù)組對象办陷，重新對table賦值：
    table = new java.util.HashMap.Entry[capacity];
    //判斷是否需要初始化hashSeed屬性：
    initHashSeedAsNeeded(capacity);
}

//計算大于等于number的2的冪數(shù)（2的幾次方）
private static int roundUpToPowerOf2(int number) {
    //在number不大于MAXIMUM_CAPACITY的情況下：
    return number >= MAXIMUM_CAPACITY ? 
        MAXIMUM_CAPACITY : 
            //再次進行三目運算：核心方法Integer.highestOneBit()
            (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

補充：Integer.highestOneBit(num)只保留二進制的最高位的1貌夕，其余全為0；

例如：number=16, (16-1) << 1=30民镜，再highestOneBit(30)啡专，只保留最高位的1，其余全為0制圈。30的二進制為11110们童，保留最高位的1，其余改為0鲸鹦，則為10000=16慧库；

為什么在初始化HashMap的Entry[]時，一定要調(diào)用highestOneBit()亥鬓，獲取一個2的N次方的數(shù)字完沪？稍后解答！Ｇ陡辍８不！

在之前介紹HashMap的成員變量時熟呛，筆者故意拉下了一個屬性宽档，這屬性就是hashSeed。現(xiàn)在我們通過介紹initHashSeedAsNeeded()順便對hashSeed做一個說明：

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

    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

    transient int hashSeed = 0;

    //HashMap的內(nèi)部類：
    private static class Holder {
        //內(nèi)部類成員變量：
        static final int ALTERNATIVE_HASHING_THRESHOLD;
        
        //靜態(tài)代碼塊：
        static {
            //獲取jvm參數(shù)-jdk.map.althashing.threshold庵朝，如果設(shè)置了吗冤，獲取其中的值；
            String altThreshold = java.security.AccessController.
                    doPrivileged(new sun.security.action.GetPropertyAction("jdk.map.althashing.threshold"));
            
            int threshold;
            
            try {
                //判斷是否設(shè)置了jdk.map.althashing.threshold參數(shù)：如果沒設(shè)置九府，則將ALTERNATIVE_HASHING_THRESHOLD_DEFAULT的值賦值給threshold

                threshold = (null != altThreshold)? Integer.parseInt(altThreshold) : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
                
                //threshold如果為-1椎瘟，jdk.map.althashing.threshold通常設(shè)置為-1
                if (threshold == -1) {
                    threshold = Integer.MAX_VALUE;
                }
                if (threshold < 0) {
                    throw new IllegalArgumentException("value must be positive integer.");
                }
            } catch(IllegalArgumentException failed) {
                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
            }
            //threshold賦值給ALTERNATIVE_HASHING_THRESHOLD，通常該值為Integer.MAX_VALUE
            ALTERNATIVE_HASHING_THRESHOLD = threshold;
        }
    }

    //判斷是否初始化hashSeed參數(shù)：
    final boolean initHashSeedAsNeeded(int capacity) {
        //判斷hashSeed是否等于0：
        boolean currentAltHashing = hashSeed != 0;

        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= java.util.HashMap.Holder.ALTERNATIVE_HASHING_THRESHOLD);
        
        boolean switching = currentAltHashing ^ useAltHashing;
        
        //判斷是否需要對hashSeed賦值：通常情況下hashSeed的值就是0
        if (switching) {
            hashSeed = useAltHashing? sun.misc.Hashing.randomHashSeed(this): 0;
        }
        return switching;
    }
}

通過源碼分析了下hashSeed初始化的過程侄旬，只要沒有單獨定義JVM屬性--jdk.map.althashing.threshold的話肺蔚，hashSeed的值一直為0，ALTERNATIVE_HASHING_THRESHOLD的值為Integer.MAX_VALUE儡羔；

那么宣羊，對于hashSeed是不是為0來說，又有什么意義呢汰蜘？ 待我們后面進行解答３鸱搿！Ｗ宀佟？良帷！！

繼續(xù)之前put(K key, V value)的源碼分析：

//新增元素的key為null的話：
private V putForNullKey(V value) {
    //遍歷數(shù)組的第一個元素泼舱，看是否已存在為null的key：
    for (java.util.HashMap.Entry<K,V> e = table[0]; e != null; e = e.next) {
        //如果存在姐赡，則將原有的value替換
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            //返回原來的value：
            return oldValue;
        }
    }
    //如果不包含null，則進行添加操作：
    modCount++;
    //向數(shù)組中的第一個角標下插入為null的key--value：
    addEntry(0, null, value, 0);
    return null;
}柠掂、

繼續(xù)看下，addEntry(int hash, K key, V value, int bucketIndex)--key的哈希值依沮，key涯贞，value，所屬數(shù)組角標

void addEntry(int hash, K key, V value, int bucketIndex) {
    //當size大于等于臨界值 并且 新增元素所屬角標的元素不為null（出現(xiàn)了哈希沖突了）危喉，進行擴容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //變成原來大小的2倍：
        resize(2 * table.length);
        //重新計算新增元素的hash值（此處不太明白為什么要重新計算）
        hash = (null != key) ? hash(key) : 0;
        //重新計算新增元素所處數(shù)組的位置（由于數(shù)組長度改變宋渔，需要重新計算所屬角標）
        bucketIndex = indexFor(hash, table.length);
    }
    //創(chuàng)建Entry數(shù)組中 entry對象：
    createEntry(hash, key, value, bucketIndex);
}

當集合中擁有的元素大于等于臨界值 并且 新增元素所處的數(shù)組位置不為null 時候，進行擴容辜限；新數(shù)組大小為原有的2倍皇拣，重新計算元素key的hash值，以及所處新數(shù)組的位置薄嫡。

那么氧急，怎么進行的擴容？

//將HashMap進行擴容：
void resize(int newCapacity) {
    //將原有Entry數(shù)組賦值給oldTable參數(shù)：
    java.util.HashMap.Entry[] oldTable = table;
    
    //獲取現(xiàn)階段Entry數(shù)組的長度：
    int oldCapacity = oldTable.length;
    
    //如果現(xiàn)階段Entry數(shù)組的長度 == MAXIMUM_CAPACITY的話：
    if (oldCapacity == MAXIMUM_CAPACITY) {
        //將閾值設(shè)置為Integer的最大值毫深，并返回
        threshold = Integer.MAX_VALUE;
        //沒有進行擴容操作：
        return;
    }
    
    //創(chuàng)建新Entry數(shù)組：容量為現(xiàn)有2倍大小
    java.util.HashMap.Entry[] newTable = new java.util.HashMap.Entry[newCapacity];
    
    //將原有Entry數(shù)組中的元素吩坝，添加到新數(shù)組中：
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    
    //新數(shù)組賦值給table屬性：
    table = newTable;
    //重新計算擴容閾值：
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

//原有元素復(fù)制到新數(shù)組中：
void transfer(java.util.HashMap.Entry[] newTable, boolean rehash) {
    //新數(shù)組長度：
    int newCapacity = newTable.length;
    
    //遍歷原有Entry數(shù)組：
    for (java.util.HashMap.Entry<K,V> e : table) {
        //判斷Entry[]中不為null的對象： 
        while(null != e) {
            java.util.HashMap.Entry<K,V> next = e.next;
            //此處需要再次判斷hashSeed是否進行初始化：
            if (rehash) {
                //對于Strig類型來說，hashSeed初始化后哑蔫，需要調(diào)用sun.misc.Hashing.stringHash32來計算hash值
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //計算新數(shù)組中元素所處于的角標：
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

創(chuàng)建Entry對象钉寝，createEntry(int hash, K key, V value, int bucketIndex)--key的哈希值，key闸迷，value嵌纲，所屬數(shù)組角標

void createEntry(int hash, K key, V value, int bucketIndex) {
    //獲取此角標下的Entry對象：
    java.util.HashMap.Entry<K,V> e = table[bucketIndex];
    
    //無論該角標下是否有元素，都將新元素插入該位置下腥沽，將原來的元素置為第二個逮走。
    table[bucketIndex] = new java.util.HashMap.Entry<>(hash, key, value, e);

    //Map集合長度+1
    size++;
}

以上，就是HashMap添加元素的整個流程巡球，也是HashMap的核心言沐。

接下來坚俗，我們來解答之前的2個遺留問題：

首先悴晰，來解惑hashSeed园骆，對應(yīng)的是hash(Object k)方法窒典；

//元素key的hash值計算：
final int hash(Object k) {
    int h = hashSeed;
    //如果為String類型千所，并且hashSeed不等于0兜材，則會調(diào)用sun.misc.Hashing.stringHash32()進行hash值計算
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    //計算key的hash值典挑，調(diào)用key的hashCode方法：
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);

    //經(jīng)過一系列位運算狞洋，得出一個hash值：
    return h ^ (h >>> 7) ^ (h >>> 4);
}

此時，你應(yīng)該知道hashSeed的作用了吧榆综！如果hashSeed進行了初始化妙痹，那么添加到HashMap中的字符串將會調(diào)用sun.misc.Hashing.stringHash32()方法來計算hash值。

下面再來看看鼻疮，highestOneBit()方法的疑惑點：

通過上面的學習怯伊，我們知道Integer.highestOneBit(number)是計算一個大于等于number的2次冪，也就是一個2的N次方數(shù)字判沟。并且這個數(shù)字耿芹，還是HashMap中Entry[]的初始長度。而在后面的擴容操作時挪哄，我們也是將原有的數(shù)組長度擴大了2倍吧秕。所以，無論如何HashMap中Entry[]的長度都是2的N次方迹炼；

此時砸彬，你可能會問：為什么一定是2的N次方呢？

下面的方法斯入，是計算新增元素應(yīng)該處于數(shù)組中的哪個角標砂碉？

通常來說，我們一般會對hash值進行取摸運算刻两，但是绽淘，在HashMap中卻使用的是與運算。主要是由于 %運算 會運用到除法闹伪，效率較低沪铭，而與運算直接操作的是101010二進制數(shù)據(jù)，效率更高偏瓤。不信的話杀怠，我們實際測試下：

public static void test() throws InterruptedException {

    Thread.sleep(3000);

    int hash = 4;

    int length = 16;

    long start = System.nanoTime();
    for(int x = 0;x<100000;x++){
        int result1 = hash%length;
        //int result2 = hash&(length-1);
    }
    long end = System.nanoTime()-start;
    System.out.println("共耗時：" + end);
}

測試結(jié)果：（納秒）

result1(模運算)：7515748  8673789  5734321  5426216  7897104

result2(與運算)：3858877  3656493  5005590  3932128  3924576

怎么樣，這回你該相信了吧厅克！

在進一步講解之前赔退，我們來回顧一下“與運算”的實現(xiàn)：

在二進制情況下的處理：
0 & 0=0
0 & 1=0
1 & 0=0
1 & 1=1

當length為2的N次方的話，一定為偶數(shù)证舟，這樣length-1則一定為奇數(shù)硕旗，而奇數(shù)轉(zhuǎn)換成二進制的話，最后一位定為1（可以自己測試下）女责，這樣當我們的hash值 與 奇數(shù) 進行與運算時候漆枚，得到的結(jié)果即可能為奇數(shù)，也可能為偶數(shù)（取決于hash值）抵知，此時的散列性更好墙基，出現(xiàn)哈希沖突的情況就比較低软族，也就是說HashMap中形成鏈表的可能性更低；

而當length為奇數(shù)時残制，length-1為偶數(shù)立砸，轉(zhuǎn)換成二進制的話最后一位是0。根據(jù)上面的與運算實現(xiàn)來看初茶，當用0來進行運算時颗祝，得到的結(jié)果均為0，既無論hash值是多少恼布，最終都只能是偶數(shù)吐葵。相比于上面來說，length是奇數(shù)相當于浪費掉Entry數(shù)組一半的空間桥氏，更容易出現(xiàn)哈希沖突，形成鏈表猛铅，進而影響整個HashMap的性能字支。

所以，HashMap選擇將length設(shè)置為2的N次方奸忽，既永遠都是偶數(shù)堕伪；

//計算元素所處于數(shù)組的位置，進行與運算
//一般使用hash值對length取模（即除法散列法）
static int indexFor(int h, int length) {
return h & (length-1);
}

• HashMap查找元素

相比于新增來說栗菜，HashMap的查找方法就很簡單了欠雌。一種是獲取key為null的情況，一種是key非null的情況疙筹。

//通過key 獲取對應(yīng)的value:
public V get(Object key) {
    if (key == null)
        //獲取key==null的value：
        return getForNullKey();

    //獲取key不為null的value值：
    java.util.HashMap.Entry<K,V> entry = getEntry(key);

    //返回對應(yīng)的value：
    return null == entry ? null : entry.getValue();
}

//獲取hashMap中key為 null的value值：
private V getForNullKey() {
    //hashmap中沒有元素富俄，則返回null：
    if (size == 0) {
        return null;
    }
    //獲取Entry數(shù)組中，角標為0的Entry對象（put的時候如果有null的key而咆，就存放到角標為0的位置）
    //獲取角標為0的Entry對象霍比，遍歷整個鏈表，看是否有key為null的key：返回對應(yīng)的value：
    for (java.util.HashMap.Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    //如果都不存在暴备，則返回null：
    return null;
}

 //通過對應(yīng)的key獲取 Entry對象：
final java.util.HashMap.Entry<K,V> getEntry(Object key) {
    //hashmap長度為0 悠瞬，則返回null：
    if (size == 0) {
        return null;
    }
    //獲取key對應(yīng)的hash值：若key為null,則hash值為0；
    int hash = (key == null) ? 0 : hash(key);
    //計算hash值對應(yīng)數(shù)組的角標涯捻，獲取數(shù)組中角標下的Entry對象：對該元素所屬的鏈表進行遍歷浅妆；
    for (java.util.HashMap.Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        //判斷key的hash值，再調(diào)用equlas方法進行判斷：hash值可能會相同障癌，equals進一步驗證凌外；
        if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    //沒找到返回null:
    return null;
}

• HashMap刪除元素

與查找相同，刪除元素的方法也比較簡單涛浙，主要是將元素移除HashMap的Entry[]數(shù)組趴乡。如果為數(shù)組角標下的第一個元素对省，則直接鏈表的第二個元素移動到頭部來。如果不為第一個元素晾捏，則將當前元素的前一個元素的next屬性指向當前元素的下一個元素即可蒿涎；

//移除hashMap中的元素，通過key：
public V remove(Object key) {
    //移除HashMap數(shù)組中的Entry對象：
    java.util.HashMap.Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

//通過key移除數(shù)組中Entry：
final java.util.HashMap.Entry<K,V> removeEntryForKey(Object key) {
    //如果Hashmap集合為0惦辛，則返回null：
    if (size == 0) {
        return null;
    }
    //計算key的hash值：
    int hash = (key == null) ? 0 : hash(key);
    //計算hash值對應(yīng)的數(shù)組角標：
    int i = indexFor(hash, table.length);

    //獲取key對應(yīng)的Entry對象：
    java.util.HashMap.Entry<K,V> prev = table[i];
    //將此對象賦值給e：
    java.util.HashMap.Entry<K,V> e = prev;

    //單向鏈表的遍歷：
    while (e != null) {
        //獲取當前元素的下一個元素：
        java.util.HashMap.Entry<K,V> next = e.next;

        Object k;
        //判斷元素的hash值劳秋、equals方法，是否和傳入的key相同：
        if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
            //增加操作數(shù)：
            modCount++;

            //減少元素數(shù)量：
            size--;
            //當為鏈表的第一個元素時胖齐，直接將下一個元素頂?shù)芥湵眍^部：
            if (prev == e)
                table[i] = next;
            else
                //當前元素的下下一個元素
                prev.next = next;
            //刪除當前遍歷到的元素：空方法玻淑，
            // 將被刪除的元素不再與map有關(guān)聯(lián)，沒有置為null之類的操作呀伙；
            e.recordRemoval(this);
            return e;
        }
        //不相同的話补履，就把
        prev = e;
        e = next;
    }
    return e;
}