ConcurrentHashMap

• Java5.0以后 在java.util.concurrent包中提供了多种并发容器类来改进同步容器的性能。

• ConcurrentHashMap同步容器类是Java5新增的一个线程安全的Hash表。对于多线程的操作，介于HashMap和HashTable之间。内部通过采用将锁进行细粒度化代替HashTable的独占锁，使得多个线程能够同时操作哈希表，提高性能。

• 此包还提供了设计用于多线程上下文中的 Collection 实现： ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListSet、 CopyOnWriteArrayList 和 CopyOnWriteArraySet。
  当期望许多线程访问一个给 定 collection 时，ConcurrentHashMap 通常优于同步的 HashMap，
  ConcurrentSkipListMap 通常优于同步的 TreeMap。
  当期望的读数和遍历远远 大于列表的更新时,CopyOnWriteArrayList 优于同步的 ArrayList。

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

concurrentLevel 锁分段级别 默认16段
每一段都是Segment，后面跟着数组+链表
优点： 每个段都是独立的锁，支持多个线程同时访问，多个线程互不影响。

示意图

1.8 分段锁 改成CAS 无锁算法。
CAS不阻塞，不存在上下文切换问题。

//默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
 
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
//默认并发级别
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
 
//集合最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
 
//分段锁的最小数量
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
 
//分段锁的最大数量
static final int MAX_SEGMENTS = 1 << 16;
 
//加锁前的重试次数
static final int RETRIES_BEFORE_LOCK = 2;
 
//分段锁的掩码值
final int segmentMask;
 
//分段锁的移位值
final int segmentShift;
 
//分段锁数组
final Segment<K,V>[] segments;

分段锁的内部结构

//分段锁
static final class Segment<K,V> extends ReentrantLock implements Serializable {
  //自旋最大次数
  static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
  //哈希表
  transient volatile HashEntry<K,V>[] table;
  //元素总数
  transient int count;
  //修改次数
  transient int modCount;
  //元素阀值
  transient int threshold;
  //加载因子
  final float loadFactor;
  //省略以下内容
  ...
}

Segment是ConcurrentHashMap的静态内部类，可以看到它继承自ReentrantLock，因此它在本质上是一个锁。它在内部持有一个HashEntry数组(哈希表)，并且保证所有对该数组的增删改查方法都是线程安全的，具体是怎样实现的后面会讲到。所有对ConcurrentHashMap的增删改查操作都可以委托Segment来进行，因此ConcurrentHashMap能够保证在多线程环境下是安全的。又因为不同的Segment是不同的锁，所以多线程可以同时操作不同的Segment，也就意味着多线程可以同时操作ConcurrentHashMap，这样就能避免HashTable的缺陷，从而极大的提高性能。

初始化操作

//核心构造器
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;
  }
  int sshift = 0;
  int ssize = 1;
  //保证ssize为2的幂, 且是最接近的大于等于并发级别的数
  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;
  //保证cap为2的幂, 且是最接近的大于等于c的数
  while (cap < c) {
    cap <<= 1;
  }
  //新建一个Segment对象模版
  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给数组第0个元素赋值
  UNSAFE.putOrderedObject(ss, SBASE, s0);
  this.segments = ss;
}

ConcurrentHashMap有多个构造器，但是上面贴出的是它的核心构造器，其他构造器都通过调用它来完成初始化。核心构造器需要传入三个参数，分别是初始容量，加载因子和并发级别。在前面介绍成员变量时我们可以知道默认的初始容量为16，加载因子为0.75f，并发级别为16。现在我们看到核心构造器的代码，首先是通过传入的concurrencyLevel来计算出ssize，ssize是Segment数组的长度，它必须保证是2的幂，这样就可以通过hash&ssize-1来计算分段锁在数组中的下标。由于传入的concurrencyLevel不能保证是2的幂，所以不能直接用它来当作Segment数组的长度，因此我们要找到一个最接近concurrencyLevel的2的幂，用它来作为数组的长度。假如现在传入的concurrencyLevel=15，通过上面代码可以计算出ssize=16，sshift=4。接下来立马可以算出segmentShift=16，segmentMask=15。注意这里的segmentShift是分段锁的移位值，segmentMask是分段锁的掩码值，这两个值是用来计算分段锁在数组中的下标，在下面我们会讲到。在算出分段锁的个数ssize之后，就可以根据传入的总容量来计算每个分段锁的容量，它的值c = initialCapacity / ssize。分段锁的容量也就是HashEntry数组的长度，同样也必须保证是2的幂，而上面算出的c的值不能保证这一点，所以不能直接用c作为HashEntry数组的长度，需要另外找到一个最接近c的2的幂，将这个值赋给cap，然后用cap来作为HashEntry数组的长度。现在我们有了ssize和cap，就可以新建分段锁数组Segment[]和元素数组HashEntry[]了。注意，与JDK1.6不同是的，在JDK1.7中只新建了Segment数组，并没有对它初始化，初始化Segment的操作留到了插入操作时进行。

元素

//根据哈希码获取分段锁
@SuppressWarnings("unchecked")
private Segment<K,V> segmentForHash(int h) {
  long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
}
 
//根据哈希码获取元素
@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);
}

• 通过哈希码计算分段锁在数组中的下标：(h >>> segmentShift) & segmentMask。
• 通过哈希码计算元素在数组中的下标：(tab.length - 1) & h。

hashMap
参考连接