ConcurrentHashMap是HashMap的線程安全版本，使用了分段加鎖的方案，在高並發時有比較好的性能。
本文分析JDK1.7中ConcurrentHashMap的實現。
HashMap不是線程安全的，要實現線程安全除非加鎖，但這樣性能很低。ConcurrentHashMap把整個HashMap數組分成了若干個Segment，每個Segment裡有一個數組。添加一個Key時，需要先根據hash值計算出其所在Segment，然後再根據hash值計算出在該Segment中的位置。Segment繼承自ReentrantLock，每個Segment就是一個鎖。在多線程的情況下，就減少了鎖競爭，提升了性能。
ConcurrentHashMap存儲結構如下圖所示：
下面我們來分析源碼，看數據是怎麼存儲的。
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
int sshift = 0;
int ssize = 1;
//concurrencyLevel為並發級別，這一步就是計算出大於concurrencyLevel的最小的2的N次方
//為什麼不用HashMap中的Integer.highestOneBit((number - 1) << 1)來計算這個值
//我的理解是concurrencyLevel一般都比較小（默認為16），采用這種計算方法效率更高。
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
//後面根據hash計算segment位置時需要用到
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//計算每一個segment中table的length
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// create segments and segments[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
和HashMap最大的不同就是多了Segment的初始化。
Segment的Size也初始化為2的N次方，這為後面的Map整體resize以及確定一個hash值所在Segment都提供簡便方法。
每個Segment中的table同HashMap中table一樣，接著來看PUT時怎麼計算Segment的位置。
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
//取得Key的Segment位置
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
segmentShift：在構造函數中計算出來的，假設concurrencyLevel為16，segmentShift=28(32-4)
segmentMask：15(16-1)
可見求Key所在Segment的算法和HashMap中求Key所在table中的位置一樣，都是 hash & (length-1)。
所以這裡Segment的length也必須是2的N次方。
hash >>> segmentShift是為了使用hash的高位進行與運算。
s.put方法，就是把Key放到Segment中table的響應位置，它的算法和HashMap中類似，只是加入了鎖。
Put一個Key時有下面這段代碼：
void createEntry(int hash, K key, V value, int bucketIndex) {
//1.取得鏈表
Entry<K,V> e = table[bucketIndex];
//2.將新Key設置為鏈表的第一個
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
假設有兩個線程A、B，同時進行第1步，它們獲取到的e是同一個，如：x,y,z
然後線程A運行到第2步，為e添加了一個新元素a，並賦值給table[bucketIndex]，此時table[bucketIndex]為：a,x,y,z
而後線程B運行到第2步，為e添加了一個新元素b，並賦值給table[bucketIndex]，此時table[bucketIndex]為：b,x,y,z
所以這種情況下就會有問題，這只是其中的一個例子，所以HashMap是非線程安全的。
Put一個Key到Table時，使用如下代碼：
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
......
} finally {
unlock();
}
return oldValue;
}
可以看到put時，加入了Lock，這就保證了線程的安全性。
查看ConcurrentHashMap源代碼可以發現，ConcurrentHashMap的remove、replace等有可能引起線程安全問題的地方都加了Lock。
ConcurrentHashMap的Get方法並不是完全線程安全，因為Get時沒有加鎖，但JDK用了很多volatile類型變量來保證在大多數情況下的線程安全。
ConcurrentHashMap在絕大多數情況下是線程安全的，在多線程情況下請使用ConcurrentHashMap。
