Питання Як ефективно прослідкувати над кожним входом у "карті"?


Якщо у мене є об'єкт, який реалізує Map інтерфейс у Java, і я хочу послідовно переглянути всі пари, що містяться в ній, який найефективніший спосіб пройти карту?

Чи буде замовлення елементів залежати від конкретної реалізації карти, яка існує для інтерфейсу?


2529
2017-09-05 21:12


походження


У Java 8, використовуючи Lambda Expression: stackoverflow.com/a/25616206/1503859 - Nitin Mahesh


Відповіді:


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



Якщо ви це зробите, то він не буде працювати, оскільки вхід - це вкладений клас на карті. java.sun.com/javase/6/docs/api/java/util/Map.html - ScArcher2
ви можете написати імпорт як "імпорт java.util.Map.Entry;" і це буде працювати. - jjujuma
@Pureferret Єдина причина, якою ви можете використовувати ітератор, - це, якщо вам потрібно викликати його remove метод Якщо це так це інша відповідь показує, як це зробити. В іншому випадку покращений цикл, як показано у відповідь вище, - це шлях. - assylias
Я вважаю, що форма Map.Entry є яскравішою, ніж імпорт внутрішнього класу до поточного простору імен. - Josiah Yoder
Зауважте, що ви можете використовувати map.values() або map.keySet() якщо ви хочете, щоб цикл тільки через значення або ключі. - dguay


Щоб підвести підсумки інших відповідей і поєднати їх з тим, що я знаю, я знайшов 10 основних способів зробити це (див. Нижче). Крім того, я написав кілька тестів продуктивності (див. Результати нижче). Наприклад, якщо ми хочемо знайти суму всіх клавіш та значень карти, ми можемо написати:

  1. Використовуючи ітератор і 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. Використовуючи для кожного і Map.Entry

    long i = 0;
    for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
        i += pair.getKey() + pair.getValue();
    }
    
  3. Використовуючи для кожного з Java 8

    final long[] i = {0};
    map.forEach((k, v) -> i[0] += k + v);
    
  4. Використовуючи keySet і для кожного

    long i = 0;
    for (Integer key : map.keySet()) {
        i += key + map.get(key);
    }
    
  5. Використовуючи keySet і ітератор

    long i = 0;
    Iterator<Integer> itr2 = map.keySet().iterator();
    while (itr2.hasNext()) {
        Integer key = itr2.next();
        i += key + map.get(key);
    }
    
  6. Використовуючи за і 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. Використання Java 8 API потоку

    final long[] i = {0};
    map.entrySet().stream().forEach(e -> i[0] += e.getKey() + e.getValue());
    
  8. Використання Java 8 Stream API паралельно

    final long[] i = {0};
    map.entrySet().stream().parallel().forEach(e -> i[0] += e.getKey() + e.getValue());
    
  9. Використовуючи IterableMap від Apache Collections

    long i = 0;
    MapIterator<Integer, Integer> it = iterableMap.mapIterator();
    while (it.hasNext()) {
        i += it.next() + it.getValue();
    }
    
  10. Використовуючи MutableMap з колекцій Eclipse (CS)

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

Випробування на виконання (режим = AverageTime, система = Windows 8.1 64-розрядний, Intel i7-4790 3,60 ГГц, 16 Гб)

  1. Для малих карт (100 елементів) оцінка 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. Для карти з 10000 елементами оцінка 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. Для карти з 100000 елементами оцінка 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
    

Графіки (тести витримки в залежності від розміру карти)

Enter image description here

Таблиця (експериментальні тести в залежності від розміру карти)

          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

Всі тести є GitHub.


677
2018-02-22 16:37



@Віачеслав: дуже гарна відповідь. Просто цікаво, як Java8 apis перешкоджає, у вашому тесті, шляхом захоплення лямбда ... (наприклад, long sum = 0; map.forEach( /* accumulate in variable sum*/); захоплює sum довго, що може бути повільніше, ніж говорити stream.mapToInt(/*whatever*/).sum наприклад. Звичайно, ви не завжди можете уникнути захоплення штату, але це може бути причиною додавання до лави. - GPI
Ваш 8 тест неправильний. він отримує доступ до однієї змінної з різних потоків без синхронізації. Перейти AtomicInteger вирішити проблему. - talex
@ЖекаКозлов: подивіться на думки, небагато великі значення помилок. Розглянемо, що результат тесту x±e випливає, що був результат у інтервалі від x-e до x+e, тому найшвидший результат (1184.767±332.968) коливається від 852 до 1518, тоді як другий повільний (1706.676±436.867) проходить між 1270 і 2144, тому результати значно перекриваються. Тепер подивіться на найнижчий результат 3289.866±1445.564, що передбачає розбіжність між ними 1844 і 4735 і ти знати що ці результати тесту безглуздо. - Holger
А як на рахунок map.entrySet().stream().[parallel().]mapToInt(e -> e.getKey() + e.getValue()).sum();? - glglgl
Що стосується порівняння 3 основних реалізацій: HashMap, LinkedHashMap та TreeMap? - Thierry


У Java 8 ви можете зробити це чисто і швидко, використовуючи нові функції лямбда:

 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));

Тип k і v буде визначено компілятором, і немає необхідності використовувати його Map.Entry більше

Простенька!


227
2017-10-21 10:15



Залежно від того, що ви хочете зробити з картою, ви також можете використовувати API потоку у записах, що повертаються map.entrySet().stream()  docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html - Vitalii Fedorenko
Це не спрацює, якщо ви хочете вказати неповні змінні, оголошені за межами вашого лямбда-виразу, в межах forEach () ... - Chris
@ Chris Correct. Це не спрацює, якщо спробуєте використовувати ефективно не фінальний змінні ззовні лямбда. - Austin Powers


Так, замовлення залежить від конкретної реалізації Карти.

@ ScArcher2 має більш елегантний синтаксис Java 1.5. У 1.4 я хотів би зробити щось подібне:

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



Перевірте для циклу, а поки .. для (Ітератори entries = myMap.entrySet (). Iterator (); entries.hasNext ();) {...} За допомогою цього синтаксису область "entries" зменшується до тільки для циклу . - HanuAthena
@jpredham Ви маєте рацію, що використовуючи for побудувати як for (Entry e : myMap.entrySet) не дозволить вам змінити колекцію, але приклад, як @HanuAthena зазначив, що він повинен працювати, оскільки він дає вам Iterator за обсягом (Якщо я щось не вистачає ...) - pkaeding
IntelliJ дає мені помилки Entry thisEntry = (Entry) entries.next();: не розпізнає Entry. Це псевдокод для чогось іншого? - JohnK
@JohnK спробуйте імпортувати java.util.Map.Entry. - pkaeding
За допомогою цього рішення тип ключа та значення не має значення. Дякую. - Andreas L.


Типовий код для повторення карти:

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

HashMap є канонічною картою виконання і не гарантує (або хоча вона не повинна змінювати порядок, якщо на нього не виконується жодна мутаційна операція). SortedMap повертає записи на основі природного замовлення ключів або a Comparator, якщо надано. LinkedHashMap буде повертати записи в порядку вставки або в порядку доступу залежно від того, як він був побудований. EnumMap повертає записи в натуральному порядку ключів.

(Оновлення: я думаю, що це вже не так.) Примітка, IdentityHashMap  entrySet ітератор наразі має своєрідну реалізацію, яка повертає те ж саме Map.Entry приклад для кожного елемента в entrySet! Однак кожен раз, коли новий ітератор розвиває Map.Entry оновлено


101
2017-09-05 21:26



EnumMap також має цю особливу поведінку разом з IdentityHashMap - Premraj
"LinkedHashMap або повертає записи в [...] замовленні доступу [...]" ... так що ви можете отримати доступ до елементів у порядку, до якого ви їм доступні? Або тавтологічний, або щось цікаве, що могло б використовувати відступ. ;-) - jpaugh
@ jpaugh Тільки прямі звернення до LinkedHashMap рахувати. Ті через iterator, spliterator, entrySetі т. д., не змінюйте порядок. - Tom Hawtin - tackline
Це звучить, як це може бути дуже корисним; або, поперемінно, чудовий спосіб засмутити себе. Дякую за цікаву лайку! - jpaugh
1 хоча → якщо? 2. Останній абзац може принести користь від покращення. - Peter Mortensen


Приклад використання ітератора та генериків:

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



Ви повинні поставити Iterator в циклі для обмеження його масштабу. - Steve Kuo
@SteveKuo Що ви маєте на увазі за допомогою "обмежити його обсяг"? - StudioWorks
@StudioWorks for (Iterator<Map.Entry<K, V>> entries = myMap.entrySet().iterator(); entries.hasNext(); ) { Map.Entry<K, V> entry = entries.next(); }. Використовуючи цю конструкцію, ми обмежуємо сферу дії (видимість змінної) entries до петлі - ComFreek
@ComFreek О, я бачу. Не знав, що це дуже важливо. - StudioWorks


Це питання з двох частин:

Як ітерації над записами карти - @ ScArcher2 має відповів що чудово.

Який порядок ітерації - якщо ви просто використовуєте Map, то, строго кажучи, є немає замовлень гарантій. Отже, ви не повинні покладатися на замовлення, надані будь-якою реалізацією. Однак, SortedMapінтерфейс розширюється Map і забезпечує саме те, що ви шукаєте - реалізація буде завжди давати послідовний порядок сортування.

NavigableMap є ще одним корисним продовженням - це SortedMap з додатковими методами пошуку записів за їхньою упорядкованою позицією в наборі ключів. Тому потенційно це може усунути необхідність переривання - можливо, ви зможете знайти конкретні entry ви після використання higherEntry, lowerEntry, ceilingEntry, або floorEntry методи The descendingMap Метод навіть дає вам явний метод сторнування перехресного порядку.


76
2017-09-05 22:15