因为HashMap并不是线程安全的，在并发操作的情况下，HashMap并不适合使用，所以我们需要一种线程安全的容器来储存key-value类型的数据。在jdk1.0中提供了Hashtable来实现线程安全，但是新版本的jdk中明确建议开发者不再使用Hashtable，而使用ConcurrentHashMap来代替它实现线程安全。
ConcurrentHashMap出现在jdk1.5中，其底层是Segment数组+HashEntry数组+链表的数据结构。该类位于java.util.concurrent包下，作者是著名的并发大师Dong Lea，所以我们有必要好好的学习下该类关于并发安全相关的设计理念。
在JDK1.7中，ConcurrentHashMap中提出了Segment(段) 和Segment Lock(分段锁)的概念，因为Segment继承了ReentrantLock，所以Segment自身是线程安全的，而ConcurrentHashMap中定义了一个Segment数组（默认大小：16），多个Segment之间并不会互相影响，这就避免了一锁锁全局，提高并发效率。
jdk1.7中ConcurrentHashMap的数据结构如下图：
ConcurrentHashMap数据结构(jdk1.7).png
put方法分析
//ConcurrentHashMap.put
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException(); //value不允许为null，遗留问题：为什么value不能为null？
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;//hash运算，定位到Segment数组的下标位置
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);//下标对应的Segment未初始化时，先去初始化,同时也会初始化Segment中的HashEntry数组
return s.put(key, hash, value, false);//Segment.put
}
//Segment.put
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//加锁
//tryLock() = false，while循环尝试加锁，循环过程中也会尝试提前创建好HashEntry数据
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;//hash运算计算出数据在HashEntry数组的下标位置
HashEntry<K,V> first = entryAt(tab, index);//获取下标位置的数据
for (HashEntry<K,V> e = first;;) {
if (e != null) {
//若下标位置已有数据
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
//若同已有数据是同一对象，或者hash值对比和equals对比结果都为true
oldValue = e.value;
if (!onlyIfAbsent) {
//新值替换旧值
e.value = value;
++modCount;
}
break;//跳出循环
}
e = e.next;//向后迭代
}
else {
if (node != null)
//加锁时数据创建成功，头插法
node.setNext(first);
else
//数据未创建成功，先创建数据，头插法
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
//大于扩容阈值，进行扩容操作和计算在新数组中的下标位置并放置，扩容后数组的大小是原来的2倍
rehash(node);
else
//向数组下标位置放置数据
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();//解锁
}
return oldValue;
}
JDK1.8中抛弃了Segment相关设计，而采用了CAS + synchronized 来保证线程安全，同时底层也更新为数组 + 链表 + 红黑树的数据结构。
jdk1.8中ConcurrentHashMap的数据结构如下图：
ConcurrentHashMap数据结构(jdk1.8).png
put方法分析
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//hash运算，减少hash碰撞
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
//数组未初始化，先初始化，这里用了CAS保证线程安全
tab = initTable();
//获取下标位置元素
// tabAt方法是通过Unsafe.getObjectVolatile方法直接取到主内存中的最新值。
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//下标位置没有元素，直接放在该下标位置上，使用CAS保证线程安全
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; //跳出循环
}
else if ((fh = f.hash) == MOVED)
//当前位置元素的hash = -1，说明正在扩容，协助扩容。
tab = helpTransfer(tab, f);
else {
//下标位置有元素
V oldVal = null;
//锁住链表头部元素
synchronized (f) {
//判断主内存中的头元素是否和我们获取的头元素是同一对象
//若不是同一对象，说明可能别的线程处理过，进入下次循环重头处理
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
//同一对象或者equals为true，新值替换旧值
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
//插入到链表尾部（尾插法）
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
//如果是红黑树
Node<K,V> p;
binCount = 2;
//插入到红黑树中，返回满足可以替换旧值的数据
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
//替换旧值
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);//链表数据大小超过8，转换为红黑树
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);//扩容
return null;
}
