Map 类和多线程
HashMap
HashMap 是我们最常用的 Map 类，在单线程存入和获取数据有非常高的性能。下面简单介绍下它的基本结构。
基本结构
HashMap 内部管理一个数组，数组中存储链表节点。将 (key, value) 插入map是，对 key 的 hashCode 调用 hash() 方法生成优化后的散列值，然后调用 indexOfHash，然后 (n - 1) & hash 计算出数组中的下标，为 (key, value) 生成 node 存入数组中。
存入的 node 一般是链表结构的，如果两个条目（Entry）散列后的数组下标相同，也就是发生哈希冲突，新条目的 node 会插入链表的最后。如果链表上 node 数量大于 8 个，为了增加查找性能，会将链表结构改变成红黑树结构。
线程不安全
HashMap 的线程不安全已经是面试的“街题”了，为了简单说明它的不安全性，可以从它的 putVal 函数入手。该函数是 HashMap 的最核心函数，它用于将 （key, value） 存入 HashMap 中。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
相比于 Java8 之前的 addEntry 要复杂不少（忍不住吐槽下，Java8 的类，包括 ConcurrentHashMap，功能越来越牛b，代码越来越复杂难懂）。尽管代码结构复杂，但是当分析线程安全的时候，只要抓住 table / modCount / size 等临界区变量的非同步访问就能足够说明问题了。
HashTable
HashTable 早在 JDK1.0 的时候就引入了，它的结构和 HashMap 类似，唯独在 public 接口上使用了 synchronized 修饰符。比如：
public synchronized int size()
public synchronized boolean isEmpty()
public synchronized V get(Object key)
public synchronized V put(K key, V value)
synchronized 的接口执行之前会抢占 HashTable 对象的内置锁，达到多线程同步的作用。但是它的读线程和写线程都会去抢占这个内置锁，比如 contains 这类需要遍历元素并调用 equal的读数据接口，可能会较长时间阻塞其他线程，不论读写。因此在线程竞争激烈的情况下HashTable的效率非常低下。
SynchronizedMap
JDK 还提供了一种获取线程安全 Map 的方式：Collections.synchronizedMap。这个接口会返回 SynchronizedMap 的对象，SynchronizedMap 其实是代理模式下，对具体 Map 的封装，我们来看看它的结构：
SynchronizedMap 就两个成员变量，一个是真正实现 Map 的线程不安全类，一个是用来同步的 mutex，当调用 Map 接口时，使用 mutex 的内置锁进行保护，实际调用内部 Map 对象的接口。类似于：
public int size() {
synchronized (mutex) {return m.size();}
}
public V get(Object key) {
synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
可以说 SynchronizedMap 和 HashTable 实现多线程同步的机制一样，所以尽管是线程安全的，但是在线程竞争激烈的情况下效率非常堪忧。
还有一个问题是既然 SynchronizedMap 和 HashTable 同步机制类似，那为什么还要有 SynchronizedMap呢？我想可能是由于 HashTable 内部结构和 HashMap 一致。但是还有很多其他的 Map 类，比如 LinkedHashMap，TreeMap 等它，它们并没有对应的同步容器版本。而 SynchronizedMap 能够成为它们的代理，既保证这些非 HashMap 的内部结构所带来的优势，又能保证线程安全性。
modCount
在看 HashMap 和 HashTable 的时候有个 modCount 引人注目。这是代码中的注释：
The number of times this Hashtable has been structurally modified
Structural modifications are those that change the number of entries in
the Hashtable or otherwise modify its internal structure (e.g.,
rehash). This field is used to make iterators on Collection-views of
the Hashtable fail-fast. (See ConcurrentModificationException).
简单来说 modCount 代表了 HashTable 结构变化的次数。结构变化是指那些如些插入条目/修改条目/删除条目等条目操作或者 rehash 这种改变内部数据结构的操作。
为什么要记录这个 modCount 呢？最主要的作用是保证使用迭代器操作时，HashTable的数据没有改变，如果 modCount 变化，则说明此时数据不一致，抛出 ConcurrentModificationException 异常。具体可以看看 HashTable.Enumerator 的代码，简单的例子如下：
public T next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return nextElement();
}
ConcurrentHashMap
同步容器 VS 并发容器
HashTable 和SynchronizedMap 都属于同步容器，这些类实现线程安全的方式是：将它们的状态封装起来，对每个公有方法的同步使得每次只有一个线程能访问容器的状态。以这种所有访问都串行化的方式，同步容器保证了线程安全性，但是这种方法的代价是严重降低并发行（想象下，所有只有读线程的情况），当多个线程竞争容器的锁时，吞吐量将严重降低。
Java 5.0 提供了并发容器来改进同步容器的性能。并发容器可以使多个线程并发的访问容器。通过并发容器来替代同步容器，可以极大地提高伸缩性并降低风险。
ConcurrentHashMap 就是一种同步容器，它采用了分段锁（Lock Striping）机制增加并发行。在这种机制下：
- 任意数量的读线程可以并发地访问 Map
- 读线程和写线程可以并发的访问 Map
- 一定数量的线程可以并发修改 Map
弱一致性
还记得上文中 HashTable 的 modCount 和 ConcurrentModificationException 吗？在使用同步容器的迭代器时，如果容器内数据变化，迭代时就会“立即失败”，抛出异常。
和 HashTable 不同，ConcurrentHashMap 的迭代器可以容忍并发修改，也就是说当创建迭代器遍历元素时，如果容器内元素增加，减少，变更时，迭代器也不会抛出异常，之后也能访问到修改后的数据，而且迭代器在构造后可以将修改操作反映给容器。
因为 ConcurrentHashMap 的 get 操作几乎全是无锁操作，get 和 put 可以同时进行。用 CAS 操作和 volitale 关键字保证临界数据的可见性，读线程总能看到最近已完成的更新，这是产生弱一致性的最根本原因。对此，Java API 有以下描述：
Retrievals reflect the results of the most
recently completed update operations holding upon their onset. (More formally, an update operation for a given key bears a happens-beforerelation with any (non-null) retrieval for that key reporting the updated value.)
数据结构
ConcurrentHashMap 内部结构实现在 Java 8 和 Java 8 之前有很大的变化。
JDK 1.7
在 JDK 1.7 中，ConcurrentHashMap 内部维护了一个 segment 数组，每一个 Segment 相当于类似于另外一个 HashMap。每个 Segment 维护一个 HashEntry 数组，HashEntry 采用了链表结构，数据结构可以看下面这图：
所以访问一个 Entry 需要进行两次哈希，第一次哈希找到 Segment，第二次哈希是在 table 中找到链表。分段锁加在 Segment 上，也就是说不同的 Segment 可以并发操作，两条写线程所要更改的数据第一次哈希到同一个 Segment 时，线程才会同步。
JDK 1.8
在 JDK 1.8 中，对 ConcurrentHashMap 进行了两个地方的优化:
- 取消了 Segment 结构，直接采用transient volatile HashEntry<K,V>[] table保存数据，采用 table 数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。
- 将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。虽然ConcurrentHashMap类默认的加载因子为0.75，但是在数据量过大或者运气不佳的情况下，还是会存在一些队列长度过长的情况，对于个数超过8(默认值)的链表，jdk1.8中采用了红黑树的结构，那么查询的时间复杂度可以降低到O(logN)，可以改进性能。
就数据结构上来看，JDK 1.8 下的 ConcurrentHashMap 和 普通的 HashMap 更加相近，但是前者通过对 table 元素的加锁，保证多个 put 线程可以并发访问。
内容来源
Java 并发编程实战
http://ifeve.com/concurrenthashmap-weakly-consistent/
http://ifeve.com/concurrenthashmap/
http://blog.csdn.net/sbq63683210/article/details/51679790
