Hashtable、HashMap、ConcurrentHash

1. Hashtable线程安全，都是synchronized方法。锁整个table，效率低下。

2. HashMap线程不安全，并发put扩容（transfer()方法）时，会形成环形链表。

JDK7：数组 + 链表

JDK8：数组 + 链表or红黑树，同ConcurrentHashMap

3. ConcurrentHashMap线程安全，get方法不需要加锁，因为value是volatile类型，总是能够获取最新值。

JDK7：分段锁

Segment[]和HashEntry[]长度皆为2的N次方，ConcurrentHashMap初始化后，Segment[]长度就固定不变了。扩容时，只需对某个Segment[i]中的HashEntry[]扩容（创建一个2倍长度的新HashEntry[]，旧数组中元素rehash，插入到新数组中）。

put时，第一次hash，定位Segment[i]，然后获取ReentrantLock锁，再次hash，定位HashEntry[i]。如果新增该元素，超过了HashEntry[]的阈值，将先进行扩容，再插入元素（HashMap是先插入元素，再进行扩容）。

JDK7的ConcurrentHashMap内部结构图.png

JDK8：使用synchronized，弃用分段锁（锁粒度更小）

put时，如果table[i]==null，则使用CAS操作把元素插入数组，插入失败，表示有其他线程已经在该位置插入元素，然后继续下次循环。此时会遇到synchronized代码块（它只锁当前Node[i]）。如果该位置是链表，则添加到链表尾部。如果该位置是红黑树，则插入树里面。当链表长度>=8时，链表会转化成红黑树。

JDK8的ConcurrentHashMap内部结构图.png

红黑树讲解

---

以上。源码就不贴了。