1 Map并發(fā)集合
1.1 ConcurrentMap
ConcurrentMap饺谬，它是一個(gè)接口辟癌，是一個(gè)能夠支持并發(fā)訪問(wèn)的java.util.map集合；
在原有java.util.map接口基礎(chǔ)上又新提供了4種方法荷鼠，進(jìn)一步擴(kuò)展了原有Map的功能：
public interface ConcurrentMap<K, V> extends Map<K, V> {
//插入元素
V putIfAbsent(K key, V value);
//移除元素
boolean remove(Object key, Object value);
//替換元素
boolean replace(K key, V oldValue, V newValue);
//替換元素
V replace(K key, V value);
}
putIfAbsent：與原有put方法不同的是扼仲，putIfAbsent方法中如果插入的key相同脏里，則不替換原有的value值浦箱；
remove：與原有remove方法不同的是佛猛，新remove方法中增加了對(duì)value的判斷缰盏，如果要?jiǎng)h除的key--value不能與Map中原有的key--value對(duì)應(yīng)上涌萤，則不會(huì)刪除該元素;
replace(K,V,V)：增加了對(duì)value值的判斷，如果key--oldValue能與Map中原有的key--value對(duì)應(yīng)上乳规，才進(jìn)行替換操作形葬；
replace(K,V)：與上面的replace不同的是，此replace不會(huì)對(duì)Map中原有的key--value進(jìn)行比較暮的，如果key存在則直接替換笙以；
其實(shí)，對(duì)于ConcurrentMap來(lái)說(shuō)冻辩，我們更關(guān)注Map本身的操作猖腕，在并發(fā)情況下是如何實(shí)現(xiàn)數(shù)據(jù)安全的。在java.util.concurrent包中恨闪，ConcurrentMap的實(shí)現(xiàn)類主要以ConcurrentHashMap為主倘感。接下來(lái)，我們具體來(lái)看下咙咽。
1.2 ConcurrentHashMap
ConcurrentHashMap是一個(gè)線程安全老玛，并且是一個(gè)高效的HashMap。
但是，如果從線程安全的角度來(lái)說(shuō)蜡豹，HashTable已經(jīng)是一個(gè)線程安全的HashMap麸粮，那推出ConcurrentHashMap的意義又是什么呢？
說(shuō)起ConcurrentHashMap镜廉，就不得不先提及下HashMap在線程不安全的表現(xiàn)弄诲，以及HashTable的效率！
- HashMap
關(guān)于HashMap的講解娇唯，在此前的文章中已經(jīng)說(shuō)過(guò)了齐遵，本篇不在做過(guò)多的描述，有興趣的朋友可以來(lái)這里看下--HashMap塔插。
在此節(jié)中梗摇，我們主要來(lái)說(shuō)下，在多線程情況下HashMap的表現(xiàn)佑淀？
HashMap中添加元素的源碼：（基于JDK1.7.0_45）
public V put(K key, V value) {
留美。。伸刃。忽略
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
。逢倍。捧颅。忽略
createEntry(hash, key, value, bucketIndex);
}
//向鏈表頭部插入元素：在數(shù)組的某一個(gè)角標(biāo)下形成鏈表結(jié)構(gòu)；
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
在多線程情況下较雕，同時(shí)A碉哑、B兩個(gè)線程走到createEntry()方法中，并且這兩個(gè)線程中插入的元素hash值相同亮蒋，bucketIndex值也相同扣典，那么無(wú)論A線程先執(zhí)行，還是B線程先被執(zhí)行慎玖，最終都會(huì)2個(gè)元素先后向鏈表的頭部插入贮尖，導(dǎo)致互相覆蓋，致使其中1個(gè)線程中的數(shù)據(jù)丟失趁怔。這樣就造成了HashMap的線程不安全湿硝，數(shù)據(jù)的不一致；
更要命的是润努，HashMap在多線程情況下還會(huì)出現(xiàn)死循環(huán)的可能关斜，造成CPU占用率升高，導(dǎo)致系統(tǒng)卡死铺浇。
舉個(gè)簡(jiǎn)單的例子：
public class ConcurrentHashMapTest {
public static void main(String[] agrs) throws InterruptedException {
final HashMap<String,String> map = new HashMap<String,String>();
Thread t = new Thread(new Runnable(){
public void run(){
for(int x=0;x<10000;x++){
Thread tt = new Thread(new Runnable(){
public void run(){
map.put(UUID.randomUUID().toString(),"");
}
});
tt.start();
System.out.println(tt.getName());
}
}
});
t.start();
t.join();
}
}
在上面的例子中痢畜，我們利用for循環(huán)，啟動(dòng)了10000個(gè)線程，每個(gè)線程都向共享變量中添加一個(gè)元素丁稀。
測(cè)試結(jié)果：通過(guò)使用JDK自帶的jconsole工具吼拥，可以看到HashMap內(nèi)部形成了死循環(huán)，并且主要集中在兩處代碼上二驰。
那么扔罪，是什么原因造成了死循環(huán)？
HashMap--put()494行：（基于JDK1.7.0_45）
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {------**for循環(huán)494行**
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
HashMap--transfer()601行：（基于JDK1.7.0_45）
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}-----**while循環(huán)601行**
}
}
通過(guò)查看代碼桶雀，可以看出矿酵，死循環(huán)的產(chǎn)生：主要因?yàn)樵诒闅v數(shù)組角標(biāo)下的鏈表時(shí)，沒(méi)有了為null的元素矗积，單向鏈表變成了循環(huán)鏈表全肮，頭尾相連了。
以上兩點(diǎn)棘捣，就是HashMap在多線程情況下的表現(xiàn)辜腺。
- HashTable
說(shuō)完了HashMap的線程不安全，接下來(lái)說(shuō)下HashTable的效率ＵЭ帧评疗！
HashTable與HashMap的結(jié)構(gòu)一致，都是哈希表實(shí)現(xiàn)茵烈。
與HashMap不同的是百匆，在HashTable中，所有的方法都加上了synchronized鎖呜投，用鎖來(lái)實(shí)現(xiàn)線程的安全性加匈。由于synchronized鎖加在了HashTable的每一個(gè)方法上，所以這個(gè)鎖就是HashTable本身--this仑荐。那么雕拼，可想而知HashTable的效率是如何，安全是保證了粘招，但是效率卻損失了啥寇。
無(wú)論執(zhí)行哪個(gè)方法，整個(gè)哈希表都會(huì)被鎖住男图，只有其中一個(gè)線程執(zhí)行完畢示姿，釋放所，下一個(gè)線程才會(huì)執(zhí)行逊笆。無(wú)論你是調(diào)用get方法栈戳，還是put方法皆是如此；
HashTable部分源碼：（基于JDK1.7.0_45）
public class Hashtable<K,V> extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
public synchronized int size() {...}
public synchronized boolean isEmpty() {...}
public synchronized V get(Object key) {...}
public synchronized V put(K key, V value) {...}
}
通過(guò)上述代碼难裆，可以清晰看出子檀，在HashTable中的主要操作方法上都加了synchronized鎖以來(lái)保證線程安全镊掖。
說(shuō)完了HashMap和HashTable，下面我們就重點(diǎn)介紹下ConcurrentHashMap褂痰，看看ConcurrentHashMap是如何來(lái)解決上述的兩個(gè)問(wèn)題的亩进！
1.3 ConcurrentHashMap結(jié)構(gòu)
在說(shuō)到ConcurrentHashMap源碼之前，我們首先來(lái)了解下ConcurrentHashMap的整體結(jié)構(gòu)缩歪，這樣有利于我們快速理解源碼归薛。
不知道，大家還是否記得HashMap的整體結(jié)構(gòu)呢匪蝙？如果忘記的話主籍，我們就在此進(jìn)行回顧下！
HashMap底層使用數(shù)組和鏈表逛球，實(shí)現(xiàn)哈希表結(jié)構(gòu)千元。插入的元素通過(guò)散列的形式分布到數(shù)組的各個(gè)角標(biāo)下；當(dāng)有重復(fù)的散列值時(shí)颤绕，便將新增的元素插入在鏈表頭部幸海，使其形成鏈表結(jié)構(gòu)，依次向后排列奥务。
下面是物独，ConcurrentHashMap的結(jié)構(gòu)：
與HashMap不同的是，ConcurrentHashMap中多了一層數(shù)組結(jié)構(gòu)氯葬，由Segment和HashEntry兩個(gè)數(shù)組組成议纯。其中Segment起到了加鎖同步的作用，而HashEntry則起到了存儲(chǔ)K.V鍵值對(duì)的作用溢谤。
在ConcurrentHashMap中，每一個(gè)ConcurrentHashMap都包含了一個(gè)Segment數(shù)組憨攒，在Segment數(shù)組中每一個(gè)Segment對(duì)象則又包含了一個(gè)HashEntry數(shù)組世杀，而在HashEntry數(shù)組中，每一個(gè)HashEntry對(duì)象保存K-V數(shù)據(jù)的同時(shí)又形成了鏈表結(jié)構(gòu)肝集，此時(shí)與HashMap結(jié)構(gòu)相同瞻坝。
在多線程中，每一個(gè)Segment對(duì)象守護(hù)了一個(gè)HashEntry數(shù)組杏瞻，當(dāng)對(duì)ConcurrentHashMap中的元素修改時(shí)所刀，在獲取到對(duì)應(yīng)的Segment數(shù)組角標(biāo)后，都會(huì)對(duì)此Segment對(duì)象加鎖捞挥，之后再去操作后面的HashEntry元素浮创，這樣每一個(gè)Segment對(duì)象下，都形成了一個(gè)小小的HashMap砌函，在保證數(shù)據(jù)安全性的同時(shí)斩披，又提高了同步的效率溜族。只要不是操作同一個(gè)Segment對(duì)象的話，就不會(huì)出現(xiàn)線程等待的問(wèn)題垦沉！
