Java 8:HashMap的性能提升

HashMap是一个高效通用的数据结构,它在每一个Java程序中都随处可见。先来介绍些基础知识。你可能也知道,HashMap使用key的hashCode()和equals()方法来将值划分到不同的桶里。桶的数量通常要比map中的记录的数量要稍大,这样每个桶包括的值会比较少(最好是一个)。当通过key进行查找时,我们可以在常数时间内迅速定位到某个桶(使用hashCode()对桶的数量进行取模)以及要找的对象。

这些东西你应该都已经知道了。你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候,这些值是存储到一个链表中的。最坏的情况下,所有的key都映射到同一个桶中,这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。我们先来测试下正常情况下hashmap在Java 7和Java 8中的表现。为了能完成控制hashCode()方法的行为,我们定义了如下的一个Key类:

有意思的是这个简单的HashMap.get()里面,Java 8比Java 7要快20%。整体的性能也相当不错:尽管HashMap里有一百万条记录,单个查询也只花了不到10纳秒,也就是大概我机器上的大概20个CPU周期。相当令人震撼!不过这并不是我们想要测量的目标。

假设有一个很差劲的key,他总是返回同一个值。这是最糟糕的场景了,这种情况完全就不应该使用HashMap:

class Key implements Comparable<Key> {
//...
@Override
public int hashCode() {
return 0;
}
}

Java 7的结果是预料中的。随着HashMap的大小的增长,get()方法的开销也越来越大。由于所有的记录都在同一个桶里的超长链表内,平均查询一条记录就需要遍历一半的列表。因此从图上可以看到,它的时间复杂度是O(n)。

不过Java 8的表现要好许多!它是一个log的曲线,因此它的性能要好上好几个数量级。尽管有严重的哈希碰撞,已是最坏的情况了,但这个同样的基准测试在JDK8中的时间复杂度是O(logn)。单独来看JDK 8的曲线的话会更清楚,这是一个对数线性分布:

为什么会有这么大的性能提升,尽管这里用的是大O符号(大O描述的是渐近上界)?其实这个优化在JEP-180中已经提到了。如果某个桶中的记录过大的话(当前是TREEIFY_THRESHOLD = 8),HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好,是O(logn),而不是糟糕的O(n)。它是如何工作的?前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面,这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树,使用哈希值作为树的分支变量,如果两个哈希值不等,但指向同一个桶的话,较大的那个会插入到右子树里。如果哈希值相等,HashMap希望key值最好是实现了Comparable接口的,这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的,不过如果实现了当然最好。如果没有实现这个接口,在出现严重的哈希碰撞的时候,你就并别指望能获得性能提升了。

这个性能提升有什么用处?比方说恶意的程序,如果它知道我们用的是哈希算法,它可能会发送大量的请求,导致产生严重的哈希碰撞。然后不停的访问这些key就能显著的影响服务器的性能,这样就形成了一次拒绝服务攻击(DoS)。JDK 8中从O(n)到O(logn)的飞跃,可以有效地防止类似的攻击,同时也让HashMap性能的可预测性稍微增强了一些。我希望这个提升能最终说服你的老大同意升级到JDK 8来。

测试使用的环境是:Intel Core i7-3635QM @ 2.4 GHz,8GB内存,SSD硬盘,使用默认的JVM参数,运行在64位的Windows 8.1系统 上。

原文发布于微信公众号 - java一日一条(mjx_java)

原文发表时间:2015-11-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏简书专栏

基于python的冒泡排序和选择排序

装饰器是python的高级用法,初学者需要单独学习1天才能理解并且熟练运用。 读者如果不理解本节内容,不影响后续内容的理解。 此装饰器只是计算函数运行花费的...

1134
来自专栏数据结构与算法

10.25解题报告

预计分数:40+50+4=94 实际分数:30+15+0=45 T1 https://www.luogu.org/problem/show?pid=T14791...

2824
来自专栏机器学习算法与Python学习

程序员必备,快速学习 Python 的全套14张思维导图(附高清版下载)

1874
来自专栏华章科技

令人困惑的TensorFlow!谷歌大脑工程师帮你解决麻烦

导读:虽然对于大多数人来说 TensorFlow 的开发语言是 Python,但它并不是一个标准的 Python 库。这个神经网络框架通过构建「计算图」来运行,...

1753
来自专栏小红豆的数据分析

小蛇学python(17)时间序列的数据处理

不管是在金融学、经济学的社会学科领域,还是生态学、系统神经的自然学科领域,时间序列数据都是一种重要的结构化数据形式。

2135
来自专栏杨建荣的学习笔记

Python之Numpy初识

今天翻了下计划,要学习Numpy了,所以得调动脑细胞的积极性,看看能有什么收获。 首先得了解下什么是Numpy,从我的印象中,一般提到这个工具都会和机器学习关...

36211
来自专栏云霄雨霁

函数依赖总结

1082
来自专栏Java成神之路

文本相似度——自己实现文本相似度算法(余弦定理)

最近由于工作项目,需要判断两个txt文本是否相似,于是开始在网上找资料研究,因为在程序中会把文本转换成String再做比较,所以最开始找到了这篇关于 距离编辑算...

2023
来自专栏潇涧技术专栏

Python Algorithms - C5 Traversal

Traversal就是遍历,主要是对图的遍历,也就是遍历图中的每个节点。对一个节点的遍历有两个阶段,首先是发现(discover),然后是访问(visit)。遍...

981
来自专栏机器学习算法与Python学习

机器学习(31)之频繁集挖掘FP Tree详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 明早7:22推送第2期免费送书活动 ...

4266

扫码关注云+社区

领取腾讯云代金券