使用的數(shù)據(jù)機構(gòu)
Node[] 鏈接結(jié)構(gòu) TreeNode[] 紅黑樹結(jié)構(gòu)
- 使用hash表（數(shù)組+鏈表），當(dāng)鏈表過長時將其轉(zhuǎn)成紅黑樹以實現(xiàn)O(logn)時間復(fù)雜度的查找
如何工作(put方法過程)
DEFAULT_INITIAL_CAPACITY = 16 初始化容量
MAXIMUM_CAPACITY= 1 << 30 = 1073741824 最大容量
DEFAULT_LOAD_FACTOR = 0.75f 默認填充因子(擴容因子)
TREEIFY_THRESHOLD = 8 閾值界弧，當(dāng)桶(bucket)上的鏈表數(shù)大于這個值時會轉(zhuǎn)成紅黑樹，put方法的有用到
UNTREEIFY_THRESHOLD = 6 閾值辣之，同上一個相反掰伸，當(dāng)桶(bucket)上的鏈表數(shù)小于這個值時樹轉(zhuǎn)鏈表
MIN_TREEIFY_CAPACITY = 64 樹的最小的容量皱炉，至少是 4 * TREEIFY_THRESHOLD = 32 然后為了避免(resizing 和 treeification thresholds) 設(shè)置成64
Node<k,v>[] table 存儲元素的數(shù)組，總是2的倍數(shù)
threshold 臨界值 當(dāng)實際大小(容量*填充因子)超過臨界值時狮鸭，會進行擴容
loadFactor 填充因子
<<左移運算：按二進制形式把所有的數(shù)字向左移動對應(yīng)的位數(shù)合搅，高位移出（舍棄），低位的空位補零歧蕉。
>>右移運算：按二進制形式把所有的數(shù)字向右移動對應(yīng)巍峨位數(shù)灾部，低位移出（舍棄），高位的空位補符號位惯退，即正數(shù)補零赌髓，負數(shù)補1.
1 << 30
0000 0000 0000 0000 0000 0000 0000 0001 -----> 0010 0000 0000 0000 0000 0000 0000 0000
在計算二進制轉(zhuǎn)十進制得到 1073741824
- 初始化數(shù)組resize()，如果Node<K,V>[] tab為空初始化長度為16的數(shù)組
- 計算key的hashCode催跪，并計算下標
什么是hash碰撞呢锁蠕？兩個輸入串的hash函數(shù)的值一樣，則稱這兩個串是一個碰撞(Collision)懊蒸。
h >>> 16 避免hash碰撞(hash collisons)將高位分散到低位上荣倾，最后進行高16位與低16位^異或運算得出key的hash值
(n - 1) & hash]) 計算下標
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);
- 如果鏈表長度超過閾值（TREEIFY_THRESHOLD > 8）,把鏈表轉(zhuǎn)化成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
- 如果節(jié)點已經(jīng)存在替換舊值
- 如果桶滿了(容量*填充因子，默認是16 x 0.75)骑丸，就resize()擴容舌仍，擴容的大小是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;
}
沖突解決妒貌、擴容過程、原數(shù)組擴容后的位置铸豁？
- 將新節(jié)點加到鏈表后
- 至少2的n次方的擴容灌曙，重新計算hash值
- 原下標或者原下標+原容量的位置
