涉及數(shù)據(jù)結(jié)構(gòu)
- 紅黑樹
- 鏈表
- 哈希
從CRUD說起
預熱知識：
DEFAULT_INITIAL_CAPACITY = 1 << 4, HashMap默認容量為16（n << m意思是n*2^m）
MAXIMUM_CAPACITY = 1 << 30最大容量度气，2^30即10,7374,1824.
DEFAULT_LOAD_FACTOR = 0.75f負載因子0.75糕簿，擴容時需要用到
TREEIFY_THRESHOLD = 8
The table, initialized on first use, and resized as necessary. When allocated, length is always a power of two. (We also tolerate length zero in some operations to allow bootstrapping mechanics that are currently not needed.)
首次使用時初始化狞谱，必要時進行調(diào)整摄闸。調(diào)整之后的容量通常為2的次冪云茸。（在一些操作中也允許長度為零是目，以允許當前不需要的自舉機制）
Node<K,V>[] table存儲KV對
The next size value at which to resize (capacity * load factor).
threshold:因為牽涉到擴容，而map的擴容（即對table進行擴容操作）不是到了存滿了才擴标捺，是以容量*負載因子作為臨界點進行擴容的懊纳。
簡單講下Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
看了之后發(fā)現(xiàn)什么揉抵，這就是個簡單的實現(xiàn)了Map.Entry接口的單鏈表。
new HashMap()
有的時候嗤疯，大家寫代碼可能會不指定初始大小Map<String, String> map = new HashMap<>();
運行map.put("test", "zhangsan");的時候冤今，首先運行一次resize()，此時table = new Node[16]
(p = tab[i = (n - 1) & hash]) == null經(jīng)過hash與n-1的與運算茂缚，找到一個位置（比如4）戏罢，如果這個位置值為null，那么tab[4]就放上一個Node（圖中僅僅以value做區(qū)分脚囊，但請大家注意龟糕，這實際上是Node，有key,有value悔耘，有hash讲岁，有next，盡管剛開始next是null）
假如此時接著執(zhí)行了map.put("test", "liss");會走p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))這個if分支衬以，然后將原來的value替換為liss但正常情況下我們寫業(yè)務邏輯缓艳，都不會這么寫的對吧。
假如繼續(xù)put("test2", "zhangsan2")按照這樣的方式put下去看峻。插入7條數(shù)據(jù)之后如下
當執(zhí)行map.put("test8", "zhangsan8");時阶淘，由于test8的hash與15做運算，得到的位置為4互妓，而4這個位置已經(jīng)有值了舶治。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 新的值就掛在上一個的next指針上
p.next = newNode(hash, key, value, null);
// 大于等于7的時候，樹化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 在找key相等的節(jié)點车猬，如果找到了霉猛，就替換掉
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
然后就這樣很開心的繼續(xù)put，直到遇見map.put("test13", "zhangsan13");
此時珠闰，size > threshold(16 * 0.75 = 12)惜浅，因此進入resize()，長度擴為16 * 2 = 32進入如下邏輯伏嗜。
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 對于單個Node節(jié)點坛悉，直接放到原來的位置+n的位置，比如原來在0承绸，則擴容后在16
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
如果e.hash在16對應的那個位置是1裸影，那么就放到hiHead那條鏈表上，位置處于[j + oldCap]處军熏。
resize()方法
調(diào)整map的大小轩猩，實現(xiàn)map初始化或擴展為原有尺寸的二倍。
HashMap默認大小16，當存儲了12個的時候均践，如果再put晤锹，會先將新的值存于原來的map中，然后發(fā)現(xiàn)++size > threshold(這里是12）彤委，就會進行調(diào)整resize鞭铆。調(diào)整的時候，新的table會變成32焦影，threshold變成24车遂，并且需要將原有的值復制進新的table中。
int hash(Object key)
key == null,hash為0斯辰；否則艰额，(h = key.hashCode()) ^ (h >>> 16)即計算hashCode，與hashCode右移16位（除以65536得到的商）做異或（同0異1）運算椒涯。
計算單個字符的hash結(jié)果就是對應的ASCII碼柄沮，例如hash('a')=97
V put(K key, V value)
put是允許key為null的
get
