摘要：前言本文的目的是閱讀理解的源碼，作為集合中重要的一個角色，平時用到十分多的一個類，深入理解它，知其所以然很重要。

本文的目的是閱讀理解HashMap的源碼，作為集合中重要的一個角色，平時用到十分多的一個類，深入理解它，知其所以然很重要。本文基于Jdk1.7，因為Jdk1.8改變了HashMap的數(shù)據(jù)結(jié)構(gòu)，進行了優(yōu)化，我們先從基礎(chǔ)閱讀，之后再閱讀理解Jdk1.8的內(nèi)容

1.通過key-value的形式快速的存取元素
2.允許鍵為Null，但只允許有一個鍵的值為Null
3.線程不安全
4.底層結(jié)構(gòu)是Hash表，元素是無序的
5.再不考慮Hash沖突的時候，插入和查詢的復(fù)雜度是可以達到O（1）的

底層數(shù)據(jù)結(jié)構(gòu)是一個Hash表，基于數(shù)組和鏈表，數(shù)組里面保存著一個單向鏈表的頭節(jié)點，單項鏈表保存著具有相同Hash值的不同元素，再不發(fā)生Hash沖突的情況下，鏈表應(yīng)該只有一個元素，這是最理想的狀態(tài)。

鏈表的數(shù)據(jù)結(jié)構(gòu)代碼
`

static class Entry implements Map.Entry {
final K key;
V value;
Entry next;    // 下一個Entry對象的引用
int hash;    // 其實就是key的hash值  
}         

// 默認初始化容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 
// HashMap允許的最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
 
// 默認的負載率 75%
static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
// 空的哈希表
static final Entry[] EMPTY_TABLE = {};
 
// 實際使用的哈希表
transient Entry[] table = (Entry[]) EMPTY_TABLE;
 
// HashMap的大小,即存儲的key-value的數(shù)量
transient int size;
 
// 擴容的閥值，當HashMap的size達到閥值時，就開始擴容 threshold=length*threshold 
int threshold;
 
// 負載率
final float loadFactor;
 
// 修改次數(shù), 用于fail-fast機制
transient int modCount;
 
// 替代哈希使用的默認擴容閥值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
 
// 隨機的哈希種子, 有助于減少發(fā)生哈希碰撞的幾率

transient int hashSeed = 0;

HashMap的初始化涉及到上面的多個常量，在了解完常量的作用之后，我們就可以理解HashMap的初始化思想，首先，HashMap并不是通過構(gòu)造函數(shù)來初始化的，構(gòu)造函數(shù)只是初始化HashMap的初始化參數(shù)，包括DEFAULT_INITIAL_CAPACITY ，loadFactor等，再初始化參數(shù)之后，真正的調(diào)用Put方法時，會判斷table 是否已經(jīng)初始化，沒有的話再根據(jù)參數(shù)進行初始化。

put方法的流程我們這邊也要先理解：
（1）檢查哈希表是否是個空表，如果是空表就調(diào)用inflateTable方法進行初始化
（2）判斷key是否為null，如果為null，就調(diào)用putForNullKey方法, 將key為null的key-value存儲在哈希表的第一個位置中
如果key不為null，則調(diào)用hash方法計算key的hash值
（3）根據(jù)hash值和Entry數(shù)組的長度定位到Entry數(shù)組的指定槽位
（4）判斷Entry數(shù)組指定槽位的值e是否為null, 如果e不為null, 則遍歷e指向的單鏈表, 如果傳入的key在單鏈表中已經(jīng)存在了, 就進行替換操作, 否則就新建一個Entry并添加到單鏈表的表頭位置
（5）如果e為null,?就新建一個Entry并添加到指定槽位

下面是代碼：
構(gòu)造方法

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);
    }
 
    // 設(shè)置負載率
    this.loadFactor = loadFactor;
 
    // 設(shè)置閥值為初始容量
    threshold = initialCapacity;
 
    // 空實現(xiàn), 交由子類實現(xiàn)
    init();
}
//

初始化數(shù)組方法

private void inflateTable(int toSize) {
    // 尋找大于toSize的,最小的,2的n次方作為新的容量
    int capacity = roundUpToPowerOf2(toSize);
 
    // 閥值=容量*負載因子, 如果容量*負載因子>最大容量時, 閥值=最大容量
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
 
    // 按新的容量創(chuàng)建一個新的數(shù)組
    table = new Entry[capacity];
 
    // 重新初始化hashSeed
    initHashSeedAsNeeded(capacity);
}

put方法

public V put(K key, V value) {
    // 如果哈希表沒有初始化就進行初始化
    if (table == EMPTY_TABLE) {
        // 初始化哈希表
        inflateTable(threshold);
    }
 
    // 當key為null時，調(diào)用putForNullKey方法，保存null于table的第一個位置中，這是HashMap允許為null的原因
    if (key == null) {
        return putForNullKey(value);
    }
 
    // 計算key的hash值
    int hash = hash(key);
    // 根據(jù)key的hash值和數(shù)組的長度定位到entry數(shù)組的指定槽位
    int i = indexFor(hash, table.length);
    // 獲取存放位置上的entry，如果該entry不為空，則遍歷該entry所在的鏈表
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        // 通過key的hashCode和equals方法判斷，key是否存在， 如果存在則用新的value取代舊的value，并返回舊的value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
 
    // 修改次數(shù)增加1
    modCount++;
    // 如果找不到鏈表 或者 遍歷完鏈表后，發(fā)現(xiàn)key不存在，則創(chuàng)建一個新的Entry，并添加到HashMap中
    addEntry(hash, key, value, i);
    return null;
}

 void addEntry(int hash, K key, V value, int bucketIndex) {
    //添加key到table[bucketIndex]位置，新的元素總是在table[bucketIndex]的第一個元素，原來的元素后移
    Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry(hash, key, value, e);
    //判斷元素個數(shù)是否達到了臨界值，若已達到臨界值則擴容，table長度翻倍
        if (size++ >= threshold)
            resize(2 * table.length);
    }

當key值為Null的時候會進行特殊處理，在table[0]的鏈表上查找Key為null的元素，get的過程是：
（1）計算hash與table.length取模計算index值
（2）遍歷table[index]上的鏈表，直到找到key

 void addEntry(int hash, K key, V value, int bucketIndex) {
//添加key到table[bucketIndex]位置，新的元素總是在table[bucketIndex]的第一個元素，原來的元素后移
Entry e = table[bucketIndex];
    table[bucketIndex] = new Entry(hash, key, value, e);
//判斷元素個數(shù)是否達到了臨界值，若已達到臨界值則擴容，table長度翻倍
    if (size++ >= threshold)
        resize(2 * table.length);
}

#HashMap的刪
remove方法同樣也是，先計算hash,在計算index，遍歷查找，找到之后刪除節(jié)點

/**
     * 根據(jù)key刪除元素
     */
    public V remove(Object key) {
        Entry e = removeEntryForKey(key);
        return (e == null ? null : e. value);
    }

    /**
     * 根據(jù)key刪除鏈表節(jié)點
     */
    final Entry removeEntryForKey(Object key) {
        // 計算key的hash值
        int hash = (key == null) ? 0 : hash(key.hashCode());
        // 根據(jù)hash值計算key在數(shù)組的索引位置
        int i = indexFor(hash, table.length );
        // 找到該索引出的第一個節(jié)點
        Entry prev = table[i];
        Entry e = prev;

        // 遍歷鏈表（從鏈表第一個節(jié)點開始next），找出相同的key，
        while (e != null) {
            Entry next = e. next;
            Object k;
            // 如果hash值和key都相等，則認為相等
            if (e.hash == hash &&
                ((k = e. key) == key || (key != null && key.equals(k)))) {
                // 修改版本+1
                modCount++;
                // 計數(shù)器減1
                size--;
                // 如果第一個就是要刪除的節(jié)點（第一個節(jié)點沒有上一個節(jié)點，所以要分開判斷）
                if (prev == e)
                    // 則將下一個節(jié)點放到table[i]位置（要刪除的節(jié)點被覆蓋）
                    table[i] = next;
                else
                 // 否則將上一個節(jié)點的next指向當要刪除節(jié)點下一個（要刪除節(jié)點被忽略，沒有指向了）
                    prev. next = next;
                e.recordRemoval( this);
                // 返回刪除的節(jié)點內(nèi)容
                return e;
            }
            // 保存當前節(jié)點為下次循環(huán)的上一個節(jié)點
            prev = e;
            // 下次循環(huán)
            e = next;
        }

        return e;
}

resize擴容是HashMap中非常重要的一個操作，在容器里的元素達到一個臨界值時，HashMap會自動進行擴容，擴容的具體流程是；
1.在put的時候檢查是否需要擴容，根據(jù)兩個參數(shù)：初始容量和裝載因子
2.創(chuàng)建一個容量為table.length*2的table，修改臨界值
3.重新計算所有元素的hash值，并放入新的table，使用的是頭插法
4.用新的table替換舊的table

 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {//最大容量為 1 << 30
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];//新建一個新表
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;//是否再hash
        transfer(newTable, rehash);//完成舊表到新表的轉(zhuǎn)移
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
--------------------- 
 void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) {//遍歷同桶數(shù)組中的每一個桶
            while(null != e) {//順序遍歷某個桶的外掛鏈表
                Entry next = e.next;//引用next
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);//找到新表的桶位置;原桶數(shù)組中的某個桶上的同一鏈表中的Entry此刻可能被分散到不同的桶中去了，有效的緩解了哈希沖突。
                e.next = newTable[i];//頭插法插入新表中
                newTable[i] = e;
                e = next;
            }
        }
    }

擴容的整體操作如上，但是有一些十分精妙的細節(jié)十分厲害

這么設(shè)計當然是為了性能，而且是十分顯著的性能提升，涉及到了位操作，我覺得非常有意思，會在下一篇專門講這樣計算進行提升性能的例子。