Если у меня есть объект, реализующий Map
интерфейс на Java, и я хочу перебирать каждую содержащуюся в нем пару, каков наиболее эффективный способ прохождения карты?
Будет ли порядок элементов зависеть от конкретной реализации карты, которую я имею для интерфейса?
Ответы:
источник
remove
метод. Если это так, этот другой ответ покажет вам, как это сделать. В противном случае расширенный цикл, как показано в ответе выше, - это путь.map.values()
или,map.keySet()
если вы хотите перебирать только значения или ключи.Чтобы суммировать другие ответы и объединить их с тем, что я знаю, я нашел 10 основных способов сделать это (см. Ниже). Кроме того, я написал несколько тестов производительности (см. Результаты ниже). Например, если мы хотим найти сумму всех ключей и значений карты, мы можем написать:
Использование итератора и Map.Entry
Использование foreach и Map.Entry
Использование forEach из Java 8
Использование keySet и foreach
Использование keySet и итератора
Использование для и Map.Entry
Использование Java 8 Stream API
Используя Java 8 Stream API параллельно
Используя IterableMap из
Apache Collections
Использование MutableMap коллекций Eclipse (CS)
Тесты производительности (режим = Среднее время, система = 64-битная Windows 8.1, Intel i7-4790 3,60 ГГц, 16 ГБ)
Для маленькой карты (100 элементов) лучше всего набрать 0,308 балла.
Для карты с 10000 элементов оценка 37.606 является лучшей
Для карты с 100000 элементов оценка 1184,767 является лучшей
Графики (тесты производительности в зависимости от размера карты)
Таблица (тесты производительности в зависимости от размера карты)
Все тесты на GitHub .
источник
long sum = 0; map.forEach( /* accumulate in variable sum*/);
захватываетsum
длинный, который может быть медленнее, чем, скажем,stream.mapToInt(/*whatever*/).sum
например. Конечно, вы не всегда можете избежать захвата состояния, но это может быть разумным дополнением на скамейку запасныхAtomicInteger
решения проблемы.x±e
подразумевает наличие результата в интервале отx-e
доx+e
, поэтому самый быстрый результат (1184.767±332.968
) варьируется от852
до1518
, тогда как второй самый медленный (1706.676±436.867
) выполняется между1270
и2144
, поэтому результаты по-прежнему существенно перекрываются. Теперь посмотрим на самый медленный результат,3289.866±1445.564
который подразумевает расхождение между1844
и,4735
и вы знаете, что эти результаты теста не имеют смысла.while
противfor
цикла не является другой техникой для итерации. И я удивлен, что в ваших тестах между ними существует такая разница - это говорит о том, что тесты не должным образом изолированы от внешних факторов, не связанных с тем, что вы собираетесь тестировать.В Java 8 вы можете делать это чисто и быстро, используя новые функции лямбда-выражений:
Тип
k
иv
будет определен компилятором, и больше нет необходимости использоватьMap.Entry
.Очень просто!
источник
map.entrySet().stream()
docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.htmlДа, порядок зависит от конкретной реализации карты.
@ ScArcher2 имеет более элегантный синтаксис Java 1.5 . В 1.4 я бы сделал что-то вроде этого:
источник
for
конструкции asfor (Entry e : myMap.entrySet)
не позволит вам изменить коллекцию, но пример, как упомянул @HanuAthena, должен работать, поскольку он предоставляет вамIterator
область действия. (Если я что-то упустил ...)Entry thisEntry = (Entry) entries.next();
: не распознаетEntry
. Это псевдокод для чего-то еще?java.util.Map.Entry
.Типичный код для итерации по карте:
HashMap
является реализацией канонической карты и не дает гарантий (или хотя она не должна изменять порядок, если на ней не выполняется операция мутации).SortedMap
будет возвращать записи на основе естественного порядка ключей, илиComparator
, если предоставлено.LinkedHashMap
будет либо возвращать записи в порядке вставки или порядке доступа в зависимости от того, как он был построен.EnumMap
возвращает записи в естественном порядке ключей.(Обновление: я думаю, что это больше не так. ) Обратите внимание,
IdentityHashMap
entrySet
итератор в настоящее время имеет своеобразную реализацию, которая возвращает один и тот жеMap.Entry
экземпляр для каждого элемента вentrySet
! Однако каждый раз, когда новый итератор продвигается,Map.Entry
обновляется.источник
LinkedHashMap
графу. Те , черезiterator
,spliterator
,entrySet
и т.д., не изменяют порядок.Пример использования итератора и обобщений:
источник
Iterator
цикл for, чтобы ограничить его область действия.for (Iterator<Map.Entry<K, V>> entries = myMap.entrySet().iterator(); entries.hasNext(); ) { Map.Entry<K, V> entry = entries.next(); }
. Используя эту конструкцию, мы ограничиваем область действия (видимость переменной)entries
циклом for.Это вопрос из двух частей:
Как перебирать записи на карте - @ ScArcher2 ответил на это отлично.
Каков порядок итерации - если вы просто используете
Map
, то, строго говоря, нет никаких гарантий порядка . Таким образом, вы не должны полагаться на порядок, заданный любой реализацией. Тем не менее,SortedMap
интерфейс расширяетсяMap
и обеспечивает именно то, что вы ищете - реализации всегда будут давать последовательный порядок сортировки.NavigableMap
Еще одно полезное расширение - этоSortedMap
с дополнительными методами для поиска записей по их упорядоченной позиции в наборе ключей. Таким образом , потенциально это может устранить необходимость в переборе в первую очередь - Вы могли бы быть в состоянии найти специфическиеentry
вы после использованияhigherEntry
,lowerEntry
,ceilingEntry
илиfloorEntry
методы. ЭтотdescendingMap
метод даже дает вам явный метод изменения порядка обхода .источник
Есть несколько способов перебора карты.
Вот сравнение их характеристик для общего набора данных, хранящегося в карте, путем сохранения миллиона пар ключ-значение в карте и будет повторяться по карте.
1) Использование
entrySet()
в каждом цикле50 миллисекунд
2) Использование
keySet()
в каждом цикле76 миллисекунд
3) Использование
entrySet()
итератора50 миллисекунд
4) Использование
keySet()
итератора75 миллисекунд
Я сослался
this link
.источник
Правильный способ сделать это - использовать принятый ответ, так как он наиболее эффективен. Я считаю, что следующий код выглядит немного чище.
источник
O(1) = 2*O(1)
это в значительной степени определение большой O нотации. вы правы в том, что он работает немного медленнее, но с точки зрения сложности они одинаковы.2
, поскольку итерации по aentrySet()
не несут поиска вообще; это просто линейный обход всех записей. Напротив, итерированиеkeySet()
и выполнение поиска по ключу требует одного поиска по ключу, поэтому мы говорим о нулевых поисках по сравнению с n поисками, где n является размеромMap
. Таким образом, фактор находится далеко за пределами2
...К вашему сведению, вы также можете использовать
map.keySet()
и,map.values()
если вас интересуют только ключи / значения карты, а не другие.источник
В Java 8 вы можете выполнять итерации Map, используя forEach и лямбда-выражения,
источник
С Eclipse , коллекцией , вы должны использовать
forEachKeyValue
метод наMapIterable
интерфейсе, который наследуетсяMutableMap
иImmutableMap
интерфейсами и их реализации.Используя анонимный внутренний класс, вы можете написать код следующим образом:
Примечание: я являюсь коммиттером для Eclipse Collections.
источник
В Java 1.8 (Java 8) это стало намного проще благодаря использованию метода forEach из Aggregate операций ( потоковых операций ), который похож на итераторы из Iterable Interface.
Просто скопируйте оператор вставки ниже в свой код и переименуйте переменную HashMap из hm в переменную HashMap, чтобы распечатать пару ключ-значение.
Ниже приведен пример кода, который я пытался использовать с помощью лямбда-выражения . Это так круто. Должен попытаться.
Также можно использовать Spliterator для того же.
ОБНОВИТЬ
Включая ссылки на документацию к Oracle Docs. Чтобы узнать больше о Lambda, перейдите по этой ссылке и прочитайте Aggregate Operations, а для Spliterator перейдите по этой ссылке .
источник
Теоретически, наиболее эффективный способ будет зависеть от того, какая реализация Map. Официальный способ сделать это - вызвать
map.entrySet()
, который возвращает наборMap.Entry
, каждый из которых содержит ключ и значение (entry.getKey()
иentry.getValue()
).В своеобразной реализации может иметь значение, используете ли вы
map.keySet()
,map.entrySet()
или что-то еще. Но я не могу придумать причину, по которой кто-то так написал бы. Скорее всего это не имеет значения для производительности, что вы делаете.И да, порядок будет зависеть от реализации, а также (возможно) порядка вставки и других трудно контролируемых факторов.
[править] Я написал
valueSet()
изначально, но, конечно,entrySet()
на самом деле ответ.источник
Java 8
У нас есть
forEach
метод, который принимает лямбда-выражения . У нас также есть потоковые API. Рассмотрим карту:Перебирать ключи:
Перебрать значения:
Перебрать записи (используя forEach и Streams):
Преимущество потоков заключается в том, что их можно легко распараллелить, если мы захотим. Нам просто нужно использовать
parallelStream()
вместоstream()
выше.forEachOrdered
противforEach
потоков? ОниforEach
не следуют порядку встреч (если они определены) и по своей природе недетерминированы по своей природеforEachOrdered
. ТакforEach
что не гарантирует, что заказ будет сохранен. Также проверьте это для большего.источник
Java 8:
Вы можете использовать лямбда-выражения:
Для получения дополнительной информации, следуйте этому .
источник
myMap.forEach( (currentKey,currentValue) -> /* action */ );
гораздо более кратким.Попробуйте это с Java 1.4:
источник
В Map можно выполнять итерации,
keys
и / или,values
и / или, вboth (e.g., entrySet)
зависимости от того, кого вы интересуете.Итерация по
keys -> keySet()
карте:Итерация по
values -> values()
карте:Итерация по
both -> entrySet()
карте:Более того, есть 3 различных способа итерации через HashMap. Они как ниже
источник
Самый компактный с Java 8:
источник
Если у вас есть общая нетипизированная карта, вы можете использовать:
источник
ИЛИ
источник
Если эффективность цикла ключей является приоритетом для вашего приложения, выберите
Map
реализацию, которая поддерживает ключи в нужном вам порядке.Да, конечно.
Map
реализации обещают определенный порядок итераций, другие нет.Map
поддерживают различный порядок пар ключ-значение.Посмотрите эту таблицу, которую я создал, суммируя различные
Map
реализации, связанные с Java 11. В частности, обратите внимание на столбец порядка итераций . Нажмите / нажмите, чтобы увеличить.Вы можете видеть, что есть четыре
Map
реализации, поддерживающие порядок :TreeMap
ConcurrentSkipListMap
LinkedHashMap
EnumMap
NavigableMap
интерфейсДва из них реализуют
NavigableMap
интерфейс:TreeMap
&ConcurrentSkipListMap
.Более старый
SortedMap
интерфейс эффективно вытесняется более новымNavigableMap
интерфейсом. Но вы можете найти сторонние реализации, реализующие только старый интерфейс.Естественный порядок
Если вы хотите,
Map
чтобы его пары располагались в «естественном порядке» ключа, используйтеTreeMap
илиConcurrentSkipListMap
. Термин «естественный порядок» означает класс ключей, реализуемыхComparable
. Значение, возвращаемоеcompareTo
методом значение используется для сравнения при сортировке.Изготовленный на заказ заказ
Если вы хотите указать собственную процедуру сортировки для ваших ключей, которая будет использоваться для поддержания порядка сортировки, передайте
Comparator
реализацию, соответствующую классу ваших ключей. Используйте либо,TreeMap
либоConcurrentSkipListMap
, передаваяComparator
.Оригинальный порядок вставки
Если вы хотите, чтобы пары вашей карты были сохранены в их первоначальном порядке, в котором вы вставили их в карту, используйте
LinkedHashMap
.Порядок определения перечисления
Если вы используете перечисление, такое как
DayOfWeek
илиMonth
как ключи, используйтеEnumMap
класс. Этот класс не только высоко оптимизирован, чтобы использовать очень мало памяти и работать очень быстро, он поддерживает ваши пары в порядке, определенном перечислением. ДляDayOfWeek
, например, ключDayOfWeek.MONDAY
будет найден , когда первая итерация, а ключDayOfWeek.SUNDAY
будет последним.Другие соображения
При выборе
Map
реализации также учитывайте:Collections::synchronizedMap
(менее предпочтительно).Оба эти соображения рассматриваются в графической таблице выше.
источник
EnumMap
, так как я впервые слышу об этом. Вероятно, во многих случаях это может пригодиться.Порядок всегда будет зависеть от конкретной реализации карты. Используя Java 8, вы можете использовать любой из них:
Или:
Результат будет таким же (в том же порядке). Набор записей поддерживается картой, поэтому вы получаете тот же заказ. Второй удобен тем, что позволяет использовать лямбды, например, если вы хотите печатать только целочисленные объекты, которые больше 5:
Код ниже показывает итерацию через LinkedHashMap и обычный HashMap (пример). Вы увидите разницу в порядке:
источник
источник
Используйте Java 8:
источник
Вы можете сделать это, используя дженерики:
источник
Эффективным итеративным решением для Map является цикл «для каждого» от Java 5 до Java 7. Вот оно:
В Java 8 вы можете использовать лямбда-выражение для итерации по карте. Это расширенный «forEach»
источник
источник
Есть много способов сделать это. Ниже приведено несколько простых шагов:
Предположим, у вас есть одна карта, например:
Затем вы можете сделать что-то вроде ниже, чтобы перебрать элементы карты.
источник
источник