Jeśli mam obiekt implementujący Map
interfejs w Javie i chcę iterować każdą zawartą w nim parę, jaki jest najbardziej efektywny sposób przeglądania mapy?
Czy kolejność elementów będzie zależeć od konkretnej implementacji mapy, którą mam dla interfejsu?
java
dictionary
collections
iteration
iMack
źródło
źródło
Odpowiedzi:
źródło
remove
metody. W takim przypadku ta inna odpowiedź pokazuje, jak to zrobić. W przeciwnym razie udoskonalona pętla, jak pokazano w powyższej odpowiedzi, jest właściwym rozwiązaniem.map.values()
lubmap.keySet()
jeśli chcesz przewijać tylko wartości lub klucze.Podsumowując pozostałe odpowiedzi i łącząc 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 (patrz wyniki poniżej). Na przykład, jeśli chcemy znaleźć sumę wszystkich kluczy i wartości mapy, możemy napisać:
Korzystanie z iteratora i mapy
Korzystanie z foreach i Map.Entry
Korzystanie z forEach z Java 8
Korzystanie z keySet i foreach
Korzystanie z keySet i iteratora
Korzystanie z i Map.Entry
Korzystanie z interfejsu API Java 8 Stream
Korzystanie z równoległego interfejsu API Java 8 Stream
Korzystanie z IterableMap z
Apache Collections
Korzystanie z MutableMap kolekcji Eclipse (CS)
Testy wydajności (tryb = średni czas, system = Windows 8.1 64-bit, Intel i7-4790 3,60 GHz, 16 GB)
W przypadku małej mapy (100 elementów) najlepszy wynik to 0,308
W przypadku mapy z 10000 elementami najlepszy wynik to 37,606
W przypadku mapy z 100000 elementów najlepszy wynik to 1184.767
Wykresy (testy wydajności w zależności od wielkości mapy)
Tabela (testy wydajności w zależności od wielkości mapy)
Wszystkie testy są na GitHub .
źródło
long sum = 0; map.forEach( /* accumulate in variable sum*/);
Rejestrujesum
długi, który może być wolniejszy niżstream.mapToInt(/*whatever*/).sum
na przykład powiedzmy . Oczywiście nie zawsze możesz uniknąć przechwytywania stanu, ale może to być uzasadniony dodatek do ławkiAtomicInteger
rozwiązać problem.x±e
implikuje, że wynik był w przedziale odx-e
dox+e
, więc najszybszy wynik (1184.767±332.968
) waha się od852
do1518
, podczas gdy drugi najwolniejszy (1706.676±436.867
) biegnie między1270
i2144
, więc wyniki wciąż znacznie się pokrywają. Spójrzmy teraz na najwolniejszym rezultacie3289.866±1445.564
, co implikuje rozbieżności pomiędzy1844
a4735
i wiem , że te wyniki badań są bez znaczenia.while
vs.for
pętla nie jest inną techniką iteracji. I jestem zaskoczony, że mają takie różnice między nimi w waszych testach - co sugeruje, że testy nie są odpowiednio odizolowane od czynników zewnętrznych niezwiązanych z rzeczami, które zamierzacie testować.W Javie 8 możesz to zrobić czysto i szybko, korzystając z nowych funkcji lambdas:
Typ
k
iv
zostanie wyprowadzony przez kompilator i nie trzeba goMap.Entry
już używać .Bułka z masłem!
źródło
map.entrySet().stream()
docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.htmlTak, kolejność zależy od konkretnej implementacji mapy.
@ ScArcher2 ma bardziej elegancką składnię Java 1.5 . W 1.4 zrobiłbym coś takiego:
źródło
for
konstruktu asfor (Entry e : myMap.entrySet)
nie pozwoli ci zmodyfikować kolekcji, ale przykład, jak wspomniano @HanuAthena, powinien działać, ponieważ daje ciIterator
zakres. (Chyba, że coś miEntry thisEntry = (Entry) entries.next();
: nie rozpoznajeEntry
. Czy to pseudokod dla czegoś innego?java.util.Map.Entry
.Typowy kod iteracji po mapie to:
HashMap
jest implementacją mapy kanonicznej i nie daje gwarancji (lub chociaż nie powinna zmieniać kolejności, jeśli nie jest na niej wykonywana żadna operacja mutacji).SortedMap
zwróci wpisy w oparciu o naturalną kolejność kluczy, lub aComparator
, jeśli podano.LinkedHashMap
zwróci wpisy w kolejności wprowadzania lub kolejności dostępu, w zależności od tego, jak zostało 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 tę samąMap.Entry
instancję dla każdego elementu wentrySet
! Jednak za każdym razem, gdy nowy iterator przesuwa się,Map.Entry
jest aktualizowany.źródło
LinkedHashMap
hrabiego. Tych przeziterator
,spliterator
,entrySet
, itd., Nie zmieniają kolejność.Przykład użycia iteratora i ogólnych:
źródło
Iterator
pętlę for, aby ograniczyć jej zasięg.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.To jest dwuczęściowe pytanie:
Jak iterować po wpisach mapy - @ ScArcher2 doskonale na to odpowiedział .
Jaka jest kolejność iteracji - jeśli tylko używasz
Map
, to mówiąc ściśle, nie ma gwarancji na zamówienie . Tak więc nie powinieneś polegać na kolejności podanej przez jakąkolwiek implementację. JednakSortedMap
interfejs się rozszerzaMap
i zapewnia dokładnie to, czego szukasz - implementacje wyeliminują spójny porządek sortowania.NavigableMap
jest kolejnym przydatnym rozszerzeniem - jest toSortedMap
dodatkowe metody wyszukiwania wpisów według ich uporządkowanej pozycji w zestawie kluczy. Więc potencjalnie może usunąć potrzebę iteracji w pierwszej kolejności - może być w stanie znaleźć konkretnegoentry
jesteś po użyciuhigherEntry
,lowerEntry
,ceilingEntry
lubfloorEntry
metod. TadescendingMap
metoda daje nawet wyraźną metodę odwrócenia kolejności przechodzenia .źródło
Istnieje kilka sposobów na iterację po mapie.
Oto porównanie ich wydajności dla wspólnego zestawu danych przechowywanego na mapie poprzez zapisanie miliona par klucz-wartość na mapie i będzie iterować po mapie.
1) Korzystanie
entrySet()
z każdej pętli50 milisekund
2) Korzystanie
keySet()
z każdej pętli76 milisekund
3) Używanie
entrySet()
i iterator50 milisekund
4) Korzystanie
keySet()
i iterator75 milisekund
Odniosłem się
this link
.źródło
Prawidłowym sposobem na to jest użycie zaakceptowanej odpowiedzi, ponieważ jest ona najbardziej wydajna. Uważam, że następujący kod wygląda na nieco czystszy.
źródło
O(1) = 2*O(1)
jest właściwie definicją dużej notacji O. masz rację, ponieważ działa nieco wolniej, ale pod względem złożoności są takie same.2
, ponieważ iteracja nadentrySet()
nie w ogóle zawiera przegląd; to tylko liniowe przejście wszystkich wpisów. W przeciwieństwie do tego, iteracjakeySet()
i wykonywanie wyszukiwania na klucz powoduje jedno wyszukiwanie na klucz, więc mówimy tutaj o zerowych przeglądach vs. n przeglądach tutaj, gdzie n jest rozmiarem plikuMap
. Więc czynnik jest znacznie większy niż2
…Do Twojej wiadomości możesz także użyć,
map.keySet()
amap.values()
jeśli interesują Cię tylko klucze / wartości mapy, a nie inne.źródło
W Javie 8 możesz iterować Mapę, używając forEach i wyrażenia lambda,
źródło
Z Eclipse Kolekcje , należy użyć
forEachKeyValue
metody wMapIterable
interfejsie, który jest dziedziczony przezMutableMap
iImmutableMap
interfejsów oraz ich implementacji.Korzystając z anonimowej klasy wewnętrznej, możesz napisać kod w następujący sposób:
Uwaga: jestem osobą odpowiedzialną za kolekcje Eclipse.
źródło
W Javie 1.8 (Java 8) stało się dużo łatwiejsze przy użyciu foreach metody z operacji kruszywa ( operacje Stream ), który wygląda podobnie do iteratorów z iterable Interface.
Wystarczy skopiować instrukcję wklej poniżej i zmień nazwę zmiennej HashMap z hm na zmienną HashMap, aby wydrukować parę klucz-wartość.
Poniżej znajduje się przykładowy kod, który próbowałem przy użyciu wyrażenia Lambda . Te rzeczy są takie fajne. Musisz spróbować.
Można również użyć Spliteratora do tego samego.
AKTUALIZACJA
Łącznie z linkami do dokumentacji do Dokumentów Oracle. Aby uzyskać więcej informacji na temat Lambda, przejdź do tego linku i musisz przeczytać Aggregate Operations, a dla Spliteratora przejdź do tego linku .
źródło
Teoretycznie najskuteczniejszy sposób będzie zależeć od tego, która implementacja mapy. Oficjalnym sposobem na to jest wywołanie
map.entrySet()
, które zwraca zestawMap.Entry
, z których każdy zawiera klucz i wartość (entry.getKey()
ientry.getValue()
).W idiosynkratycznej implementacji może mieć znaczenie, czy używasz
map.keySet()
,map.entrySet()
czy coś innego. Ale nie mogę wymyślić powodu, dla którego ktoś mógłby tak to napisać. Najprawdopodobniej nie ma to wpływu na wydajność tego, co robisz.I tak, kolejność zależy od implementacji - a także (ewentualnie) kolejności wprowadzania i innych trudnych do kontrolowania czynników.
[edytuj] Napisałem
valueSet()
pierwotnie, ale oczywiścieentrySet()
jest to odpowiedź.źródło
Java 8
Mamy
forEach
metodę, która akceptuje wyrażenie lambda . Mamy również interfejsy API strumieni . Rozważ mapę:Iterate over keys:
Iterate over values:
Iteruj po wpisach (Korzystanie z forEach i strumieni):
Zaletą strumieni jest to, że można je łatwo zrównoleglać w razie potrzeby. Musimy po prostu użyć
parallelStream()
zamiaststream()
powyższego.forEachOrdered
kontraforEach
ze strumieniami?forEach
Nie wynika kolejności napotkać (jeśli określona) i jest z natury nie deterministyczny w przyrodzie, gdzie jakoforEachOrdered
ma. TakforEach
nie gwarantuje, że zamówienie zostanie utrzymane. Należy również sprawdzić to na dłużej.źródło
Java 8:
Możesz użyć wyrażeń lambda:
Aby uzyskać więcej informacji, wykonaj następujące czynności .
źródło
myMap.forEach( (currentKey,currentValue) -> /* action */ );
jest o wiele bardziej zwięzłe.Wypróbuj to w Javie 1.4:
źródło
W Mapie można iterację ponad
keys
i / lubvalues
i / lubboth (e.g., entrySet)
zależy od tego, czy jest zainteresowany:Iteruj po
keys -> keySet()
mapie:Iteruj po
values -> values()
mapie:Iteruj po
both -> entrySet()
mapie:_Ponadto istnieją 3 różne sposoby iteracji poprzez HashMap. Są jak poniżej__
źródło
Najbardziej kompaktowy z Javą 8:
źródło
Jeśli masz ogólną mapę bez typu, możesz użyć:
źródło
LUB
źródło
Jeśli wydajność zapętlania kluczy jest priorytetem dla Twojej aplikacji, wybierz
Map
implementację, która utrzymuje klucze w żądanej kolejności.Tak, absolutnie.
Map
implementacje obiecują określony porządek iteracji, inne nie.Map
utrzymują różne kolejność par klucz-wartość.Zobacz tabelę, którą utworzyłem, podsumowującą różne
Map
implementacje zawarte w Javie 11. W szczególności zwróć uwagę na kolumnę kolejności iteracji . Kliknij / dotknij, aby powiększyć.Widać, że są cztery
Map
implementacje utrzymujące zamówienie :TreeMap
ConcurrentSkipListMap
LinkedHashMap
EnumMap
NavigableMap
berłoDwa z nich implementują
NavigableMap
interfejs:TreeMap
iConcurrentSkipListMap
.Starszy
SortedMap
interfejs jest skutecznie zastępowany przez nowszyNavigableMap
interfejs. Ale możesz znaleźć implementacje innych firm implementujące tylko starszy interfejs.Naturalny porządek
Jeśli chcesz,
Map
aby pary układały się według „naturalnego porządku” klucza, użyjTreeMap
lubConcurrentSkipListMap
. Termin „porządek naturalny” oznacza klasę kluczyComparable
. Wartość zwrócona przezcompareTo
metodę służy do porównania podczas sortowania.Zamówienie klienta
Jeśli chcesz określić niestandardową procedurę sortowania kluczy, która będzie używana w celu utrzymania uporządkowanej kolejności, przekaż
Comparator
implementację odpowiednią dla klasy kluczy. Użyj albo,TreeMap
alboConcurrentSkipListMap
przekazując swojąComparator
.Oryginalne zamówienie reklamowe
Jeśli chcesz, aby pary mapy były przechowywane w oryginalnej kolejności, w jakiej wstawiłeś je na mapie, użyj
LinkedHashMap
.Kolejność wyliczania
Jeśli używasz wyliczenia, takiego jak
DayOfWeek
lubMonth
jako klucze, użyjEnumMap
klasy. Ta klasa jest nie tylko wysoce zoptymalizowana, aby zużywała bardzo mało pamięci i działała bardzo szybko, ale także utrzymuje pary w kolejności określonej przez wyliczenie. NaDayOfWeek
przykład kluczDayOfWeek.MONDAY
zostanie najpierw znaleziony podczas iteracji, a kluczDayOfWeek.SUNDAY
będzie ostatni.Inne uwagi
Wybierając
Map
implementację, weź również pod uwagę:Collections::synchronizedMap
(mniej preferowane).Oba te rozważania zostały przedstawione w powyższej tabeli graficznej.
źródło
EnumMap
, ponieważ po raz pierwszy o tym słyszałem. Prawdopodobnie jest wiele przypadków, w których może się to przydać.Kolejność zawsze będzie zależeć od konkretnej implementacji mapy. Korzystając z Java 8, możesz użyć jednego z tych:
Lub:
Wynik będzie taki sam (ta sama kolejność). EntrySet poparty mapą, dzięki czemu otrzymujesz to samo zamówienie. Drugi jest przydatny, ponieważ pozwala używać lambd, np. Jeśli chcesz drukować tylko obiekty całkowite, które są większe niż 5:
Poniższy kod pokazuje iterację poprzez LinkedHashMap i normalną HashMap (przykład). Zobaczysz różnicę w kolejności:
źródło
źródło
Użyj Java 8:
źródło
Możesz to zrobić przy użyciu ogólnych:
źródło
Skutecznym rozwiązaniem iteracyjnym nad mapą jest pętla „dla każdej” od Java 5 do Java 7. Oto ona:
W Javie 8 możesz używać wyrażenia lambda do iteracji po mapie. To ulepszone „forEach”
źródło
źródło
Można to zrobić na wiele sposobów. Poniżej znajduje się kilka prostych kroków:
Załóżmy, że masz jedną mapę, np .:
Następnie możesz zrobić coś takiego jak poniżej, aby iterować elementy mapy.
źródło
źródło