1.什么是ConcurrentHashMap
ConcurrentHashMap是java.util.concurrent包下AbstractMap的一個子類噪裕，此類遵守與Hashtable相同的功能規(guī)范，并且包括對應于Hashtable的每個方法的方法版本股毫。
2.ConcurrentHashMap的設計思路
在JDK1.7中膳音，ConcurrentHashMap是由Segment數(shù)組結構和HashEntry數(shù)組結構組成。Segment是一種可重入鎖ReentrantLock铃诬，在ConcurrentHashMap里扮演鎖的角色祭陷，HashEntry則用于存儲鍵值對數(shù)據(jù)。一個ConcurrentHashMap里包含一個Segment數(shù)組趣席，Segment的結構和HashMap類似兵志，是一種數(shù)組和鏈表結構， 一個Segment里包含一個HashEntry數(shù)組宣肚，每個HashEntry是一個鏈表結構的元素想罕， 每個Segment守護者一個HashEntry數(shù)組里的元素,當對HashEntry數(shù)組的數(shù)據(jù)進行修改時，必須首先獲得它對應的Segment鎖霉涨。
在JDK1.8中按价，取消了Segment分段鎖的數(shù)據(jù)結構惭适，取而代之的是數(shù)組+鏈表（紅黑樹）的結構。對每個數(shù)組元素加鎖楼镐。
3.ConcurrentHashMap的方法
Get方法：
//JDK1.7 get方法
public V get(Object key) {
Segment<K,V> s;
HashEntry<K,V>[] tab;
int h = hash(key); //找出對應的segment的位置
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) { //使用Unsafe獲取對應的Segmen
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) { //找出對應的HashEntry癞志，從頭開始遍歷
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
1.為輸入的Key做Hash運算，得到hash值框产。
2.通過hash值今阳，定位到對應的Segment對象。
3.再次通過hash值茅信，定位到Segment當中數(shù)組的具體位置盾舌。
//JDK1.8 get方法
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
1.首先定位到table[]中的i。
2.若table[i]存在蘸鲸，則繼續(xù)查找妖谴。
3.首先比較鏈表頭部，如果是則返回酌摇。
4.然后如果為紅黑樹膝舅，查找樹。
5.最后再循環(huán)鏈表查找窑多。
Put方法：
//JDK1.7 put方法
//將一個HashEntry放入到該Segment中仍稀，使用自旋機制，減少了加鎖的可能性
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value); //如果加鎖失敗埂息，則調用該方法
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash; //同hashMap相同的哈希定位方式
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
//若不為null技潘，則持續(xù)查找，知道找到key和hash值相同的節(jié)點千康，將其value更新
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else { //若頭結點為null
if (node != null) //在遍歷key對應節(jié)點鏈時沒有找到相應的節(jié)點
node.setNext(first);
//當前修改并不需要讓其他線程知道享幽，在鎖退出時修改自然會
//更新到內存中,可提升性能
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node); //如果超過閾值，則進行rehash操作
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
1.為輸入的Key做Hash運算拾弃，得到hash值值桩。
2.通過hash值，定位到對應的Segment對象豪椿。
3.獲取可重入鎖奔坟。
4.再次通過hash值，定位到Segment當中數(shù)組的具體位置搭盾。
5.插入或覆蓋HashEntry對象咳秉。
6.釋放鎖。
//JDK1.8 put方法
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
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;
}
}
}
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) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
1.參數(shù)校驗增蹭。
2.若table[]未創(chuàng)建滴某，則初始化磅摹。
3.當table[i]后面無節(jié)點時滋迈，直接創(chuàng)建Node（無鎖操作）霎奢。
4.如果當前正在擴容，則幫助擴容并返回最新table[]饼灿。
5.然后在鏈表或者紅黑樹中追加節(jié)點幕侠。
6.最后還回去判斷是否到達閥值，如到達變?yōu)榧t黑樹結構碍彭。
Size方法：
//JDK1.7 size方法晤硕，求出所有的HashEntry的數(shù)目
public int size() {
final Segment<K,V>[] segments = this.segments;
int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {
for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
}
1.遍歷所有的Segment。
2.把Segment的元素數(shù)量累加起來庇忌。
3.把Segment的修改次數(shù)累加起來舞箍。
4.判斷所有Segment的總修改次數(shù)是否大于上一次的總修改次數(shù)。如果大于皆疹，說明統(tǒng)計過程中有修改疏橄，重新統(tǒng)計，嘗試次數(shù)+1略就；如果不是捎迫。說明沒有修改，統(tǒng)計結束表牢。
5.如果嘗試次數(shù)超過閾值窄绒，則對每一個Segment加鎖，再重新統(tǒng)計崔兴。
6.再次判斷所有Segment的總修改次數(shù)是否大于上一次的總修改次數(shù)彰导。由于已經加鎖，次數(shù)一定和上次相等敲茄。
7.釋放鎖螺戳，統(tǒng)計結束。
//JDK1.8 size方法
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
// 1.8加入的API
public long mappingCount() {
long n = sumCount();
return (n < 0L) ? 0L : n; // ignore transient negative values
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
1.每個table[i]都有一個CounterCell與之對應折汞。
2.把所有的table[i] 加在一起倔幼。
4.ConcurrentHashMap和HashMap以及HashTable的區(qū)別
HashMap： 線程不安全，在多線程情況下爽待，HashMap在做put操作時损同，會在擴容時形成環(huán)狀鏈表，這樣在進行get操作時會引起死循環(huán)鸟款；HashMap的key值和value值都可以是null;
HashTable： HashTable和HashMap的實現(xiàn)原理幾乎一樣膏燃，HashTable是線程安全的，但是實現(xiàn)原理是在整個方法上加鎖何什，這樣導致性能非常差组哩；HashTable不允許key和value為null；
ConcurrentHashMap：所采用的"分段鎖"思想，不會存在鎖競爭問題伶贰，可以提高效率
5.總結
ConcurrentHashMap是一種線程安全且高效的哈希表的解決方案蛛砰，相比HashTable的全表鎖在性能上的提升非常大。
6.引用
第一次寫博客黍衙，找了很多好的博客泥畅，跟著博客去查找jdk源碼，可以更快的理解其中的含義琅翻。
參考：
http://tool.oschina.net/apidocs/apidoc?api=jdk-zh
https://blog.csdn.net/fouy_yun/article/details/77816587
http://www.importnew.com/22007.html
http://www.sohu.com/a/205451532_684445
http://www.cnblogs.com/yydcdut/p/3959815.html
