参考文档：
漫画：什么是ConcurrentHashMap？
漫画：什么是HashMap？
漫画：高并发下的HashMap
Hashmap实现原理及扩容机制详解
HashMap JDK1.7和1.8区别（完整版）
HashMap
HashMap 基本知识
-
hashmap 初始长度为 16，初始化的时候，传入参数不是 2 的幂数，也会自动设置为 2 的幂数
-
hashmap 长度必须为 2 的幂数
-
加载因数是 0.75，当前数量 * 加载因子 >= 容量的时候，就会扩容，容量翻倍，最大容量为 1 << 30。
1.7 和 1.8 区别
| 不同 | JDK 1.7 | JDK 1.8 |
|---|---|---|
| 存储结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |
| 初始化方式 | 单独函数：inflateTable（） | 直接集成到了扩容函数resize（）中 |
| hash值计算 | 扰动处理=9次扰动=4次位运算+5次异或运算 | 扰动处理=2次扰动=1次位运算+1次异或运算 |
| 存放数据的规则 | 无冲突时，存放数组；冲突时，存放链表 | 无冲突时，存放数组；冲突&链表长度<8:存放单链表; 冲突&链表长度>8:树化并存放红黑树 |
| 插入数据方式 | 头插法（先讲原位置的数据移到后1位，再插入数据到该位置） | 尾插法（直接插入到链表尾部/红黑树） |
| 扩容后存储位置的计算方式 | 全部按照原来方法进行计算（即hashCode -> 扰动函数 ->（h&length-1) | 按照扩容后的规律计算（即扩容后的位置=原位置or原位置+旧容量） |
存储方式
我们先看几个参数
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始容量
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子 也就是0.75F
static final int TREEIFY_THRESHOLD = 8; // 链表长度大于8时树化，数据8是由hashmap作者计算而出
static final int UNTREEIFY_THRESHOLD = 6; //还原成链表的阈值
static final int MIN_TREEIFY_CAPACITY = 64;//最小树化容量
得出以下结论：
如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，treeifyBin首先判断当前hashMap的长度，如果不足64，只进行resize，扩容table，同时最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）， 否则，若桶内元素太多时，则直接扩容，而不是树形化，为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD，这里就是64。
一定是在大于MIN_TREEIFY_CAPACITY的时候，才会树化，无论链表的长度是否大于 TREEIFY_THRESHOLD
优点
相比于jdk1.7的数组+链表结构，先看看hshMap在jdk 1.8的结构，如下图，用的是数组+链表+红黑树的结构，也叫哈希桶，在jdk 1.8之前都是数组+链表的结构，因为在链表的查询操作都是O(N)的时间复杂度，而且hashMap中查询操作也是占了很大比例的，如果当节点数量多，转换为红黑树结构，那么将会提高很大的效率，因为红黑树结构中，增删改查都是O(log n)。
但阈值的存在毫无疑问是必要的，红黑树虽然效率高，但红黑树本身是一个复杂的数据结构，涉及到自旋的操作，在链表节点数量比较少的时候，很明显链表增删改查更为合适，所以并不能直接采用红黑树
为什么选 8 做树形化的阀值？
根据作者计算出的概率
- 0: 0.60653066
- 1: 0.30326533
- 2: 0.07581633
- 3: 0.01263606
- 4: 0.00157952
- 5: 0.00015795
- 6: 0.00001316
- 7: 0.00000094
- 8: 0.00000006
8 个节点的概率接近为 0，可以减少节点树形化。
扰动函数
一个好的 hash 算法，应该是尽量避免不同的 key 映射出相同的 index，这样才能减少哈希冲突的出现。
index 怎么获取：
//获取index的方法，1.7源码，1.8中用tab[(n - 1) & hash]代替，但原理一样
static int indexFor(int h, int length) {
return h & (length-1);
}
index 的获取很简单，就是把 h 对 length-1 取模，其中 length 为数组长度，所以关键的是 h 是怎么计算得到的。
在JDK1.7中的扰动函数源码
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
而在JDK1.8中
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
而至于为什么JDK1.8进行了缩减，是因为做多了离散分布提升不明显，还是为了效率考虑，进行了缩减。
h & (length-1) 详解
在公式 h & (length-1) 中，其中 length 为数组的长度，HashMap 的数组默认长度是 16，因为大多数情况来说数组长度都不会太大，所以影响 h & (length-1) 计算结果的主要因素就是 h 的低位数据了，也就是大多数情况下 h 的高位数据对计算结果是没有影响的。比如只有当数组长度 length 大于 2^16 即大于 65536的时候，h 的高 16 位才会对 h & (length-1) 的计算结果产生影响，所以在 HashMap 中我们也主要对h的低 16 位进行优化，也就是让 h 的低 16 位的数据尽量分散，上面的 (h = key.hashCode()) ^ (h >>> 16) 算法也是基于这个目的而设计的。
为什么不依赖于 hashCode 呢？ hashCode 为系统实现，不可靠。
key.hashCode()) ^ (h >>> 16) 详解
首先 h = key.hashCode() 是 key 对象的一个 hashCode，每个不同的对象其哈希值都不相同，其实底层是对象的内存地址的散列值，所以最开始的 h 是 key 对应的一个整数类型的哈希值
h >>> 16 的意思是将 h 右移 16 位，然后高位补 0，然后再与 (h = key.hashCode()) 异或运算得到最终的 h 值，为什么是异或运算呢？是为了让 h 的低 16 位更有散列性，但为什么是异或运算就更有散列性呢？
先来看一下下面的这组运算
上面是将 0110 和 0101分别进行与、或、异或三种运算得到不同的结果，我们主要来看计算的过程：
与运算：其中 1&1=1，其他三种情况 1&0=0, 0&0=0, 0&1=0 都等于0，可以看到与运算的结果更多趋向于0，这种散列效果就不好了，运算结果会比较集中在小的值
或运算：其中 0&0=0，其他三种情况 1&0=1, 1&1=1, 0&1=1 都等于1，可以看到或运算的结果更多趋向于1，散列效果也不好，运算结果会比较集中在大的值
异或运算：其中 0&0=0, 1&1=0，而另外0&1=1, 1&0=1 ，可以看到异或运算结果等于1和0的概率是一样的，这种运算结果出来当然就比较分散均匀了
总的来说，与运算的结果趋向于得到小的值，或运算的结果趋向于得到大的值，异或运算的结果大小值比较均匀分散，这就是我们想要的结果，这也解释了为什么要用异或运算，因为通过异或运算得到的h值会更加分散，进而 h & (length-1) 得到的index也会更加分散，哈希冲突也就更少
插入方式
在1.7中使用的是头插法，1.8改成了尾插法，为了避免头插法导致的在多线程的情况下 hashmap 在 put 元素时产生的环形链表的问题，但 1.8 仍然存在数据覆盖的问题，所以仍然不是线程安全的
2 的幂次方容量
为什么是 2 的幂数?
为了更快的计算 hash，index = hash(key) % length 效率太低，开发者采用位运算来计算 index = hash(key) & (length -1)，如果 length 不是 2 的幂数，会产生大量冲突。
2的幂次方是指数组长度length的大小，假如length等于2的幂次方，那样length-1的二进制数据的低位就全部为1了，比如当数组长度为16，那么15的二进制就为1111，只有这样，在计算数组下标index的时候才能更好地利用h的散列性，举个例子：
比如 length-1=15，二进制即为1111，分别跟三个不同的h值进行与运算，计算如下
1111 & 101010100101001001000 结果：1000 = 8
1111 & 101000101101001001001 结果：1001 = 9
1111 & 101010101101101001010 结果：1010 = 10
1111 & 101100100111001101100 结果： 1100 = 12
但是如果length为11的话，那么length-1的二进制则表示为1010，与同样的三个h值与运算，计算如下
1010 & 101010100101001001000 结果：1000 = 8
1010 & 101000101101001001001 结果：1000 = 8
1010 & 101010101101101001010 结果：1010 = 10
1010 & 101100100111001101100 结果： 1000 = 8
很明显，当数组长度为 16 的时候，没有产生哈希冲突，而为11的时候，产生了 3 次哈希冲突，所以这就说明了为什么 HashMap 的容量建议为 2 的幂次方
扩容后新坐标
HashMap 扩容时使用 rehash 方法很巧妙，因为每次扩容都是翻倍，和原来计算的一样 (n-1)&hash 相比之下，结果只是多了一个 bit, 所以节点要么在原来的位置，要么分配到"原位置+旧容量"这个位置。
ConcurrentHashMap
- resize() 扩容
- rehash() 重新计算 hash
扩容的时候干了两件事
- 创建一个新的Entry空数组，长度是原数组的2倍。
- 遍历原Entry数组，把所有的Entry重新Hash到新数组。
但是多线程同时 resize 的时候就会造成线程不安全问题。
HashMap 线程安全的解决方案有 HashTable 或者 Collections.synchronizedMap，但无论读写，都会给整个集合加锁，有性能问题。
这时候我们使用 ConcurrentHashMap，兼顾了线程安全和性能。
Segment
ConcurrentHashMap 的一个重要概念。
Segment是什么呢？Segment本身就相当于一个HashMap对象。
同HashMap一样，Segment包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点。
单一的Segment结构如下：
像这样的Segment对象，在ConcurrentHashMap集合中有多少个呢？有2的N次方个，共同保存在一个名为segments的数组当中。
因此整个ConcurrentHashMap的结构如下：
可以说，ConcurrentHashMap是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。
这样的二级结构，和数据库的水平拆分有些相似。
读写情况
ConcurrentHashMap优势就是采用了锁分段技术，每一个Segment就好比一个自治区，读写操作高度自治，Segment之间互不影响。
Case1：不同Segment的并发写入
Case2：同一Segment的一写一读
Case3：同一Segment的并发写入
由此可见，ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。
get
- 为输入的Key做Hash运算，得到hash值。
- 通过hash值，定位到对应的Segment对象
- 再次通过hash值，定位到Segment当中数组的具体位置。
put
- 为输入的Key做Hash运算，得到hash值。
- 通过hash值，定位到对应的Segment对象
- 获取可重入锁
- 再次通过hash值，定位到Segment当中数组的具体位置。
- 插入或覆盖HashEntry对象。
- 释放锁。
size
ConcurrentHashMap的Size方法是一个嵌套循环，大体逻辑如下：
- 遍历所有的Segment。
- 把Segment的元素数量累加起来。
- 把Segment的修改次数累加起来。
- 判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。
- 如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。
- 再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。
- 释放锁，统计结束。
JDK 1.8 更新
Java 8 几乎完全重写了 ConcurrentHashMap，ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。
Java 8 中，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。
JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。