课程咨询 :18669403922
QQ: 2720475033

济南Java培训 > 达内新闻 > Java 8中HashMap的性能提升
  • Java 8中HashMap的性能提升

    发布:济南达内小编      来源:互联网      时间:2016-10-12

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

    这些东西你应该都已经知道了。你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的 时候,这些值是存储到一个链表中的。

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

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

    classKeyimplementsComparable{

    //...

    @Override

    publicinthashCode()

    {

    return

    0;

    }

    }

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

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

    为什么会有这么大的性能提升,尽管这里用的是大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性能的可预测性稍微增强了一些。我希望这个提升能最终说服你的 老大同意升级到JDK8来。

    测试使用的环境是:Intel Core i7-3635QM

    @ 2.4 GHz,8GB内存,SSD硬盘,使用默认的JVM参数,运行在64位的Windows

    8.1系统 上。

    推荐文章

上一篇:Java快速入门的六个技巧

下一篇: 为什么Java中的String是不可变的?

最新开班日期  |  更多

Java--名企定制班

Java--名企定制班

开班日期:2月15日

Java--在职提升班

Java--在职提升班

开班日期:2月15日

Java--零基础全日制班

Java--零基础全日制班

开班日期:2月15日

Java--名企就业班

Java--名企就业班

开班日期:2月15日

  • 山大路中心地址:济南市历下区山大路47号数码港大厦A座102 电话:0531-55588120
    趵突泉中心地址:济南市历下区趵突泉北路三联商社八楼 电话:0531-55583636
    济宁中心地址:济宁市市中区太白路10号苏宁生活广场19层 电话:0537-5125585
  • 课程培训电话:18669403922
    QQ: 2720475033     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内时代科技集团有限公司 版权所有 京ICP证8000853号-56