HashMap源码解析(五)

拉链法导致的链表过深的问题为什么不用二叉树替换而选择红黑树，为什么不一直使用红黑树

之所以选择使用红黑树是为了解决二叉查找树的缺点，二叉查找树在特殊情况下会变成一条线性结构,这就变成和链表结果一样了，遍历查找会非常慢，但是红黑树在插入新数据可能通过左旋，右旋，变色这些操作来保持平衡，引入红黑树就是为了查找数据块，解决链表查询深度的问题，我们知道红黑树属于红黑树，但是为了保持平衡是需要付出代价的，但是代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的时候，根本你不需要引入红黑树，引入反而会慢

为什么HashMap中的链表转成红黑树的阀值是8

首先和hashcode碰撞次数的泊松分布有关，主要为了寻找一种时间和空间的平衡，在负载因子0.75的情况下，单个hash槽内元素个数为8的概率小于百万分之一，将7作为一个分水岭，等于7做转换，大于等于8才转红黑树，小于等于6才转链表，链表中元素为8的概率已经非常小，更多就更少了，所以选择了个数为8,是根据概率统计而选择的

大量实验发现，hash碰撞发生8次的概率已经降到了0.00000006，几乎为不可能事件,如果真的碰撞发生8次,那么这个时候说明由于元素和hash函数的原因,此次操作hash碰撞可能性非常大,发生8次碰撞之后，再次碰撞就会转成红黑树，最后红黑树转成链表的阀值是6，这个是为了发生链表和红黑树的不停互相激荡转换，拜拜浪费资源

fail-fast策略

fail-fast经常和一个异常类ConcurrentModificationException联系在一起,首先我们要知道发的意思就是

当遇到可能诱导失败的条件时候立即上报错误,快速失效系统往往被设计在
立即终止正常操作过程，而不是尝试去继续一个可能会存在错误的过程

其实就是尽可能早的发现问题,立即终止当前执行过程，有更高层级的系统做处理.

在HashMap中，我们知道有一个变量modCount和一个exceptedModCount局部变量，在迭代的过程中，若干内容作了修改次数的一致性校验，如果有其他线程或本线程修改了map的内容,就会导致modCount和exceptedModCount不一致,立刻抛出ConcurrentModifcationException异常

HashMap如何规避线程不安全

我们知道HashMap是线程不安全的，他会导致什么问题呢

• 数据覆盖 JDK1.8中我们使用有两个线程同时操作put方法,当线程A和B都获取到bucket的时候，线程A阻塞住了,而线程B完成了插入操作,此时线程A恢复过来就会导致覆盖的之前线程B插入的值
• 死循环 jdk1.7才会出现这个问题，是因为使用的头插法，导致原来的顺序做了反转，最终导致死循环的可能，jdk1.8中已经修复了这个问题使用尾插法
• 数据丢失 在jdk1.7中多线程扩容的时候,就会导致数据丢失

那么有什么办法呢？

• 使用Collections.SynchronizeMap包装
• 使用ConcurrentHashMap替换