使用的數(shù)據(jù)機(jī)構(gòu)

Node[] 鏈接結(jié)構(gòu) TreeNode[] 紅黑樹結(jié)構(gòu)

• 使用hash表（數(shù)組+鏈表），當(dāng)鏈表過長(zhǎng)時(shí)將其轉(zhuǎn)成紅黑樹以實(shí)現(xiàn)O(logn)時(shí)間復(fù)雜度的查找

如何工作(put方法過程)

DEFAULT_INITIAL_CAPACITY = 16 初始化容量
MAXIMUM_CAPACITY= 1 << 30  = 1073741824 最大容量
DEFAULT_LOAD_FACTOR = 0.75f 默認(rèn)填充因子(擴(kuò)容因子)
TREEIFY_THRESHOLD = 8 閾值，當(dāng)桶(bucket)上的鏈表數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹，put方法的有用到
UNTREEIFY_THRESHOLD = 6 閾值，同上一個(gè)相反，當(dāng)桶(bucket)上的鏈表數(shù)小于這個(gè)值時(shí)樹轉(zhuǎn)鏈表
MIN_TREEIFY_CAPACITY = 64 樹的最小的容量，至少是 4 * TREEIFY_THRESHOLD = 32 然后為了避免(resizing 和 treeification thresholds) 設(shè)置成64
Node<k,v>[] table 存儲(chǔ)元素的數(shù)組，總是2的倍數(shù)
threshold 臨界值 當(dāng)實(shí)際大小(容量*填充因子)超過臨界值時(shí)，會(huì)進(jìn)行擴(kuò)容
loadFactor 填充因子

<<左移運(yùn)算：按二進(jìn)制形式把所有的數(shù)字向左移動(dòng)對(duì)應(yīng)的位數(shù)，高位移出（舍棄），低位的空位補(bǔ)零。
>>右移運(yùn)算：按二進(jìn)制形式把所有的數(shù)字向右移動(dòng)對(duì)應(yīng)巍峨位數(shù)，低位移出（舍棄），高位的空位補(bǔ)符號(hào)位，即正數(shù)補(bǔ)零，負(fù)數(shù)補(bǔ)1.
1 << 30
0000 0000 0000 0000 0000 0000 0000 0001 -----> 0010 0000 0000 0000 0000 0000 0000 0000
在計(jì)算二進(jìn)制轉(zhuǎn)十進(jìn)制得到 1073741824

• 初始化數(shù)組resize()，如果Node<K,V>[] tab為空初始化長(zhǎng)度為16的數(shù)組
• 計(jì)算key的hashCode，并計(jì)算下標(biāo)

什么是hash碰撞呢？?jī)蓚€(gè)輸入串的hash函數(shù)的值一樣，則稱這兩個(gè)串是一個(gè)碰撞(Collision)。
h >>> 16 避免hash碰撞(hash collisons)將高位分散到低位上，最后進(jìn)行高16位與低16位^異或運(yùn)算得出key的hash值
(n - 1) & hash]) 計(jì)算下標(biāo)

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 如果沒有碰撞直接放入桶中

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

• 如果發(fā)生碰撞了以鏈表的方式放到后面

if (p.hash == hash &&
   ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

......
afterNodeAccess(e);

• 如果鏈表長(zhǎng)度超過閾值（TREEIFY_THRESHOLD > 8）,把鏈表轉(zhuǎn)化成紅黑樹

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
    break;
}

• 如果節(jié)點(diǎn)已經(jīng)存在替換舊值
• 如果桶滿了(容量*填充因子，默認(rèn)是16 x 0.75)，就resize()擴(kuò)容，擴(kuò)容的大小是2的n次方

for (int binCount = 0; ; ++binCount) {
      if ((e = p.next) == null) {
         p.next = newNode(hash, key, value, null);
         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
            break;
         }
         if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
         p = e;
}

沖突解決、擴(kuò)容過程、原數(shù)組擴(kuò)容后的位置？

• 將新節(jié)點(diǎn)加到鏈表后
• 至少2的n次方的擴(kuò)容，重新計(jì)算hash值
• 原下標(biāo)或者原下標(biāo)+原容量的位置