HashMap在Java1.7与1.8中的区别

- 日理万妓 2022-06-13 05:48 136阅读 0赞

基于JDK1.7.0\_80与JDK1.8.0\_66做的分析

JDK1.7中

使用一个Entry数组来存储数据，但是这个Entry是链表结构，如果插入的key的hashcode相同（hash collision），那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表。

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

也就是说时间复杂度退化到了O(n)的级别

JDK1.8中

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

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

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

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

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

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

听起来挺不错，但是真正想要利用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不会造成不可承受的开销。

参考资料：

jdk1.7.0\_80的HashMap源码

jdk1.8.0\_66的HashMap源码

[Java 8系列之重新认识HashMap][Java 8_HashMap]

[HASH COLLISION DOS 问题][HASH COLLISION DOS]

[Java 8_HashMap]: http://tech.meituan.com/java-hashmap.html
[HASH COLLISION DOS]: http://coolshell.cn/articles/6424.html

发表评论取消回复

表情：

评论列表（有 0 条评论，136人围观）

还没有评论，来说两句吧...

相关阅读

相关 HashMap底层实现原理？HashMap与HashTable区别？HashMap与HashSet区别？

①HashMap的工作原理： HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的

╰半橙微兮°/ 2022年12月20日 12:35/ 0 赞/ 156 阅读

相关 Java中HashTable和HashMap的区别

（1）HashTable的方法是同步的，HashMap不同步，所以在多线程情况下，使用的是HashTable （2）HashTable不允许null值(key和value都不

- 日理万妓/ 2022年08月21日 04:23/ 0 赞/ 140 阅读

相关 java中Hashtable的使用案例及与HashMap的区别

package itcast07; import java.util.HashMap; import java.util.Hashtable;

迈不过友情╰/ 2022年06月17日 07:55/ 0 赞/ 128 阅读

相关 HashMap在Java1.7与1.8中的区别

基于JDK1.7.0\_80与JDK1.8.0\_66做的分析 JDK1.7中使用一个Entry数组来存储数据，但是这个Entry是链表结构，如果插入的key的ha

- 日理万妓/ 2022年06月13日 05:48/ 0 赞/ 137 阅读

相关 HashMap底层实现原理/HashMap与HashTable区别/HashMap与HashSet区别

①HashMap的工作原理 HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的h

旧城等待，/ 2022年06月08日 03:43/ 0 赞/ 237 阅读

相关 Java中Hashtable与HashMap的区别

Java中Map用于保存具有映射关系的数据，Map集合中保存着两组值，一组用来存放key，另外一组用来存放value，key和value为一对一的单向关系，即每个key值对应唯

浅浅的花香味﹌/ 2022年05月27日 00:58/ 0 赞/ 169 阅读

相关 Java中HashMap,LinkedHashMap,TreeMap的区别

java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap

小咪咪/ 2022年05月26日 02:37/ 0 赞/ 203 阅读

相关 HashMap在Java1.7与1.8中的区别

转载自：[https://blog.csdn.net/jek123456/article/details/73869203][https_blog.csdn.net_jek12

川长思鸟来/ 2022年03月19日 14:08/ 0 赞/ 156 阅读

相关 Java中 HashMap 和 ConcurrentHashMap 的区别

放入 HashMap 的元素是 key-value 对。 - 底层说白了就是散列结构。 - 要将元素放入到 HashMap 中，那么 key 的类型必须要实现 hashc...

灰太狼/ 2020年04月24日 16:34/ 0 赞/ 845 阅读

相关 Java中 HashMap 和 HashTable 的区别

HashMap 几乎可以等价于 HashTable，除了 HashMap 是非 synchronized 的，并可以接受 null(HashMap 可以接受为 null ...

灰太狼/ 2020年04月24日 16:31/ 0 赞/ 832 阅读