• Java5.0以后 在java.util.concurrent包中提供了多種并發(fā)容器類來改進同步容器的性能。

• ConcurrentHashMap同步容器類是Java5新增的一個線程安全的Hash表。對于多線程的操作，介于HashMap和HashTable之間。內(nèi)部通過采用將鎖進行細粒度化代替HashTable的獨占鎖，使得多個線程能夠同時操作哈希表，提高性能。

• 此包還提供了設(shè)計用于多線程上下文中的 Collection 實現(xiàn)： ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListSet、 CopyOnWriteArrayList 和 CopyOnWriteArraySet。
  當(dāng)期望許多線程訪問一個給 定 collection 時，ConcurrentHashMap 通常優(yōu)于同步的 HashMap，
  ConcurrentSkipListMap 通常優(yōu)于同步的 TreeMap。
  當(dāng)期望的讀數(shù)和遍歷遠遠 大于列表的更新時,CopyOnWriteArrayList 優(yōu)于同步的 ArrayList。

Collectons.syn***(new HashMap()) 或 HashTable

concurrentLevel 鎖分段級別 默認16段
每一段都是Segment，后面跟著數(shù)組+鏈表
優(yōu)點： 每個段都是獨立的鎖，支持多個線程同時訪問，多個線程互不影響。

示意圖

1.8 分段鎖 改成CAS 無鎖算法。
CAS不阻塞，不存在上下文切換問題。

//默認初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
 
//默認加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
//默認并發(fā)級別
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
 
//集合最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
 
//分段鎖的最小數(shù)量
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
 
//分段鎖的最大數(shù)量
static final int MAX_SEGMENTS = 1 << 16;
 
//加鎖前的重試次數(shù)
static final int RETRIES_BEFORE_LOCK = 2;
 
//分段鎖的掩碼值
final int segmentMask;
 
//分段鎖的移位值
final int segmentShift;
 
//分段鎖數(shù)組
final Segment<K,V>[] segments;

分段鎖的內(nèi)部結(jié)構(gòu)

//分段鎖
static final class Segment<K,V> extends ReentrantLock implements Serializable {
  //自旋最大次數(shù)
  static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
  //哈希表
  transient volatile HashEntry<K,V>[] table;
  //元素總數(shù)
  transient int count;
  //修改次數(shù)
  transient int modCount;
  //元素閥值
  transient int threshold;
  //加載因子
  final float loadFactor;
  //省略以下內(nèi)容
  ...
}

Segment是ConcurrentHashMap的靜態(tài)內(nèi)部類，可以看到它繼承自ReentrantLock，因此它在本質(zhì)上是一個鎖。它在內(nèi)部持有一個HashEntry數(shù)組(哈希表)，并且保證所有對該數(shù)組的增刪改查方法都是線程安全的，具體是怎樣實現(xiàn)的后面會講到。所有對ConcurrentHashMap的增刪改查操作都可以委托Segment來進行，因此ConcurrentHashMap能夠保證在多線程環(huán)境下是安全的。又因為不同的Segment是不同的鎖，所以多線程可以同時操作不同的Segment，也就意味著多線程可以同時操作ConcurrentHashMap，這樣就能避免HashTable的缺陷，從而極大的提高性能。

初始化操作

//核心構(gòu)造器
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
  if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) {
    throw new IllegalArgumentException();
  }
  //確保并發(fā)級別不大于限定值
  if (concurrencyLevel > MAX_SEGMENTS) {
    concurrencyLevel = MAX_SEGMENTS;
  }
  int sshift = 0;
  int ssize = 1;
  //保證ssize為2的冪, 且是最接近的大于等于并發(fā)級別的數(shù)
  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;
  //分段鎖容量總和不小于初始總?cè)萘?  if (c * ssize < initialCapacity) {
    ++c;
  }
  int cap = MIN_SEGMENT_TABLE_CAPACITY;
  //保證cap為2的冪, 且是最接近的大于等于c的數(shù)
  while (cap < c) {
    cap <<= 1;
  }
  //新建一個Segment對象模版
  Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor), (HashEntry<K,V>[])new HashEntry[cap]);
  //新建指定大小的分段鎖數(shù)組
  Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
  //使用UnSafe給數(shù)組第0個元素賦值
  UNSAFE.putOrderedObject(ss, SBASE, s0);
  this.segments = ss;
}

ConcurrentHashMap有多個構(gòu)造器，但是上面貼出的是它的核心構(gòu)造器，其他構(gòu)造器都通過調(diào)用它來完成初始化。核心構(gòu)造器需要傳入三個參數(shù)，分別是初始容量，加載因子和并發(fā)級別。在前面介紹成員變量時我們可以知道默認的初始容量為16，加載因子為0.75f，并發(fā)級別為16。現(xiàn)在我們看到核心構(gòu)造器的代碼，首先是通過傳入的concurrencyLevel來計算出ssize，ssize是Segment數(shù)組的長度，它必須保證是2的冪，這樣就可以通過hash&ssize-1來計算分段鎖在數(shù)組中的下標(biāo)。由于傳入的concurrencyLevel不能保證是2的冪，所以不能直接用它來當(dāng)作Segment數(shù)組的長度，因此我們要找到一個最接近concurrencyLevel的2的冪，用它來作為數(shù)組的長度。假如現(xiàn)在傳入的concurrencyLevel=15，通過上面代碼可以計算出ssize=16，sshift=4。接下來立馬可以算出segmentShift=16，segmentMask=15。注意這里的segmentShift是分段鎖的移位值，segmentMask是分段鎖的掩碼值，這兩個值是用來計算分段鎖在數(shù)組中的下標(biāo)，在下面我們會講到。在算出分段鎖的個數(shù)ssize之后，就可以根據(jù)傳入的總?cè)萘縼碛嬎忝總€分段鎖的容量，它的值c = initialCapacity / ssize。分段鎖的容量也就是HashEntry數(shù)組的長度，同樣也必須保證是2的冪，而上面算出的c的值不能保證這一點，所以不能直接用c作為HashEntry數(shù)組的長度，需要另外找到一個最接近c的2的冪，將這個值賦給cap，然后用cap來作為HashEntry數(shù)組的長度?，F(xiàn)在我們有了ssize和cap，就可以新建分段鎖數(shù)組Segment[]和元素數(shù)組HashEntry[]了。注意，與JDK1.6不同是的，在JDK1.7中只新建了Segment數(shù)組，并沒有對它初始化，初始化Segment的操作留到了插入操作時進行。

元素

//根據(jù)哈希碼獲取分段鎖
@SuppressWarnings("unchecked")
private Segment<K,V> segmentForHash(int h) {
  long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
}
 
//根據(jù)哈希碼獲取元素
@SuppressWarnings("unchecked")
static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
  HashEntry<K,V>[] tab;
  return (seg == null || (tab = seg.table) == null) ? null :
  (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
}

public V get(Object key) {
    int hash = hash(key); // throws NullPointerException if key null
    return segmentFor(hash).get(key, hash);
}

• 通過哈希碼計算分段鎖在數(shù)組中的下標(biāo)：(h >>> segmentShift) & segmentMask。
• 通過哈希碼計算元素在數(shù)組中的下標(biāo)：(tab.length - 1) & h。

hashMap
參考連接