為什么要使用 ConcurrentHashMap
因為 HashMap 是非線程安全的
在多線程情況下，HashMap 的 put 操作會形成死循環。 原因：Entry 鏈表形成環形結構。
下面具體說明形成環形結構的過程：
正常的 Rehash 過程
并發的 Rehash
rehash 關鍵代碼：
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; } }}（1）線程二執行完成
注意：因為線程一的 e 指向了 key(3)，而 next 指向了 key(7)，其在線程二 rehash 后，指向了線程二重組后的鏈表。
（2）接下來線程一被調度回來執行
（3）線程一接著工作。把 key(7)摘下來，放到 newTable[i] 的第一個，然后把e和next往下移。
（4）環形鏈表出現 e.next = newTable[i] 導致 key(3).next 指向了 key(7)。注意：此時的key(7).next 已經指向了key(3)， 環形鏈表就這樣出現了。
因為 HashTable 效率低下
HashTable 對所有操作都做了同步操作，在線程競爭激烈的情況下因過多的阻塞導致效率低下。
ConcurrentHashMap 鎖分段技術提高并發效率
ConcurrentHashMap 實現了線程安全，因此解決了 HashMap 的不足；同時它不像 HashTable 一樣對所有的操作都加同步，而是使用鎖分段技術，容器中有多把鎖，每一把鎖管理著一段數據，當一個線程占用鎖訪問其數據時，其他段的數據也能被其他線程訪問到。極大的提升并發效率。在 HashMap 的介紹中我們知道其結構如下：
而 ConcurrentHashMap 的結構如下：
HashMap 是一個數組（數組+鏈表）結構，數組的每個元素都是一個鏈表的表頭；ConcurrentHashMap 是多個數組（數組+鏈表）結構，每個數組歸一個 Segment 管理，因此 ConcurrentHashMap 也可以看做是一個 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; while (ssize < concurrencyLevel) { ++sshift; ssize <<= 1; } this.segmentShift = 32 - sshift; this.segmentMask = ssize - 1; if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; 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;}先是根據 concurrentLevel 來 new 出 Segment，這里 Segment 的數量是不大于 concurrentLevel 的最大的 2 的指數（ssize），這樣的好處是方便采用移位操作來進行 hash，加快 hash 的過程；接下來就是根據 intialCapacity 確定 Segment 的容量的大小，每一個 Segment 的容量大小也是 2 的指數，同樣使為了加快 hash 的過程。get 操作
public V get(Object key) { Segment<K,V> s; // manually integrate access methods to reduce overhead HashEntry<K,V>[] tab; int h = hash(key); long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); e != null; e = e.next) { K k; if ((k = e.key) == key || (e.hash == h && key.equals(k))) return e.value; } } return null;}經過一次 hash 定位到 Segment 并得到 segment 的 HashEntry 數組。定位其在 HashEntry 數組中的哪個位置得到鏈表頭；遍歷鏈表根據 key 得到 valueget 方法并沒有加鎖，原因是它只讀不寫，并且將要使用的共享變量都定義成 volatile 類型，比如 HashEntry 的 value。
put 操作
首先定位到 Segment；然后在 Segment 里進行插入操作（加鎖）： 第一步判斷是否需要對 Segment 里的 HashEntry 數組進行擴容；第二步定位添加元素的位置，然后將其放在HashEntry數組里。Q：是否需要擴容
A：若插入元素前 Segment 里的 HashEntry 數組長度超過閾值，則對數組進行擴容。 值得一提的是，Segment 的擴容判斷比HashMap更恰當，因為 HashMap 是在插入元素后判斷元素是否已經到達容量的，如果到達了就進行擴容，但是很有可能擴容之后沒有新元素插入，這時HashMap就進行了一次無效的擴容。
Q：如何擴容
A：在擴容的時候，首先會創建一個容量是原來容量兩倍的數組，然后將原數組里的元素進行再散列后插入到新的數組里。
size 操作
代碼：
public int size() { // Try a few times to get accurate count. On failure due to // continuous async changes in table, resort to locking. 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;}Q：是不是直接把所有 Segment 的 count 相加就可以得到整個ConcurrentHashMap大小了呢？ A：不是的。
雖然相加時可以獲取每個Segment的count的最新值，但是可能累加前使用的count發生了變化，那么統計結果就不準了。所以，最安全的做法是在統計 size 的時候把所有 Segment 的 put、remove 和 clean 方法全部鎖住，但是這種做法顯然非常低效。巧妙的方式（如上述代碼）： 先嘗試 2 次通過不鎖住 Segment 的方式來統計，如果統計的過程中，容器的 count 發生了變化，則再采用加鎖的方式來統計。那么如何判斷在統計的時候容器是否發生了變化呢？使用 modCount 變量，所有的 update 操作都會將變量 modCount 進行加 1。remove 操作
先進行定位得到 segment；然后在 segment 中進行 remove（需加鎖） 定位到 segment 中的 HashEntry；遍歷 HashEntry 鏈表找到并刪除；
