前面通過分析HashMap的數(shù)據(jù)結(jié)構(gòu)發(fā)現(xiàn)漾稀，HashMap通過Hash表和鏈表的結(jié)構(gòu)構(gòu)成的一個數(shù)據(jù)結(jié)構(gòu)设江，當(dāng)有兩個hash值相同的數(shù)據(jù)需要并發(fā)插入（刪除）時哎垦，可能會造成數(shù)據(jù)丟失的情況乙嘀。那么HashTable的存在就是為了保證Map的線程安全的，但是熙揍，當(dāng)Hashtable操作數(shù)據(jù)時，是將整個table都加入Sync氏涩，造成全部數(shù)據(jù)同時lock届囚，效率比較低。
!
那么ConcurrentHashMap在并發(fā)方面對數(shù)據(jù)結(jié)構(gòu)做了微調(diào)是尖，同時結(jié)合了并發(fā)操作進行了一些算法改進意系。首先看一下ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)：
那么可以看出，他在HashTable的table結(jié)構(gòu)上再加了一層segment饺汹，ConcurrentHashMap就是通過加入多一層的segment蛔添，通過鎖去獨立控制每一個segment，來優(yōu)化數(shù)據(jù)不用同時lock首繁。
看一下segment的定義：
final Segment<K,V>[] segments;
static final class Segment<K,V> extends ReentrantLock implements Serializable{
... ...
}
其中Segment<K,V>繼承了ReentrantLock（重入鎖作郭，后續(xù)開文詳細分析），那么每一個segment都有一個單獨的lock進行管理和分配弦疮。
Segment<K,V>實現(xiàn)的是一個類似HashMap的結(jié)構(gòu)夹攒，如上圖可以看出，其實ConcurrentHashMap就是定義了一層Segment來包含每個單獨的HashMap胁塞，也可以膚淺的認為咏尝，ConcurrentHashMap就是由多個HashTable構(gòu)成的（每個HashTable獨立控制自己的鎖）压语。
那么，數(shù)據(jù)通過怎么樣落入到不同的segment中呢编检？這里同樣是使用hash算法進行segment的選擇：
private int hash(Object k) {
int h = hashSeed;
if ((0 != h) && (k instanceof String)) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}
一眼看上去胎食，好長，不就一個hash算法么允懂，為什么會這么復(fù)雜厕怜，注釋中還涉及到了 Wang/Jenkins的hash算法。如果不詳細探討這個hash算法的數(shù)據(jù)理論的話蕾总，可以簡單的這么理解：如果使用一般的hash算法粥航，有可能造成很多的值同時落到一個segment中，那么最終這些數(shù)據(jù)都公用這個segment中的lock生百，那么多一層segments的結(jié)構(gòu)就起不到獨立鎖的目的递雀；所以這個算法就是用來調(diào)和讓每個segment都能落入接近數(shù)量的數(shù)據(jù)，讓segments層的lock真正獨立起來蚀浆。
我們來看一下ConcurrentHashMap是怎么實現(xiàn)put方法的：
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
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);
}
可以看到缀程，他是通過hash算法先找到對應(yīng)的segment，然后交由這個segement去處理put方法市俊，看一下segment的put方法：
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
... ...
}
這里先通過ReentrantLock獲取鎖杨凑。然后，通過hash值計算秕衙，得到table的bucket中的鏈表 蠢甲，在獲取鏈表的第一個元素：
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
然后，看一下如果這個bucket為空的即鏈表為空的情況：
setEntryAt(tab, index, node);
將此對象設(shè)為header据忘，并將header放入table中鹦牛，如果bucket不為空時：
e = e.next;
類似hashmap的結(jié)構(gòu)，把table的header換成當(dāng)前勇吊，并將當(dāng)前的next指針指向原來的header曼追。
ConcurrentHashMap暫時分析到這里，后續(xù)分析并發(fā)編程再重新回來分析這里的并發(fā)編程的技術(shù)汉规。
