主要介绍HashMap的四种循环遍历方式，各种方式的性能测试对比，根据HashMap的源码实现分析性能结果，总结结论。
1. Map的四种遍历方式
下面只是简单介绍各种遍历示例(以HashMap为例)，各自优劣会在本文后面进行分析给出结论。
(1) for each map.entrySet()
|
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()的集合迭代器
|
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获取
|
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()
|
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各种遍历方式所花费的时间。
|
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 |
package cn.trinea.java.test; import java.text.DecimalFormat; import java.util.Calendar; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; import java.util.Set; /** * JavaLoopTest * * @author www.trinea.cn 2013-10-28 */ public class JavaLoopTest { public static void main(String[] args) { System.out.print("compare loop performance of HashMap"); loopMapCompare(getHashMaps(10000, 100000, 1000000, 2000000)); } public static Map<String, String>[] getHashMaps(int... sizeArray) { Map<String, String>[] mapArray = new HashMap[sizeArray.length]; for (int i = 0; i < sizeArray.length; i++) { int size = sizeArray[i]; Map<String, String> map = new HashMap<String, String>(); for (int j = 0; j < size; j++) { String s = Integer.toString(j); map.put(s, s); } mapArray[i] = map; } return mapArray; } public static void loopMapCompare(Map<String, String>[] mapArray) { printHeader(mapArray); long startTime, endTime; // Type 1 for (int i = 0; i < mapArray.length; i++) { Map<String, String> map = mapArray[i]; startTime = Calendar.getInstance().getTimeInMillis(); for (Entry<String, String> entry : map.entrySet()) { entry.getKey(); entry.getValue(); } endTime = Calendar.getInstance().getTimeInMillis(); printCostTime(i, mapArray.length, "for each entrySet", endTime - startTime); } // Type 2 for (int i = 0; i < mapArray.length; i++) { Map<String, String> map = mapArray[i]; startTime = Calendar.getInstance().getTimeInMillis(); Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<String, String> entry = iterator.next(); entry.getKey(); entry.getValue(); } endTime = Calendar.getInstance().getTimeInMillis(); printCostTime(i, mapArray.length, "for iterator entrySet", endTime - startTime); } // Type 3 for (int i = 0; i < mapArray.length; i++) { Map<String, String> map = mapArray[i]; startTime = Calendar.getInstance().getTimeInMillis(); for (String key : map.keySet()) { map.get(key); } endTime = Calendar.getInstance().getTimeInMillis(); printCostTime(i, mapArray.length, "for each keySet", endTime - startTime); } // Type 4 for (int i = 0; i < mapArray.length; i++) { Map<String, String> map = mapArray[i]; startTime = Calendar.getInstance().getTimeInMillis(); Set<Entry<String, String>> entrySet = map.entrySet(); for (Entry<String, String> entry : entrySet) { entry.getKey(); entry.getValue(); } endTime = Calendar.getInstance().getTimeInMillis(); printCostTime(i, mapArray.length, "for entrySet=entrySet()", endTime - startTime); } } static int FIRST_COLUMN_LENGTH = 23, OTHER_COLUMN_LENGTH = 12, TOTAL_COLUMN_LENGTH = 71; static final DecimalFormat COMMA_FORMAT = new DecimalFormat("#,###"); public static void printHeader(Map... mapArray) { printRowDivider(); for (int i = 0; i < mapArray.length; i++) { if (i == 0) { StringBuilder sb = new StringBuilder().append("map size"); while (sb.length() < FIRST_COLUMN_LENGTH) { sb.append(" "); } System.out.print(sb); } StringBuilder sb = new StringBuilder().append("| ").append(COMMA_FORMAT.format(mapArray[i].size())); while (sb.length() < OTHER_COLUMN_LENGTH) { sb.append(" "); } System.out.print(sb); } TOTAL_COLUMN_LENGTH = FIRST_COLUMN_LENGTH + OTHER_COLUMN_LENGTH * mapArray.length; printRowDivider(); } public static void printRowDivider() { System.out.println(); StringBuilder sb = new StringBuilder(); while (sb.length() < TOTAL_COLUMN_LENGTH) { sb.append("-"); } System.out.println(sb); } public static void printCostTime(int i, int size, String caseName, long costTime) { if (i == 0) { StringBuilder sb = new StringBuilder().append(caseName); while (sb.length() < FIRST_COLUMN_LENGTH) { sb.append(" "); } System.out.print(sb); } StringBuilder sb = new StringBuilder().append("| ").append(costTime).append(" ms"); while (sb.length() < OTHER_COLUMN_LENGTH) { sb.append(" "); } System.out.print(sb); if (i == size - 1) { printRowDivider(); } } } |
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<K> { public K next() { return nextEntry().getKey(); } } private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } } |
分别是keySet()和entrySet()返回的set的迭代器，从中我们可以看到只是返回值不同而已，父类相同，所以性能相差不多。只是第三种方式多了一步根据key get得到value的操作而已。get的时间复杂度根据hash算法而异，源码如下：
|
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的话，可以直接用
|
1 2 3 4 |
Map<String, String> map = new HashMap<String, String>(); for (String key : map.keySet()) { // key process } |
Null(Ctrl+enter)
楼主分析得很好
微乎其微啊，上百万都感受不到明显差距
泛型数据类型非得是String类型吗？
讲的很细致
不错哦
100百万数据 72 82 74 90 73 79 82 78 76 83 93 70 100 79 80 81 92 100 78 77 86 67 85 78 76 73 72 71 85 81 80 76 59 75 79 95 63 84 79 77总耗时 782 803 802 793 71 64 84 71 84 88 80 78 82 77 83 83 74 93 115 101 73 76 79 70 101 79 78 79 81 62 104 92 80 86 78 60 71 70 85 79 82 83 77 84总耗时 799 778 863 797 69 86 84 87 64 80 75 57 84 60 88 95 75 80 89 89 79 84 79 62 64 62 75 67 102 78 77 96 81 56 78 77 73 77 79 58 79 70 85 83总耗时 770 733 809 771
？
Map的四种遍历方式的结果不合理, 方式 1 2 3 4 78 78 68 86 84 77 79 80 78 86 76 80 86 74 85 79 109 61 69 74 78 56 81 80 74 78 84 81 57 73 76 77 79 84 81 76 85 95 89 94 总耗时 808 762 788 807
m