Java : HashMap을 통한 반복, 어느 것이 더 효율적입니까?

Java : HashMap을 통한 반복, 어느 것이 더 효율적입니까?

---

다음 코드를 반복하는 두 가지 대체 방법이있는 경우이
두 방법간에 성능 차이가 있습니까?

        Map<String, Integer> map = new HashMap<String, Integer>();
        //populate map

        //alt. #1
        for (String key : map.keySet())
        {
            Integer value = map.get(key);
            //use key and value
        }

        //alt. #2
        for (Map.Entry<String, Integer> entry : map.entrySet())
        {
            String key = entry.getKey();
            Integer value = entry.getValue();
            //use key and value
        }

나는 그것이 alt. #2전체를 반복하는 더 효율적인 수단 이라고 생각하는 경향 map이 있습니다 (하지만 틀릴 수 있습니다)

---

두 번째 옵션은 첫 번째 옵션의 n 번에 비해 한 번만 조회를 수행하기 때문에 확실히 더 효율적입니다.

그러나 가능한 한 시도하는 것보다 더 좋은 것은 없습니다. 그래서 여기에-

(완벽하지는 않지만 어쨌든 내 컴퓨터에서 가정을 검증하기에 충분합니다)

public static void main(String args[]) {

    Map<String, Integer> map = new HashMap<String, Integer>();
    // populate map

    int mapSize = 500000;
    int strLength = 5;
    for(int i=0;i<mapSize;i++)
        map.put(RandomStringUtils.random(strLength), RandomUtils.nextInt());

    long start = System.currentTimeMillis();
    // alt. #1
    for (String key : map.keySet()) {
        Integer value = map.get(key);
        // use key and value
    }
    System.out.println("Alt #1 took "+(System.currentTimeMillis()-start)+" ms");

    start = System.currentTimeMillis();
    // alt. #2
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        String key = entry.getKey();
        Integer value = entry.getValue();
        // use key and value
    }
    System.out.println("Alt #2 took "+(System.currentTimeMillis()-start)+" ms");
}

결과 (흥미로운 결과 )

와 int mapSize = 5000; int strLength = 5;
Alt 키 # 1 26 밀리했다
# 2 20 밀리했다 ALT

와 int mapSize = 50000; int strLength = 5;
Alt 키 # 1 32 밀리했다
# 2 20 밀리했다 ALT

와 int mapSize = 50000; int strLength = 50;
Alt 키 # 1 22 밀리했다
# 2 21 밀리했다 ALT

와 int mapSize = 50000; int strLength = 500;
Alt 키 # 1 28 밀리했다
# 2 23 밀리했다 ALT

와 int mapSize = 500000; int strLength = 5;
Alt 키 # 1 92 밀리했다
# 2 57 밀리했다 ALT

...등등

---

두 번째 스 니펫은 키를 다시 조회 할 필요가 없기 때문에 약간 더 빠릅니다.

모든 HashMap반복자는 호출 nextEntry방법 를 반환합니다 Entry<K,V>.

첫 번째 스 니펫은 항목 (in KeyIterator) 에서 값을 삭제 한 다음 사전에서 다시 조회합니다.

두 번째 스 니펫은 키와 값을 직접 사용합니다 (에서 EntryIterator).

(모두 keySet()와 entrySet()저렴한 전화입니다)

---

후자는 전자보다 효율적입니다. FindBugs 와 같은 도구 는 실제로 전자에 플래그를 지정하고 후자를 수행하도록 제안합니다.

---

지도:

Map<String, Integer> map = new HashMap<String, Integer>();

두 가지 옵션 외에 하나 더 있습니다.

1) keySet () - 키만 사용해야 하는 경우 사용

for ( String k : map.keySet() ) {
    ...
}

2) entrySet () - 키와 값이 모두 필요한 경우 사용

for ( Map.Entry<String, Integer> entry : map.entrySet() ) {
    String k = entry.getKey();
    Integer v = entry.getValue();
    ...
}

3) 값 () -를 사용하는 경우 필요 에만 값

for ( Integer v : map.values() ) {
    ...
}

---

일반적으로 두 번째는 HashMap의 경우 조금 더 빠릅니다. 그 이후로 당신은, 해시 충돌 많이 있습니다 만 정말 문제 않을 경우 get(key)호출이보다 느리게 도착 O(1)- 그것은 취득 O(k)과 k같은 버킷의 항목 수 (동일한 해시 코드 또는 유도 할 수있는 다른 해시 코드와 키, 즉 수있는 여전히 동일한 버킷에 매핑되어 있습니다. 이는 맵의 용량, 크기 및로드 비율에 따라 달라집니다.

항목 반복 변형은 조회를 수행 할 필요가 없으므로 여기에서 조금 더 빨라집니다.

또 다른 참고 사항 : 맵의 용량이 실제 크기보다 훨씬 크고 반복을 많이 사용하는 경우 대신 LinkedHashMap을 사용하는 것이 좋습니다. O(size)대신 O(size+capacity)완전한 반복 (예측 가능한 반복 순서)에 대한 복잡성을 제공합니다 . (요인이 다를 수 있으므로 이것이 실제로 개선되는지 측정해야합니다. LinkedHashMap은지도를 만드는 데 더 큰 오버 헤드를가집니다.)

---

bguiz,

나는 EntrySet (대안 2)을 반복하는 것이 약간 더 효율적이라고 생각합니다. 단순히 값을 얻기 위해 각 키를 해시하지 않기 때문에 ... 그렇지만 해시 계산은 O입니다. (1) 항목 당 작업이므로 전체에 대해 O (n) 만 이야기하고 있습니다 HashMap. 그러나이 모든 것이 적용된다는 점에 유의하십시오 HashMap. 다른 구현 Map은 매우 다른 성능 특성을 가질 수 있습니다.

나는 당신이 실제로 성능의 차이를 알아 차리기 위해 "밀고"될 것이라고 생각한다. 걱정된다면 두 반복 기술의 시간을 맞추기 위해 테스트 케이스를 설정하는 것은 어떨까요?

REAL,보고 된 성능 문제가없는 경우에는 그다지 걱정하지 않는 것입니다. 여기에 몇 개의 클럭 틱이 있으면 프로그램의 전반적인 사용성에 영향을주지 않습니다.

나는 코드의 많은 다른 측면이 일반적으로 완전한 성능보다 더 중요하다고 생각합니다. 물론 일부 블록은 "성능에 중요"하며 이는 작성되기 전에도 알려져 있으며 단독 성능 테스트를 거쳤습니다. 그러나 그러한 경우는 매우 드뭅니다. 일반적인 접근 방식으로 완전하고, 정확하고, 유연하고, 테스트 가능하고, 재사용 가능하고, 읽기 가능하고, 유지 관리 가능한 코드를 작성하는 데 집중하는 것이 좋습니다. 성능은 필요에 따라 나중에 빌드 할 수 있습니다.

버전 0은 "최적화"없이 가능한 단순해야합니다.

---

내 벤치 마크에 따르면 가장 효율적인 방법 HashMap.forEach()은 Java 8 또는 HashMap.entrySet().forEach().

JMH 벤치 마크 :

@Param({"50", "500", "5000", "50000", "500000"})
int limit;
HashMap<String, Integer> m = new HashMap<>();
public Test() {
}
@Setup(Level.Trial)
public void setup(){
    m = new HashMap<>(m);
    for(int i = 0; i < limit; i++){
        m.put(i + "", i);
    }
}
int i;
@Benchmark
public int forEach(Blackhole b){
    i = 0;
    m.forEach((k, v) -> { i += k.length() + v; });
    return i;
}
@Benchmark
public int keys(Blackhole b){
    i = 0;
    for(String key : m.keySet()){ i += key.length() + m.get(key); }
    return i;
}
@Benchmark
public int entries(Blackhole b){
    i = 0;
    for (Map.Entry<String, Integer> entry : m.entrySet()){ i += entry.getKey().length() + entry.getValue(); }
    return i;
}
@Benchmark
public int keysForEach(Blackhole b){
    i = 0;
    m.keySet().forEach(key -> { i += key.length() + m.get(key); });
    return i;
}
@Benchmark
public int entriesForEach(Blackhole b){
    i = 0;
    m.entrySet().forEach(entry -> { i += entry.getKey().length() + entry.getValue(); });
    return i;
}
public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder()
            .include(Test.class.getSimpleName())
            .forks(1)
            .warmupIterations(25)
            .measurementIterations(25)
            .measurementTime(TimeValue.milliseconds(1000))
            .warmupTime(TimeValue.milliseconds(1000))
            .timeUnit(TimeUnit.MICROSECONDS)
            .mode(Mode.AverageTime)
            .build();
    new Runner(opt).run();
}

결과 :

Benchmark            (limit)  Mode  Cnt      Score    Error  Units
Test.entries              50  avgt   25      0.282 ±  0.037  us/op
Test.entries             500  avgt   25      2.792 ±  0.080  us/op
Test.entries            5000  avgt   25     29.986 ±  0.256  us/op
Test.entries           50000  avgt   25   1070.218 ±  5.230  us/op
Test.entries          500000  avgt   25   8625.096 ± 24.621  us/op
Test.entriesForEach       50  avgt   25      0.261 ±  0.008  us/op
Test.entriesForEach      500  avgt   25      2.891 ±  0.007  us/op
Test.entriesForEach     5000  avgt   25     31.667 ±  1.404  us/op
Test.entriesForEach    50000  avgt   25    664.416 ±  6.149  us/op
Test.entriesForEach   500000  avgt   25   5337.642 ± 91.186  us/op
Test.forEach              50  avgt   25      0.286 ±  0.001  us/op
Test.forEach             500  avgt   25      2.847 ±  0.009  us/op
Test.forEach            5000  avgt   25     30.923 ±  0.140  us/op
Test.forEach           50000  avgt   25    670.322 ±  7.532  us/op
Test.forEach          500000  avgt   25   5450.093 ± 62.384  us/op
Test.keys                 50  avgt   25      0.453 ±  0.003  us/op
Test.keys                500  avgt   25      5.045 ±  0.060  us/op
Test.keys               5000  avgt   25     58.485 ±  3.687  us/op
Test.keys              50000  avgt   25   1504.207 ± 87.955  us/op
Test.keys             500000  avgt   25  10452.425 ± 28.641  us/op
Test.keysForEach          50  avgt   25      0.567 ±  0.025  us/op
Test.keysForEach         500  avgt   25      5.743 ±  0.054  us/op
Test.keysForEach        5000  avgt   25     61.234 ±  0.171  us/op
Test.keysForEach       50000  avgt   25   1142.416 ±  3.494  us/op
Test.keysForEach      500000  avgt   25   8622.734 ± 40.842  us/op

당신이 볼, 수 있듯이 HashMap.forEach및 HashMap.entrySet().forEach()대형지도를 위해 최선을 수행하고에 루프에 의해 결합되는 entrySet()작은지도를위한 최고의 성능을 제공합니다.

The reason the keys methods are slower is probably because they have to lookup the value again for each entry, while the other methods just need to read a field in an object they already have to get the value. The reason that I would expect the iterator methods to be slower is that they are doing external iteration, which requires two method calls (hasNext and next) for each element as well as storing the iteration state in the iterator object, while the internal iteration done by forEach requires just one method call to accept.

You should profile on your target hardware with your target data and doing your target action in the loops to get a more accurate result.

ReferenceURL : https://stackoverflow.com/questions/5826384/java-iteration-through-a-hashmap-which-is-more-efficient