Java基础、中级、高级、架构面试资料

HashMap 在JDK1.8与JDK1.7的性能测试对比

JAVA herman 3580浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog2,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog2,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领
腾讯云】1核2G5M轻量应用服务器50元首年,高性价比,助您轻松上云

任何数据结构的产生总对应着要解决一个实际的问题!我在《HashMap 存在的意义是什么?》这篇文章中总结到:HashMap 这种数据结构解决存取一组 key-vaule 键值对数据,并且在插入、删除、遍历都有不错性能的数据结构。我们也知道,JDK1.8 对 HashMap 的改动还不少,那么这些改动对 HashMap 的使用性能到底有多少影响呢?今天我们一起来探究探究!

影响 HashMap 性能的一个重要指标就是 Hash,Hash 的好坏(也就是 Hash 冲突的概率)。根据这个特性,我们来自己实现一个 Key,进行它的 Hash 计算。

class Key implements Comparable<Key> {
    // 业余草:www.xttblog.com
    private final int value;
    Key(int value) {
        this.value = value;
    }
    @Override
    public int compareTo(Key o) {
        return Integer.compare(this.value, o.value);
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Key key = (Key) o;
        return value == key.value;
    }
    @Override
    public int hashCode() {
        return value;
    }
}

针对这个 Key,我们重写了 equals、hashCode、compareTo 3 个方法。这个 Hash 的计算应该是相当好的了,直接使用 int 的 value 值。为了避免频繁的 GC,我将不变的 Key 实例缓存起来。

public class Keys {
    // 业余草:www.xttblog.com
    public static final int MAX_KEY = 10_000_000;
    private static final Key[] KEYS_CACHE = new Key[MAX_KEY];
    static {
        for (int i = 0; i < MAX_KEY; ++i) {
            KEYS_CACHE[i] = new Key(i);
        }
    }
    public static Key of(int value) {
        return KEYS_CACHE[value];
    }
}

下面看我们的测试代码:

static void test(int mapSize) {
    HashMap<Key, Integer> map = new HashMap<Key,Integer>(mapSize);
    for (int i = 0; i < mapSize; ++i) {
        map.put(Keys.of(i), i);
    }
    // 业余草:www.xttblog.com
    long beginTime = System.nanoTime(); //获取纳秒
    for (int i = 0; i < mapSize; i++) {
        map.get(Keys.of(i));
    }
    long endTime = System.nanoTime();
    System.out.println(endTime - beginTime);
}
public static void main(String[] args) {
    for(int i=10;i<= 10000000;i*= 10){
        test(i);
    }
}

为了实验测试,我们需要做的是,创建不同 size 的 HashMap(1、10、100、……10000000),这样可以屏蔽扩容的影响。

分别在 JDK1.7 和 JDK1.8 上运行上面的代码,并记录不同 size 所花费的时间。结果如下:

HashMap 在JDK1.8与JDK1.7的性能测试对比

通过多次的测试,结果表明:JDK1.8 的性能要高于 JDK1.7 15%以上,在某些 size 的区域上,甚至高于 100%。由于 Hash 算法较均匀,JDK1.8 引入的红黑树效果不明显,下面我们看看 Hash 不均匀的的情况。

我们改进一下 Key 对 Hash 的计算。

class Key implements Comparable<Key> {
    //...
    // 业余草:www.xttblog.com
    @Override
    public int hashCode() {
        return 1;
    }
}

模拟一个非常差的 Hash 计算,hashCode 始终返回 1,这样就会用到 JDK1.8 引入的红黑树。

测试代码和过程和上面类似,我直接贴出结果。

Jdk1.7和Jdk1.8中链表测试比对

结果表明:随着 size 的变大,JDK1.7 的花费时间是增长的趋势,而 JDK1.8 是明显的降低趋势,并且呈现对数增长稳定。当一个链表太长的时候,HashMap 会动态的将它替换成一个红黑树,这话的话会将时间复杂度从 O(n) 降为 O(logn)。hash 算法均匀和不均匀所花费的时间明显也不相同,这两种情况的相对比较,可以说明一个好的 hash 算法的重要性。

测试硬件环境、操作系统之类的我就不写了,大家自己去测试,得到的才是最真实的感观。

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号:xttblog2。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » HashMap 在JDK1.8与JDK1.7的性能测试对比