Câu hỏi Làm thế nào để có hiệu quả lặp qua mỗi mục trong một 'Bản đồ'?


Nếu tôi có một đối tượng thực hiện Map giao diện trong Java và tôi muốn lặp qua tất cả các cặp chứa trong nó, cách hiệu quả nhất để đi qua bản đồ là gì?

Thứ tự các phần tử có phụ thuộc vào việc triển khai bản đồ cụ thể mà tôi có cho giao diện không?


2529
2017-09-05 21:12


gốc


Trong Java 8 sử dụng biểu thức Lambda: stackoverflow.com/a/25616206/1503859 - Nitin Mahesh


Các câu trả lời:


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



Nếu bạn làm điều đó, sau đó nó sẽ không hoạt động như Entry là một lớp lồng nhau trong bản đồ. java.sun.com/javase/6/docs/api/java/util/Map.html - ScArcher2
bạn có thể viết nhập khẩu là "import java.util.Map.Entry;" và nó sẽ hoạt động. - jjujuma
@Pureferret Lý do duy nhất bạn có thể muốn sử dụng một trình lặp là nếu bạn cần gọi nó remove phương pháp. Nếu đó là trường hợp, câu trả lời khác này cho bạn thấy làm thế nào để làm điều đó. Nếu không, vòng lặp nâng cao như được hiển thị trong câu trả lời ở trên là cách để đi. - assylias
Tôi tin rằng biểu mẫu Map.Entry rõ ràng hơn là nhập lớp bên trong vào không gian tên hiện tại. - Josiah Yoder
Lưu ý rằng bạn có thể sử dụng map.values() hoặc là map.keySet() nếu bạn chỉ muốn lặp qua các giá trị hoặc khóa. - dguay


Để tóm tắt các câu trả lời khác và kết hợp chúng với những gì tôi biết, tôi đã tìm thấy 10 cách chính để thực hiện việc này (xem bên dưới). Ngoài ra, tôi đã viết một số bài kiểm tra hiệu suất (xem kết quả bên dưới). Ví dụ, nếu chúng ta muốn tìm tổng của tất cả các khóa và giá trị của một bản đồ, chúng ta có thể viết:

  1. Sử dụng người lặp và 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. Sử dụng cho mỗi và Map.Entry

    long i = 0;
    for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
        i += pair.getKey() + pair.getValue();
    }
    
  3. Sử dụng cho mỗi từ Java 8

    final long[] i = {0};
    map.forEach((k, v) -> i[0] += k + v);
    
  4. Sử dụng bộ chìa khoá và cho mỗi

    long i = 0;
    for (Integer key : map.keySet()) {
        i += key + map.get(key);
    }
    
  5. Sử dụng bộ chìa khoá và người lặp

    long i = 0;
    Iterator<Integer> itr2 = map.keySet().iterator();
    while (itr2.hasNext()) {
        Integer key = itr2.next();
        i += key + map.get(key);
    }
    
  6. Sử dụng cho và 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. Sử dụng Java 8 API luồng

    final long[] i = {0};
    map.entrySet().stream().forEach(e -> i[0] += e.getKey() + e.getValue());
    
  8. Sử dụng Java 8 Tương tác luồng API

    final long[] i = {0};
    map.entrySet().stream().parallel().forEach(e -> i[0] += e.getKey() + e.getValue());
    
  9. Sử dụng IterableMap của Apache Collections

    long i = 0;
    MapIterator<Integer, Integer> it = iterableMap.mapIterator();
    while (it.hasNext()) {
        i += it.next() + it.getValue();
    }
    
  10. Sử dụng MutableMap của các bộ sưu tập Eclipse (CS)

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

Kiểm tra sự hoàn hảo (chế độ = Thời gian trung bình, hệ thống = Windows 8.1 64 bit, Intel i7-4790 3.60 GHz, 16 GB)

  1. Đối với bản đồ nhỏ (100 phần tử), điểm 0.308 là tốt nhất

    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. Đối với bản đồ với 10000 yếu tố, điểm số 37,606 là tốt nhất

    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. Đối với bản đồ với 100000 yếu tố, điểm số 1184.767 là tốt nhất

    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
    

Đồ thị (kiểm tra hiệu ứng nước hoa tùy thuộc vào kích thước bản đồ)

Enter image description here

Bảng (các bài kiểm tra hiệu ứng nước hoa tùy thuộc vào kích thước bản đồ)

          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

Tất cả các bài kiểm tra đều được bật GitHub.


677
2018-02-22 16:37



@Viacheslav: câu trả lời rất hay. Chỉ cần tự hỏi làm thế nào Java8 apis bị cản trở, trong tiêu chuẩn của bạn, bằng cách bắt lambdas ... (ví dụ: long sum = 0; map.forEach( /* accumulate in variable sum*/); nắm bắt sum dài, có thể chậm hơn nói stream.mapToInt(/*whatever*/).sum ví dụ. Tất nhiên bạn có thể không phải lúc nào cũng tránh trạng thái bắt giữ, nhưng đó có thể là một sự bổ sung hợp lý cho băng ghế dự bị. - GPI
Kiểm tra 8 của bạn là sai. nó truy cập cùng một biến từ các luồng khác nhau mà không cần đồng bộ hóa. Thay đổi thành AtomicInteger để giải quyết vấn đề. - talex
@ZhekaKozlov: nhìn vào các giá trị lỗi lớn mindblowingly. Hãy xem xét rằng kết quả thử nghiệm của x±e ngụ ý rằng có kết quả trong khoảng thời gian từ x-e đến x+e, do đó, kết quả nhanh nhất (1184.767±332.968) từ 852 đến 1518, trong khi thứ hai chậm nhất (1706.676±436.867) chạy giữa 1270 và 2144, do đó kết quả vẫn chồng chéo đáng kể. Bây giờ hãy xem kết quả chậm nhất, 3289.866±1445.564, ngụ ý phân tách giữa 1844 và 4735 còn bạn biết rằng các kết quả thử nghiệm này là vô nghĩa. - Holger
Thế còn map.entrySet().stream().[parallel().]mapToInt(e -> e.getKey() + e.getValue()).sum();? - glglgl
Điều gì về việc so sánh 3 triển khai chính: HashMap, LinkedHashMap và TreeMap? - Thierry


Trong Java 8, bạn có thể làm nó sạch sẽ và nhanh chóng bằng cách sử dụng các tính năng lambdas mới:

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

Các loại k và v sẽ được trình biên dịch suy ra và không cần sử dụng Map.Entry nữa không.

Dễ như ăn bánh!


227
2017-10-21 10:15



Tùy thuộc vào những gì bạn muốn làm với bản đồ, bạn cũng có thể sử dụng API luồng trên các mục được trả về bởi map.entrySet().stream()  docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html - Vitalii Fedorenko
Điều này sẽ không hoạt động nếu bạn muốn tham chiếu các biến không phải cuối cùng được khai báo bên ngoài biểu thức lambda của bạn từ bên trong forEach () ... - Chris
@Chris đúng. Nó sẽ không hoạt động nếu bạn cố gắng sử dụng không hiệu quả biến từ bên ngoài lambda. - Austin Powers


Có, thứ tự phụ thuộc vào việc triển khai Bản đồ cụ thể.

@ ScArcher2 có cú pháp Java 1.5 thanh lịch hơn. Trong 1,4, tôi sẽ làm một cái gì đó như thế này:

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



Thích cho vòng lặp hơn trong khi .. cho (Iterator entries = myMap.entrySet (). Iterator (); entries.hasNext ();) {...} Với cú pháp này phạm vi 'mục' được giảm xuống chỉ cho vòng lặp . - HanuAthena
@jpredham Bạn có quyền sử dụng for xây dựng như for (Entry e : myMap.entrySet) sẽ không cho phép bạn sửa đổi bộ sưu tập, nhưng ví dụ như @HanuAthena đề cập đến nó sẽ hoạt động, vì nó cung cấp cho bạn Iterator trong phạm vi. (Trừ khi tôi đang thiếu thứ gì đó ...) - pkaeding
IntelliJ đang cho tôi lỗi Entry thisEntry = (Entry) entries.next();: không nhận ra Entry. Là giả mã cho cái gì khác? - JohnK
@JohnK thử nhập java.util.Map.Entry. - pkaeding
Với giải pháp này, loại khóa và giá trị không quan trọng. Cảm ơn bạn. - Andreas L.


Mã điển hình để lặp qua bản đồ là:

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

HashMap là việc triển khai bản đồ chuẩn và không đảm bảo (hoặc mặc dù nó không thay đổi thứ tự nếu không có hoạt động đột biến nào được thực hiện trên nó). SortedMap sẽ trả về các mục dựa trên thứ tự tự nhiên của các khóa hoặc Comparator, Nếu được cung cấp. LinkedHashMap sẽ trả về các mục nhập theo thứ tự chèn hoặc thứ tự truy cập tùy thuộc vào cách nó được xây dựng. EnumMap trả về các mục theo thứ tự các khóa tự nhiên.

(Cập nhật: Tôi nghĩ điều này không còn đúng nữa.) Chú thích, IdentityHashMap  entrySet iterator hiện có một triển khai đặc biệt, trả về cùng Map.Entry ví dụ cho mọi mục trong entrySet! Tuy nhiên, mỗi lần một trình lặp mới tiến lên Map.Entry đã cập nhật.


101
2017-09-05 21:26



EnumMap cũng có hành vi đặc biệt này cùng với IdentityHashMap - Premraj
"LinkedHashMap sẽ trả về các mục nhập trong [...] để truy cập [...]" ... để bạn truy cập các phần tử theo thứ tự bạn truy cập chúng? Hoặc là tautological, hoặc một cái gì đó thú vị mà có thể sử dụng một digression. ;-) - jpaugh
@jpaugh Chỉ truy cập trực tiếp vào LinkedHashMap đếm. Những người thông qua iterator, spliterator, entrySet, v.v., không sửa đổi thứ tự. - Tom Hawtin - tackline
Nghe có vẻ như nó rất hữu ích; hoặc, luân phiên một cách tuyệt vời để phạm tội của một người. Cảm ơn vì miếng ngon thú vị! - jpaugh
1. Tuy nhiên → nếu? 2. Đoạn cuối cùng có thể được hưởng lợi từ việc đánh răng. - Peter Mortensen


Ví dụ về sử dụng trình lặp và generics:

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



Bạn nên đặt Iterator trong vòng lặp for để giới hạn phạm vi của nó. - Steve Kuo
@SteveKuo Những gì bạn có nghĩa là "giới hạn phạm vi của nó"? - StudioWorks
@StudioWorks for (Iterator<Map.Entry<K, V>> entries = myMap.entrySet().iterator(); entries.hasNext(); ) { Map.Entry<K, V> entry = entries.next(); }. Bằng cách sử dụng cấu trúc đó, chúng tôi giới hạn phạm vi (khả năng hiển thị của biến) entries cho vòng lặp for. - ComFreek
@ Sufreek Ồ, tôi hiểu rồi. Không biết rằng nó quan trọng đến thế. - StudioWorks


Đây là câu hỏi gồm hai phần:

Cách lặp lại các mục nhập của Bản đồ - @ ScArcher2 có đã trả lời điều đó hoàn hảo.

Thứ tự lặp lại là gì - nếu bạn chỉ sử dụng Map, sau đó nói đúng, có không bảo đảm đặt hàng. Vì vậy, bạn không nên thực sự dựa vào thứ tự được đưa ra bởi bất kỳ việc thực hiện nào. Tuy nhiên, SortedMapgiao diện mở rộng Map và cung cấp chính xác những gì bạn đang tìm kiếm - triển khai sẽ cung cấp một thứ tự sắp xếp nhất quán.

NavigableMap là một phần mở rộng hữu ích khác - đây là một SortedMap với các phương pháp bổ sung để tìm các mục nhập theo vị trí đặt hàng của chúng trong bộ khóa. Vì vậy, có khả năng điều này có thể loại bỏ sự cần thiết phải lặp lại ngay từ đầu - bạn có thể tìm thấy entry bạn đang sử dụng higherEntry, lowerEntry, ceilingEntry, hoặc là floorEntry phương pháp. Các descendingMap phương pháp thậm chí cung cấp cho bạn một phương pháp rõ ràng đảo ngược thứ tự truyền tải.


76
2017-09-05 22:15





Có một số cách để lặp qua bản đồ.

Đây là so sánh các buổi biểu diễn của họ cho một tập dữ liệu chung được lưu trữ trong bản đồ bằng cách lưu trữ một triệu cặp giá trị khóa trong bản đồ và sẽ lặp lại trên bản đồ.

1) Sử dụng entrySet() trong mỗi vòng lặp

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

50 mili giây

2) Sử dụng keySet() trong mỗi vòng lặp

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

76 mili giây

3) Sử dụng entrySet() và trình lặp

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

50 mili giây

4) Sử dụng keySet() và trình lặp

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

75 mili giây

Tôi đã gọi this link.


62
2018-02-05 06:42



Ví dụ rất tốt! Tôi thích sử dụng cách # 1. - Phuong


FYI, bạn cũng có thể sử dụng map.keySet() và map.values() nếu bạn chỉ quan tâm đến các khóa / giá trị của bản đồ chứ không quan tâm đến các khóa / giá trị khác.


41
2017-09-05 22:27