分析Java中Map的遍歷性能問題
一、引言
我們知道java HashMap的擴(kuò)容是有成本的,為了減少擴(kuò)容的次數(shù)和成本,可以給HashMap設(shè)置初始容量大小,如下所示:
HashMap<string, integer=""> map0 = new HashMap<string, integer="">(100000);
但是在實(shí)際使用的過程中,發(fā)現(xiàn)性能不但沒有提升,反而顯著下降了!代碼里對(duì)HashMap的操作也只有遍歷了,看來是遍歷出了問題,于是做了一番測(cè)試,得到如下結(jié)果:
HashMap的迭代器遍歷性能與 initial capacity 有關(guān),與size無關(guān)
二、迭代器測(cè)試
貼上測(cè)試代碼:
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() + " 耗時(shí): " + (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); } }
這是運(yùn)行結(jié)果:
我們將第一個(gè)Map初始化10w大小,第二個(gè)map不指定大小(實(shí)際16),兩個(gè)存儲(chǔ)相同的數(shù)據(jù),但是用迭代器遍歷100次的時(shí)候發(fā)現(xiàn)性能迥異,一個(gè)36ms一個(gè)4ms,實(shí)際上性能差距更大,這里的4ms是600次System.out.print的耗時(shí),這里將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 }
輸出結(jié)果如下:
可以發(fā)現(xiàn)第二個(gè)map耗時(shí)幾乎為0,第一個(gè)達(dá)到了28ms,遍歷期間沒有進(jìn)行任何操作,既然石錘了和 initial capacity 有關(guān),下一步我們?nèi)タ纯礊槭裁磿?huì)這樣,找找Map迭代器的源碼看看。
三、迭代器源碼探究
我們來看看Map.entrySet().iterator()
的源碼;
public final Iterator<map.entry<k,v>> iterator() { return new EntryIterator(); }
其中EntryIterator是HashMap的內(nèi)部抽象類,源碼并不多,我全部貼上來并附上中文注釋
abstract class HashIterator { // 下一個(gè)Node Node<k,v> next; // next entry to return // 當(dāng)前Node Node<k,v> current; // current entry // 預(yù)期的Map大小,也就是說每個(gè)HashMap可以有多個(gè)迭代器(每次調(diào)用 iterator() 會(huì)new 一個(gè)迭代器出來),但是只能有一個(gè)迭代器對(duì)他remove,否則會(huì)直接報(bào)錯(cuò)(快速失敗) int expectedModCount; // for fast-fail // 當(dāng)前節(jié)點(diǎn)所在的數(shù)組下標(biāo),HashMap內(nèi)部是使用數(shù)組來存儲(chǔ)數(shù)據(jù)的,不了解的先去看看HashMap的源碼吧 int index; // current slot HashIterator() { // 初始化 expectedModCount expectedModCount = modCount; // 淺拷貝一份Map的數(shù)據(jù) Node<k,v>[] t = table; current = next = null; index = 0; // 如果 Map 中數(shù)據(jù)不為空,遍歷數(shù)組找到第一個(gè)實(shí)際存儲(chǔ)的素,賦值給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; // 定義一個(gè)e指存儲(chǔ)next,并在找到下一值時(shí)返它自己 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; } /** * 刪除元素,這里不講了,調(diào)的是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; } }
上面的代碼一看就明白了,迭代器每次尋找下一個(gè)元素都會(huì)去遍歷數(shù)組,如果 initial capacity
特別大的話,也就是說 threshold
也大,table.length
就大,所以遍歷比較耗性能。
table數(shù)組的大小設(shè)置是在resize()方法里:
Node<k,v>[] newTab = (Node<k,v>[])new Node[newCap]; table = newTab;
四、其他遍歷方法
注意代碼里我們用的是Map.entrySet().iterator()
,實(shí)際上和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(); } }
這兩個(gè)就不分析了,性能一樣。
實(shí)際使用中對(duì)集合的遍歷還有幾種方法:
- 普通for循環(huán)+下標(biāo)
- 增強(qiáng)型for循環(huán)
- Map.forEach
- Stream.forEach
普通for循環(huán)+下標(biāo)的方法不適用于Map,這里不討論了。
4.1、增強(qiáng)型for循環(huán)
增強(qiáng)行for循環(huán)實(shí)際上是通過迭代器來實(shí)現(xiàn)的,我們來看兩者的聯(lián)系
源碼:
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()); } }
編譯后的字節(jié)碼:
// 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
都不用耐心觀察,兩個(gè)方法的字節(jié)碼除了局部變量不一樣其他都幾乎一樣,由此可以得出增強(qiáng)型for循環(huán)性能與迭代器一樣,實(shí)際運(yùn)行結(jié)果也一樣,我不展示了,感興趣的自己去copy文章開頭和結(jié)尾的代碼試下。
4.2、Map.forEach
先說一下為什么不把各種方法一起運(yùn)行同時(shí)打印性能,這是因?yàn)镃PU緩存的原因和JVM的一些優(yōu)化會(huì)干擾到性能的判斷,附錄全部測(cè)試結(jié)果有說明
直接來看源碼吧
@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(); } }
很簡(jiǎn)短的源碼,就不打注釋了,從源碼我們不難獲取到以下信息:
- 該方法也是快速失敗的,遍歷期間不能刪除元素
- 需要遍歷整個(gè)數(shù)組
- BiConsumer加了@FunctionalInterface注解,用了 lambda
第三點(diǎn)和性能無關(guān),這里只是提下
通過以上信息我們能確定這個(gè)性能與table數(shù)組的大小有關(guān)。
但是在實(shí)際測(cè)試的時(shí)候卻發(fā)現(xiàn)性能比迭代器差了不少:
4.3、Stream.forEach
Stream與Map.forEach的共同點(diǎn)是都使用了lambda表達(dá)式。但兩者的源碼沒有任何復(fù)用的地方。
不知道你有沒有看累,先上測(cè)試結(jié)果吧:
耗時(shí)比Map.foreach還要高點(diǎn)。
下面講講Straam.foreach順序流的源碼,這個(gè)也不復(fù)雜,不過累的話先去看看總結(jié)吧。
Stream.foreach的執(zhí)行者是分流器,HashMap的分流器源碼就在HashMap類中,是一個(gè)靜態(tài)內(nèi)部類,類名叫 EntrySpliterator
下面是順序流執(zhí)行的方法
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(); } }
從以上源碼中我們也可以輕易得出遍歷需要順序掃描所有數(shù)組
五、總結(jié)
至此,Map的四種遍歷方法都測(cè)試完了,我們可以簡(jiǎn)單得出兩個(gè)結(jié)論
- Map的遍歷性能與內(nèi)部table數(shù)組大小有關(guān),也就是說與常用參數(shù) initial capacity 有關(guān),不管哪種遍歷方式都是的
- 性能(由高到低):迭代器 == 增強(qiáng)型For循環(huán) > Map.forEach > Stream.foreach
這里就不說什么多少倍多少倍的性能差距了,拋開數(shù)據(jù)集大小都是扯淡,當(dāng)我們不指定initial capacity的時(shí)候,四種遍歷方法耗時(shí)都是3ms,這3ms還是輸入輸出流的耗時(shí),實(shí)際遍歷耗時(shí)都是0,所以數(shù)據(jù)集不大的時(shí)候用哪種都無所謂,就像不加輸入輸出流耗時(shí)不到1ms一樣,很多時(shí)候性能消耗是在遍歷中的業(yè)務(wù)操作,這篇文章不是為了讓你去優(yōu)化代碼把foreach改成迭代器的,在大多數(shù)場(chǎng)景下并不需要關(guān)注迭代本身的性能,Stream與Lambda帶來的可讀性提升更加重要。
所以此文的目的就當(dāng)是知識(shí)拓展吧,除了以上說到的遍歷性能問題,你還應(yīng)該從中能獲取到的知識(shí)點(diǎn)有:
- HashMap的數(shù)組是存儲(chǔ)在table數(shù)組里的
- table數(shù)組是resize方法初始化的,new Map不會(huì)初始化數(shù)組
- Map遍歷是table數(shù)組從下標(biāo)0遞增排序的,所以他是無序的
- keySet().iterator,values.iterator, entrySet.iterator 來說沒有本質(zhì)區(qū)別,用的都是同一個(gè)迭代器
- 各種遍歷方法里,只有迭代器可以remove,雖然增強(qiáng)型for循環(huán)底層也是迭代器,但這個(gè)語法糖隱藏了 remove 方法
- 每次調(diào)用迭代器方法都會(huì)new 一個(gè)迭代器,但是只有一個(gè)可以修改
- Map.forEach與Stream.forEach看上去一樣,實(shí)際實(shí)現(xiàn)是不一樣的
附:四種遍歷源碼
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()); }); }
附:完整測(cè)試類與測(cè)試結(jié)果+一個(gè)奇怪的問題
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() + " 迭代器 耗時(shí): " + (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() + " 增強(qiáng)型For 耗時(shí): " + (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 耗時(shí): " + (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 耗時(shí): " + (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); } }
測(cè)試結(jié)果:
如果你認(rèn)真看了上面的文章的話,會(huì)發(fā)現(xiàn)測(cè)試結(jié)果有個(gè)不對(duì)勁的地方:
MapStreamForeach的耗時(shí)似乎變少了
我可以告訴你這不是數(shù)據(jù)的原因,從我的測(cè)試測(cè)試結(jié)果來看,直接原因是因?yàn)橄葓?zhí)行了 Map.foreach,如果你把 MapForeach 和 MapStreamForeach 調(diào)換一下執(zhí)行順序,你會(huì)發(fā)現(xiàn)后執(zhí)行的那個(gè)耗時(shí)更少。
以上就是分析Java中Map的遍歷性能問題的詳細(xì)內(nèi)容,更多關(guān)于Java Map 遍歷性能的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
SpringBoot 統(tǒng)一請(qǐng)求返回的實(shí)現(xiàn)
這篇文章主要介紹了SpringBoot 統(tǒng)一請(qǐng)求返回的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07mybatis-plus分頁查詢的實(shí)現(xiàn)示例
這篇文章主要介紹了mybatis-plus分頁查詢的實(shí)現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08Java實(shí)現(xiàn)文件名倒序排序的技術(shù)指南
在實(shí)際開發(fā)過程中,我們經(jīng)常需要對(duì)文件進(jìn)行操作和處理,一個(gè)常見的需求是按文件名倒序排列文件列表,以便于文件的管理和查找,本文將介紹如何在Java中實(shí)現(xiàn)文件名倒序排序,并提供詳細(xì)的代碼案例,需要的朋友可以參考下2024-08-08spring boot task實(shí)現(xiàn)動(dòng)態(tài)創(chuàng)建定時(shí)任務(wù)的方法
這篇文章主要介紹了spring boot task實(shí)現(xiàn)動(dòng)態(tài)創(chuàng)建定時(shí)任務(wù),小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-01-01