java 8中hashmap的性能提升-mile米乐体育

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

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

class key implements comparable { 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()方法。为了避免过度的gc，我将不可变的key对象缓存了起来，而不是每次都重新开始创建一遍：

class key implements comparable { public class keys { 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]; } }

现在我们可以开始进行测试了。我们的基准测试使用连续的key值来创建了不同的大小的hashmap（10的乘方，从1到1百万）。在测试中我们还会使用key来进行查找，并测量不同大小的hashmap所花费的时间：

import com.google.caliper.param; import com.google.caliper.runner; import com.google.caliper.simplebenchmark; public class mapbenchmark extends simplebenchmark { private hashmap map; @param private int mapsize; @override protected void setup() throws exception { map = new hashmap<>(mapsize); for (int i = 0; i < mapsize;   i) { map.put(keys.of(i), i); } } public void timemapget(int reps) { for (int i = 0; i < reps; i  ) { map.get(keys.of(i % mapsize)); } } }

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

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

class key implements comparable { //... @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系统 上。