介绍ConcurrentHashMap

小明：ConcurrentHashMap 是 java 并发包里提供的一个并发集合，它基于了以往 Hashmap 或 Hashtable ，以一种安全高效的方式提供并发，所以我们可以在多线程环境去使用它，且不用担心并发安全

ConcurrentHashMap一定并发安全吗

小明： 严格意义上讲，并不能！ 并发安全并不是一个非黑即白的东西，相反，它有多种程度，比如不可变、绝对线程安全、相对线程安全等，

比如 ConcurrentHashMap 就属于其中的 相对线程安全，如果你对它做单次操作，那么它是安全的。但如果以特定顺序的连续调用，就可能无法预料结果，举个简单的例子，100个线程，在 ConcurrentHashMap 里取值后加一再存回，其最终结果可能并不是 +100。如果想在这种场景下做到线程安全，必须添加其他的代码来做安全保障

ConcurrentHashMap 是怎么实现

小明：ConcurrentHashMap 的实现采用的是 数组 + 链表 + 红黑树 混合的结构，基本结构是个数组，对键值对里的key进行hash计算，得到个整数，然后对当前容量取余来求得一个下标，然后把键值对放入数组的该位置，我们把数组的每个位置称为“箱”。当然，这一过程中，肯定有数据会下标重复，所以允许每个箱存放多个元素，如果元素少，就用链表排起来，元素多，就转变成红黑树。上述内容同HashMap基本一致，但不同的则是采用了CAS 和 synchronized 来加强并发安全

举几个在ConcurrentHashMap 使用CAS 和 synchronized 来加强并发安全的例子

小明：比如插入元素的时候，当找到桶时，如果桶里没元素，就以CAS方式把该元素放入桶中，如果有元素，则使用synchronized锁住该桶的第一个元素，然后再遍历该桶各个元素进行比对。同理，在删除，或者扩容迁移的时候，也会使用这两种方法

说说 ConcurrentHashMap 在jdk7 到 jdk8 都发生了什么变化

小明：

第一点：jdk7是基于锁分离的思想，把之前的hashmap继续细分为一个个Segment，而每个Segment其实又包含一个数组，里面元素的改动会以Segment为单位进行上锁，然后操作。到了jdk1.8，取消了Segment，意味着两次定位变为一次定位，同时锁的粒度更细了，数组的每一位都可以单独上锁，这其实增加了并发数。

第二点：在jdk8时，当一个“箱“中的元素大于等于8时，会将链表结构转为红黑树结构。这一点在1.7中是没有的，而1.8里的HashMap 和 ConcurrentHashMap 则使用了此种设计。这种设计优化了极限情况的效率，说是极限情况，是因为因为扩容机制的存在，只要hash算法够均匀，单个箱中的元素很难达到8个。

第三点：在jdk7时，元素个数是由各Segment自己统计并维护的，因此求总数量时，会遍历各Segment记录的数字，累加并记录总和，然后再重复遍历一次又得到一次总和，比较两次总和如果一样就返回，如果不一样就把所有Segment全部上锁后，最后遍历一次并最终返回该值。而jdk8，则是把统计数值分为两部分，一部分是基础值baseCount，一般来说，我们添加1个元素，会使用CAS让basecount自增1。但如果竞争激烈CAS失败，则会使用一个countCell数组，把这个1使用CAS加入到数组中的某个位置，因此最终统计总元素数量时，会遍历累加countCell数组里的值，最后和basecount相加并返回，且过程中不会使用同步手段。因此，不难看出JDK7方法类似于先用乐观锁，不行再悲观锁，兼顾效率与强一致性。而JDK8的统计效率更高，但是结果无法保证强一致性，因为在你遍历累加的过程中，前面的countCell值可能又会变化，导致得到的总数并不实时。

第四点：扩容实现不一样，jdk1.7里Segment数量是不会变的，扩容的是每个Segment里面的小数组，而每个Segment内部的数据更新都需要竞争一把锁，扩容也同样如此，因此这个扩容只会有一个线程独自完成。而jdk1.8的扩容就是数组扩容成2倍，且扩容过程允许其他线程帮忙，每个线程一次会选定至少16个“箱”，然后依次将这些“箱”的数据迁移至新表，在移一个“箱”前会先对这个箱打上标签后再移，此后若有其他的线程试图往该“箱”插数据，发现这个标志后也会尝试参与到迁移过程中，然后该线程也会被分至少16个“箱”来迁移

调整扩容因子会有什么影响？

小明：装载因子从hashmap 时期就有，指的是容器内元素个数和容器长度的比值，通过调节这个参数，我们可以调整hashmap在什么时候扩容。但是…），在ConcurrentHashMap 里，这个扩容因子不能被调整，尽管我们可以在创建容器时，传入一个扩容因子，但这个值仅仅在初始化计算容量时会被用到，并不会保存，这与hashmap是不一样的，在后续的扩容中，判断是否扩容的条件总是元素个数是否大于 sizeCtl 变量，而这个变量的值与当前容器长度n有关，结果是0.75n，所以扩容因子实际上还是0.75.

扩容因子默认为什么要固定成0.75呢

小明：这个问题 Doug Lea 其实在注释里就有说明，0.75其实是个数学和计算问题，我们假设hash结果足够均匀，在指定发生哈希冲突数学期望为0.5的前提下，可以倒推出一个合适的扩容因子。具体的推算过程应属于离散数学的范畴，假定扩容因子为0.75时，那它的冲突的期望大概是0.53，比较符合预期的。当然扩容因子如果是0.7或0.8，其实也不会差多少。但是ConcurrentHashMap里用到了大量的位运算，而在计算容器扩容阈值时，0.75却是可以直接用位运算和加减法得出的，比如0.75n = n - (n >>> 2)，从性能和风格角度考虑，也达成了一种均衡

ConcurrentHashMap用的“头插法”，扩容会有环化问题吗

小明：扩容死锁发生在jdk1.7版本的hashmap中，其原因是因为采用了头插法，在两个线程并发对hashmap扩容时，有概率导致“箱”里的链表循环。但1.8中，采用了尾插法，且各线程自己会记录迁移的尾节点，因此不会再出现环化。而ConcurrentHashMap从源码看，到了jdk1.8时，ConcurrentHashMap在做迁移时其实是直接将“桶”的数据预先分割成低位、高位两个链表，然后再挂到新容器的两个位置中，在生成两个链表的时候，确实仍然采用的头插，也因此会产生元素的倒序。但不管是1.7还是1.8，都不会有环化问题，因为ConcurrentHashMap限制了一个“箱”的数据只会由一个单一的线程来迁移，因此根本不会有此类问题。

什么时候链表转为红黑树

小明：当前“箱”的元素个数达到8，并且数组长度达到或超过64，那么才会对本“箱”的元素进行树化，后一个条件表明，在容量不大的时候，作者更推荐扩容来解决哈希冲突，而不是树化

树化的阈值为什么是8，从树退化下来阈值又是6呢

小明：在数组每个位置发生哈希冲突时，优先使用的是链表来存储。但我们都知道链表的时间复杂度为o(n)，一旦链表长了，效率是比较低的。所以在达到8时，会转换成红黑树，红黑树时间复杂度o(logN)就比较好了。至于这个阈值为8，（思索片刻）主要是红黑树的构建和维护比较耗时和复杂，当可以建起一个三层的满树时，使用红黑树才算有效率上的优势。树的退化阈值是6，则主要是为了和8拉开间隔，这种例子是为了降低在边缘阈值波动时，反复建树和去树。这种例子生活里也常见，比如手机CPU到50℃就会降频，但却温度降低到45℃时才恢复频率也是一样的道理

为什么选用红黑树，如果用AVL、B+、跳表等结构呢

小明：自然是出于时间复杂度考虑，实际上平衡二叉树也有同样的效果，但平衡二叉树为了做到平衡，有时会有不必要的调整，虽然平衡二叉树高度可能低于红黑树，这让其查询更快，但是对于频繁的增改来说，平衡二叉树效率就不如红黑树，红黑树的特征就是增、删、查均衡。

对于B或者B+等结构，因为map并非数据库，数据库通常将数据存储在硬盘中，所以B或者B+主要目的是降低树的高度，从而减少硬盘访问次数，但是其查找路径实际是更长的，而map存储于内存，就是要缩短查找路径才能体现效率

如果支持范围查找，跳表更合适，但对于单次只查一个数据的map来说，其实际效率低于红黑树，而且跳表占用的空间更大