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

//HashMap是動(dòng)態(tài)擴(kuò)容的，就是容量大小不能大于 1<<30
static final int MAXIMUM_CAPACITY = 1 << 30;

//默認(rèn)的擴(kuò)容因子，這個(gè)值可以通過構(gòu)造修改
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//空數(shù)據(jù)，默認(rèn)構(gòu)造的時(shí)候賦值為空的Entry數(shù)組，在添加元素的時(shí)候
//會(huì)判斷table=EMPTY_TABLE ，然后就擴(kuò)容
static final Entry<?,?>[] EMPTY_TABLE = {};

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

//Hashmap的大小
transient int size;

//threshold表示當(dāng)HashMap的size大于threshold時(shí)會(huì)執(zhí)行resize操作。
DEFAULT_INITIAL_CAPACITY=16

//擴(kuò)容的閾值
int threshold;

//擴(kuò)容因子，沒有傳入就使用默認(rèn)的DEFAULT_LOAD_FACTOR = 0.75f
final float loadFactor;

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

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

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

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

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

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

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

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

// 獲取key的hash值
    int hash = hash(key);
    // 根據(jù)hash值和數(shù)組長(zhǎng)度計(jì)算要放入的數(shù)組下標(biāo)位置
    int i = indexFor(hash, table.length);

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

static int indexFor(int h, int length) {
    // 計(jì)算數(shù)組下標(biāo)位置，數(shù)組長(zhǎng)度必須為2的n次方
    return h & (length-1);
}

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;
        }
    }
    
   // 修改次數(shù)+1
    modCount++;
    // 下標(biāo)位置為空或沒有能夠匹配的key值，創(chuàng)建Entry放入鏈表
    addEntry(hash, key, value, i);

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

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

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

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

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

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

0000 1111
0001 1111
0011 1111

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

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

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

Entry<K,V> next = e.next;