ConcurrentHashMap也是一种Map，也可以用来存放key-value，但它是线程安全的Map，在高并发的情况下，不会像HashMap那样出现添加数据丢失，扩展形成死链的情况。HashTable也是线程安全的，但是相比HashTable直接加锁的做法，1.8里面的ConcurrentHashMap采用lock-free显得更加高效。
Map体系图
由图可知，ConcurrentHashMap和HashMap一样，也是继承AbstractMap，而AbstractMap实现了Map接口。
ConcurrentHashMap源码大概了解（1.8）
ConcurrentHashMap的数据结构
/**
* concurrentHashMap存放单个key-value的地方，有TreeBin，TreeNode，ForwardingNode，ReservationNode四个子类
*/
static class Node<K,V> implements Map.Entry<K,V> {
/**
* 计算key的得到的哈希值
* int hash = spread(key.hashCode());
* static final int spread(int h) {
* return (h ^ (h >>> 16)) & HASH_BITS;
* }
* static final int HASH_BITS = 0x7fffffff;
*/
final int hash;
final K key;
volatile V val;
//节点所在的连接中指向的下一个元素
volatile Node<K,V> next;
}
/**
* 跟HashMap一样，table是存放所有key-value的地方，默认为null，当插入元素时会初始化，初始化大小为16，每次扩容为原来的两倍
*/
transient volatile Node<K,V>[] table;
/**
* 扩容时新生成的数组，大小为table的两倍
*/
private transient volatile Node<K,V>[] nextTable;
/**
* 重要属性，用来控制table的初始化和扩容，
* 0： 默认值，表示初始化table或扩容用默认值16和2倍
* > 0 : 使用sizeCtl的大小来扩容
* -1 ： 表示正在初始化
* -n : 表示有（n - 1）个线程正在扩容
*/
private transient volatile int sizeCtl;
/**
* Node链表转成红黑树会先判断当前整个map的size是否大于MIN_TREEIFY_CAPACITY并且当前链表大小大于TREEIFY_THRESHOLD
*/
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
ConcurrentHashMap添加元素
put()源码
final V putVal(K key, V value, boolean onlyIfAbsent) {
//key 和 value 为null都报空指针异常
if (key == null || value == null) throw new NullPointerException();
//计算hash值
int hash = spread(key.hashCode());
//元素的数量
int binCount = 0;
//一个死循环
for (ConcurrentHashMap.Node<K,V>[] tab = table;;) {
ConcurrentHashMap.Node<K,V> f; int n, i, fh;
//如果table为null，说明是第一次插数据，要初始化table
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//(n - 1) & hash)为元素在table中的位置，tabAt是用来获取tab的第i个元素是否为空
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//用CAS把节点置上去，如果节点不为null返回false
if (casTabAt(tab, i, null,
new ConcurrentHashMap.Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//moved为 -1 ，如果一个节点的hash值为 -1，表示他是扩容转发节点
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//当table不为空，并且tab上第i个元素也不为空的时候执行这里，说明要形成链表了
else {
V oldVal = null;
//加锁，为什么要加锁？
synchronized (f) {
//为什么还要再次比较呢？
if (tabAt(tab, i) == f) {
//fh是首节点的哈希值，大于0说明不是红黑树，而是链表
if (fh >= 0) {
//链表的元素数量
binCount = 1;
//遍历链表并且插入
for (ConcurrentHashMap.Node<K,V> e = f;; ++binCount) {
K ek;
//如果是已经有的元素，替换它的value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
ConcurrentHashMap.Node<K,V> pred = e;
//如果已经是最后一个元素，把新进来的元素添加进去，否则遍历链表
if ((e = e.next) == null) {
pred.next = new ConcurrentHashMap.Node<K,V>(hash, key,
value, null);
break;
}
}
}
//红黑树做红黑树的处理
else if (f instanceof ConcurrentHashMap.TreeBin) {
ConcurrentHashMap.Node<K,V> p;
binCount = 2;
if ((p = ((ConcurrentHashMap.TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
//如果链表元素大于TREEIFY_THRESHOLD 转成红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
//返回元素
if (oldVal != null)
return oldVal;
break;
}
}
}
//扩容
addCount(1L, binCount);
return null;
}
initTable()源码
private final ConcurrentHashMap.Node<K,V>[] initTable() {
ConcurrentHashMap.Node<K,V>[] tab; int sc;
//只有当table不为空的时候，才跳出循环
while ((tab = table) == null || tab.length == 0) {
//sizeCtl< 0 说明有其它线程正在初始化table，线程让出CPU
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
//SIZECTL对应的偏移量正式sizeCtl，CAS将sc置为 -1，表示正在初始化，如果返回false，说明传进去的sc和sizeCtl不一致
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//再次判断table是否为空
if ((tab = table) == null || tab.length == 0) {
//扩容大小，如果sc>0，则用sizeCtl的值，否则用默认值16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
//初始化table数据
@SuppressWarnings("unchecked")
ConcurrentHashMap.Node<K,V>[] nt = (ConcurrentHashMap.Node<K,V>[])new ConcurrentHashMap.Node<?,?>[n];
table = tab = nt;
//这个地方看不懂
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
get()源码
public V get(Object key) {
ConcurrentHashMap.Node<K,V>[] tab; ConcurrentHashMap.Node<K,V> e, p; int n, eh; K ek;
//计算哈希值
int h = spread(key.hashCode());
//如果table不为空，并且长度大于0，还有对应链表首节点不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//如果链表首节点和key的hash值一样，并且key也一致
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//这个好像是扩容时候的转发节点
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
//遍历链表直到找到key也一样的节点
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
ConcurrentHashMap（1.7）也了解一下
1.7中的ConcurrentHashMap采用了分段锁的机制，底层是一个Segment数组，而每个Segment可以理解为指向一个HashMap。当ConcurrentHashMap进行读写操作的时候，首先会计算对应Segment数组的哪个位置，然后计算在segment指向的HashMap的哪个位置。当进行写操作时，会对对应的segment进行加锁，不同的segment并发操作时不会互相影响。
