引言
今天刷题时遇到了一个很奇怪的问题，我们知道java HashMap的扩容是有成本的，为了减少扩容的次数和成本，可以给HashMap设置初始容量大小，如下所示：
HashMap<String, Integer> map0 = new HashMap<String, Integer>(100000);
但是在实际使用的过程中，发现性能不但没有提升，反而显著下降了！代码里对HashMap的操作也只有遍历了，看来是遍历出了问题，于是做了一番测试，得到如下结果：
- HashMap的迭代器遍历性能与 initial capacity 有关
迭代器测试
贴上测试代码：
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注掉再试下
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()的源码；
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
其中EntryIterator是HashMap的内部抽象类，源码并不多，我全部贴上来并附上中文注释
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()方法里：
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
其他遍历方法
注意代码里我们用的是Map.entrySet().iterator()，实际上和keys().iterator(), values().iterator() 一样，源码如下：
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循环
增强行for循环实际上是通过迭代器来实现的，我们来看两者的联系
源码：
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());
}
}
编译后的字节码：
// 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/lang/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/lang/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/lang/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/lang/Integer;>;
// declaration: map extends java.util.HashMap<java.lang.String, java.lang.Integer>
MAXSTACK = 2
MAXLOCALS = 3
都不用耐心观察，两个方法的字节码除了局部变量不一样其他都几乎一样，由此可以得出增强型for循环性能与迭代器一样，实际运行结果也一样，我不展示了，感兴趣的自己去copy文章开头和结尾的代码试下。
Map.forEach
直接来看源码吧
@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数组的大小有关。
但是在实际测试的时候却发现性能比迭代器差了不少：
其中详细原因等我下期的文章吧，这里不讲了
Stream.forEach
Stream与Map.forEach的共同点是都使用了lambda表达式。但两者的源码没有任何复用的地方。
不知道你有没有看累，先上测试结果吧：
耗时比Map.foreach还要高点。
下面讲讲Straam.foreach顺序流的源码，这个也不复杂，不过累的话先去看看总结吧。
Stream.foreach的执行者是分流器，HashMap的分流器源码就在HashMap类中，是一个静态内部类，类名叫 EntrySpliterator
下面是顺序流执行的方法
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看上去一样，实际实现是不一样的
附：四种遍历源码
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());
});
}
附：完整测试类与测试结果+一个奇怪的问题
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);
}
}
测试结果：
如果你认真看了上面的文章的话，会发现测试结果有个不对劲的地方：
我可以告诉你这不是数据的原因，从我的测试测试结果来看，直接原因是因为先执行了 Map.foreach，如果你把 MapForeach 和 MapStreamForeach 调换一下执行顺序，你会发现后执行的那个耗时更少。 至于这个问题的根本的原因，你有兴趣可以自己探索下，或者等我之后的文章