一、集合
1. ConcurrentHashMap 的实现原理
ConcurrentHashMap 在 JDK 1.6 和 1.7 都采用了相同的数据结构，即分段锁的技术来实现的。ConcurrentHashMap 内部有一个叫 Segment 的数组，里面存放的都是 Segment 对象。Segment 对象继承了 ReentrantLock，这样就使得每个段都有一把锁。 Segment 里面有一个被 volatile 修饰的 HashEntry 的数组。（在 ConcurrentHashMap 初始化的时候，创建了 Segment 数组，并初始化第一个元素。）
JDK 1.7
重要变量
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
transient volatile HashEntry<K,V>[] table;
transient int count;
transient int modCount;
transient int threshold;
final float loadFactor;
}
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
put 操作
判断 value 是否为 null， 如果 value 为 null 则抛出异常。
当用户调用 put 方法的时候，首先根据 key 的 hash 值找到具体的 Segment 在 table 中的位置。
如果这个位置上的 Segment 没有初始化，则进行初始化的操作。
最后委托给 Segment 的 put 方法。此方法中会根据计算出的 (tab.length - 1) & hash 的 index 定位到 HashEntry， 如果这个位置上的节点为null，则新建一个 HashEntry并返回 。如果不为 null，则遍历 HashEntry 的每一个节点，如果有相同的 key 存在则更新 value， 如果没有则新建一个 HashEntry 放入链表头部的位置。
如果 ConcurrentHashMap 内存放的元素个数超过了阈值，那么需要对其进行扩容。整个操作都是加锁的。
get 操作
get 操作的时候没有对 ConcurrentHashMap 进行上锁，
根据 key 的 hash 值计算出在哪个 Segment 上，再根据 hash 值计算出在哪个 HashEntry 上
然后遍历 HashEntry 的所有节点，如果找到 key，那么就返回对应的 value，如果 key 没有找到，就返回 null。
remove 操作
根据 key 的 hash 值找到在哪个 Segment 上
然后调用 Segment 的 remove 方法，根据
int index = (tab.length - 1) & hash;计算出 index 并找到对应的 HashEntry遍历 HashEntry 的所有节点，找到相同的 key（调用 key 的 equals 和 hashCode 方法）并删除，并且返回 value。
扩容操作（具体步骤还没找到）
ConcurrentHashMap不会增加Segment的数量，而只会增加Segment中链表数组的容量大小，这样的好处是扩容过程不需要对整个ConcurrentHashMap做rehash，而只需要对Segment里面的元素做一次 resize 就可以了。
整个步骤如下：
- 创建一个大小为原来 HashEntry 两倍大小的数组，根据 hash 算法重新将老 table 中的元素放入到新 table 中去。
这里的重点就是：
首先找到一个lastRun，lastRun之后的元素和lastRun是在同一个桶中，所以后面的不需要进行变动。然后对开始到lastRun部分的元素，重新计算下设置到newTable中，每次都是将当前元素作为newTable的首元素，之前老的链表作为该首元素的next部分。
JDK 1.8
ConcurrentHashMap 在 JDK 1.8 中进行了大幅度的改进。取消了 Segment 分段锁的概念。采用了数组 + 链表 + 红黑树的数据结构实现。内部存放了一个 Node<K,V>[] table 的 table。 ConcurrentHashMap 在初始化的时候只是设置了一些变量值，并没有对整个 table 进行初始化，初始化的动作被放入到了第一次 put 元素的时候。
一些重要的变量
/**
* races. Updated via CAS.
* 记录容器的容量大小，通过CAS更新
*/
private transient volatile long baseCount;
/**
* 这个sizeCtl是volatile的，那么他是线程可见的，一个思考:它是所有修改都在CAS中进行，但是sizeCtl为什么不设计成LongAdder(jdk8出现的)类型呢？
* 或者设计成AtomicLong(在高并发的情况下比LongAdder低效)，这样就能减少自己操作CAS了。
*
* 来看下注释，当sizeCtl小于0说明有多个线程正则等待扩容结果，参考transfer函数
*
* sizeCtl等于0是默认值，大于0是扩容的阀值
*/
private transient volatile int sizeCtl;
/**
* 自旋锁 （锁定通过 CAS） 在调整大小和/或创建 CounterCells 时使用。 在CounterCell类更新value中会使用，功能类似显示锁和内置锁，性能更好
* 在Striped64类也有应用
*/
private transient volatile int cellsBusy;
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(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
sizeCtl 变量
控制标识符，用来控制table初始化和扩容操作的，在不同的地方有不同的用途，其值也不同，所代表的含义也不同
负数代表正在进行初始化或扩容操作
-1代表正在初始化
-N 表示有N-1个线程正在进行扩容操作
正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小
put 操作
首先判断 key 和 value 是否为 null， 如果为 null 则抛出异常。
然后在判断 table 是否初始化，如果没有初始化则通过 CAS 操作将 sizeCtl 的值设置为 -1，并执行 table 的初始化操作。
根据 key 的 hash 定位到 key 所在 table 的位置，如果这个位置上没有元素，则直接插入元素后返回。
如果当前节点的 hash 值为 -1，说明当前的节点是 forwardingNode 节点，表示 table 正在扩容，当前线程需要帮助一起扩容。（上面的过程走完之后，说明当前的节点上有元素，需要对当前节点加锁然后操作）。
如果当前节点的 hash 值大于等于 0，说明是一个链表结构，则遍历链表，如果存在当前 key 节点则替换 value，否则插入到链表尾部。
如果 f 是 TreeBin 类型节点，则按照红黑树的方法更新或者增加节点。
若链表长度 > TREEIFY_THRESHOLD(默认是8)，则将链表转换为红黑树结构（并不是直接转的，还需要进一步判断，具体的在
treeifyBin方法中）。最后调用 addCount 方法，将 ConcurrentHashMap 的 size + 1，并判断是否需要执行扩容操作，整个 put 过程结束。
get 操作
get 操作的时候没有上锁，如果整个table 为空，则返回null，否则根据 key 的 hash 值找到 table 的 index 位置，然后根据链表或者树形方式找到相对应的节点，返回其 value 值。
remove 操作
源码最后调用的是 replaceNode() 方法。具体没有详细看。
红黑树转换
1. 什么时候转换?
链表的元素个数达到了阈值 8 ，则会调用 treeifyBin 方法把链表转换成红黑树，不过在结构转换之前，会对数组长度进行判断。如果数组长度n小于阈值 MIN_TREEIFY_CAPACITY ，默认是64，则会调用 tryPresize 方法把数组长度扩大到原来的两倍，并触发 transfer 方法，重新调整节点的位置。
扩容操作
http://www.jianshu.com/p/487d00afe6ca
整个扩容操作分为两步：
构建一个nextTable，其大小为原来大小的两倍，这个步骤是在单线程环境下完成的。
将原来table里面的内容复制到nextTable中，这个步骤是允许多线程操作的，所以性能得到提升，减少了扩容的时间消耗。
并发扩容的具体步骤如下：
为每个内核分任务，并保证其不小于16
检查nextTable是否为null，如果是，则初始化 nextTable，使其容量为 table 的两倍。然后死循环遍历节点，直到finished。节点从 table 复制到 nextTable 中，支持并发，思路如下：
如果节点 f 为 null，则插入 ForwardingNode（采用 Unsafe.compareAndSwapObject 方法实现），这个是触发并发扩容的关键
如果 f 为链表的头节点（fh >= 0）,则先构造一个反序链表，然后把他们分别放在nextTable的 i 和 i + n位置，并将 ForwardingNode 插入原节点位置，代表已经处理过了
如果 f 为 TreeBin 节点，同样也是构造一个反序链表 ，==同时需要判断是否需要进行 unTreeify() 操作==，并把处理的结果分别插入到 nextTable 的 i 和 i+n 位置，并插入 ForwardingNode 节点
所有节点复制完成后，则将 table 指向 nextTable，同时更新 sizeCtl = nextTable 的 0.75 倍，完成扩容过程。
在多线程环境下，ConcurrentHashMap 用两点来保证正确性：ForwardingNode 和 synchronized。当一个线程遍历到的节点如果是 ForwardingNode，则继续往后遍历，如果不是，则将该节点加锁，防止其他线程进入，完成后设置 ForwardingNode 节点，以便要其他线程可以看到该节点已经处理过了，如此交叉进行，高效而又安全。
更多关于 ConcurrentHashMap 的问题在这里罗列
-
为什么 ConcurrentHashMap 的 table 大小是 2 的次幂?
参见扩容机制的描述。
-
ConcurrentHashMap JDK 8 在什么样的情况下会扩容?
(1) 当前容量超过阈值时扩容
(2) 当链表中元素个数超过默认设定（8个），当数组的大小还未超过64的时候，此时进行数组的扩容，如果超过则将链表转化成红黑树。
-
ConcurrentHashMap JDK 8 如何实现线程安全?
使用 CAS + Synchronized 来保证并发更新的安全。
-
HashMap 的 hash 算法
参见扩容机制的描述。
-
ConcurrentHashMap 的弱一致性
(1) 在 JDK 1.6 的时候，一个线程在 ConcurrentHashMap 里 put 元素时写 count，另一个线程 get 数据的时候不会得到最新的实时数据。这是因为源码中 put 操作的写
new HashEntry和 get 操作的getFirst()存在 happened-before 关系。具体可以查看笔记。(2) 貌似在 JDK 1.7 的时候也存在同样的问题。
2. HashMap 实现原理
JDK 1.7
HashMap 在 JDK 7 中的数据结构是数组 + 链表的实现。 HashMap 中存储了一个 Entry[] 类型的数组，里面存储了 Entry 对象。Entry 对象的结构如下：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
put
当调用 put 方法的时候，会根据 key 的 hash 值定位到 key 要存到 table 的哪个 index 上
如果 key 为 null，那么就 put 到链表的头结点上。
如果 key 不为 null，那么遍历 index 上的链表，如果存在相同的 key，那么就更新 value。
如果不存在相同的 key，那么将 key 存到链表的头结点中。
get
根据 key 的 hash 值计算出 key 在 table 的哪个 index 上。遍历 index 上的链表，找到相同的 key，并返回 value。
如果 key 不存在则返回 null。
扩容
什么时候扩容?
当 HashMap 内的容量数超过了阈值（默认 12 个）的时候会触发扩容。整个扩容过程如下：
新建一个比原来数组两倍大的新数组。
重算 key 的 hash 值来得到在新数组的位置，并将 key 放入新数组中。
死循环问题
主要是多线程同时put时，如果同时触发了rehash操作，会导致HashMap中的链表中出现循环节点，进而使得后面get的时候，会死循环。而且还会丢失元素。
主要重现过程可以看： http://blog.csdn.net/xuefeng0707/article/details/40797085
JDK 1.8
在 JDK 1.8 中， HashMap 重新设计了实现。放弃 1.7 中的数组 + 链表的存储结构，改为了数组 + 链表 + 红黑树的实现。
put
根据 key 的 hash 值，计算出 table 中的 index。
如果 index 上没有元素，那么直接插入元素。
如果 index 上有元素的话，并且是链表结构的话，就遍历链表，判断是否有相同的 key 存在，如果存在则替换 value，如果不存在则新建 Node ==放入链表尾部==。同时判断当前链表是否过长，如果超过 TREEIFY_THRESHOLD 的话，则需要将链表转换成红黑树。
如果 index 上的节点是 TreeNode 类型的话，则用红黑树的方式添加元素。
最后判断 HashMap 中的元素是否超过了阈值，如果超过了需要进行 resize 扩容。
get
根据 key 的 hash 值定位到 table 中的 index。
如果 index 上没有元素，则返回 null。
如果 index 上有元素，那么根据节点类型的不同，调用链表或红黑树的方式获取 value。
扩容
在 JDK 1.8 的实现中，优化了高位运算的算法，通过 hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图
有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。
红黑树转换
如果链表上的元素大于 8 个，那么需要转换成红黑树。不过在结构转换之前，会对数组长度进行判断。如果数组长度n小于阈值 MIN_TREEIFY_CAPACITY ，默认是64，则会调用 tryPresize 方法把数组长度扩大到原来的两倍，并触发 transfer 方法，重新调整节点的位置。
