Pytanie Jak skutecznie iterować po każdym wpisie w "Mapie"?


Jeśli mam obiekt implementujący Map interfejs w Javie i chciałbym przetestować każdą parę w nim zawartą, jaki jest najskuteczniejszy sposób poruszania się po mapie?

Czy kolejność elementów zależy od konkretnej implementacji mapy, którą mam dla interfejsu?


2529
2017-09-05 21:12


pochodzenie


W języku Java 8 przy użyciu wyrażenia Lambda: stackoverflow.com/a/25616206/1503859 - Nitin Mahesh


Odpowiedzi:


Map<String, String> map = ...
for (Map.Entry<String, String> entry : map.entrySet())
{
    System.out.println(entry.getKey() + "/" + entry.getValue());
}

4093
2017-09-05 21:15



Jeśli to zrobisz, to nie zadziała, ponieważ pozycja jest zagnieżdżoną klasą w Mapie. java.sun.com/javase/6/docs/api/java/util/Map.html - ScArcher2
możesz napisać import jako "import java.util.Map.Entry;" i to zadziała. - jjujuma
@Pureferret Jedynym powodem, dla którego możesz chcieć użyć iteratora, jest to, że musisz go wywołać remove metoda. Jeśli tak jest, ta inna odpowiedź pokazuje, jak to zrobić. W przeciwnym razie ulepszona pętla, jak pokazano w powyższej odpowiedzi, jest drogą do zrobienia. - assylias
Uważam, że formularz Map.Entry jest czystszy niż importowanie klasy wewnętrznej do bieżącej przestrzeni nazw. - Josiah Yoder
Zauważ, że możesz użyć map.values() lub map.keySet() jeśli chcesz przechodzić tylko przez wartości lub klucze. - dguay


Aby podsumować inne odpowiedzi i połączyć je z tym, co wiem, znalazłem 10 głównych sposobów, aby to zrobić (patrz poniżej). Napisałem też kilka testów wydajności (zobacz wyniki poniżej). Na przykład, jeśli chcemy znaleźć sumę wszystkich kluczy i wartości mapy, możemy napisać:

  1. Za pomocą iterator i Map.Entry

    long i = 0;
    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry<Integer, Integer> pair = it.next();
        i += pair.getKey() + pair.getValue();
    }
    
  2. Za pomocą dla każdego i Map.Entry

    long i = 0;
    for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
        i += pair.getKey() + pair.getValue();
    }
    
  3. Za pomocą dla każdego z Java 8

    final long[] i = {0};
    map.forEach((k, v) -> i[0] += k + v);
    
  4. Za pomocą zestaw kluczy i dla każdego

    long i = 0;
    for (Integer key : map.keySet()) {
        i += key + map.get(key);
    }
    
  5. Za pomocą zestaw kluczy i iterator

    long i = 0;
    Iterator<Integer> itr2 = map.keySet().iterator();
    while (itr2.hasNext()) {
        Integer key = itr2.next();
        i += key + map.get(key);
    }
    
  6. Za pomocą dla i Map.Entry

    long i = 0;
    for (Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator(); entries.hasNext(); ) {
        Map.Entry<Integer, Integer> entry = entries.next();
        i += entry.getKey() + entry.getValue();
    }
    
  7. Korzystanie z Java 8 Stream API

    final long[] i = {0};
    map.entrySet().stream().forEach(e -> i[0] += e.getKey() + e.getValue());
    
  8. Korzystanie z Java 8 Stream API równolegle

    final long[] i = {0};
    map.entrySet().stream().parallel().forEach(e -> i[0] += e.getKey() + e.getValue());
    
  9. Za pomocą IterableMap z Apache Collections

    long i = 0;
    MapIterator<Integer, Integer> it = iterableMap.mapIterator();
    while (it.hasNext()) {
        i += it.next() + it.getValue();
    }
    
  10. Za pomocą MutableMap kolekcji Eclipse (CS)

    final long[] i = {0};
    mutableMap.forEachKeyValue((key, value) -> {
        i[0] += key + value;
    });
    

Testy perfomance (mode = AverageTime, system = Windows 8.1 64-bit, Intel i7-4790 3,60 GHz, 16 GB)

  1. W przypadku małej mapy (100 elementów) najlepszy jest wynik 0.308

    Benchmark                          Mode  Cnt  Score    Error  Units
    test3_UsingForEachAndJava8         avgt  10   0.308 ±  0.021  µs/op
    test10_UsingEclipseMap             avgt  10   0.309 ±  0.009  µs/op
    test1_UsingWhileAndMapEntry        avgt  10   0.380 ±  0.014  µs/op
    test6_UsingForAndIterator          avgt  10   0.387 ±  0.016  µs/op
    test2_UsingForEachAndMapEntry      avgt  10   0.391 ±  0.023  µs/op
    test7_UsingJava8StreamApi          avgt  10   0.510 ±  0.014  µs/op
    test9_UsingApacheIterableMap       avgt  10   0.524 ±  0.008  µs/op
    test4_UsingKeySetAndForEach        avgt  10   0.816 ±  0.026  µs/op
    test5_UsingKeySetAndIterator       avgt  10   0.863 ±  0.025  µs/op
    test8_UsingJava8StreamApiParallel  avgt  10   5.552 ±  0.185  µs/op
    
  2. W przypadku mapy zawierającej 10000 elementów najlepszy jest wynik 37,606

    Benchmark                           Mode   Cnt  Score      Error   Units
    test10_UsingEclipseMap              avgt   10    37.606 ±   0.790  µs/op
    test3_UsingForEachAndJava8          avgt   10    50.368 ±   0.887  µs/op
    test6_UsingForAndIterator           avgt   10    50.332 ±   0.507  µs/op
    test2_UsingForEachAndMapEntry       avgt   10    51.406 ±   1.032  µs/op
    test1_UsingWhileAndMapEntry         avgt   10    52.538 ±   2.431  µs/op
    test7_UsingJava8StreamApi           avgt   10    54.464 ±   0.712  µs/op
    test4_UsingKeySetAndForEach         avgt   10    79.016 ±  25.345  µs/op
    test5_UsingKeySetAndIterator        avgt   10    91.105 ±  10.220  µs/op
    test8_UsingJava8StreamApiParallel   avgt   10   112.511 ±   0.365  µs/op
    test9_UsingApacheIterableMap        avgt   10   125.714 ±   1.935  µs/op
    
  3. W przypadku mapy zawierającej 100 000 elementów najlepszy jest wynik 1184.767

    Benchmark                          Mode   Cnt  Score        Error    Units
    test1_UsingWhileAndMapEntry        avgt   10   1184.767 ±   332.968  µs/op
    test10_UsingEclipseMap             avgt   10   1191.735 ±   304.273  µs/op
    test2_UsingForEachAndMapEntry      avgt   10   1205.815 ±   366.043  µs/op
    test6_UsingForAndIterator          avgt   10   1206.873 ±   367.272  µs/op
    test8_UsingJava8StreamApiParallel  avgt   10   1485.895 ±   233.143  µs/op
    test5_UsingKeySetAndIterator       avgt   10   1540.281 ±   357.497  µs/op
    test4_UsingKeySetAndForEach        avgt   10   1593.342 ±   294.417  µs/op
    test3_UsingForEachAndJava8         avgt   10   1666.296 ±   126.443  µs/op
    test7_UsingJava8StreamApi          avgt   10   1706.676 ±   436.867  µs/op
    test9_UsingApacheIterableMap       avgt   10   3289.866 ±  1445.564  µs/op
    

Wykresy (testy wydajności w zależności od wielkości mapy)

Enter image description here

Tabela (testy wydajności w zależności od wielkości mapy)

          100     600      1100     1600     2100
test10    0.333    1.631    2.752    5.937    8.024
test3     0.309    1.971    4.147    8.147   10.473
test6     0.372    2.190    4.470    8.322   10.531
test1     0.405    2.237    4.616    8.645   10.707
test2     0.376    2.267    4.809    8.403   10.910
test7     0.473    2.448    5.668    9.790   12.125
test9     0.565    2.830    5.952   13.220   16.965
test4     0.808    5.012    8.813   13.939   17.407
test5     0.810    5.104    8.533   14.064   17.422
test8     5.173   12.499   17.351   24.671   30.403

Wszystkie testy są włączone GitHub.


677
2018-02-22 16:37



@Viacheslav: bardzo ładna odpowiedź. Zastanawiam się, w jaki sposób Java CE apis są utrudnione w twoim benchmarku, przechwytując lambdy ... (np. long sum = 0; map.forEach( /* accumulate in variable sum*/); przechwytuje sum długi, który może być wolniejszy niż powiedzenie stream.mapToInt(/*whatever*/).sum na przykład. Oczywiście nie zawsze można uniknąć przechwycenia stanu, ale może to być sensowny dodatek do ławki. - GPI
Twój 8 test jest nieprawidłowy. uzyskuje dostęp do tej samej zmiennej z różnych wątków bez synchronizacji. Zmień na AtomicInteger rozwiązać problem. - talex
@ZhekaKozlov: spójrz na wartości dudniąco dużych błędów. Rozważ, że wynik testu x±e oznacza, że ​​wynik był w przedziale od x-e do x+e, więc najszybszy wynik (1184.767±332.968) wynosi od 852 do 1518, podczas gdy drugi najwolniejszy (1706.676±436.867) biegnie pomiędzy 1270 i 2144, więc wyniki nadal znacznie się pokrywają. Teraz spójrz na najwolniejszy wynik, 3289.866±1445.564, co oznacza rozbieżność między 1844 i 4735 a ty wiedzieć że te wyniki testu są bez znaczenia. - Holger
Co powiesz na map.entrySet().stream().[parallel().]mapToInt(e -> e.getKey() + e.getValue()).sum();? - glglgl
A co z porównywaniem 3 głównych implementacji: HashMap, LinkedHashMap i TreeMap? - Thierry


W Javie 8 możesz to zrobić szybko i czysto, korzystając z nowych funkcji lambdas:

 Map<String,String> map = new HashMap<>();
 map.put("SomeKey", "SomeValue");
 map.forEach( (k,v) -> [do something with key and value] );

 // such as
 map.forEach( (k,v) -> System.out.println("Key: " + k + ": Value: " + v));

Typ k i v zostanie wywnioskowane przez kompilator i nie ma potrzeby używania Map.Entry już.

Bułka z masłem!


227
2017-10-21 10:15



W zależności od tego, co chcesz zrobić z mapą, możesz użyć strumienia API dla wpisów zwróconych przez map.entrySet().stream()  docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html - Vitalii Fedorenko
To nie zadziała, jeśli chcesz odwołać się do zmiennych nie-końcowych zadeklarowanych poza twoim wyrażeniem lambda z forEach () ... - Chris
@ Chris Poprawnie. Nie zadziała, jeśli spróbujesz użyć skutecznie nie-końcowy zmienne spoza lambda. - Austin Powers


Tak, kolejność zależy od konkretnej implementacji mapy.

@ ScArcher2 ma bardziej elegancką składnię Java 1.5. W 1.4 chciałbym zrobić coś takiego:

Iterator entries = myMap.entrySet().iterator();
while (entries.hasNext()) {
  Entry thisEntry = (Entry) entries.next();
  Object key = thisEntry.getKey();
  Object value = thisEntry.getValue();
  // ...
}

196
2017-09-05 21:15



Wolisz dla pętli niż podczas ... dla (wpisy iteratora = myMap.entrySet (). Iterator (); wpisy.hasNext ();) {...} Przy takiej składni zakres "pozycji" jest zredukowany tylko do pętli for . - HanuAthena
@jpredham Masz rację, że używając for skonstruować jako for (Entry e : myMap.entrySet) nie pozwoli ci modyfikować kolekcji, ale przykład jak @HanuAthena wspomniał, że powinien działać, ponieważ daje ci to Iterator w ramach. (Chyba że czegoś mi brakuje ...) - pkaeding
IntelliJ daje mi błędy Entry thisEntry = (Entry) entries.next();: nie rozpoznaje Entry. Czy to pseudokod dla czegoś innego? - JohnK
@JohnK spróbuj importować java.util.Map.Entry. - pkaeding
Dzięki temu rozwiązaniu typ klucza i wartość nie mają znaczenia. Dziękuję Ci. - Andreas L.


Typowy kod do iteracji na mapie to:

Map<String,Thing> map = ...;
for (Map.Entry<String,Thing> entry : map.entrySet()) {
    String key = entry.getKey();
    Thing thing = entry.getValue();
    ...
}

HashMap jest implementacją mapy kanonicznej i nie daje gwarancji (lub nie powinna zmieniać kolejności, jeśli nie jest wykonywana żadna operacja mutowania). SortedMap zwróci wpisy w oparciu o naturalną kolejność klawiszy lub Comparator, jeśli zapewniono. LinkedHashMap albo zwróci pozycje w kolejności wstawiania lub kolejności dostępu w zależności od tego, jak zostały skonstruowane. EnumMap zwraca wpisy w naturalnej kolejności kluczy.

(Aktualizacja: myślę, że to już nie jest prawda.) Uwaga, IdentityHashMap  entrySet iterator ma obecnie osobliwą implementację, która zwraca to samo Map.Entry instancja dla każdego elementu w entrySet! Jednak za każdym razem, gdy nowy iterator przyspiesza Map.Entry jest zaktualizowane.


101
2017-09-05 21:26



EnumMap ma również to dziwne zachowanie wraz z IdentityHashMap - Premraj
"LinkedHashMap albo zwróci pozycje w [...] kolejności dostępu [...]" ... aby uzyskać dostęp do elementów w kolejności, w której je uzyskujesz? Albo tautologiczna, albo coś interesującego, co mogłoby posłużyć się dygresją. ;-) - jpaugh
@jpaugh Tylko bezpośredni dostęp do pliku LinkedHashMap liczyć. Te przez iterator, spliterator, entrySetitp., nie modyfikuj zamówienia. - Tom Hawtin - tackline
To brzmi, jakby to mogło być bardzo przydatne; lub, na przemian, świetny sposób na faul własnej osoby. Dzięki za ciekawą ciekawostkę! - jpaugh
1. chociaż → gdyby? 2. Ostatni akapit może zyskać na odświeżeniu. - Peter Mortensen


Przykład użycia iteratora i generycznych:

Iterator<Map.Entry<String, String>> entries = myMap.entrySet().iterator();
while (entries.hasNext()) {
  Map.Entry<String, String> entry = entries.next();
  String key = entry.getKey();
  String value = entry.getValue();
  // ...
}

89
2017-08-18 17:34



Powinieneś umieścić Iterator w pętli for, aby ograniczyć jej zakres. - Steve Kuo
@SteveKuo Co masz na myśli mówiąc "ogranicz jego zakres"? - StudioWorks
@StudioWorks for (Iterator<Map.Entry<K, V>> entries = myMap.entrySet().iterator(); entries.hasNext(); ) { Map.Entry<K, V> entry = entries.next(); }. Używając tego konstruktu ograniczamy zakres (widoczność zmiennej) entries do pętli for. - ComFreek
@ComFreek Oh, rozumiem. Nie wiedziałem, że to było tak ważne. - StudioWorks


To jest dwuczęściowe pytanie:

Jak iterować nad wpisami mapy - @ ScArcher2 ma odpowiedział to doskonale.

Jaka jest kolejność iteracji - jeśli tylko używasz Map, a ściśle mówiąc, są brak gwarancji na zamówienie. Więc nie powinieneś polegać na zamówieniu podanym przez jakąkolwiek implementację. Jednakże SortedMapinterfejs się rozszerza Map i zapewnia dokładnie to, czego szukasz - implementacje odejdą, dając spójną kolejność sortowania.

NavigableMap to kolejne przydatne rozszerzenie - to jest SortedMap z dodatkowymi metodami wyszukiwania pozycji według ich uporządkowanej pozycji w zestawie kluczy. Potencjalnie może to w pierwszej kolejności wyeliminować konieczność iteracji - możesz znaleźć konkretną entry jesteś po użyciu higherEntry, lowerEntry, ceilingEntry, lub floorEntry metody. The descendingMap metoda daje nawet wyraźną metodę odwracanie kolejności traversal.


76
2017-09-05 22:15





Istnieje kilka sposobów na iterację na mapie.

Oto porównanie ich wydajności dla wspólnego zestawu danych przechowywanych na mapie poprzez przechowywanie miliona par wartości klucza na mapie i będzie iterować na mapie.

1) Korzystanie entrySet() w każdej pętli

for (Map.Entry<String,Integer> entry : testMap.entrySet()) {
    entry.getKey();
    entry.getValue();
}

50 milisekund

2) Korzystanie keySet() w każdej pętli

for (String key : testMap.keySet()) {
    testMap.get(key);
}

76 milisekund

3) Korzystanie entrySet() i iterator

Iterator<Map.Entry<String,Integer>> itr1 = testMap.entrySet().iterator();
while(itr1.hasNext()) {
    Map.Entry<String,Integer> entry = itr1.next();
    entry.getKey();
    entry.getValue();
}

50 milisekund

4) Korzystanie keySet() i iterator

Iterator itr2 = testMap.keySet().iterator();
while(itr2.hasNext()) {
    String key = itr2.next();
    testMap.get(key);
}

75 milisekund

Odniosłem się this link.


62
2018-02-05 06:42



Bardzo dobry przykład! Wolę korzystać ze sposobu # 1. - Phuong


FYI, możesz również użyć map.keySet() i map.values() jeśli interesują Cię tylko klucze / wartości mapy, a nie inne.


41
2017-09-05 22:27