數(shù)據(jù)結構
//一個Node數(shù)組,Node是一個單向鏈表
transient Node<K,V>[] table;
//Node內部類
static class Node<K,V> implements Map.Entry<K,V> {
// hash值
final int hash;
// key
final K key;
// value
V value;
// 下一個節(jié)點,形成單向鏈表
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;
}
}
image.png
1.hash算法
put操作時,會先計算key的hash值
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
// 如果key是null，那么hash值就為0怠李，所以為null的key只能存在一個。
// 否則, 取key的hashCode 按位異或(位不同 結果為1蛤克，其余為0) hashCode 無符號右移16位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
經(jīng)典問題1：為什么hashCode 要無符號右移 16位后 再與hashCode進行 異或操作捺癞？
image.png
將h無符號右移16為相當于將高區(qū)16位移動到了低區(qū)的16位，再與原h(huán)ashcode做異或運算构挤。
從上文可知高區(qū)的16位與原h(huán)ashcode相比沒有發(fā)生變化髓介，低區(qū)的16位發(fā)生了變化
我們可知通過上面(h = key.hashCode()) ^ (h >>> 16)進行運算可以把高區(qū)與低區(qū)的二進制特征混合到低區(qū)，那么為什么要這么做呢筋现？
因為 重新計算出的新哈希值在后面將會參與hashmap中數(shù)組槽位的計算唐础。
計算公式：(n - 1) & hash箱歧，假如這時數(shù)組槽位有16個，則槽位計算如下：
image.png
可以看到 高區(qū)的16位很有可能會被數(shù)組槽位數(shù)的二進制碼鎖屏蔽一膨，并沒有參與到 槽位的計算中,也就是在計算槽位時將丟失高區(qū)特征叫胁。高位不同，低位相同的hashCode 出現(xiàn)哈希碰撞的 概率增大汞幢。
2. 計算槽位
// n為數(shù)組長度
(n - 1) & hash
經(jīng)典問題2：為什么槽位數(shù)必須使用2^n
因為 a %b,當b等于2的n次方時， 等價于 a & (b - 1)微谓，也就是 a % (2^n) 等價于 a & (2^n - 1) 渊鞋，可以直接轉化為 按位與 鼻种，位運算的運算效率高于算術運算。
image.png
2^n -1 比較特殊 ， 倒數(shù)第n位以及它之前的全部是0辽社，后面全部是1，與其他數(shù)做&運算時贫堰，剛好可以把 表示 2^n倍數(shù)的位全部 抹成0,剩下的就是 取余后的結果缕溉。
3. put操作?
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//獲取hash值
static final int hash(Object key) {
int h;
//獲取key的hashcode,并亦或哈希值的右移16位之后的值,再返回
//為什么要右移16位？
//加入高16位特征肴焊，減少哈希沖突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//首先根據(jù)(n-1)&hash === n%hash,這個運算可以獲取一個0到數(shù)組長度-1的值(不會超出數(shù)組),來獲取在數(shù)組的下表位置,如果沒值,創(chuàng)建一個新的鏈表(node頭節(jié)點)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果頭節(jié)點有值(上面那個if 有賦值操作,賦值給p了),并頭節(jié)點的hash值與要put的值相等前联，那就把頭結點p賦值給e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果node節(jié)點已經(jīng) 進化成 紅黑樹了
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果還是鏈表的話，一直往下循環(huán)
for (int binCount = 0; ; ++binCount) {
// 如果當前值是null娶眷，說明已經(jīng)到達了鏈表的尾部似嗤，仍然沒有找到之前存在的key
if ((e = p.next) == null) {
// 就在鏈表尾部 新建并加入一個node節(jié)點，
p.next = newNode(hash, key, value, null);
// 如果遍歷次數(shù)達到7届宠，也就是鏈表長度到達8（加上了上面新加入的節(jié)點）, 進化成 紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 加入節(jié)點 或者長度達到8時進化成紅黑樹之后, 退出for循環(huán)
break;
}
// 如果當前節(jié)點e不等于null,判斷當前Node key是不是與要加入的k相等,相等就返回,到下面 替換當前節(jié)點的e.value為新值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果e有值,說明這個key之前是存在的,
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 替換e.value 為新值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 并返回
return oldValue;
}
}
++modCount;
// 如果當前占用槽位的數(shù)量> 長度*負載因子0.75
if (++size > threshold)
// 擴容
resize();
afterNodeInsertion(evict);
return null;
}
看完以上HashMap的put操作我們就可以這樣一個疑問
為什么重寫一個類的equals方法烁落，需要重寫類的hashcode方法。
在hashSet和hashMap等根據(jù)Hash值進行判斷的幾個中,假設你重寫了equals方法,改變了對象的比較邏輯,但未重寫hashcode方法,即使你put了兩個內容相等的對象,但hashMap還是認為你是不同的key豌注，因為你判斷的是hashcode伤塌，導致都插入成功.
4. get操作
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// "tab[(1)&hash]"取出該key計算哈希之后對應數(shù)據(jù)下標的頭結點
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判斷頭結點的hash值是否與傳入的Hash值相等并且（頭結點的Key是否與傳入的key 地址相等 或者內容相等）
// 為什么要先判斷一下((k = first.key) == key || (key!= null && key.equals(k)))呢？
// 其實hashMap的鏈表存的只是hashCode相同的一個集合,有可能key值的內容是不同的轧铁，但計算出的哈希一樣,這樣hashMap還是會把他們放入同一個節(jié)點中.
//這個操作其實就是找到鏈表中key與傳入key相等的節(jié)點
if (first.hash == hash && // always check first node
((k = first.key) == key || (key!= null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e; } while ((e = e.next) != null);
}
}
return null;
}
5. 擴容resize
當數(shù)組被占用的數(shù)量 > 數(shù)組長度 * 加載因子 0.75每聪，就會擴容，容量*2齿风。 擴容后會把所有值的 node節(jié)點 重新計算hash槽位熊痴，再設置到擴容后的數(shù)組中。
問題三 ：為什么要擴容聂宾？
當HashMap中元素越來越多時果善，由于槽位數(shù)固定，碰撞的幾率越來越高,為提高效率系谐，進行擴容巾陕，增加槽位讨跟。
增大取模之后值的范圍,減少哈希沖突,減緩鏈表長度越來越長的原因
加載因子 0.75(默認)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
總結
應盡量避免resize，如果預支元素的個數(shù),可以指定hashmap的容量,比如1000鄙煤，應制定為 2048（2000的話hashMap會自動設置為2的n次方）,因為 2048*0.75>1000晾匠，既避免了碰撞幾率過大的風險，又規(guī)避了resize操作梯刚。
