摘要：取模主要是為了能夠平均的落在每個數(shù)組上面。在多線程的情況下，會造成死循環(huán)。把先暫存單線程情況，創(chuàng)建一個對象參見方法，然后把引入給數(shù)組的位置。隊頭插入的效率高，如果隊尾插入，還要遍歷鏈表。此時，線程執(zhí)行以下代碼。

table，Entry類型數(shù)組的數(shù)據(jù)

Entry，包括了key，value，Entry，以及hash

final K key;
V value;
Entry next;
int hash;

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);//見putForNullKey方法
    int hash = hash(key);
    int i = indexFor(hash, table.length);//見indexFor方法，取模
    for (Entry e = table[i]; e != null; e = e.next) {//遍歷落在取模的數(shù)組上，遍歷鏈表
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//判斷hash值一樣，并且key也要一樣
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);//見addEntry方法
    return null;
}

key為空的情況，在數(shù)組的第一個位置的鏈表遍歷查找，如果有key為空，返回相應(yīng)的值，如果沒有，添加到鏈表后面。

private V putForNullKey(V value) {
    for (Entry 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++;
    addEntry(0, null, value, 0);
    return null;
}

注釋已經(jīng)提醒了，length長度必須是2的非0冪數(shù)，h & (length-1)是對h%length的意思（length長度為2的非0冪數(shù)時有效）。比如123243423 % 16的值是15，123243423 & 15也是15，當然123243423是我隨便打的。取模主要是為了能夠平均的落在每個數(shù)組上面。

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    //擴容為2倍長度，跟上面取模要求的一樣，乘以2也是2的非0冪數(shù)
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);//見createEntry方法
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry e = table[bucketIndex];//取到數(shù)組的位置的entry
    table[bucketIndex] = new Entry<>(hash, key, value, e);//新entry加到鏈表的頭部，并把數(shù)組指向新entry
    size++;
}
/**
 * Creates new entry.
 */
Entry(int h, K k, V v, Entry n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry entry = getEntry(key);//見getEntry方法

    return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry e = table[0]; e != null; e = e.next) {//因為put的時候，直接放數(shù)組的第一個，所以查詢的時候，也查詢第一個
        if (e.key == null)
            return e.value;
    }
    return null;
}

final Entry getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);//先取hash
    for (Entry e = table[indexFor(hash, table.length)];//取模，找到數(shù)組位置，然后遍歷鏈表
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))//判斷hash和key都相等
            return e;
    }
    return null;
}

這個方法在調(diào)用put的時候，在resize擴容的時候調(diào)用。在多線程的情況下，會造成死循環(huán)。

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry e : table) {
        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);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

1、put("a",1)，創(chuàng)建一個entry對象（參見createEntry方法），然后把引入給數(shù)組0的位置。

2、put("b",1)，再創(chuàng)建一個entry對象，然后新對象的next指向舊的entry對象，最后數(shù)組指向新entry。隊頭插入的效率高，如果隊尾插入，還要遍歷鏈表。


3、如果擴容到4，參加transfer方法，依然采用隊頭插入，也就是說，如果鏈表是1，2，3，4，那么插入后就變成4，3，2，1。
現(xiàn)創(chuàng)建一個表，取到鏈表數(shù)據(jù)，開始遍歷。這里假設(shè)都到index為3的數(shù)組。

Entry next = e.next;//把next先暫存
e.next = newTable[i]時，這個e是key為b的entry
newTable[i] = e;執(zhí)行完后，index為3的數(shù)組執(zhí)行b。

現(xiàn)在執(zhí)行暫存的a
繼續(xù)執(zhí)行上面幾個步驟，完成擴容，結(jié)果如下：

我們設(shè)想一下，如果兩個線程同時進行擴容，A線程獲取key為b的entry的時候，時間分片到了，現(xiàn)在線程B線程執(zhí)行，完成上面單線程的情況。
此時，A線程執(zhí)行以下代碼。

e.next = newTable[i];
newTable[i] = e;
e = next;

e.next = newTable[i];的時候，此時b的next指向a

newTable[i] = e;的時候

可以看到，index為3的指向b，b的next指向a，a的next指向b。當有g(shù)et操作，并且hash也落在index為3的時候，就死循環(huán)了。