一、引言
我们知道java hashmap的扩容是有成本的，为了减少扩容的次数和成本，可以给hashmap设置初始容量大小，如下所示：
|
1 |
hashmap<string, integer= "" > map0 = new hashmap<string, integer= "" >( 100000 ); |
但是在实际使用的过程中，发现性能不但没有提升，反而显著下降了！代码里对hashmap的操作也只有遍历了，看来是遍历出了问题，于是做了一番测试，得到如下结果：
hashmap的迭代器遍历性能与 initial capacity 有关，与size无关
二、迭代器测试
贴上测试代码：
|
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 |
public class mapforeachtest {
public static void main(string[] args) { hashmap<string, integer= "" > map0 = new hashmap<string, integer= "" >( 100000 );
initdataandprint(map0);
hashmap<string, integer= "" > map1 = new hashmap<string, integer= "" >();
initdataandprint(map1);
}
private static void initdataandprint(hashmap map) {
initdata(map);
long start = system.currenttimemillis();
for ( int i = 0 ; i < 100 ; i++) { foreach(map); } long end = system.currenttimemillis(); system.out.println( "" ); system.out.println( "hashmap size: " + map.size() + " 耗时: " + (end - start) + " ms" ); }
private static void foreach(hashmap map) { for (iterator<map.entry<string, integer= "" >> it = map.entryset().iterator(); it.hasnext();){ map.entry<string, integer= "" > item = it.next(); system.out.print(item.getkey()); // do something }
}
private static void initdata(hashmap map) { map.put( "a" , 0 ); map.put( "b" , 1 ); map.put( "c" , 2 ); map.put( "d" , 3 ); map.put( "e" , 4 ); map.put( "f" , 5 ); }
} |
这是运行结果：
我们将第一个map初始化10w大小，第二个map不指定大小(实际16)，两个存储相同的数据，但是用迭代器遍历100次的时候发现性能迥异，一个36ms一个4ms，实际上性能差距更大，这里的4ms是600次system.out.print的耗时，这里将print注掉再试下
|
1 2 3 4 5 |
for (iterator<map.entry<string, integer= "" >> it = map.entryset().iterator(); it.hasnext();){ map.entry<string, integer= "" > item = it.next(); // system.out.print(item.getkey()); // do something } |
输出结果如下：
可以发现第二个map耗时几乎为0，第一个达到了28ms，遍历期间没有进行任何操作，既然石锤了和 initial capacity 有关，下一步我们去看看为什么会这样，找找map迭代器的源码看看。
三、迭代器源码探究
我们来看看 map.entryset().iterator() 的源码；
|
1 2 3 |
public final iterator<map.entry<k,v>> iterator() { return new entryiterator(); } |
其中entryiterator是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 |
abstract class hashiterator { // 下一个node node<k,v> next; // next entry to return // 当前node node<k,v> current; // current entry // 预期的map大小，也就是说每个hashmap可以有多个迭代器(每次调用 iterator() 会new 一个迭代器出来)，但是只能有一个迭代器对他remove，否则会直接报错(快速失败) int expectedmodcount; // for fast-fail
// 当前节点所在的数组下标，hashmap内部是使用数组来存储数据的，不了解的先去看看hashmap的源码吧 int index; // current slot
hashiterator() { // 初始化 expectedmodcount expectedmodcount = modcount; // 浅拷贝一份map的数据 node<k,v>[] t = table; current = next = null ; index = 0 ; // 如果 map 中数据不为空，遍历数组找到第一个实际存储的素，赋值给next if (t != null && size > 0 ) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null ); } }
public final boolean hasnext() { return next != null ; }
final node<k,v> nextnode() { // 用来浅拷贝table，和别名的作用差不多，没啥用 node<k,v>[] t; // 定义一个e指存储next，并在找到下一值时返它自己 node<k,v> e = next; if (modcount != expectedmodcount) throw new concurrentmodificationexception(); if (e == null ) throw new nosuchelementexception();
// 使current指向e，也就是next，这次要找的值，并且让next = current.next，一般为null if ((next = (current = e).next) == null && (t = table) != null ) { do {} while (index < t.length && (next = t[index++]) == null ); } return e; }
/** * 删除元素，这里不讲了，调的是hashmap的removenode，没啥特别的 **/ public final void remove() { node<k,v> p = current; if (p == null ) throw new illegalstateexception(); if (modcount != expectedmodcount) throw new concurrentmodificationexception(); current = null ; k key = p.key; removenode(hash(key), key, null , false , false ); // 用来保证快速失败的 expectedmodcount = modcount; } } |
上面的代码一看就明白了，迭代器每次寻找下一个元素都会去遍历数组，如果 initial capacity 特别大的话，也就是说 threshold 也大， table.length 就大，所以遍历比较耗性能。
table数组的大小设置是在resize()方法里：
|
1 2 |
node<k,v>[] newtab = (node<k,v>[]) new node[newcap]; table = newtab; |
四、其他遍历方法
注意代码里我们用的是 map.entryset().iterator() ，实际上和 keys().iterator() , values().iterator() 一样，源码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
final class keyiterator extends hashiterator implements iterator<k> { public final k next() { return nextnode().key; } }
final class valueiterator extends hashiterator implements iterator<v> { public final v next() { return nextnode().value; } }
final class entryiterator extends hashiterator implements iterator<map.entry<k,v>> { public final map.entry<k,v> next() { return nextnode(); } } |
这两个就不分析了，性能一样。
实际使用中对集合的遍历还有几种方法：
普通for循环+下标 增强型for循环 map.foreach stream.foreach普通for循环+下标的方法不适用于map，这里不讨论了。
4.1、增强型for循环
增强行for循环实际上是通过迭代器来实现的，我们来看两者的联系
源码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
private static void foreach(hashmap map) { for (iterator<map.entry<string, integer= "" >> it = map.entryset().iterator(); it.hasnext();){ map.entry<string, integer= "" > item = it.next(); system.out.print(item.getkey()); // do something } }
private static void foreach0(hashmap<string, integer= "" > map) { for (map.entry entry : map.entryset()) { system.out.print(entry.getkey()); } } |
编译后的字节码：
|
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 |
// access flags 0xa private static foreach(ljava/util/hashmap;)v l0 linenumber 41 l0 aload 0 invokevirtual java/util/hashmap.entryset ()ljava/util/set; invokeinterface java/util/set.iterator ()ljava/util/iterator; (itf) astore 1 l1 frame append [java/util/iterator] aload 1 invokeinterface java/util/iterator.hasnext ()z (itf) ifeq l2 l3 linenumber 42 l3 aload 1 invokeinterface java/util/iterator.next ()ljava/lang/object; (itf) checkcast java/util/map$entry astore 2 l4 linenumber 43 l4 getstatic java/lang/system.out : ljava/io/printstream; aload 2 invokeinterface java/util/map$entry.getkey ()ljava/lang/object; (itf) checkcast java/lang/string invokevirtual java/io/printstream.print (ljava/lang/string;)v l5 linenumber 45 l5 goto l1 l2 linenumber 46 l2 frame chop 1 return l6 localvariable item ljava/util/map$entry; l4 l5 2 // signature ljava/util/map$entry<ljava lang="" string;ljava="" integer;="">; // declaration: item extends java.util.map$entry<java.lang.string, java.lang.integer=""> localvariable it ljava/util/iterator; l1 l2 1 // signature ljava/util/iterator<ljava util="" map$entry<ljava="" lang="" string;ljava="" integer;="">;>; // declaration: it extends java.util.iterator<java.util.map$entry<java.lang.string, java.lang.integer="">> localvariable map ljava/util/hashmap; l0 l6 0 maxstack = 2 maxlocals = 3
// access flags 0xa // signature (ljava/util/hashmap<ljava lang="" string;ljava="" integer;="">;)v // declaration: void foreach0(java.util.hashmap<java.lang.string, java.lang.integer="">) private static foreach0(ljava/util/hashmap;)v l0 linenumber 50 l0 aload 0 invokevirtual java/util/hashmap.entryset ()ljava/util/set; invokeinterface java/util/set.iterator ()ljava/util/iterator; (itf) astore 1 l1 frame append [java/util/iterator] aload 1 invokeinterface java/util/iterator.hasnext ()z (itf) ifeq l2 aload 1 invokeinterface java/util/iterator.next ()ljava/lang/object; (itf) checkcast java/util/map$entry astore 2 l3 linenumber 51 l3 getstatic java/lang/system.out : ljava/io/printstream; aload 2 invokeinterface java/util/map$entry.getkey ()ljava/lang/object; (itf) invokevirtual java/io/printstream.print (ljava/lang/object;)v l4 linenumber 52 l4 goto l1 l2 linenumber 53 l2 frame chop 1 return l5 localvariable entry ljava/util/map$entry; l3 l4 2 localvariable map ljava/util/hashmap; l0 l5 0 // signature ljava/util/hashmap<ljava lang="" string;ljava="" integer;="">; // declaration: map extends java.util.hashmap<java.lang.string, java.lang.integer=""> maxstack = 2 maxlocals = 3 |
都不用耐心观察，两个方法的字节码除了局部变量不一样其他都几乎一样，由此可以得出增强型for循环性能与迭代器一样，实际运行结果也一样，我不展示了，感兴趣的自己去copy文章开头和结尾的代码试下。
4.2、map.foreach
先说一下为什么不把各种方法一起运行同时打印性能，这是因为cpu缓存的原因和jvm的一些优化会干扰到性能的判断，附录全部测试结果有说明
直接来看源码吧
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
@override public void foreach(biconsumer<!--? super k, ? super v--> action) { node<k,v>[] tab; if (action == null ) throw new nullpointerexception(); if (size > 0 && (tab = table) != null ) { int mc = modcount; for ( int i = 0 ; i < tab.length; ++i) { for (node<k,v> e = tab[i]; e != null ; e = e.next) action.accept(e.key, e.value); } if (modcount != mc) throw new concurrentmodificationexception(); } } |
很简短的源码，就不打注释了，从源码我们不难获取到以下信息：
该方法也是快速失败的，遍历期间不能删除元素 需要遍历整个数组 biconsumer加了@functionalinterface注解，用了 lambda第三点和性能无关，这里只是提下
通过以上信息我们能确定这个性能与table数组的大小有关。
但是在实际测试的时候却发现性能比迭代器差了不少：
4.3、stream.foreach
stream与map.foreach的共同点是都使用了lambda表达式。但两者的源码没有任何复用的地方。
不知道你有没有看累，先上测试结果吧：
耗时比map.foreach还要高点。
下面讲讲straam.foreach顺序流的源码，这个也不复杂，不过累的话先去看看总结吧。
stream.foreach的执行者是分流器，hashmap的分流器源码就在hashmap类中，是一个静态内部类，类名叫 entryspliterator
下面是顺序流执行的方法
|
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 |
public void foreachremaining(consumer<!--? super map.entry<k,v-->> action) { int i, hi, mc; if (action == null ) throw new nullpointerexception(); hashmap<k,v> m = map; node<k,v>[] tab = m.table; if ((hi = fence) < 0 ) { mc = expectedmodcount = m.modcount; hi = fence = (tab == null ) ? 0 : tab.length; } else mc = expectedmodcount; if (tab != null && tab.length >= hi && (i = index) >= 0 && (i < (index = hi) || current != null )) { node<k,v> p = current; current = null ; do { if (p == null ) p = tab[i++]; else { action.accept(p); p = p.next; } } while (p != null || i < hi); if (m.modcount != mc) throw new concurrentmodificationexception(); } } |
从以上源码中我们也可以轻易得出遍历需要顺序扫描所有数组
五、总结
至此，map的四种遍历方法都测试完了，我们可以简单得出两个结论
map的遍历性能与内部table数组大小有关，也就是说与常用参数 initial capacity 有关，不管哪种遍历方式都是的 性能（由高到低）：迭代器 == 增强型for循环 > map.foreach > stream.foreach这里就不说什么多少倍多少倍的性能差距了，抛开数据集大小都是扯淡，当我们不指定initial capacity的时候，四种遍历方法耗时都是3ms，这3ms还是输入输出流的耗时，实际遍历耗时都是0，所以数据集不大的时候用哪种都无所谓，就像不加输入输出流耗时不到1ms一样，很多时候性能消耗是在遍历中的业务操作，这篇文章不是为了让你去优化代码把foreach改成迭代器的，在大多数场景下并不需要关注迭代本身的性能，stream与lambda带来的可读性提升更加重要。
所以此文的目的就当是知识拓展吧，除了以上说到的遍历性能问题，你还应该从中能获取到的知识点有：
hashmap的数组是存储在table数组里的 table数组是resize方法初始化的，new map不会初始化数组 map遍历是table数组从下标0递增排序的，所以他是无序的 keyset().iterator，values.iterator， entryset.iterator 来说没有本质区别，用的都是同一个迭代器 各种遍历方法里，只有迭代器可以remove，虽然增强型for循环底层也是迭代器，但这个语法糖隐藏了 remove 方法 每次调用迭代器方法都会new 一个迭代器，但是只有一个可以修改 map.foreach与stream.foreach看上去一样，实际实现是不一样的附：四种遍历源码
|
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 |
private static void foreach(hashmap map) { for (iterator<map.entry<string, integer= "" >> it = map.entryset().iterator(); it.hasnext();){ map.entry<string, integer= "" > item = it.next(); // system.out.print(item.getkey()); // do something } }
private static void foreach0(hashmap<string, integer= "" > map) { for (map.entry entry : map.entryset()) { system.out.print(entry.getkey()); } }
private static void foreach1(hashmap<string, integer= "" > map) { map.foreach((key, value) -> { system.out.print(key); });
}
private static void foreach2(hashmap<string, integer= "" > map) { map.entryset().stream().foreach(e -> { system.out.print(e.getkey()); });
} |
附：完整测试类与测试结果+一个奇怪的问题
|
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 |
public class mapforeachtest {
public static void main(string[] args) { hashmap<string, integer= "" > map0 = new hashmap<string, integer= "" >( 100000 ); hashmap<string, integer= "" > map1 = new hashmap<string, integer= "" >(); initdata(map0); initdata(map1);
testiterator(map0); testiterator(map1); testfor(map0); testfor(map1); testmapforeach(map0); testmapforeach(map1); testmapstreamforeach(map0); testmapstreamforeach(map1);
}
private static void testiterator(hashmap map) {
long start = system.currenttimemillis();
for ( int i = 0 ; i < 100 ; i++) { foreach(map); } long end = system.currenttimemillis(); system.out.println( "" ); system.out.println( "hashmap size: " + map.size() + " 迭代器 耗时: " + (end - start) + " ms" ); }
private static void testfor(hashmap map) {
long start = system.currenttimemillis();
for ( int i = 0 ; i < 100 ; i++) { foreach0(map); } long end = system.currenttimemillis(); system.out.println( "" ); system.out.println( "hashmap size: " + map.size() + " 增强型for 耗时: " + (end - start) + " ms" ); }
private static void testmapforeach(hashmap map) {
long start = system.currenttimemillis();
for ( int i = 0 ; i < 100 ; i++) { foreach1(map); } long end = system.currenttimemillis(); system.out.println( "" ); system.out.println( "hashmap size: " + map.size() + " mapforeach 耗时: " + (end - start) + " ms" ); }
private static void testmapstreamforeach(hashmap map) {
long start = system.currenttimemillis();
for ( int i = 0 ; i < 100 ; i++) { foreach2(map); } long end = system.currenttimemillis(); system.out.println( "" ); system.out.println( "hashmap size: " + map.size() + " mapstreamforeach 耗时: " + (end - start) + " ms" ); }
private static void foreach(hashmap map) { for (iterator<map.entry<string, integer= "" >> it = map.entryset().iterator(); it.hasnext();){ map.entry<string, integer= "" > item = it.next(); system.out.print(item.getkey()); // do something } }
private static void foreach0(hashmap<string, integer= "" > map) { for (map.entry entry : map.entryset()) { system.out.print(entry.getkey()); } }
private static void foreach1(hashmap<string, integer= "" > map) { map.foreach((key, value) -> { system.out.print(key); });
}
private static void foreach2(hashmap<string, integer= "" > map) { map.entryset().stream().foreach(e -> { system.out.print(e.getkey()); });
}
private static void initdata(hashmap map) { map.put( "a" , 0 ); map.put( "b" , 1 ); map.put( "c" , 2 ); map.put( "d" , 3 ); map.put( "e" , 4 ); map.put( "f" , 5 ); }
} |
测试结果：
如果你认真看了上面的文章的话，会发现测试结果有个不对劲的地方：
mapstreamforeach的耗时似乎变少了
我可以告诉你这不是数据的原因，从我的测试测试结果来看，直接原因是因为先执行了 map.foreach，如果你把 mapforeach 和 mapstreamforeach 调换一下执行顺序，你会发现后执行的那个耗时更少。
以上就是分析java中map的遍历性能问题的详细内容，更多关于java map 遍历性能的资料请关注其它相关文章！
原文链接：https://www.cnblogs.com/lifan1998/p/14864021.html
查看更多关于分析Java中Map的遍历性能问题的详细内容...