jdk源码分析之HashMap--遍历性能知多少?

注：以下代码分析基于jdk1.7

分析了两篇HashMap中并发导致的线程安全问题，这一篇将详细的描述一下HashMap遍历的性能相关的问题。

使用过HashMap的相比也都操作过遍历元素，常用的也就是keySet()和entrySet()方式，今天就这两种方式展开话题，首先提出几个问题：

1. 哪一种遍历方式性能比较好？
2. 为什么此种方式性能好？

很多人甚至很多网上的资料认为使用entrySet()遍历HashMap中的元素性能比较好，是真的吗？还是先写段代码试一下：

这段代码的意思是生成一个HashMap然后使用keySet()和entrySet()两种方式遍历并打印耗时。把capacity设定不同的值，运行对比：

1. capacity=1000，运行结果如下

可以看到基本一致。

1. 设定capacity=10000，运行结果如下

可以看到keyset比entryset耗时多了一倍。

1. 把capacity=100000，运行结果如下

同样，keyset耗时差不多也是entryset的两倍。

理论上我们可以得出entryset遍历方式比keyset性能要好，那为什么性能要好？简单粗暴，不妨我们分析一下HashMap中的entrySet和keySet是先方式：

1. entrySet()代码

可以看出第一次调用entrySet的时候是生成了一个EntrySet,我们测试代码中用得的增强for循环(jdk1.5引入),其本质就是调用iterator(),所以遍历的时候是调用EntrySet中的iterator方法,看一下newEntryIterator实现 Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } 接着看EntryIterator() private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } } 可以看出需要使用HashIterator自带的无参构造器和nextEntry方法,接着看HashIterator实现

第一个红框是要用到的无参构造器，意思是把next指针指向table数组中第一个不为null的Entry节点，并把index变成该节点在table中的索引位置；第二个红框是我们遍历过程中要用到的，也就是遍历下一个元素，代码中表达的意思是如果e.next(先赋值给next)不为空，也就是table中该index位置没有链表结构，那就直接将next指针指向table中的下一个非null位置，index改为该位置索引，然后返回e(此时e已经指向移动table位置后的next)，如果if中不成立，说明e.next不为空,这时的next指向e所在链表的下一个节点，直接返回。 总结得出，entrySet方式遍历其实是table中Entry节点的移动，也就是以Entry节点为粒度。

1. 我们再看一下keySet的代码

同样，第一次调用entrySet的时候是生成了一个KeySet,我们测试代码中用得的增强for循环其实就是遍历的时候调用KeySet中的iterator方法,看一下newKeyIterator实现 Iterator<K> newKeyIterator() { return new KeyIterator(); } 然后再看KeyIterator private final class KeyIterator extends HashIterator<K> { public K next() { return nextEntry().getKey(); } } 同样可以看出需要使用HashIterator自带的无参构造器和nextEntry方法,接着看HashIterator实现。但是不同的地方这里调用nextEntry()得到一个Entry然后获取Entry中存放的key，也就是说和1中相比，按照1中的方式移动Entry节点后再获取节点内容。

我们可以看出1和2步骤的分析，并没有在遍历过程中使性能发生分化的代码，但是上边的例子中很明显entrySet方式性能更好一些，为什么呢？

回到文章开始我们的测试代码中，看到for循环中遍历有一些区别：

可以看到entryset方式中，执行了Entry节点移动，然后获取key和value；

然而keyset方式中走了Entry节点移动之后，执行了map.get()。哦，恍然大悟，原来性能差异是在这里产生的，因为get操作要hash映射得到table中索引位置，然后在该位置链表中查找key对应的节点，for循环多少次，get执行了多少次，所以遍历的时候比entryset方式慢，也解释的通了。

或许这时候，我们就可以下结论说，entryset遍历HashMap比keyset方式块，是这样吗？按照文章开始的测试代码，我们设置capacity = 1000000(一百万)，再次运行代码，看到如下结果：

我去，为什么这时候突然entryset方式一下子变慢了，并且性能急剧下降，到底是为什么？

遇到这种问题，我们暂且不要漫无目的的着急，不放假设一下可能的情况：

1. entryset比keyset性能好，难道是有条件的，只是在HashMap大小有限的情况下才生效？
2. 是不是jvm自身的机制，在HashMap很大的情况下做了什么限制？
3. 还是有其他什么原因？

仔细考虑了一下，怀疑是不是垃圾回收导致的，打开gc日志，重新运行测试代码，看到如下结果：

密密麻麻看不太懂，但是隐隐约约看到entryset遍历时候出现了Full GC，对jvm底层不是很熟悉，但是我知道Full GC的时候会出现jvm卡顿，也就是回收过程中是线程阻塞的，只有Full GC结束后，其他线程才恢复工作。

明白了，原来我们的数据量过大，在StringBuilder拼接的过程中导致jvm出现了Full GC，那我们如果继续验证capacity = 1000000情况下，entryset性能比keyset高呢？

很简单，我们调整jvm启动参数，增加启动内存：

然后我们再运行测试代码，可以看到以下运行结果：

终于，又看到了我们期待的结果。这次我们可以下结论了，也就是抛开业务层面的需求，遍历HashMap的常用两种方式，entrySet肯定是优于keySet的。

此篇我们根据jdk1.7源码通过实例介绍了HashMap常见的两种遍历方式，并进行了性能对比分析，以及中间遇到的一些问题，后边会继续对jdk源码做分析，若带来帮助，荣幸至极！