博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HashMap在Java1.7与1.8中的区别
阅读量:4451 次
发布时间:2019-06-07

本文共 1130 字,大约阅读时间需要 3 分钟。

JDK1.7中

 

使用一个Entry数组来存储数据,用key的hashcode取模来决定key会被放到数组里的位置,如果hashcode相同,或者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不会造成不可承受的开销。

转载于:https://www.cnblogs.com/cxfly/p/10540952.html

你可能感兴趣的文章
Nodejs学习笔记(2) 阻塞/非阻塞实例 与 Nodejs事件
查看>>
跟我一起读postgresql源码(六)——Executor(查询执行模块之——查询执行策略)
查看>>
scala的4中for循环,及while和do while循环
查看>>
Go语言程序结构
查看>>
自定义圆形头像
查看>>
JavaScript&jQuery.动态创建元素
查看>>
WebBrowser记录
查看>>
什么是FreeMaker
查看>>
设计模式学习笔记(总结篇:模式分类)
查看>>
算法笔记_075:蓝桥杯练习 最短路(Java)
查看>>
TCP的三次握手/建立连接
查看>>
Python 教程阅读笔记(一):使用解释器
查看>>
运算符重载
查看>>
SDWebImage 新版接口使用方法
查看>>
简单的jQuery检测注册用户名
查看>>
DataTable导出为word,excel,html,csv,pdf,.txt
查看>>
android ListView详解
查看>>
软件工程 第一次作业
查看>>
Content Server HA搭建
查看>>
vue-textarea 自适应高度
查看>>