本文主要讨论哈希冲突下的一些性能测试。
为什么要写这篇文章,不是为了KPI不是为了水字数。
hashmap是广大JAVA程序员最为耳熟能详,使用最广泛的集合框架。它是大厂面试必问,著名八股经必备。在小公司呢?这些年也面过不少人,对于3,5年以上的程序员,问到hashmap也仅限于要求知道底层是数组+链表,知道怎么放进去,知道有哈希冲突这么一回事即可,可依然免不了装备的嫌疑。
可hashmap背后的思想,在缓存,在数据倾斜,在负载均衡等分布式大数据领域都能广泛看到其身影。了解其背后的思想不仅仅只是为了一个hashmap.
更重要的是,hashmap不像jvm底层原理那么遥远,不像并发编程那么宏大,它只需要通勤路上十分钟就可搞定基本原理,有什么理由不呢?
所以本文试着从相对少见的一个微小角度来重新审视一下hashmap.
新建两个class,一个正常重写equals和hashcode方法,一个故意在hashcode方法里返回一定范围内的随机数,模拟哈希冲突,以及控制哈希冲突的程序。
不冲突的类
@Setter
public class KeyTest2 {
private String name;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
KeyTest2 keyTest = (KeyTest2) o;
return name != null ? name.equals(keyTest.name) : keyTest.name == null;
}
@Override
public int hashCode() {
return name != null ? name.hashCode() : 0;
}
}
冲突的类
@Setter
@NoArgsConstructor
public class KeyTest {
private String name;
private Random random;
public KeyTest(Random random){
this.random = random;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
KeyTest keyTest = (KeyTest) o;
return name != null ? name.equals(keyTest.name) : keyTest.name == null;
}
@Override
public int hashCode() {
// return name != null ? name.hashCode() : 0;
return random.nextInt(1000);
}
}
众所周知,hashmap在做put的时候,先根据key求hashcode,找到数组下标位置,如果该位置有元素,再比较equals,如果返回true,则替换该元素并返回被替换的元素;否则就是哈希冲突了,即hashcode相同但equals返回false。
哈希冲突的时候在冲突的数组处形成数组,长度达到8以后变成红黑树。
这里使用JMH进行基准测试.
JMH是Java Microbenchmark Harness的简称,一般用于代码的性能调优,精度甚至可以达到纳秒级别,适用于 java 以及其他基于 JVM 的语言。和 Apache JMeter 不同,JMH 测试的对象可以是任一方法,颗粒度更小,而不仅限于rest api.
jdk9以上的版本自带了JMH,如果是jdk8可以使用maven引入依赖。
点击查看JMH依赖
点击查看初始化长度基本测试代码
测试结果图
对测试结果图例做一个简单的说明:
以上基准测试,会得到一个json格式的结果。然后将该结果上传到官方网站,会得到一个上述图片的结果。
横坐标,红色驻图代表有冲突,浅蓝色驻图无冲突。
众坐标,ops/ns代表平均每次操作花费的时间,单位为纳秒,1秒=1000000000纳秒,这样更精准。
下同。
简单说,驻图越高代表性能越低。
我测了两次,分别是无哈希冲突和有哈希冲突的,这里只贴一种结果。
测试结果表明,hashmap定义时有初始化对比无初始化,有大约4%到12%的性能损耗。
足够的初始化长度下,有哈希冲突的测试结果:
足够的初始化长度下,没有哈希冲突的测试结果:
众所周知,hashmap在频繁做resize时,性能损耗非常严重。以上是没初始化长度,无冲突和有冲突的情况下,前者性能是后者性能的53倍。
那么在初始化长度的情况下呢?
HashMap map = new HashMap(1000000);
同样的代码下,得到的测试结果
以上是有初始化长度,无冲突和有冲突的情况下,前者性能是后者性能的58倍。
大差不差,不管有无初始化长度,无冲突的效率都是有冲突效率的50倍以上。说明,这是哈希冲突带来的性能损耗。
将KeyTest的hashcode方法改为:
@Override
public int hashCode() {
// return name != null ? name.hashCode() : 0;
return random.nextInt(130000);
}
这样1000000/130000 < 8,这样大多数的哈希链将不会扩展为红黑树。
测试结果为:
测试结果说明,**有冲突的效率反而比无冲突的效率要高**,差不多高出80%左右。
这其实有点违反常识,我们通常讲,hashmap要尽量避免哈希冲突,哈希冲突的情况下写入和读取性能都会受到很大的影响。
但是上面的测试结果表明,大数据量相对比较大的时候,适当的哈希冲突(<8)反而读取效率更高。
个人猜测是,适当的哈希冲突,数组长度大为减少。
为了证明以上猜想,直接对ArrayList进行基准测试。
模拟一个哈希冲突非常严重下,底层数组长度较小的list,和哈希冲突不严重情况下,底层数组较大的list,再随机测试Get的效率如何。
点击查看测试代码
测试结果如下:
可以看到,这里不能(有误,待重测)间接证实了以上的猜想。
当然这里的代码可能并不严谨,也欢迎大家一起讨论。
测试结果说明:在jdk8,无冲突效率是有有冲突的3倍左右。
测试结果说明:在jdk7,无冲突效率是有有冲突的12倍左右。
结合4.1和4.2的测试对比,说明jdk1.8红黑树的优化效率确实提升很大。
1.初始化的时候指定长度,长度要考虑到负载因子0.75.初始化的影响受到哈希冲突的影响,没有那么大(相对于倍数而言),但也不小。
2.哈希冲突严重时,put性能急剧下降。(几十倍级)
3.相同元素个数的前提下,在哈希冲突时,get效率反而更高。
4.相比之前的版本,哈希冲突严重时,jdk8红黑树对get效率有非常大的提升。
测试代码和测试结果在 这里
苍茫之天涯,乃吾辈之所爱也;浩瀚之程序,亦吾之所爱也,然则何时而爱耶?必曰:先天下之忧而忧,后天下之爱而爱也!
页面更新:2024-04-02
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号