HashMap在jdk1.7和1.8中的区别

今天重温了下HashMap的源码，对比了下HashMap在jdk1.7和jdk1.8中的区别，搜到网上有一篇文章总结的挺好，于是摘抄了下来，另外也补充了一些自己总结的知识点和面试容易被问到的点（红色字体），有不正确的地方还请留言指正，谢谢。

 

学习jdk1.8中的HashMap之前，需要先了解下什么是红黑树(了解红黑树的同学直接从共同点开始看即可)：

参考：https://www.cnblogs.com/ysocean/p/8032642.html

https://www.cnblogs.com/ysocean/p/8004211.html

二叉树：每个节点最多只能有两个子节点的树型结构。超过两个节点的成为多路树。

二叉搜索树：二叉搜索树是特殊的二叉树，需满足要求：若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不为空，则它的右子树上所有节点的值均大于它的根节点的值。它的左右子树也分别为二叉排序树。

如果是在平衡的二叉搜索树上，也就是说如果插入的数据是随机的，则其效率很高，其查找、插入和删除的时间复杂度都是O(logn)，底数为2；如果插入的数据是有序的，比如从小到大的顺序，则数据的排布效果全部在根节点的右边，和链表没什么区别，这种情况下的时间复杂度为O(n)，而不是O(logn)，当然这是在最不平衡的条件下，实际情况下，二叉搜索树的效率应该在O(n)和O(logn)之间，这取决于树的不平衡度。

红-黑树：是一种用来保证树总是平衡的(或大部分是平衡的)，也就是说，每个节点的左子树节点个数和右子树节点个数尽量相等。对于要插入的数据项（删除也是），插入例程要检查会不会破坏树的平衡，如果破坏了，程序就会通过改变节点的颜色、左旋、右旋的方式进行纠正，根据需要改变树的结构，从而保证树的平衡。

红黑树的特征：

有如下两个特征：

　　①、节点都有颜色；

　　②、在插入和删除的过程中，要遵循保持这些颜色的不同排列规则。

　　第一个很好理解，在红-黑树中，每个节点的颜色或者是黑色或者是红色的。当然也可以是任意别的两种颜色，这里的颜色用于标记，我们可以在节点类Node中增加一个boolean型变量isRed，以此来表示颜色的信息。

　　第二点，在插入或者删除一个节点时，必须要遵守的规则称为红-黑规则：

　　1.每个节点不是红色就是黑色的；

　　2.根节点总是黑色的；

　　3.如果节点是红色的，则它的子节点必须是黑色的（反之不一定）,(也就是从每个叶子到根的所有路径上不能有两个连续的红色节点)；

　　4.从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。

　　从根节点到叶节点的路径上的黑色节点的数目称为黑色高度，规则 4 另一种表示就是从根到叶节点路径上的黑色高度必须相同。

　　注意：新插入的节点颜色总是红色的，这是因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小，原因是插入黑色节点总会改变黑色高度（违背规则4），但是插入红色节点只有一半的机会会违背规则3（因为父节点是黑色的没事，父节点是红色的就违背规则3）。另外违背规则3比违背规则4要更容易修正。当插入一个新的节点时，可能会破坏这种平衡性，那么红-黑树是如何修正的呢？

 

引自：https://www.aliyun.com/jiaocheng/787890.html 

参考文档：

https://blog.csdn.net/carson_ho/article/details/79373026

https://www.jianshu.com/p/8324a34577a0?utm_source=oschina-app

https://www.cnblogs.com/ysocean/p/8711071.html

 

 

 -------------------------------华丽的分割线--------------------------------

共同点：

1. 容量（capacity）：HashMap中数组的长度

 a. 容量范围：必须是2的幂 & <最大容量（2的30次方）

 b. 初始容量 = 哈希表创建时的容量

 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

 最大容量 = 2的30次方（若传入的容量过大，将被最大值替换）

static final int MAXIMUM_CAPACITY = 1 << 30;

 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度

 a. 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）

 b. 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高（链表不长）

 默认加载因子 = 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f 

扩容机制

扩容时resize(2 * table.length)，扩容到原数组长度的2倍。

若key == null，则hash(key) = 0，则将该键-值 存放到数组table 中的第1个位置，即table [0]

 

异同点：

JDK1.7中使用一个Entry数组来存储数据,用key的hashcode取模来决定key会被放到数组里的位置,如果hashcode相同,或者hashcode取模后的结果相同(hashcollision),那么这些key会被定位到Entry数组的同一个格子里,这些key会形成一个链表。在hashcode特别差的情况下,比方说所有key的hashcode都相同,这个链表可能会很长,那么put/get操作都可能需要遍历这个链表也就是说时间复杂度在最差情况下会退化到O(n)

 

JDK1.7中

使用一个Entry数组来存储数据,用key的hashcode取模来决定key会被放到数组里的位置,如果hashcode相同,或者hashcode取模后的结果相同(hash collision),那么这些key会被定位到Entry数组的同一个格子里,这些key会形成一个链表。

• 在hashcode特别差的情况下,比方说所有key的hashcode都相同,这个链表可能会很长,那么put/get操作都可能需要遍历这个链表

  也就是说时间复杂度在最差情况下会退化到O(n)。

• 发生hash冲突时，新元素插入到链表头中，即新元素总是添加到数组中，就元素移动到链表中。 

• 在扩容resize（）过程中，采用单链表的头插入方式，在将旧数组上的数据 转移到 新数组上时，转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况 。

• HashMap线程不安全的一个重要原因就是：多线程下resize()容易出现死循环
  此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出现 环形链表，从而在获取数据、遍历链表时 形成死循环（Infinite Loop），即 死锁的状态 。

• JDK1.8中

  使用一个Node数组来存储数据,但这个Node可能是链表结构,也可能是红黑树结构

  如果插入的key的hashcode相同,那么这些key也会被定位到Node数组的同一个格子里。

  如果同一个格子里的key不超过8个,使用链表结构存储。

  如果超过了8个,那么会调用treeifyBin函数,将链表转换为红黑树。

  那么即使hashcode完全相同,由于红黑树的特点,查找某个特定元素,也只需要O(log n)的开销

  也就是说put/get的操作的时间复杂度最差只有O(log n)

• 由于 JDK 1.8 转移数据操作 = 按旧链表的正序遍历链表、在新链表的尾部依次插入，所以不会出现链表 逆序、倒置的情况，故不容易出现环形链表的情况 ，但jdk1.8仍是线程不安全的，因为没有加同步锁保护。

  发生hash冲突后，会优先判断该节点的数据结构式是红黑树还是链表，如果是红黑树，则在红黑树中插入数据，如果是链表，则将数据插入到链表的尾部并判断链表长度是否大于8，如果大于8要转成红黑树，另一还要判断数组长度是否超过阀值，超过阀值要进行扩容。听起来挺不错,但是真正想要利用JDK1.8的好处,有一个限制:

• key的对象,必须正确的实现了Compare接口

• 如果没有实现Compare接口,或者实现得不正确(比方说所有Compare方法都返回0)

• 那JDK1.8的HashMap其实还是慢于JDK1.7的

   

  简单的测试数据如下:

  向HashMap中put/get 1w条hashcode相同的对象

  JDK1.7:                                  put 0.26s,get 0.55s

  JDK1.8(未实现Compare接口):put 0.92s,get 2.1s

  但是如果正确的实现了Compare接口,那么JDK1.8中的HashMap的性能有巨大提升,这次put/get 100W条hashcode相同的对象

  JDK1.8(正确实现Compare接口,):put/get大概开销都在320ms左右

   

   

  为什么要这么操作呢?

  我认为应该是为了避免Hash Collision DoS攻击

  Java中String的hashcode函数的强度很弱,有心人可以很容易的构造出大量hashcode相同的String对象。

  如果向服务器一次提交数万个hashcode相同的字符串参数,那么可以很容易的卡死JDK1.7版本的服务器。

  但是String正确的实现了Compare接口,因此在JDK1.8版本的服务器上,Hash Collision DoS不会造成不可承受的开销。

   补充：为什么说HashMap是线程不安全的？
  参考文档：https://www.cnblogs.com/qiumingcheng/p/5259892.html