作為Javaer呈础，對于Map這個單詞絕對不會陌生，無論是開發(fā)過程中還是出去面試的時候拓轻，都會經(jīng)常遇到，而最頻繁使用和面試提問的無非這么幾個经伙，HashMap, HashTable, ConcurrentHashMap扶叉。那么本文就針對這幾個知識點做一個歸納和總結(jié)。
從HashMap說起
HashMap是上面提到的幾個Map中使用頻率最高的了帕膜，畢竟需要考慮到多線程并發(fā)的場景并不算太多辜梳。下面是Map的一個關(guān)系圖，大家了解一下即可泳叠。
HashMap在Java8之前和之后有很大差別作瞄，在Java8以前，它的數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表的形式危纫，8以后就變成了數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)宗挥。它的key是保存在一個Set里面的，也就是有去重的功能种蝶，values是存在一個Collections里面契耿。
HashMap里的數(shù)組每個元素存放的是key-value形式的實例，Java7里面叫做Entry螃征，8里面叫Node搪桂。這個Node里面包含了hash值，鍵值對盯滚，下一個節(jié)點next這幾個屬性組成踢械。數(shù)組被分為一個個bucket，也就是桶魄藕，通過hash值決定了鍵值對在這個數(shù)組中的尋址内列，hash值相同的則以鏈表的形式存儲，鏈表長度超過閾值就轉(zhuǎn)成紅黑樹背率。那么先來看看HashMap的put操作话瞧，
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;
// 算出鍵值對在table中的具體位置，沒有就new一個node
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();
// 這是為了繼承HashMap的LinkedHashMap類服務(wù)的寝姿，用來回調(diào)移除最早放入Map的對象
afterNodeInsertion(evict);
return null;
}
那么總結(jié)一下就是：
- 若HashMap未被初始化交排，則進行初始化操作
- 對Key求Hash值，依據(jù)Hash值計算下標
- 若未發(fā)生碰撞饵筑，則直接放入桶中
- 若發(fā)生碰撞埃篓，則以鏈表的方式鏈接到后面
- 若鏈表長度超過閾值，且HashMap元素超過最低樹化容量翻翩，則將鏈表轉(zhuǎn)成紅黑樹
- 若節(jié)點已經(jīng)存在都许，則用新值替換舊值
- 若桶滿了稻薇，就需要resize（擴容2倍后重排）
這個put的操作引申出幾個知識點，首先胶征，
HashMap的初始容量是多少塞椎？為什么設(shè)置成這個值呢？
翻看源碼我們可以看到有這么一個變量DEFAULT_INITIAL_CAPACITY睛低，
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
這個就是HashMap的初始容量案狠，也就是16，為啥用位運算這么騷的寫法是因為位運算比算數(shù)計算的效率要高钱雷。那么為啥用16骂铁？看看上面說的下標計算的公式: index = HashCode（Key） & （Length- 1）,當(dāng)長度為16時候，Length-1的二進制就是1111,是一個所有位都為1的數(shù)罩抗，而且看上述注釋拉庵，建議的HashMap的初始長度都是2的冪次方，這種情況下套蒂，index的結(jié)果等同于HashCode后幾位的值钞支。那么只要輸入的HashCode本身分布均勻，Hash算法的結(jié)果就是均勻的操刀。
另一個問題烁挟，Java8里面引入了紅黑樹，當(dāng)鏈表達到一定長度的時候會轉(zhuǎn)換成紅黑樹骨坑，引入紅黑樹的好處是什么撼嗓？這個變換的閾值是多少，為什么是這個值欢唾？
當(dāng)元素put的時候且警，首先是要根據(jù)哈希函數(shù)和長度計算下標的，但即使哈希函數(shù)取得再好匈辱，也很難達到元素百分百均勻分布振湾，那么就有可能導(dǎo)致 HashMap 中有大量的元素都存放到同一個桶中時杀迹，這個桶下有一條長長的鏈表亡脸，這個時候 HashMap 就相當(dāng)于一個單鏈表，假如單鏈表有 n 個元素树酪，遍歷的時間復(fù)雜度就是 O(n)浅碾，完全失去了它的優(yōu)勢。
引入紅黑樹后续语，但鏈表長度大于8時垂谢，就會轉(zhuǎn)換成紅黑樹，若鏈表元素個數(shù)小于等于6時疮茄，樹結(jié)構(gòu)還原成鏈表滥朱。至于為什么是8根暑，我看到過兩個說法，一個是因為紅黑樹的平均查找長度是log(n)徙邻，長度為8的時候排嫌，平均查找長度為3，如果繼續(xù)使用鏈表缰犁，平均查找長度為8/2=4淳地，這才有轉(zhuǎn)換為樹的必要。鏈表長度如果是小于等于6帅容，6/2=3颇象，雖然速度也很快的，但是轉(zhuǎn)化為樹結(jié)構(gòu)和生成樹的時間并不會太短并徘。另一個說法是根據(jù)泊松分布遣钳，在負載因子默認為0.75的時候，單個hash槽內(nèi)元素個數(shù)為8的概率小于百萬分之一麦乞，所以將7作為一個分水嶺耍贾，等于7的時候不轉(zhuǎn)換，大于等于8的時候才進行轉(zhuǎn)換路幸，小于等于6的時候就化為鏈表荐开。兩種都有道理我覺得哪一種都是可以的。
當(dāng)桶滿了的時候简肴，HashMap會進行擴容resize晃听，它是何時并且如何擴容的呢？
當(dāng)桶的容量達到長度乘以負載因子的時候就會進行擴容砰识，默認的負載因子為0.75能扒。
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
首先，它會創(chuàng)建一個新的Entry空數(shù)組辫狼，長度是原數(shù)組的2倍初斑。然后遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組膨处。這里要進行ReHash的原因是我們知道下標的計算是跟長度有關(guān)的见秤，長度不一樣了，那么index計算的結(jié)果自然也不一樣真椿，因此需要重新Hash到新數(shù)組鹃答，rehash是一個比較耗時的過程。
接下來還是插入相關(guān)的問題突硝，新的Entry節(jié)點在插入鏈表的時候测摔，是怎么插入的？
這個問題我是在一篇博客上看到的，之前的確從未考慮過這個問題锋八。Java8之前是頭插法浙于，就是說新來的值會取代原有的值，原有的值就順推到鏈表中去挟纱，就像上面的例子一樣路媚，因為寫這個代碼的作者認為后來的值被查找的可能性更大一點，提升查找的效率樊销，在Java8之后整慎，都是所用尾部插入了。 由于在擴容的時候會存在條件競爭,如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了围苫，它們會同時試著調(diào)整大小裤园。用頭插法的話，假設(shè)原來鏈表是A指向B指向C剂府，新的鏈表可能出現(xiàn)B指向A但A同時也指向B拧揽。用尾插的方法擴容保持鏈表元素原油的順序，就不會出現(xiàn)這種鏈表成環(huán)的問題了腺占。
put的時候會先判斷是否碰撞淤袜，那么如何減少碰撞呢？
一般有兩個方法衰伯，一個是使用擾動函數(shù)铡羡，讓不同對象返回不同hashcode；一個是使用final對象意鲸，防止鍵值改變烦周，并采用合適的equeals方法和hashCode方法，減少碰撞的發(fā)生怎顾。
那么對于get方法因為比較簡單就不做太多詳細解釋读慎，其實就是根據(jù)key的hashcode算出元素在數(shù)組中的下標,之后遍歷Entry對象鏈表,直到找到元素為止。
SynchronizedMap
這里額外再提一個Map槐雾，也是解決HashMap多線程安全的一種方案夭委。那就是Collections.synchronizedMap(Map)。它會返回一個線程安全的SynchronizedMap的實例募强。它里面維護了一個排斥鎖mutex株灸。對于里面的public方法，使用了synchronized對mutex進行加鎖钻注。多線程環(huán)境下串行化執(zhí)行蚂且，效率低下。
上面就是一些關(guān)于HashMap的一些簡單的知識點幅恋，我這里整理的其實也不算太多但還是很實用的（我就知道這么多）。
HashTable
關(guān)于HashTable其實說不了太多泵肄，因為說實話反正我是從來沒用過捆交。都知道它線程安全淑翼，但它用的手段很簡單粗暴。涉及到修改的地方使用了synchronized修飾品追，以串行化方式運行玄括，效率比較低下。它和上面說的SynchronizedMap實現(xiàn)線程安全的方式很接近肉瓦，只是鎖的對象不一樣遭京。
ConcurrentHashMap
那么還是來談?wù)劻硪粋€還挺常見的ConcurrentHashMap,它現(xiàn)在的數(shù)據(jù)結(jié)構(gòu)和原來的也是不一樣的，早期也是數(shù)組+鏈表泞莉，現(xiàn)在是數(shù)組+鏈表+紅黑樹哪雕。
在Java8以前，由Segment數(shù)組鲫趁、HashEntry組成斯嚎，通過分段鎖Segment來實現(xiàn)線程安全，ConcurrentHashMap內(nèi)部維護了Segment內(nèi)部類挨厚，繼承了RetrantLock堡僻。它將鎖一段一段的存儲，給每一段數(shù)據(jù)分配一個鎖疫剃，也就是segment钉疫，當(dāng)一個線程訪問一個鎖時，其他線程也可以訪問其他segment的數(shù)據(jù)巢价，不會被阻塞陌选，默認分配16個segment。也就是理論上它的效率比HashTable提高了16倍蹄溉。而HashEntry跟HashMap差不多咨油，只是它用volatile修飾了數(shù)據(jù)的value還有下一個節(jié)點next。
到了Java8柒爵，它就不再是使用Segment分段鎖役电，而是使用了CAS+synchronized來保證線程安全。
synchronized鎖住當(dāng)前鏈表或者紅黑樹的首節(jié)點棉胀，這樣只要哈希不沖突法瑟，就不會出現(xiàn)并發(fā)問題。
/**
* Table initialization and resizing control. When negative, the
* table is being initialized or resized: -1 for initialization,
* else -(1 + the number of active resizing threads). Otherwise,
* when table is null, holds the initial table size to use upon
* creation, or 0 for default. After initialization, holds the
* next element count value upon which to resize the table.
*/
private transient volatile int sizeCtl;
ConcurrentHashMap和HashMap的參數(shù)差不多唁奢，但有些特有的霎挟，比如sizeCtl。它是哈希表初始化或擴容時的一個控制位標識量麻掸，負數(shù)代表正在初始化或正在擴容操作酥夭。同樣的，我們也看看它的put操作。
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 鍵值都不能為null
if (key == null || value == null) throw new NullPointerException();
//計算key的hash值
int hash = spread(key.hashCode());
int binCount = 0;
// 數(shù)組元素的更新熬北，使用CAS疙描，所以需要不斷失敗重試
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
// 初始化
tab = initTable();
//找到f，即鏈表或者紅黑樹的頭節(jié)點讶隐，沒有就添加
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//CAS添加起胰，失敗break
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 如果正在移動元素，就協(xié)助擴容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
//發(fā)生hash碰撞巫延，鎖定鏈表或者紅黑樹的頭節(jié)點f
V oldVal = null;
synchronized (f) {
// 判斷f是否時鏈表的頭節(jié)點
// fh就是頭節(jié)點的hash值
if (tabAt(tab, i) == f) {
if (fh >= 0) {
//如果是效五，初始化鏈表的計數(shù)器
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
//節(jié)點存在就更新
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
// 不更新就插入
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//頭節(jié)點是紅黑樹的頭，用紅黑樹的方式插入
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//鏈表長度達到了8炉峰，則轉(zhuǎn)換成樹結(jié)構(gòu)
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// ConcurrentHashMap的size+1
addCount(1L, binCount);
return null;
}
上面是整段代碼的解釋畏妖，總結(jié)一下就下面幾個步驟：
- 判斷Node[]數(shù)組是否初始化，沒有則進行初始化操作
- 通過hash定位數(shù)組的索引坐標讲冠，是否有Node節(jié)點瓜客，如果沒有則使用CAS進行添加（鏈表的頭節(jié)點），添加失敗則進入下次循環(huán)
- 檢查到內(nèi)部正在擴容竿开，就幫助它一塊擴容
- 如果頭節(jié)點f谱仪！=null,則使用synchronized鎖住f元素（鏈表/紅黑二叉樹的頭元素）
- 如果是Node（鏈表結(jié)構(gòu)）則進行鏈表的添加操作
- 如果是TreeNode結(jié)構(gòu)則執(zhí)行樹添加操作
- 判斷鏈表長度已經(jīng)達到臨界值8，這個8可以自己調(diào)整否彩，當(dāng)節(jié)點數(shù)超過這個值就把鏈表轉(zhuǎn)換為樹結(jié)構(gòu)
使用這種方式相對于Segment而言疯攒，鎖拆的更細。首先使用無鎖操作CAS插入節(jié)點列荔，失敗則循環(huán)重試敬尺。若頭節(jié)點存在，則嘗試獲取頭節(jié)點的同步鎖再進行操作贴浙。至于get操作也比較簡單砂吞，也是根據(jù)hashcode尋址，如果就在桶上就直接返回值崎溃，不是的話就按照鏈表或者紅黑樹的方式遍歷獲取值蜻直。
HashMap、HashTable以及ConcurrentHashMap的區(qū)別
大致講述了他們?nèi)齻€的基礎(chǔ)知識袁串，那么來總結(jié)下它們區(qū)別概而。這里做了個list大家可以看看。
- HashMap線程不安全囱修，數(shù)組+鏈表+紅黑樹
- HashTable線程安全赎瑰，鎖住整個對象，數(shù)組+鏈表
- ConcurrentHashMap線程安全破镰，CAS+同步鎖餐曼，數(shù)組+鏈表+紅黑樹
- HashMap的key压储，value均可為null，其他兩個不可以
- HashTable使用的是安全失敗機制（fail-safe）晋辆，這種機制會使你此次讀到的數(shù)據(jù)不一定是最新的數(shù)據(jù)渠脉。如果你使用null值宇整，就會使得其無法判斷對應(yīng)的key是不存在還是為空瓶佳，因為你無法再調(diào)用一次contain(key）來對key是否存在進行判斷，ConcurrentHashMap同理
- HashMap 的初始容量為：16鳞青，Hashtable 初始容量為：11霸饲，兩者的負載因子默認都是：0.75。
- 當(dāng)現(xiàn)有容量大于總?cè)萘?* 負載因子時臂拓，HashMap 擴容規(guī)則為當(dāng)前容量翻倍厚脉，Hashtable 擴容規(guī)則為當(dāng)前容量翻倍 + 1。
- HashMap 中的 Iterator 迭代器是 fail-fast 的胶惰，而 Hashtable 的 Enumerator 不是 fail-fast 的傻工。
- 快速失敗（fail—fast）是java集合中的一種機制孵滞， 在用迭代器遍歷一個集合對象時中捆，如果遍歷過程中對集合對象的內(nèi)容進行了修改（增加、刪除坊饶、修改）泄伪，則會拋出Concurrent Modification Exception。
以上就是關(guān)于Map相關(guān)的一些知識點匿级，里面很多引申的知識點我都沒有再往深里說蟋滴，比如里面使用到的紅黑樹數(shù)據(jù)結(jié)構(gòu)，volatile關(guān)鍵字痘绎，CAS等等津函，這個在后面會針對相應(yīng)的知識點再繼續(xù)梳理。
