飞利浦·斯塔克|厉害了！阿里大佬把 HashMap 剖析得只剩渣渣了( 三 ) 阿里巴巴

HashMap对红黑树进行了限制，让红黑树只有在极少数极端情况下进行抗压。

扩容方案
当HashMap中的数据越来越多，那么发生hash冲突的概率也就会越来越高，通过数组扩容可以利用空间换时间，保持查找效率在常数时间复杂度。那什么时候进行扩容？由HashMap的一个关键参数控制：装载因子。
装载因子=HashMap中节点数/数组长度，它是一个比例值。当HashMap中节点数到达装载因子这个比例时，就会触发扩容；也就是说，装载因子控制了当前数组能够承载的节点数的阈值。如数组长度是16 ，装载因子是0.75 ，那么可容纳的节点数是16*0.75=12 。装载因子的数值大小需要仔细权衡。装载因子越大，数组利用率越高，同时发生哈希冲突的概率也就越高；装载因子越小，数组利用率降低，但发生哈希冲突的概率也降低了。所以装载因子的大小需要权衡空间与时间之间的关系。在理论计算中， 0.75是一个比较合适的数值，大于0.75哈希冲突的概率呈指数级别上升，而小于0.75冲突减少并不明显。 HashMap中的装载因子的默认大小是0.75 ，没有特殊要求的情况下，不建议修改它的值。
那么在到达阈值之后， HashMap是如何进行扩容的呢？HashMap会把数组长度扩展为原来的两倍，再把旧数组的数据迁移到新的数组，而HashMap针对迁移做了优化：使用HashMap数组长度是2的整数次幂的特点，以一种更高效率的方式完成数据迁移。
JDK1.7之前的数据迁移比较简单，就是遍历所有的节点，把所有的节点依次通过hash函数计算新的下标，再插入到新数组的链表中。这样会有两个缺点：1、每个节点都需要进行一次求余计算；2、插入到新的数组时候采用的是头插入法，在多线程环境下会形成链表环。 jdk1.8之后进行了优化，原因在于他控制数组的长度始终是2的整数次幂，每次扩展数组都是原来的2倍，带来的好处是key在新的数组的hash结果只有两种：在原来的位置，或者在原来位置+原数组长度。具体为什么我们可以看下图：
从图中我们可以看到，在新数组中的hash结果，仅仅取决于高一位的数值。如果高一位是0 ，那么计算结果就是在原位置，而如果是1 ，则加上原数组的长度即可。这样我们只需要判断一个节点的高一位是1 or 0就可以得到它在新数组的位置，而不需要重复hash计算。 HashMap把每个链表拆分成两个链表，对应原位置或原位置+原数组长度，再分别插入到新的数组中，保留原来的节点顺序，如下：
小结

装载因子决定了HashMap扩容的阈值，需要权衡时间与空间，一般情况下保持0.75不作改动；
HashMap扩容机制结合了数组长度为2的整数次幂的特点，以一种更高的效率完成数据迁移，同时避免头插法造成链表环。

线程安全
HashMap作为一个集合，主要功能则为CRUD ，也就是增删查改数据，那么就肯定涉及到多线程并发访问数据的情况。并发产生的问题，需要我们特别关注。
HashMap并不是线程安全的，在多线程的情况下无法保证数据的一致性。举个例子：HashMap下标2的位置为null ，线程A需要将节点X插入下标2的位置，在判断是否为null之后，线程被挂起；此时线程B把新的节点Y插入到下标2的位置；恢复线程A ，节点X会直接插入到下标2 ，覆盖节点Y ，导致数据丢失，如下图：
jdk1.7及以前扩容时采用的是头插法，这种方式插入速度快，但在多线程环境下会造成链表环，而链表环会在下一次插入时找不到链表尾而发生死循环。
那如果结果数据一致性问题呢？解决这个问题有三个方案：

采用Hashtable
调用Collections.synchronizeMap()方法来让HashMap具有多线程能力
采用ConcurrentHashMap

前两个方案的思路是相似的，均是每个方法中，对整个对象进行上锁。 Hashtable是老一代的集合框架，很多的设计均以及落后，他在每一个方法中均加上了synchronize关键字保证线程安全。
// Hashtable
public synchronized V get(Object key) {...
public synchronized V put(K key V value) {...
public synchronized V remove(Object key) {...
public synchronized V replace(K key V value) {...
...

第二种方法是返回一个SynchronizedMap对象，这个对象默认每个方法会锁住整个对象。如下源码：
这里的mutex是什么呢？直接看到构造器：