HashMap循环遍历方式及其性能对比
HashMap循环遍历方式及其性能对比
主要介绍HashMap的四种循环遍历方式，各种方式的性能测试对比，根据HashMap的源码实现分析性能结果，总结结论。
1. Map的四种遍历方式
下面只是简单介绍各种遍历示例(以HashMap为例)，各自优劣会在本文后面进行分析给出结论。
(1) for each map.entrySet()
Java| 1 2 3 4 5 | Map < String , String > map = new HashMap < String , String > ( ) ; for ( Entry < String , String > entry : map . entrySet ( ) ) { entry . getKey ( ) ; entry . getValue ( ) ; } |
(2) 显示调用map.entrySet()的集合迭代器
Java| 1 2 3 4 5 6 | Iterator < Map . Entry < String , String >> iterator = map . entrySet ( ) . iterator ( ) ; while ( iterator . hasNext ( ) ) { Map . Entry < String , String > entry = iterator . next ( ) ; entry . getKey ( ) ; entry . getValue ( ) ; } |
(3) for each map.keySet()，再调用get获取
Java| 1 2 3 4 | Map < String , String > map = new HashMap < String , String > ( ) ; for ( String key : map . keySet ( ) ) { map . get ( key ) ; } |
(4) for each map.entrySet()，用临时变量保存map.entrySet()
Java| 1 2 3 4 5 | Set < Entry < String , String >> entrySet = map . entrySet ( ) ; for ( Entry < String , String > entry : entrySet ) { entry . getKey ( ) ; entry . getValue ( ) ; } |
在测试前大家可以根据对HashMap的了解，想想上面四种遍历方式哪个性能更优。
2、HashMap四种遍历方式的性能测试及对比
以下是性能测试代码，会输出不同数量级大小的HashMap各种遍历方式所花费的时间。
PS：如果运行报异常in thread “main” java.lang.OutOfMemoryError: Java heap space，请将main函数里面map size的大小减小。
其中getHashMaps函数会返回不同size的HashMap。
loopMapCompare函数会分别用上面的遍历方式1-4去遍历每一个map数组(包含不同大小HashMap)中的HashMap。
print开头函数为输出辅助函数，可忽略。
测试环境为Windows7 32位系统 3.2G双核CPU 4G内存，Java 7，Eclipse -Xms512m -Xmx512m
最终测试结果如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 | compare loop performance of HashMap -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - map size | 10 , 000 | 100 , 000 | 1 , 000 , 000 | 2 , 000 , 000 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - for each entrySet | 2 ms | 6 ms | 36 ms | 91 ms -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - for iterator entrySet | 0 ms | 4 ms | 35 ms | 89 ms -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - for each keySet | 1 ms | 6 ms | 48 ms | 126 ms -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - for entrySet = entrySet ( ) | 1 ms | 4 ms | 35 ms | 92 ms -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - |
表横向为同一遍历方式不同大小HashMap遍历的时间消耗，纵向为同一HashMap不同遍历方式遍历的时间消耗。
PS：由于首次遍历HashMap会稍微多耗时一点，for each的结果稍微有点偏差，将测试代码中的几个Type顺序调换会发现，for each entrySet耗时和for iterator entrySet接近。
3、遍历方式性能测试结果分析
(1) foreach介绍
见：ArrayList和LinkedList的几种循环遍历方式及性能对比分析中介绍。
(2) HashMap遍历方式结果分析
从上面知道for each与显示调用Iterator等价，上表的结果中可以看出除了第三种方式(for each map.keySet())，再调用get获取方式外，其他三种方式性能相当。本例还是hash值散列较好的情况，若散列算法较差，第三种方式会更加耗时。
我们看看HashMap entrySet和keySet的源码
| 1 2 3 4 5 6 7 8 9 10 11 | private final class KeyIterator extends HashIterator |
分别是keySet()和entrySet()返回的set的迭代器，从中我们可以看到只是返回值不同而已，父类相同，所以性能相差不多。只是第三种方式多了一步根据key get得到value的操作而已。get的时间复杂度根据hash算法而异，源码如下：
Java| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | public V get ( Object key ) { if ( key == null ) return getForNullKey ( ) ; Entry < K , V > entry = getEntry ( key ) ; return null == entry ? null : entry . getValue ( ) ; } /** * Returns the entry associated with the specified key in the * HashMap. Returns null if the HashMap contains no mapping * for the key. */ final Entry < K , V > getEntry ( Object key ) { int hash = ( key == null ) ? 0 : hash ( key ) ; for ( Entry < K , V > e = table [ indexFor ( hash , table . length ) ] ; e != null ; e = e . next ) { Object k ; if ( e . hash == hash && ( ( k = e . key ) == key || ( key != null && key . equals ( k ) ) ) ) return e ; } return null ; } |
get的时间复杂度取决于for循环循环次数，即hash算法。
4、结论总结
从上面的分析来看：
a. HashMap的循环，如果既需要key也需要value，直接用
| 1 2 3 4 5 | Map < String , String > map = new HashMap < String , String > ( ) ; for ( Entry < String , String > entry : map . entrySet ( ) ) { entry . getKey ( ) ; entry . getValue ( ) ; } |
即可，foreach简洁易懂。
b. 如果只是遍历key而无需value的话，可以直接用
Java| 1 2 3 4 | Map < String , String > map = new HashMap < String , String > ( ) ; for ( String key : map . keySet ( ) ) { // key process } |
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！