HashMap扩容机制以及尾插法

1. resize定义

 当HashMap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。 

2. 扩容触发条件

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容。

loadFactor的默认值为0.75，数组大小为16。也就是说，默认情况下，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置。

而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，HashMap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。 

为什么数组默认长度是16？那是为了实现均匀分布。因为在使用2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

3. 扩容原理

HashMap扩容分为两步：

• 扩容：创建一个新的Entry空数组，长度是原数组的2倍。
• ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

为什么要重新Hash呢，不直接复制过去呢？因为长度扩大以后，Hash的规则也随之改变。

Hash的公式---> index = HashCode（Key） & （Length - 1）

原来长度（Length）是8你位运算出来的值是2 ，新的长度是16你位运算出来的值明显不一样了,之前的所有数据的hash值得到的位置都需要变化。

扩容前:

扩容后:

4. 头插法和尾插法

当HashMap要在链表里插入新的Entry时，在Java 8之前是将Entry插入到链表头部，在Java 8开始是插入链表尾部（Java 8用Node对象替代了Entry对象）。

Java 7插入链表头部，是考虑到新插入的数据，更可能作为热点数据被使用，放在头部可以减少查找时间。

Java 8改为插入链表尾部，原因就是防止环化。因为resize的赋值方式，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

这也是HashMap不能用于多线程场景的一个重要原因。我们来看一下多线程场景下的示例：

图是网上找的，话我就凑合着说了，图上的hash算法是自定义的，不要纠结这个，是简单的用key mod 一下表的大小（也就是数组的长度）。不是那个实际的hash算法！

最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。接下来的三个步骤是Hash表 扩容变成4，然后所有的

do {
    Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

而我们的线程二执行完成了。于是我们有下面的这个样子。

注意，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

这里的意思是线程1这会还没有完全开始扩容，但e和next已经指向了，线程2是正常的扩容的，那这会在3这个位置上，就是7->3这个顺序。

然后：线程一被调度回来执行。

回到线程1里面的时候，一切安好。线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。

这时候，原来的线程2里面的key7的e和key3的next没了，e=key3,next=null。当继续执行，需要将key3加回到key7的前面。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)

注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

我理解是线程2生成的e和next的关系影响到了线程1里面的情况。从而打乱了正常的e和next的链。于是，当我们的线程一调用到，HashTable.get(11)时，即又到了3这个位置，需要插入新的，那这会就e 和next就乱了。