1.简介
HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。但HashMap不是线程安全的，即在多线程并发操作HashMap时可能会发生意向不到的结果。想在并发下操作Map,主要有以下方法：
第一种：使用Hashtable线程安全类（现在已经被高效ConcurrentHashMap替代）
第二种：使用Collections.synchronizedMap方法，对方法进行加同步锁；
第三种：使用并发包中的ConcurrentHashMap类；
第一种方法是通过对Hashtable中的方法添加synchronized同步锁来保证线程安全的，第二种是通过对对象加synchronized锁来保证线程安全，相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争激烈的多线程场景中性能就会非常差。前两种方法在多线程操作时效率都比较低下，所以不建议采用。ConcurrentHashMap是线程安全且高效的HashMap，JDK7中ConcurrentHashMap采用锁分段技术，首先将数据分成一段段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程方法，这样我们就不用像前两种方法直接对整个HashMap加锁，采用锁分段技术来提升性能。JDK7中ConcurrentHashMap结构如下图所示：
ConcurrentHashMap结构图7.JPG
其中Segment是一种可重入锁（ReentrantLock），在JDK7的ConcurrentHashMap中扮演锁的角色。Segment结构和HashMap类似，是一种数组和链表结构。
JDK8中对HashMap做了改造，当冲突链表长度大于8时，会将链表转变成红黑树结构，JDK8中ConcurrentHashMap类取消了Segment分段锁，采用CAS+sychronized来保证并发安全，数据结构跟JDK8中的HashMap结构类似，都是数组加链表（当链表长度大于8时，链表结构转为红黑树）结构。JDK8中的、ConcurrentHashMapsynchronized只锁定当前链表或红黑二叉树的首节点，只要节点hash不冲突，就不会产生并发，相比 JDK7中的ConcurrentHashMap效率又提升了N倍。JDK8中ConcurrentHashMap的结构如下所示：
concurrenthashmap8结构图.png
误区：印象中一直以为ConcurrentHashMap是基于Segment分段锁来实现的，之前没仔细看过源码，一直有这么个错误的认识。ConcurrentHashMap是基于Segment分段锁来实现的，这句话也不能说不对，加个前提条件就是正确的了，ConcurrentHashMap从JDK1.5开始随java.util.concurrent包一起引入JDK中，在JDK8以前，ConcurrentHashMap都是基于Segment分段锁来实现的，在JDK8以后，就换成synchronized和CAS这套实现机制了。
2.JDK7中ConcurrentHashMap实现同步的方式
Segment继承自ReentrantLock，所以我们可以很方便的对每一个Segment上锁。
读操作：获取Key所在的Segment时，需要保证可见性，具体实现上可以使用volatile关键字，也可使用锁。但使用锁开销太大，而使用volatile时每次写操作都会让所有CPU内缓存无效，也有一定开销。ConcurrentHashMap使用如下方法保证可见性，取得最新的Segment。
Segment<K,V> s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)；
获取Segment中的HashEntry时也使用了类似方法：
HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE)
写操作：并不要求同时获取所有Segment的锁，因为那样相当于锁住了整个Map。它会先获取该Key-Value对所在的Segment的锁，获取成功后就可以像操作一个普通的HashMap一样操作该Segment，并保证该Segment的安全性。同时由于其它Segment的锁并未被获取，因此理论上可支持concurrencyLevel（等于Segment的个数）个线程安全的并发读写。获取锁时，并不直接使用lock来获取，因为该方法获取锁失败时会挂起（参考可重入锁）。事实上，它使用了自旋锁，如果tryLock获取锁失败，说明锁被其它线程占用，此时通过循环再次以tryLock的方式申请锁。如果在循环过程中该Key所对应的链表头被修改，则重置retry次数。如果retry次数超过一定值，则使用lock方法申请锁。
3.JDK8中ConcurrentHashMap实现同步的方式
JDK8中ConcurrentHashMap保证线程安全主要有三个地方。
（1）使用volatile保证当Node中的值变化时对于其他线程是可见的，以此来保证读安全
（2）写安全（头结点不为null）：使用table数组的头结点作为synchronized的锁来保证写操作的安全。
（3）写安全（头结点为null）：使用CAS操作来保证数据能正确的写入。
使用volatile保证读安全
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
}
可以看到，Node中的val和next都被volatile关键字修饰。也就是说，我们改动val的值或者next的值对于其他线程是可见的，因为volatile关键字，会在读指令前插入读屏障，可以让高速缓存中的数据失效，重新从主内存加载数据。ConcurrentHashMap提供类似tabAt来读取Table数组中的元素，这里是以volatile读的方式读取table数组中的元素，主要通过Unsafe这个类来实现的，保证其他线程改变了这个数组中的值的情况下，在当前线程get的时候能拿到。
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
而与之对应的，是setTabAt,这里是以volatile写的方式往数组写入元素，这样能保证修改后能对其他线程可见。
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
写安全（头结点为null）
当table数组的头结点为null时，使用for循环+CAS来保证线程安全，头结点为null时，可能多个线程并发写入头结点，所以需要保证线程安全。当有一个新的值需要put到ConcurrentHashMap中时，首先会遍历ConcurrentHashMap的table数组，然后根据key的hashCode来定位到需要将这个value放到数组的哪个位置。tabAt(tab, i = (n - 1) & hash))就是定位到这个数组的位置，如果当前这个位置的Node为null，则通过CAS方式的方法写入。所谓的CAS，即compareAndSwap，执行CAS操作的时候，将内存位置的值与预期原值比较，如果相匹配，那么处理器会自动将该位置值更新为新值，否则，处理器不做任何操作。这里就是调用casTabAt方法来实现的。
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
casTabAt同样是通过调用Unsafe类来实现的，调用Unsafe的compareAndSwapObject来实现，其实如果仔细去追踪这条线路，会发现其实最终调用的是cmpxchg这个CPU指令来实现的，这是一个CPU的原子指令，能保证数据的一致性问题。
Java原子类的自增操作，也是通过for循环+CAS操作的方式实现的
// AtomicInteger 类的原子自增操作
public final int getAndIncrement() {
for (;;) {
//获取value
int current = get();
int next = current + 1;
//value值没有变，说明其他线程没有自增过,将value设置为next
if (compareAndSet(current, next))
return current;
//否则说明value值已经改变，回到循环开始处，重新获取value。
}
}
写安全（头结点不为bull）
当头结点不为null时，对头结点使用sychronized加锁来保证线程安全：当头结点不为null时，则使用该头结点加锁，这样就能多线程去put hashCode相同的时候不会出现数据丢失的问题。synchronized是互斥锁，有且只有一个线程能够拿到这个锁，从而保证了put操作是线程安全的。
写安全总结：头结点为null使用for循环+cas保证线程安全，头结点不为null使用sychronized保证线程安全，如下图所示：
头结点为null使用cas保证线程安全-头结点不为null使用sychronized保证线程安全.png
4.JDK7与JDK8主要区别
（1）更小的锁粒度
JDK8中摒弃了Segment锁，直接将hash桶的头结点当做锁。旧版本的一个segment锁，保护了多个hash桶，而JDK8版本的一个锁只保护一个hash桶，由于锁的粒度变小了，写操作的并发性得到了极大的提升。 可以参考下图：
ConcurrentHashMap78锁版本区别.png
（2）更高效的扩容
更多的扩容线程：扩容时，需要锁的保护。因此：旧版本最多可以同时扩容的线程数是segment锁的个数。而JDK8的版本，理论上最多可以同时扩容的线程数是：hash桶的个数。扩容期间，依然保证较高的并发度，旧版本的segment锁，锁定范围太大，导致扩容期间，写并发度，严重下降。而新版本的采用更加细粒度的hash桶级别锁，扩容期间，依然可以保证写操作的并发度。如下图所示：
扩容期间依然保证较高的并发度.png
5.相关问题
（1）谈谈你理解的 HashMap，讲讲其中的 get put 过程。
（2）JDK 做了什么优化？
（3）是线程安全的嘛？
（4）不安全会导致哪些问题？
（5）如何解决？有没有线程安全的并发容器？
（6）ConcurrentHashMap 是如何实现的？ JDK7、JDK8 实现有何不同？为什么这么做？
（7）HashMap如何保证数据有序存放，LRU算法如何实现？
搞明白以上几个问题以后，对HashMap、LinkedHashMap、ConcurrentHashMap也就熟悉了。
参考资料及相关好文
美团技术文章Java 8系列之重新认识HashMap
讲述 ConcurrentHashMap 线程安全最牛逼的一篇文章
ConcurrentHashMap是如何保证线程安全的
从ConcurrentHashMap的演进看Java多线程核心技术
ConcurrentHashMap源码分析（JDK8）
彻头彻尾理解 LinkedHashMap
《Java并发编程的艺术》
网友评论