一蚪拦、前言
什么是Hash冻押？
在談論HashMap前驰贷，先討論一下Hash洛巢。Hash，就是把任意長度的輸入通過散列算法稿茉，變換成固定長度的輸出，該輸出就是散列值狈邑。這種轉換是一種壓縮映射，也就是米苹，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出蘸嘶，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)训唱。
HashMap
哈希表是根據設定的哈希函數(shù)H（key）和處理沖突方法將一組關鍵字映射到一個有限的地址區(qū)間上，并以關鍵字在地址區(qū)間中的象作為記錄在表中的存儲位置况增，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址澳骤。作為線性數(shù)據結構與表格和隊列等相比，哈希表是查找速度比較快的一種为肮。
HashMap以鍵值對的形式存儲數(shù)據，且鍵可以為null颊艳。這里會關鍵討論到hash表在Java中的實現(xiàn)以及解決沖突的方法忘分。
二白修、屬性
*1.DEFAULT_INITIAL_CAPACITY
默認容量，16
2.MAXIMUM_CAPACITY
最大容量熬荆，2^30
*3.DEFAULT_LOAD_FACTOR
默認裝填因子，0.75
*4.TREEIFY_THRESHOLD
默認值為8卤恳，在hashmap中寒矿，不同的key可能經過hash函數(shù)會映射成相同的哈希值突琳，這些哈希值相同的數(shù)據將會放在一條鏈表中或一棵紅黑樹中存儲符相。在初始時，這些數(shù)據會形成鏈表啊终，當鏈表長度大于8時，鏈表會轉換成紅黑樹
*5.TREEIFY_THRESHOLD
默認值為6蓝牲，當上述的數(shù)據長度小于6時，紅黑樹又會轉回鏈表以達到性能均衡
6.MIN_TREEIFY_CAPACITY
默認值為64例衍，最小樹形化容量閾值。當哈希表中的容量大于該值佛玄，則將鏈表樹形化。為了避免進行擴容梦抢、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD
7.Node
Node是Entry的實現(xiàn)類奥吩，HashMap中每一個K，V鍵值對數(shù)據都存放在一個Entry(Node)中圈驼。Node主要有以下屬性及方法
hash
用來記錄節(jié)點的hash值
key
用來記錄一個key
value
用來記錄一個value
next
Node類型，用來指向下一個相同hash值的節(jié)點
Node(int hash,K key ,V value,Node<K,V>)
構造函數(shù)
8.table
table是一個Node<K,V>數(shù)組萤厅，用來表示一個HashMap對象的所有的初始節(jié)點的節(jié)點集橄抹。每一個table的項被稱為桶
9.entrySet
是一個Set<Map.Entry<K,V>>惕味，存放了HashMap中的所有節(jié)點
10.size
HashMap中包含的鍵值對的數(shù)量
11.modCount
HashMap結構修改次數(shù)
12.threshold
threshold=capacity*loadFactor
當HashMap的size大于threshold時會執(zhí)行resize操作
13.loadFactor
裝載因子。用于hashMap的擴容名挥。
14.KeySet
用于存放key
15.Value
用來存放Values
16.EntrySet
用于存放Entry
17.TreeNode
紅黑樹的實現(xiàn)
三、構造函數(shù)
HashMap(int initialCapacity,float loadFactor)
傳入初始化容量和裝填因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
這里需要留心最后的tableSizeFor方法禀倔，這里會對傳入的initialCapacity做判斷并進行優(yōu)化后再初始化Hash Map的初始容量
Hash(int initialCapacity)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
這里不做過多說明，下同
HashMap()
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
HashMap(Map<? extends K,? extends V> m)
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
將參數(shù)作為新的hashMap的entry救湖，putMapEntries將在下面介紹
四、方法
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
用于實現(xiàn)putAll()以及構造方法力九，主要功能為將參數(shù)中的Map傳遞到當前實例中。
傳入Map時先判斷是否為初始化HashMap的情況跌前，即table是否為空陡舅。
若table為空抵乓，需要考慮Map的對應的threshold值是否會超出當前HashMap的threshold蹭沛，因為threshold=capacity*loadFactor臂寝，所以傳入的threshold為m.size()/loadFactor摊灭，考慮計算結果可能為小數(shù)，因此為了保守計算容量加上1帚呼。隨后將計算出的的threshold與當前實例進行比較，隨后通過tableSizeFor優(yōu)化容量并初始化煤杀。
若table不為空，則判斷s>threshold沈自，若成立，則resize枯途。
最后一步籍滴，就是通過for循環(huán)將數(shù)據存入實例中
tableSizeFor(int cap)
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
舉個例子能更好的看懂代碼榴啸，因為涉及到移位操作孽惰，故用二進制數(shù)作為參數(shù)舉例：
令cap= 00100001(33)
則n=cap-1=00100000(32)
經過一系列移位后
n=00111111
再通過return中語句的執(zhí)行鸥印，n最終等于01000000(32)
問：不難發(fā)現(xiàn)，其實上述操作是將傳入的參數(shù)轉換為最靠近的2的n次方库说，這是為什么呢?
答：HashMap將不同的鍵放入不同的桶中，主要采用了hash&capacity-1的方法璃弄，在計算機中，直接除以capacity運算的效率低于位運算夏块，且sun公司的大牛們發(fā)現(xiàn)纤掸，當容量為2的n次方時脐供，hash & (capacity - 1) == hash % capacity借跪，前提就是容量必須為2的n次方。
hash(Object key)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
jdk1.8的hash算法是將key的hashCode與其右移16為的抑或結果掏愁。抑或：若位相等，則返回0果港，不相等則返回1
問：為什么不直接用hashCode？
答：上面討論到hashmap將key放入到桶中使用的是hash&capacity-1辛掠，一般情況下capacity的大小都不超過低16位（65535），舉16（默認容量）作為例子萝衩，在做與運算時，若使用hashCode猩谊，則hash的有效位只有低4位，如210,220,2^30在運算時就會產生沖突牌捷。因此通過抑或將hashCode的高16位與hashCode進行計算涡驮，可以減少產生沖突的幾率
get(Object key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
通過getNode方法獲取到鍵值對
getNode()
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
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;
}
判斷table是否為null憔古，table長度是否大于0，桶是否存在
若存在鸿市，則first指向桶的第一個元素，且先判斷first節(jié)點的key是否與傳入的key相同焰情。
若不相同，則判斷first是否有下一個節(jié)點内舟，若有下一個節(jié)點，則可能是鏈表验游，也可能是樹形，若是樹形耕蝉，調用getTreeNode并返回結果。
若是鏈表垒在，則調用while循環(huán)完成搜索。
containsKey(Object o)
調用了getNode方法判斷獲取到的node是否為null
containsValue(Object value)
比價好理解场躯，不貼代碼了，時間復雜度為O(n^2)
put(K,V)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
將鍵值對關聯(lián)到當前map對象中踢关，若此前map中已有該key，則會被覆蓋耘成。
pubIfAbsent(K key,V value)
調用了putVal(hash(key), key, value, true, true)，若碰到key已存在的情況瘪菌，若key對應value為空，則覆蓋师妙，不為空，則不覆蓋。
putVal(K key,V value,boolean onlyIfAbcent,boolean evict)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//若table為空怔檩，則初始化threshOld
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//若桶為空，新建元素并直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//桶不為空
else {
Node<K,V> e; K k;
//若hash值和key都和桶首節(jié)點相同薛训，則可能會覆蓋原有節(jié)點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//桶為樹形結構
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//桶中不存在樹形結構，且key值不與首元素相同
else {
for (int binCount = 0; ; ++binCount) {
//若后續(xù)元素為空闸英，則插入并判斷是否需要樹形化
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//后續(xù)元素不為空則執(zhí)行以下語句，判斷是否有相同的key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//若e不為空甫何，說明有相同key，根據onlyIfAbsent判斷是否需要覆蓋
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//LinkedHashMap相關操作辙喂，暫時不討論
afterNodeAccess(e);
//返回被覆蓋的值
return oldValue;
}
}
++modCount;
//判斷是否需要擴容
if (++size > threshold)
resize();
//LinkedHashMap相關操作鸠珠，暫時不討論
afterNodeInsertion(evict);
return null;
}
代碼較多巍耗，以注釋形式呈現(xiàn)渐排。如果線程A和線程B同時進行put操作芍锦，剛好這兩條不同的數(shù)據hash值一樣飞盆，并且該位置數(shù)據為null次乓，所以這線程A吓歇、B都會進入第8行代碼中票腰。假設一種情況，線程A進入后還未進行數(shù)據插入時掛起杏慰，而線程B正常執(zhí)行，從而正常插入數(shù)據缘滥，然后線程A獲取CPU時間片，此時線程A不用再進行hash判斷了朝扼，問題出現(xiàn)：線程A會把線程B插入的數(shù)據給覆蓋，發(fā)生線程不安全擎颖。
resize()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//若table長度已經是最大值观游，則直接返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//若oldCap的2倍小于最大長度且oldCap大于等于16，則newCap長度為oldCap的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
//table長度為0懂缕，oldThr=16*loadFactor作為當前新的容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//oldCap和threshOld都為0，則使用默認值
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//newThr可能為0搪柑，若為0，則需要通過計算初始化
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新threshOld
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//舊表不為空拌屏，則需要將舊表的數(shù)據復制到新表
if (oldTab != null) {
//操作每一個桶中的節(jié)點元素
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//gc
oldTab[j] = null;
//后續(xù)元素為空
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//后續(xù)元素不為空术荤，且是樹形的
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//后續(xù)元素不為空倚喂，且是鏈表
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;
//這里是e.hash&oldCap瓣戚，并不是e.hash&oldCap-1，后面解釋
//若為0子库，插入第一個元素時為loHead賦值e
//之后每一個元素都為loTail賦值，并更新loTail到loTail.next
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//若不為0仑嗅，插入第一個元素時為hiHead賦值e
//之后每一個元素都為hiTail賦值，并更新hiTail到hiTail.next
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//while循環(huán)結束后仓技，最終會形成2條鏈表——loHead和hiHead
//loHead放在原來的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//hiHead放在新的位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
初始化表，或者令表長度加倍脖捻。若表為空，則按照初始容量分配容量地沮。若不為空，由于容量為2n摩疑，所以每個桶中元素必須保持相同的索引，或者在新的table中按照2n規(guī)則進行偏移未荒。代碼有些長，用注釋代替長篇的解釋了。
e.hash & oldCap原理
引用自https://blog.csdn.net/u013494765/article/details/77837338
// (e.hash & oldCap) 得到的是 元素的在數(shù)組中的位置是否需要移動,示例如下
// 示例1：
// e.hash=10 0000 1010
// oldCap=16 0001 0000
// & =0 0000 0000 比較高位的第一位 0
//結論：元素位置在擴容后數(shù)組中的位置沒有發(fā)生改變
// 示例2：
// e.hash=17 0001 0001
// oldCap=16 0001 0000
// & =1 0001 0000 比較高位的第一位 1
//結論：元素位置在擴容后數(shù)組中的位置發(fā)生了改變速侈，新的下標位置是原下標位置+原數(shù)組長度
// (e.hash & (oldCap-1)) 得到的是下標位置,示例如下
// e.hash=10 0000 1010
// oldCap-1=15 0000 1111
// & =10 0000 1010
// e.hash=17 0001 0001
// oldCap-1=15 0000 1111
// & =1 0000 0001
//新下標位置
// e.hash=17 0001 0001
// newCap-1=31 0001 1111 newCap=32
// & =17 0001 0001 1+oldCap = 1+16
//元素在重新計算hash之后，因為n變?yōu)?倍倚搬，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：
treeifyBin(Node<K,V>[] tab,int hash)
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
除非table太小了每界，需要resize，否則替換所有桶中的鏈表元素眨层。
判斷table是否為空，或table容量小于MIN_TREEIFY_CAPACITY（6）,則resize趴樱。
若上述條件不成立，則判斷桶是否存在叁征，存在則利用replacementTreeNode進行樹形化
putAll(Map<? extends K,? extends V> m)
調用了putMapEntries(m, true)
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
判斷table是否為空逛薇，若為空捺疼，則調用tableSizeFor檢查是否需要擴容永罚，并更新threshOld啤呼。
若不為空呢袱，則判斷s是否大于threshOld媳友，大于則需要擴容产捞。
通過for循環(huán)調用putVal插入元素
remove(Object key)
通過removeNode實現(xiàn)
remove(Object key,Object value)
調用了removeNode(hash(key),key,value,true,true),只有當value相同時才會刪除
removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//table不為空哼御，長度大于0坯临，對應桶存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//node是需要被刪除的元素
Node<K,V> node = null, e; K k; V v;
//桶首元素正好是要刪除的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//桶首元素與key不相等恋昼，判斷next
else if ((e = p.next) != null) {
//樹形結構
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//鏈表結構
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//上述操作是為了找到相應的節(jié)點
//matchValue為true時，需要判斷value值是否相等液肌，只有相等才會刪除
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//樹形結構刪除
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//node==p,說明刪除元素在桶第一個，直接為tabl[index]賦值即可
else if (node == p)
tab[index] = node.next;
//若node！=p,由于p指向的是node前一個節(jié)點婿滓，因此將p.next指向node.next即可
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction)
public V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
if (value == null)
throw new NullPointerException();
if (remappingFunction == null)
throw new NullPointerException();
//獲取key的hash值
int hash = hash(key);
Node<K,V>[] tab; Node<K,V> first; int n, i;
//桶元素數(shù)量
int binCount = 0;
TreeNode<K,V> t = null;
//old用來存儲舊的value值
Node<K,V> old = null;
//容量不足粥喜，table為空都需要resize
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
//判斷hash&值對應桶存在與否
if ((first = tab[i = (n - 1) & hash]) != null) {
//桶為樹形結構
if (first instanceof TreeNode)
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
//鏈表結構
else {
Node<K,V> e = first; K k;
//找到對應節(jié)點
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
}
//old不為空凸主，進行merge操作
if (old != null) {
V v;
if (old.value != null)
v = remappingFunction.apply(old.value, value);
else
v = value;
if (v != null) {
old.value = v;
afterNodeAccess(old);
}
//merge后的v為空额湘，則將該節(jié)點刪除
else
removeNode(hash, key, null, false, true);
return v;
}
//old為空，即不存在key
if (value != null) {
//紅黑樹不為空
if (t != null)
t.putTreeVal(this, tab, hash, key, value);
//紅黑樹為空
else {
//新建節(jié)點到first
tab[i] = newNode(hash, key, value, first);
//判斷binCount锋华，選擇是否treeifyBin
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
afterNodeInsertion(true);
}
return value;
}
五、總結
HashMap有關紅黑樹的實現(xiàn)以及compute*相關方法未介紹毯焕，后面有機會會補上，上述的介紹主要涉及到了HashMap關鍵的數(shù)據結構以及相關擴容芥丧、插入紧阔、刪除等操作续担，有一些比較理解較為簡單的地方略過了沒有講，大概就是這個樣子了物遇。
