• 基于上一篇博客继续分析

JDK1.7、1.8 HashMap的差异

JDK1.8中hashmap实现相较于1.7有重大的变化

Hash算法有什么区别呢？

• JDK 1.7

• JDK 1.8

区别

• 1.8计算出来的结果只可能是一个，所以hash值设置为final修饰。
• 1.7会先判断这Object是否是String，如果是，则不采用String复写的hashcode方法，处于一个Hash碰撞安全问题的考虑

初始化又有什么区别呢？

1. JDK1.8 构造方法

• tableSizeFor

• 官方解释：Returns a power of two size for the given target capacity. （返回给定目标容量的二次幂。）

  也就是获取比传入参数大的最小的2的N次幂。
  比如：传入8，就返回8，传入9，就返回16.

2. JDK1.7

• 首先是put方法时，发现是空表，初始化。传入threshold，也就是我们之前传入的initCapactity自定义初始容量

public V put(K key, V value) {//判断是否是空表if (table == EMPTY_TABLE) {//初始化inflateTable(threshold);}...
}

• 这个方法也有官方的注释，意思就是找到大于等给定toSize的最小2的次幂

private void inflateTable(int toSize) {// Find a power of 2 >= toSizeint capacity = roundUpToPowerOf2(toSize);...
}

private static int roundUpToPowerOf2(int number) {// assert number >= 0 : "number must be non-negative";return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

• 最终调用了Integer的计算2次幂的方法。

public static int highestOneBit(int i) {// HD, Figure 3-1i |= (i >>  1);i |= (i >>  2);i |= (i >>  4);i |= (i >>  8);i |= (i >> 16);return i - (i >>> 1);
}

• 其实和1.8的是一致的，但是我们阅读源码发现1.8更趋向于一个方法完成一个大的功能，比如putVal，resize，代码阅读性比较差，而1.7趋向于尽可能的方法拆分，提升阅读性，但是也增加了嵌套关系，结构复杂。

区别

Jdk1.7：

• table是直接赋值给了一个空数组，在第一次put元素时初始化和计算容量。
• table是单独定义的inflateTable（）初始化方法创建的。

Jdk1.8

• 的table没有赋值，属于懒加载，构造方式时已经计算好了新的容量位置（大于等于给定容量的最小2的次幂）。
• table是resize（）方法创建的

扩容有什么区别呢？

• Jdk1.7：

  头插法，添加前先判断扩容，当前准备插入的位置不为空并且容量大于等于阈值才进行扩容，是两个条件！
  扩容后可能会重新计算hash值。

• Jdk1.8：

  尾插法，初始化时,添加节点结束之后和判断树化的时候都会去判断扩容。我们添加节点结束之后只要size大于阈值，就一定会扩容，是一个条件。
  由于hash是final修饰，通过e.hash & oldCap==0来判断新插入的位置是否为原位置。

• jdk 1.8扩容时机

1. 实际上在判断是否树化的时候，也会判断扩容。我们知道树化的两个条件，单条桶长度大于等于8，桶总数大于等于64才发生。但是我们可能不知道这里不满足条件会扩容 呢？那么为什么有扩容这个考虑？

2. 我们认为：桶长度小于64。由于我们的扩容都是翻倍操作，所以我们此时的元素总数小于等于32。假设此时我们的数组容量为32，单个桶长度大于8的概率是微乎其微的，因为阈值是24，平均下来一个桶还不到一个Node节点，

3. 上图也说明了为什么选择8作为树化的阈值。
   但是此时已经有一条链表长度为8了，也就是说阈值没到24，已经有1/3的节点在单条链表了，我们认为这个哈希表太过于集中了，所以我们进行扩容来增加哈希表内元素的散列程度。

插入顺序有什么区别？

区别

• jdk1.7无论是resize的转移和新增节点createEntry，都是头插法
• jdk1.8则都是尾插法，为什么这么做呢为了解决多线程的链表死循环问题。

当采用头插法时会容易出现逆序且环形链表死循环问题 也就是1.7线程不安全问题

• 以 JDK 1.7 为例，假设 HashMap 默认大小为 2，原本 HashMap 中有一个元素 key(5)，我们再使用两个线程：t1 添加元素 key(3)，t2 添加元素 key(7)，当元素 key(3) 和 key(7) 都添加到 HashMap 中之后，线程 t1 在执行到 Entry<K,V> next = e.next; 时，交出了 CPU 的使用权，源码如下：

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next; // 线程一执行此处if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;}}
}

• 那么此时线程 t1 中的 e 指向了 key(3)，而 next 指向了 key(7) ；之后线程 t2 重新 rehash 之后链表的顺序被反转，链表的位置变成了 key(5) → key(7) → key(3)，其中 “→” 用来表示下一个元素。

• 当 t1 重新获得执行权之后，先执行 newTalbe[i] = e 把 key(3) 的 next 设置为 key(7)，而下次循环时查询到 key(7) 的 next 元素为 key(3)，于是就形成了 key(3) 和 key(7) 的循环引用，因此就导致了死循环的发生，如下图所示：

​ 当然发生死循环的原因是 JDK 1.7 链表插入方式为头部倒序插入，这个问题在 JDK 1.8 得到了改善，变成了尾部正序插入。

• 在jdk1.8中，HashMap引入了红黑树，在插入数据时需要判断链表是否达到长度8，所以需要遍历链表，所以当遍历到最后一个节点时顺便把数据插入进去，这样就不需要像头插法那样移动链表了

那1.8线程不安全体现在哪里呢？

• 其中第630行代码是判断是否出现hash碰撞，假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第630行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

• 除此之前，还有就是代码的第662行处有个++size，我们这样想，还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap的zise大小为10，当线程A执行到第662行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU，线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将size=11写回内存，此时，线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全