說明

hashMap在JAVA1.7和java1.8版本中有做一些調整，我們本篇只說java1.7的hashMap。

數據結構

hashMap的數據結構是由數組和鏈表組成，table是一個存放Entry對象的數組，每個Entry對象由4個屬性組成，分別是key、value、next、hash，key和value是我們熟知的鍵值對，不需要過多解釋，next是當前元素在鏈表中指向下一個元素的引用，hash是計算出來的hashcode，hashMap中的hsah是通過對key.hashcode()進行一定操作得出的，并不是直接使用key.hashcode()方法計算數來的值。

屬性信息

先來了解下hashMap中一些重要的屬性

//Hashmap的初始化大小，初始化的值為16,1往右移4位為16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

//HashMap是動態擴容的，就是容量大小不能大于 1<<30
static final int MAXIMUM_CAPACITY = 1 << 30;

//默認的擴容因子，這個值可以通過構造修改
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//空數據，默認構造的時候賦值為空的Entry數組，在添加元素的時候
//會判斷table=EMPTY_TABLE ，然后就擴容
static final Entry<?,?>[] EMPTY_TABLE = {};

//表示一個空的Hashmap
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//Hashmap的大小
transient int size;

//threshold表示當HashMap的size大于threshold時會執行resize操作。
DEFAULT_INITIAL_CAPACITY=16

//擴容的閾值
int threshold;

//擴容因子，沒有傳入就使用默認的DEFAULT_LOAD_FACTOR = 0.75f
final float loadFactor;

//數據操作次數，用于迭代檢查修改異常
transient int modCount;

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

put方法

步驟：

判斷table是否為空，如果為空則初始化，不為空則下一步
判斷key是否為null，如果為null則處理，不為null則下一步
根據key計算下標
如果下標處的桶不為空，則從下標處開始遍歷鏈表，如果找到key相同的則更新覆蓋并返回舊值，如果為空則下一步
插入前判斷是否需要擴容，如果需要則進行擴容，如果不需要就下一步
頭插法插入桶中

接下來我們對每一步驟分別展開討論

1.table初始化

private void inflateTable(int toSize) {
    // 找到大于等于指定數組長度的2的n次方
    int capacity = roundUpToPowerOf2(toSize);
 // 擴容閾值，數組長度*負載因子
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 創建數組
    table = new Entry[capacity];
    // 是否重新賦值hashSeed 
    initHashSeedAsNeeded(capacity);
}

private static int roundUpToPowerOf2(int number) {
    // 使用Integer的highestOneBit方法找到大于等于指定數組長度的2的n次方
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

數組初始化其實就三個步驟：計算數組容量，創建數組，判斷是否重hash

「數組容量」：如果指定數組長度值大于MAXIMUM_CAPACITY(最大數組容量:2的30次方)，就用最大值;如果指定數組長度值小于等于1，就用1；如果指定數組長度值大于1，就用下面的方法得到大于等于指定數組長度的第一個2的n次方的值。

Integer.highestOneBit((number - 1) << 1)

public static int highestOneBit(int i) {
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    }

這個方法內部是通過位移和亦或操作得到的值，感興趣的可以直接看下源碼。

「創建數組」：直接用計算出來的數組長度創建Entry數組table，元素類型為Entry。

「判斷是否重hash」：

重hash就是對同個key重新計算hash值，那么為什么要重新計算hash值，實際上只是為了讓hsah值更復雜，在計算下標的時候就會更加散列,減少hash沖突。

那么什么樣的條件下才會重hash呢，從源碼可以看出switching為true表示需要重hash，影響switching取值的是下面這段代碼

final boolean initHashSeedAsNeeded(int capacity) {
 // hashSeed 初始值為0，false
    boolean currentAltHashing = hashSeed != 0;
    // 數組長度是否 >= 2^31-1 
    boolean useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    // 使用異或，currentAltHashing 為false，只有數組長度>= 2^31-1時返回true
    boolean switching = currentAltHashing ^ useAltHashing;
    //switching為true，則hashSeed重新賦值（一般不會出現）
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

initHashSeedAsNeeded方法用來判斷是否進行重hash，如果需要重hash，會同步更新hash種子，最后返回boolean類型的值。

sun.misc.VM.isBooted()指jvm運行狀態，一般為true；

hashSeed初始為0，所以currentAltHashing一定為false；

Holder.ALTERNATIVE_HASHING_THRESHOLD取的是環境變量jdk.map.althashing.threshold配置的值(程序員配置)，如果沒有配置就默認取Integer.MAX_VALUE。

通過上面的分析可以知道是否進行重hash只會受到capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD的影響。

「我們可以得出一個結論：」如果程序員不配置環境變量jdk.map.althashing.threshold，那么就永遠不會進行重hash，因為數組長度capacity最大是2的30次方，而Integer.MAX_VALUE的值是2的31次方減1，即這個條件永遠不會滿足，但是你可能會說擴容的時候傳入的capacity正好是最大值2的30次方的2倍，但是我會告訴你，如果數組成都達到2的30次方，是不允許擴容的。

所以說如果程序員不設置環境變量，initHashSeedAsNeeded方法實際上沒有意義的。

那為什么要更新hash種子呢？

這就要了解下hsah值是怎么生成的了：

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
 
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

hashMap的hsah值是由key調用自身的hashCode方法得到的值與hashSeed進行5次亦或操作4次位移運算得到的。

所以相同的key只有在hashSeed變化后才有生成不同的hash值，否則生成的永遠是相同的hsah值，所以需要重hash的時候就必須改變hashSeed，否則重hash的結果會和原來一樣。

2.處理key為null

private V putForNullKey(V value) {
 // 當key為null時，數組下標指定為0
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
     // 判斷現在有沒有key為null的Entry
        if (e.key == null) {
         //value替換為新值，返回舊的value
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    //修改次數+1
    modCount++;
    // table[0]中沒有值或沒有匹配到null的key，創建一個Entry放入table[0]
    addEntry(0, null, value, 0);
    return null;
}

上面這段代碼是對key為null的情況的處理，同時也說明hashmap是允許key為null的，通過上面可以看出hashMap中key為null的元素只會存儲在數組下標為0的桶中，如果桶中有多個，就遍歷鏈表找到key為null的元素進行覆蓋更新，如果桶中無元素，就調用addEntry方法插入元素，這里只需要知道調用addEntry方法的結果是將數據插入數組下標為0的桶中，addEntry方法我們下面再具體看。

3.計算下標

// 獲取key的hash值
    int hash = hash(key);
    // 根據hash值和數組長度計算要放入的數組下標位置
    int i = indexFor(hash, table.length);

計算下標實際上分為兩步，計算hsah值和計算下標，計算下標的原理是用hash值除以數組容量，得到的余數就是下標，用這種方式可以保證不同的key一定會放在數組中的某個桶中，不會越界，而hash值可以讓不同的key在數組中的分部足夠分散，減少hsah沖突。

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
 
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

上面已將說過hash方法，這里再來說一次，我們知道java中每個類都默認由hashcode方法生成hashcode，但是hashMap中并沒有直接用此方法生成的hashcode，而是對其生成的hahshcode與hash種子進行亦或和位移操作，1.7的hashMap在計算hsah的時候進行了5次亦或操作和4次位移運算，這樣做的目的就是使得不同的key計算出來的hash更加分散，更加能減少hash沖突。

static int indexFor(int h, int length) {
    // 計算數組下標位置，數組長度必須為2的n次方
    return h & (length-1);
}

我們上面說了hash除以數組容量得到數組下標，但是這種做法在java中太慢了，而和此做法同效的一種方式就是h & (length-1)，就是數組容量減去1，再與hash做&操作。這種方式在java中是非常高效的。

4.遍歷查找key

運行到這里，數組已經有了，key對應的下標也有了，接下來就是插入操作，插入之前會先查看下標對應的桶中是否為空桶，如果不為空桶就要先遍歷查找是否有相同key。

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 判斷key的值是否相等
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
         // key的值相等則寫入新的value值，將舊value返回
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    
   // 修改次數+1
    modCount++;
    // 下標位置為空或沒有能夠匹配的key值，創建Entry放入鏈表
    addEntry(hash, key, value, i);

因為hashMap是由數組和鏈表組成，數組的每個桶中都由鏈表組成，所以需要遍歷鏈表查找相同的key，如果存在相同的key就更新覆蓋，如果沒有，就調用addEntry方法進行插入。

//addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
 // 如果當前數組長度>=擴容閾值 并且 當前數組下標位置不為null
    if ((size >= threshold) && (null != table[bucketIndex])) {
     // 數組擴容為當前長度*2
        resize(2 * table.length);
        // key是否為null，不為null計算hash值，null則直接hash值為0
        hash = (null != key) ? hash(key) : 0;
        // 根據hash值和新數組長度計算下標位置
        bucketIndex = indexFor(hash, table.length);
    }
 //創建Entry放入table中
    createEntry(hash, key, value, bucketIndex);
}

可以看到在正式添加元素之前會先判斷是否需要擴容，如果需要則先進行擴容。

5.擴容處理

從上面的源碼可以知道擴容需要滿足兩個條件：

數組長度達到threshold，threshold是由負載因子和數組容量計算出來的
當前數組下標對應的桶不為null

如果滿足條件則進入resize方法進行擴容

void resize(int newCapacity) {
 // 原數組
    Entry[] oldTable = table;
    // 原數組長度
    int oldCapacity = oldTable.length;
    // 如果原數組長度為2^30，不進行擴容，把擴容閾值修改為2^31-1
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
 // 根據新的數組長度，創建數組
    Entry[] newTable = new Entry[newCapacity];
    // 轉移數組數據 
    // 調用initHashSeedAsNeeded方法，根據新數組的長度判斷是否會hashSeed重新賦值
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // table指向新數組
    table = newTable;
    // 計算新的擴容閾值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// transfer方法
void transfer(Entry[] newTable, boolean rehash) {
 // 新數組長度
    int newCapacity = newTable.length;
    // 遍歷原數組的Entry
    for (Entry<K,V> e : table) {
     // Entry不為null
        while(null != e) {
         // 先找到鏈表中下一個要轉移的Entry
            Entry<K,V> next = e.next;
            // 如果hashSeed變了，重新進行hash計算
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 重新計算數組下標，結果分兩種：1.與原下標一直 2.原下標+本次擴容了多長
            int i = indexFor(e.hash, newCapacity);
            /*原數組統一鏈表中的數據轉移到新數組中時，所處鏈表順序顛倒，因此多線程的情況下可能會出現環形鏈表問題*/
            // Entry的next指向新數組的鏈表頭
            e.next = newTable[i];
            // Entry放入新數組的鏈表中
            newTable[i] = e;
            // 下一次進行操作的就是原數組鏈表的下一個
            e = next;
        }
    }
}

擴容步驟：

首先傳入的newCapacity是數組容量的2倍，也是2的n次方
如果數組的容量已經達到2的30次方，則不進行擴容，直接返回
用新的數組長度newCapacity創建Entry數組
initHashSeedAsNeeded判斷是否要重hash，并更新hash種子
transfer方法進行擴容處理

「transfer方法進行具體的擴容處理：」

實際上就是遍歷舊數組，從舊數組的第一個桶中拿到鏈表，從鏈表頭部開始遍歷，一個一個的取出計算新的下標(如果需要重hash就會用新的hsah種子計算hsah值，如果不需要重hash就用原來的hsah值，最終用hsah值和新數組容量計算下標)，然后頭插法插到新的數組中。

「你會發現兩個規律：」

原來數組中的鏈表和新數組中鏈表的順序相反。
計算所得的新下標要么等于原下標值，要么等于原下標加擴容的長度。

我們通過一個例子來分析一下第二條規律。

假設table.length=16，現在有兩個key,key1對應的hash值為68,key2對應hash值為84,根據公式h & (length-1)計算，&運算規則是遇0為0，結果如下：

68 key1 0100 0100 & 0000 1111 =0000 0100 =4 84 key2 0101 0100 & 0000 1111 =0000 0100 =4

可見兩個值都落在table[4]這個桶中。

擴容一次后table.length=32，再根據公式h & (length-1)計算結果如下

68 key1 0100 0100 & 0001 1111 =0000 0100 =4 84 key2 0101 0100 & 0001 1111 =0001 0100 =20

可見68依然被放在新數組的table[4],而84被放在table[20]

再擴容一次后table.length=64，再根據公式h & (length-1)計算結果如下

68 key1 0100 0100 & 0011 1111 =0000 0100 =4 84 key2 0101 0100 & 0011 1111 =0001 0100 =20

可見兩個值還在原來的數組下標對應的桶中。

結論：同一個桶中的鏈表中的數據，擴容后，在新數組中的下標要么和原數組相同，要么是原數組下標加擴容的長度。

這個規律是怎么形成的呢？

這得益于數組的容量都為2的n次方，數組每次擴容的后結果都是原來數組容量的兩倍，例如：16，32,64...，length-1的結果分別是15,31,63，而對應的二進制如下：

0000 1111

0001 1111

0011 1111

可以看的出，每次擴容都是高位加1，就導致在計算的時候只需要看hash值中與高位對應的那個位上是0還是1，也就導致新數組中的下標只有兩種可能：如果是0下標不變，如果是1下標就會變化。

這個規律有什么好處呢？

這個規律可以使原來在同個桶中的數據可以分散到其他桶中，使得數組分部更加均勻，減少hash沖突，擴容的時候同個桶中的數據將會被分部到新數組中的哪個桶中，可以通過只判斷高位就能確定，所以可以以此來優化擴容效率。

6.頭插法

// createEntry方法
void createEntry(int hash, K key, V value, int bucketIndex) {
 // 獲取當前數組下標位置的鏈表頭
    Entry<K,V> e = table[bucketIndex];
    // 在鏈表頭位置創建新的Entry，next指向原鏈表頭（頭插法）
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    // 數組長度+1
    size++;
}

頭插法的源碼就很簡單了，就是新建一個Entry對象，新建Entry對象的next屬性指向當前坐標下的頭部Entry對象，再把新的Entry對象引用賦值給當前數組下標處。

這里的文字說明可能比自己看源碼更繞。自己看源碼應該一目了然。

問題匯總

為什么要計算得到大于等于指定數組長度的第一個2的n次方的值

只有在數組長度為2的n次方時，數組長度-1轉換為2進制時才可以轉換為低位全部為1的二進制，和hash值進行&運算時才能等效于hash值除以數組容量求余的結果。

為什么要用頭插法？

實際上無論是頭插法還是尾插法，都是需要遍歷鏈表的，如果在遍歷過程中找到key相同的，則更新覆蓋，這種情況不會有插入操作，所以無所謂頭插法和尾插法，但是如果沒有找到key相同的元素，那這時肯定已經遍歷到鏈表的尾部了，所以但凡插入，不管是頭插法還是尾插法都不會在遍歷鏈表上節省時間，又因為鏈表的插入僅僅是更換next屬性的指針，所以兩種插入方式的效率是沒有區別的。

java1.7之所以使用頭插法應該和自身的代碼結構有關，因為插入方法是獨立的，如果用尾插法，就要在遍歷的時候記錄最后一個元素的值，而頭插法就不需要了，但是我覺得這個不是主要原因，個人覺得java開發者只不過是兩者選擇了一個而已，沒有什么特殊考慮，否則也不至于會有循環鏈表的問題了。

hashMap為什么是線程不安全的

hashMap線程不安全主要表現在兩個方面

多線程插入數據的時候，數據丟失問題

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

上面是頭插法的代碼邏輯，在多線程操作下，如果兩個線程同時走到方法內第一行，那么獲取到的e是相同的，然后兩個線程分別創建Entry對象，并且Entry對象的next屬性賦值為e，這樣一來總會有一個線程的數據被丟掉了。

多線程情況下擴容的時候可能會發生循環鏈表

循環鏈表發生在多線程擴容的情況下，下面是擴容的部分代碼：

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

這段代碼邏輯是把舊數組中的數據從鏈表頭部一個個利用頭插法插入到新數組中。

假設有兩個線程同時進行擴容，兩條線程都執行到下面這行代碼：