HashMap涉及的技術(shù)點(diǎn)非常多，典型的數(shù)據(jù)結(jié)構(gòu)和算法有機(jī)結(jié)合，JDK對(duì)HashMap優(yōu)化變化中不斷權(quán)衡時(shí)間復(fù)雜和空間復(fù)雜度。
一. 存儲(chǔ)結(jié)構(gòu)
1.JDK1.8之前 HashMap = 數(shù)組(O(1)）+ 單向鏈表（O(n)）
2.JDK1.8之后 HashMap = 數(shù)組(O(1)）+ 單向鏈表（O(n)）+ 紅黑樹(O(log n)
關(guān)于結(jié)構(gòu)的幾個(gè)關(guān)鍵數(shù)字：
1.默認(rèn)初始化數(shù)組容量大小是16。
2.數(shù)組擴(kuò)容剛好是2的次冪。
3.默認(rèn)的加載因子是0.75。
4.鏈表長(zhǎng)度超過(guò)8時(shí)將鏈表轉(zhuǎn)化成紅黑樹結(jié)構(gòu)。
5.紅黑樹節(jié)點(diǎn)數(shù)減少到6的時(shí)候退化成鏈表。
以上幾個(gè)數(shù)字關(guān)系，又為什么是上邊的幾個(gè)數(shù)字接下來(lái)一個(gè)個(gè)分析。
二. 操作原理
1. put儲(chǔ)存流程
①計(jì)算桶的位置，根據(jù)key的hashcode求出hash值，位置index = hash%length。
②判斷是否達(dá)到擴(kuò)容條件，threshold=DEFAULT_INITIAL_CAPACITY * loadFactor（16*0.75=12）大于這個(gè)閥門值就需要擴(kuò)容，否則下一步。
③判斷桶位置是否為空，如果為空直接在數(shù)據(jù)插入數(shù)據(jù)。如果不為空，下一步。
④判斷是鏈表還是紅黑樹，鏈表是否到達(dá)轉(zhuǎn)化紅黑樹，當(dāng)前鏈表節(jié)點(diǎn)數(shù)<=8，插入節(jié)點(diǎn)；如果是紅黑樹插入節(jié)點(diǎn)，否則下一步。
⑤鏈表轉(zhuǎn)化成紅黑樹，插入節(jié)點(diǎn)。
⑥插入節(jié)點(diǎn)后計(jì)算當(dāng)前size是否需要擴(kuò)容，如果大于閥門值需要擴(kuò)容resize。
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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);
else {
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
以上是JDK1.8的HashMap的get調(diào)用關(guān)鍵方法源碼。
2. get獲取過(guò)程
①計(jì)算桶的位置，根據(jù)key的hashcode求出hash值，位置index = hash%length。
②無(wú)論是數(shù)組，鏈表還是紅黑樹，for循環(huán)判斷hash值沖突就比對(duì)key是否相等，相等就返回對(duì)應(yīng)的value。
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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;
}
以上是JDK1.8的HashMap的put調(diào)用關(guān)鍵方法源碼。
三. 數(shù)據(jù)結(jié)構(gòu)和算法思考
1.為什么選擇數(shù)組和鏈表結(jié)構(gòu)？
①數(shù)組內(nèi)存連續(xù)塊分配，效率體現(xiàn)查詢更快。HashMap中用作查找數(shù)組桶的位置，利用元素的key的hash值對(duì)數(shù)組長(zhǎng)度取模得到。
②鏈表效率體現(xiàn)增加和刪除。HashMap中鏈表是用來(lái)解決hash沖突，增刪空間消耗平衡。
擴(kuò)展：為什么不是ArrayList而是使用Node<K,V>[] tab？因?yàn)锳rrayList的擴(kuò)容機(jī)制是1.5倍擴(kuò)容，而HashMap擴(kuò)容是2的次冪。
2.為什么擴(kuò)容是2次冪，根據(jù)key的hashcode再求hash值？
①key的hash值計(jì)算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
代碼意思是hash = hashcode的高16位異化低16位，而不是直接hashcode。
②計(jì)算桶的位置代碼
index = (n - 1) & hash
思想：
一是，為了減少hash沖突使用hash%length計(jì)算，求模計(jì)算保證了得到的結(jié)果一定在0-length范圍之內(nèi)。
二是，為了提高運(yùn)算速度，模運(yùn)算比不上位運(yùn)算，當(dāng)n是2的次冪才滿足hash%length == （n-1）&hash。
確定公式中（n-1）符合最優(yōu)等式，剩下考慮hash值的最優(yōu)，hash值這個(gè)因子考慮影響結(jié)果盡可能不沖突。
因?yàn)橛?jì)算速度體現(xiàn)在位運(yùn)算上，條件n是2的次冪，那么n-1的換算成二進(jìn)制前邊都是連續(xù)的0，后邊都是連續(xù)的1,。比如n=16，則n-1=15，15的二進(jìn)制1111。hash & 1111 = 只要關(guān)注的hash的二進(jìn)制的最后四位數(shù)進(jìn)行&運(yùn)算。
如上圖，最終會(huì)與15的二進(jìn)制進(jìn)行1111四位運(yùn)算，如果與key.hashcode進(jìn)行與運(yùn)算的話，只要key的hashcode最后四位為0000前邊無(wú)論是什么都沒關(guān)系，這樣出現(xiàn)相同值的概率高很多。所以，引入hashcode先高低16位進(jìn)行異或運(yùn)算，減少hash沖突。
擴(kuò)展：
hashcode與equals相等判斷對(duì)比：
兩個(gè)key的hashcode相等，key不一定equals。
兩個(gè)key的equals，hashcode一定相等。
3.為什么加載因子為0.75，鏈表長(zhǎng)度大于8轉(zhuǎn)成紅黑樹？
思想：
上邊問(wèn)題不是兩個(gè)獨(dú)立問(wèn)題而是相互相關(guān)，目的盡量減少?zèng)_突前提提高空間利用率和減少查詢成本的折中。
加載因子決定了HashMap的擴(kuò)容的閥門值，如果桶是16，那么擴(kuò)容值16* 0.75=12，也就是12的時(shí)候就要考慮擴(kuò)容，還有4個(gè)沒有被利用到，犧牲的空間。如果加載因子是1，空間利用率高，但是查詢速度變慢。
原理：
權(quán)衡依據(jù)是以上情況符合泊松分布（一種統(tǒng)計(jì)與概率學(xué)里常見到的離散概率分布，適合于描述單位時(shí)間（或空間）內(nèi)隨機(jī)事件發(fā)生的次數(shù)），用0.75作為加載因子，每個(gè)碰撞位置的鏈表長(zhǎng)度超過(guò)８?jìng)€(gè)概率非常低，少于千萬(wàn)分之一。
源碼說(shuō)明：
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
擴(kuò)展：
為什么不一開始選擇紅黑樹？
紅黑樹近乎于平衡二叉樹，結(jié)構(gòu)適合均勻分布節(jié)點(diǎn)，減少樹的深度像鏈表長(zhǎng)度情況。原因主要是插入效率上，紅黑樹增加節(jié)點(diǎn)很可能需要進(jìn)行左旋，右旋，著色操作，這些時(shí)間效率并沒有鏈表形式高。
4.HashMap的key選擇
1）選擇不可變的對(duì)象，比如字符串或int類型。
2）如果要用一個(gè)自定義實(shí)體類作為key：
①類添加final修飾符，保證類不被繼承。
②保證所有成員變量必須私有，并且加上final修飾。
③不提供改變成員變量的方法，包括setter。
④通過(guò)構(gòu)造器初始化所有成員，進(jìn)行深拷貝(deep copy)。
5.String類中的hashcode計(jì)算
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
哈希計(jì)算公式：s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]
四. 橫向擴(kuò)展
1.HashMap出現(xiàn)線程問(wèn)題
①多線程擴(kuò)容，引起的死循環(huán)問(wèn)題（jdk1.8中，死循環(huán)問(wèn)題已經(jīng)解決）。
②多線程put的時(shí)候可能導(dǎo)致元素丟失
③put非null元素后get出來(lái)的卻是null
2.使用線程安全Map
①HashMap并不是線程安全，要實(shí)現(xiàn)線程安全可以用Collections.synchronizedMap(m)獲取一個(gè)線程安全的HashMap。
②CurrentHashMap和HashTable是線程安全的。CurrentHashMap使用分段鎖技術(shù)，要操作節(jié)點(diǎn)先獲取段鎖，在修改節(jié)點(diǎn)。
3.Android提倡使用ArrayMap
①ArrayMap數(shù)據(jù)結(jié)構(gòu)是兩個(gè)數(shù)組，一個(gè)存放hash值，另一個(gè)存放key和value。
②根據(jù)key的hash值利用二分查找在hash數(shù)組中找出index。
③根據(jù)index在key-value數(shù)組中對(duì)應(yīng)位置查找，如果不相等認(rèn)為沖突了，會(huì)以key為中心，分別上下展開，逐一查找。
優(yōu)勢(shì)，數(shù)據(jù)量少時(shí)（少于1000）相比HashMap更節(jié)省內(nèi)存。劣勢(shì)，刪除和插入時(shí)效率要比HashMap要低。
