HashMap在Java1.7与1.8中的区别

- 日理万妓 2022-06-13 05:48 150阅读 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 条评论，150人围观）

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

相关阅读

相关 HashMap与 ConcurrentHashMap与。SynchronizedMap –如何在Java中同步HashMap

`HashMap`是Java中非常强大的数据结构。我们每天都在几乎所有应用程序中使用它。我之前写过很多关于[如何实现Threadsafe缓存][Threadsafe]，如何将[

深藏阁楼爱情的钟/ 2023年10月04日 09:45/ 0 赞/ 6 阅读

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

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

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

相关 HashMap与ConcurrentHashMap的区别

本文转自http://blog.csdn.net/xuefeng0707/article/details/40834595 从JDK1.2起，就有了HashMap，

雨点打透心脏的1/2处/ 2022年07月16日 09:11/ 0 赞/ 154 阅读

相关 HashTable与HashMap的区别

HashTable与HashMap的区别 1）、HashTable与HashMap实现的是不同的接口 Hashtable是Dictionary的子类 Ha

柔情只为你懂/ 2022年07月12日 03:08/ 0 赞/ 241 阅读

相关 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 赞/ 151 阅读

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

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

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

相关 HashMap与ConcurrentHashMap的区别

从JDK1.2起，就有了HashMap，正如前一篇文章所说，HashMap不是线程安全的，因此多线程操作时需要格外小心。在JDK1.5中，伟大的Doug Lea给我们带来

心已赠人/ 2022年06月04日 06:06/ 0 赞/ 190 阅读

相关 Java中Hashtable与HashMap的区别

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

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

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

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

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

相关 HashMap 与 HashTable的区别

HashMap 实现了Map接口非线程同步，非线程安全不允许重复键键和值均允许为null HashMap<Interger,Str

本是古典何须时尚/ 2022年01月05日 08:45/ 0 赞/ 249 阅读