자바 에서 맵 의 성능 문 제 를 분석 합 니 다.

머리말
자바 HashMap 의 확장 은 원가 가 있다 는 것 을 알 고 있 습 니 다.확장 횟수 와 원 가 를 줄 이기 위해 HashMap 에 초기 용량 크기 를 설정 할 수 있 습 니 다.다음 과 같 습 니 다.

HashMap<string, integer=""> map0 = new HashMap<string, integer="">(100000);

그러나 실제 사용 하 는 과정 에서 성능 이 향상 되 지 않 았 을 뿐만 아니 라 오히려 현저히 떨 어 진 것 을 발견 했다!코드 에서 HashMap 에 대한 조작 도 옮 겨 다 니 기만 했 습 니 다.문제 가 생 긴 것 같 습 니 다.그래서 테스트 를 했 는데 다음 과 같은 결 과 를 얻 었 습 니 다.
HashMap 의 교체 기 는 initial capacity 와 관련 이 있 으 며,size 와 는 무관 합 니 다.
2.교체 기 테스트
테스트 코드 붙 이기:

public class MapForEachTest {

    public static void main(String[] args) {
        HashMap<string, integer=""> map0 = new HashMap<string, integer="">(100000);

        initDataAndPrint(map0);

        HashMap<string, integer=""> map1 = new HashMap<string, integer="">();

        initDataAndPrint(map1);

    }



    private static void initDataAndPrint(HashMap map) {

        initData(map);

        long start = System.currentTimeMillis();

        for (int i = 0; i < 100; i++) {
            forEach(map);
        }
        long end = System.currentTimeMillis();
        System.out.println("");
        System.out.println("HashMap Size: " + map.size() +  "   : " + (end - start) + " ms");
    }

    private static void forEach(HashMap map) {
        for (Iterator<map.entry<string, integer="">> it = map.entrySet().iterator(); it.hasNext();){
            Map.Entry<string, integer=""> item = it.next();
            System.out.print(item.getKey());
            // do something
        }

    }

    private static void initData(HashMap map) {
        map.put("a", 0);
        map.put("b", 1);
        map.put("c", 2);
        map.put("d", 3);
        map.put("e", 4);
        map.put("f", 5);
    }

}

이것 은 실행 결과 입 니 다:

우 리 는 첫 번 째 맵 을 10w 크기 로 초기 화 합 니 다.두 번 째 맵 은 크기(실제 16)를 지정 하지 않 습 니 다.두 개 는 같은 데 이 터 를 저장 합 니 다.그러나 교체 기 를 사용 하여 100 번 을 옮 겨 다 닐 때 성능 이 현저히 다 릅 니 다.하 나 는 36ms 이 고 하 나 는 4ms 입 니 다.실제 성능 차이 가 더 큽 니 다.이곳 의 4ms 는 600 번 System.out.print 입 니 다.print 의 소모 시간 입 니 다.여 기 는 print 주 를 걸 고 다시 시도 해 보 겠 습 니 다.

for (Iterator<map.entry<string, integer="">> it = map.entrySet().iterator(); it.hasNext();){
    Map.Entry<string, integer=""> item = it.next();
    // System.out.print(item.getKey());
    // do something
}

출력 결 과 는 다음 과 같 습 니 다.

두 번 째 맵 은 거의 0 이 걸 렸 고 첫 번 째 맵 은 28ms 에 달 했 습 니 다.옮 겨 다 니 는 동안 아무런 조작 도 하지 않 았 습 니 다.망치 가 initial capacity 와 관련 이 있 으 니 다음 단 계 는 왜 이러 는 지 확인 하고 맵 교체 기의 소스 코드 를 찾 아 보 겠 습 니 다.
3.교체 기 소스 코드 탐구Map.entrySet().iterator()의 소스 코드 를 살 펴 보 자.

public final Iterator<map.entry<k,v>> iterator() {
    return new EntryIterator();
}

그 중에서 Entry Iterator 는 HashMap 의 내부 추상 류 로 소스 코드 가 많 지 않 습 니 다.저 는 모두 중국어 주석 을 붙 이 고 첨부 했 습 니 다.

abstract class HashIterator {
    //    Node
    Node<k,v> next; // next entry to return
    //   Node
    Node<k,v> current;     // current entry
    //    Map  ，      HashMap        (     iterator()  new        )，            remove，       (    )
    int expectedModCount;  // for fast-fail
    
    //            ，HashMap             ，        HashMap    
    int index;             // current slot

    HashIterator() {
        //     expectedModCount
        expectedModCount = modCount;
        //      Map   
        Node<k,v>[] t = table;
        current = next = null;
        index = 0;
        //    Map       ，               ，   next
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<k,v> nextNode() {
        //      table，         ，   
        Node<k,v>[] t;
        //     e   next，            
        Node<k,v> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
            
        //  current  e，   next，      ，   next = current.next，   null
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

    /**
     *     ，     ，   HashMap removeNode，     
     **/
    public final void remove() {
        Node<k,v> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        //          
        expectedModCount = modCount;
    }
}

위의 코드 를 보면 알 수 있 듯 이 교체 기 는 다음 요 소 를 찾 을 때마다 배열 을 옮 겨 다 닌 다.initial capacity가 특히 크 면threshold도 크 고table.length도 커서 옮 겨 다 니 는 것 이 성능 을 소모 한 다 는 것 이다.
table 배열 의 크기 설정 은 resize()방법 에 있 습 니 다.

Node<k,v>[] newTab = (Node<k,v>[])new Node[newCap];
table = newTab;

4.다른 옮 겨 다 니 는 방법
주의 코드 에서 우리 가 사용 하 는 것 은Map.entrySet().iterator()입 니 다.실제로keys().iterator(),values().iterator()와 마찬가지 로 소스 코드 는 다음 과 같 습 니 다.

final class KeyIterator extends HashIterator
    implements Iterator<k> {
    public final K next() { return nextNode().key; }
}

final class ValueIterator extends HashIterator
    implements Iterator<v> {
    public final V next() { return nextNode().value; }
}

final class EntryIterator extends HashIterator
    implements Iterator<map.entry<k,v>> {
    public final Map.Entry<k,v> next() { return nextNode(); }
}

이 두 개 는 분석 하지 않 고 성능 이 같다.
실제 사용 중 집합 을 옮 겨 다 니 는 방법 은 몇 가지 가 있다.

보통 for 순환+하 표

증강 형 for 순환

Map.forEach

Stream.forEach

일반 for 순환+아래 표 시 된 방법 은 Map 에 적용 되 지 않 습 니 다.여 기 는 토론 하지 않 습 니 다.
4.1,증강 형 for 순환
증강 행 for 순환 은 사실상 교체 기 를 통 해 이 루어 진 것 이다.우 리 는 이들 의 관 계 를 살 펴 보 자.
원본 코드:

private static void forEach(HashMap map) {
    for (Iterator<map.entry<string, integer="">> it = map.entrySet().iterator(); it.hasNext();){
        Map.Entry<string, integer=""> item = it.next();
        System.out.print(item.getKey());
        // do something
    }
}


private static void forEach0(HashMap<string, integer=""> map) {
    for (Map.Entry entry : map.entrySet()) {
        System.out.print(entry.getKey());
    }
}

컴 파일 된 바이트 코드:

// access flags 0xA
  private static forEach(Ljava/util/HashMap;)V
   L0
    LINENUMBER 41 L0
    ALOAD 0
    INVOKEVIRTUAL java/util/HashMap.entrySet ()Ljava/util/Set;
    INVOKEINTERFACE java/util/Set.iterator ()Ljava/util/Iterator; (itf)
    ASTORE 1
   L1
   FRAME APPEND [java/util/Iterator]
    ALOAD 1
    INVOKEINTERFACE java/util/Iterator.hasNext ()Z (itf)
    IFEQ L2
   L3
    LINENUMBER 42 L3
    ALOAD 1
    INVOKEINTERFACE java/util/Iterator.next ()Ljava/lang/Object; (itf)
    CHECKCAST java/util/Map$Entry
    ASTORE 2
   L4
    LINENUMBER 43 L4
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ALOAD 2
    INVOKEINTERFACE java/util/Map$Entry.getKey ()Ljava/lang/Object; (itf)
    CHECKCAST java/lang/String
    INVOKEVIRTUAL java/io/PrintStream.print (Ljava/lang/String;)V
   L5
    LINENUMBER 45 L5
    GOTO L1
   L2
    LINENUMBER 46 L2
   FRAME CHOP 1
    RETURN
   L6
    LOCALVARIABLE item Ljava/util/Map$Entry; L4 L5 2
    // signature Ljava/util/Map$Entry<ljava lang="" string;ljava="" integer;="">;
    // declaration: item extends java.util.Map$Entry<java.lang.string, java.lang.integer="">
    LOCALVARIABLE it Ljava/util/Iterator; L1 L2 1
    // signature Ljava/util/Iterator<ljava util="" map$entry<ljava="" lang="" string;ljava="" integer;="">;>;
    // declaration: it extends java.util.Iterator<java.util.map$entry<java.lang.string, java.lang.integer="">>
    LOCALVARIABLE map Ljava/util/HashMap; L0 L6 0
    MAXSTACK = 2
    MAXLOCALS = 3

  // access flags 0xA
  // signature (Ljava/util/HashMap<ljava lang="" string;ljava="" integer;="">;)V
  // declaration: void forEach0(java.util.HashMap<java.lang.string, java.lang.integer="">)
  private static forEach0(Ljava/util/HashMap;)V
   L0
    LINENUMBER 50 L0
    ALOAD 0
    INVOKEVIRTUAL java/util/HashMap.entrySet ()Ljava/util/Set;
    INVOKEINTERFACE java/util/Set.iterator ()Ljava/util/Iterator; (itf)
    ASTORE 1
   L1
   FRAME APPEND [java/util/Iterator]
    ALOAD 1
    INVOKEINTERFACE java/util/Iterator.hasNext ()Z (itf)
    IFEQ L2
    ALOAD 1
    INVOKEINTERFACE java/util/Iterator.next ()Ljava/lang/Object; (itf)
    CHECKCAST java/util/Map$Entry
    ASTORE 2
   L3
    LINENUMBER 51 L3
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ALOAD 2
    INVOKEINTERFACE java/util/Map$Entry.getKey ()Ljava/lang/Object; (itf)
    INVOKEVIRTUAL java/io/PrintStream.print (Ljava/lang/Object;)V
   L4
    LINENUMBER 52 L4
    GOTO L1
   L2
    LINENUMBER 53 L2
   FRAME CHOP 1
    RETURN
   L5
    LOCALVARIABLE entry Ljava/util/Map$Entry; L3 L4 2
    LOCALVARIABLE map Ljava/util/HashMap; L0 L5 0
    // signature Ljava/util/HashMap<ljava lang="" string;ljava="" integer;="">;
    // declaration: map extends java.util.HashMap<java.lang.string, java.lang.integer="">
    MAXSTACK = 2
    MAXLOCALS = 3

모두 인내심 을 가지 고 관찰 할 필요 가 없다.두 가지 방법의 바이트 코드 는 국부 변수 가 다른 것 을 제외 하고 거의 같다.이 를 통 해 증강 형 for 순환 성능 은 교체 기와 마찬가지 로 실제 운행 결과 도 마찬가지 이다.나 는 보 여주 지 않 고 관심 이 있 는 자신 이 copy 글 의 시작 과 끝 에 있 는 코드 를 시험 해 보 았 다.

4.2、Map.forEach
먼저 여러 가지 방법 을 함께 실행 하지 않 고 동시에 출력 하 는 이 유 는 CPU 캐 시 원인 과 JVM 의 일부 최적화 가 성능 판단 을 방해 하기 때 문 입 니 다.모든 테스트 결 과 를 부록 으로 설명 합 니 다.
그냥 소스 볼 게 요.

@Override
public void forEach(BiConsumer<!--? super K, ? super V--> action) {
    Node<k,v>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
            for (Node<k,v> e = tab[i]; e != null; e = e.next)
                action.accept(e.key, e.value);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

아주 짧 은 소스 코드 는 주석 을 달 지 않 습 니 다.소스 코드 에서 다음 과 같은 정 보 를 얻 기 어렵 지 않 습 니 다.

이 방법 도 빠 른 속도 로 실 패 했 습 니 다.옮 겨 다 니 는 동안 요 소 를 삭제 할 수 없습니다

전체 배열 을 옮 겨 다 녀 야 합 니 다

BiConsumer 는@Functional Interface 주 해 를 달 고 lambda

를 사용 했다.
세 번 째 는 성능 과 상 관 없 이 여 기 는 단지 제시 할 뿐이다.
이상 의 정 보 를 통 해 우 리 는 이 성능 이 table 배열 의 크기 와 관계 가 있다 는 것 을 확인 할 수 있 습 니 다.
그러나 실제 테스트 를 할 때 성능 이 교체 기 보다 많이 떨 어 진 것 을 발견 했다.

4.3、Stream.forEach
Stream 과 Map.foreach 의 공통점 은 모두 lambda 표현 식 을 사용 했다 는 것 이다.그러나 이들 의 소스 코드 는 재 활용 할 곳 이 없다.
힘 들 었 는 지 모 르 겠 지만 먼저 테스트 결 과 를 올 려 보 세 요.

맵 foreach 보다 시간 이 더 많이 걸 립 니 다.
다음은 Straam.foreach 순서 흐름 의 소스 코드 를 말씀 드 리 겠 습 니 다.이것 도 복잡 하지 않 지만 피곤 하면 먼저 정 리 를 보 세 요.
Stream.foreach 의 실행 자 는 분류 기 입 니 다.HashMap 의 분류 기 소스 코드 는 HashMap 류 에 있 습 니 다.정적 내부 클래스 로 Entry Spliterator 라 고 합 니 다.
다음은 순서대로 실행 하 는 방법 입 니 다.

public void forEachRemaining(Consumer<!--? super Map.Entry<K,V-->> action) {
    int i, hi, mc;
    if (action == null)
        throw new NullPointerException();
    HashMap<k,v> m = map;
    Node<k,v>[] tab = m.table;
    if ((hi = fence) < 0) {
        mc = expectedModCount = m.modCount;
        hi = fence = (tab == null) ? 0 : tab.length;
    }
    else
        mc = expectedModCount;
    if (tab != null && tab.length >= hi &&
        (i = index) >= 0 && (i < (index = hi) || current != null)) {
        Node<k,v> p = current;
        current = null;
        do {
            if (p == null)
                p = tab[i++];
            else {
                action.accept(p);
                p = p.next;
            }
        } while (p != null || i < hi);
        if (m.modCount != mc)
            throw new ConcurrentModificationException();
    }
}

상기 소스 코드 에서 우 리 는 모든 배열 을 순서대로 스 캔 해 야 한 다 는 것 을 쉽게 알 수 있다.
총화
이로써 맵 의 네 가지 옮 겨 다 니 는 방법 을 모두 테스트 하 였 으 니,우 리 는 간단하게 두 가지 결론 을 얻 을 수 있다.

Map 의 옮 겨 다 니 는 성능 은 내부 table 배열 의 크기 와 관련 이 있 습 니 다.즉,자주 사용 하 는 매개 변수 initial capacity 와 관련 이 있 습 니 다.어떤 옮 겨 다 니 는 방식 이 든

성능(높 은 것 에서 낮은 것 으로):교체 기==증강 형 For 순환>Map.foreach>Stream.foreach

여기 서 몇 배,몇 배의 성능 차 이 는 말 할 것 도 없고 데이터 세트 크기 는 모두 헛소리 입 니 다.우리 가 initial capacity 를 지정 하지 않 을 때 네 가지 옮 겨 다 니 는 방법 은 모두 3ms 입 니 다.이 3ms 는 입 출력 흐름 의 소모 시간 입 니까?실제 옮 겨 다 니 는 데 소모 되 는 시간 은 0 이기 때문에 통계 집합 이 크 지 않 을 때 어떤 것 을 사용 하 든 상 관 없 습 니 다.입 출력 흐름 을 추가 하지 않 으 면 1ms 가 안 되 는 것 과 같 습 니 다.많은 경우 성능 소 모 는 옮 겨 다 니 는 업무 작업 이다.이 글 은 코드 를 최적화 시 키 기 위해 foreach 를 교체 기로 바 꾸 는 것 이 아니 라 대부분 장면 에서 교체 자체 의 성능 에 관심 을 가 질 필요 가 없다.Stream 과 Lambda 가 가 져 온 가 독성 향상 이 더욱 중요 하 다.
그래서 이 글 의 목적 은 지식 확장 이 라 고 생각 하 세 요.상기 에서 말 한 성능 문 제 를 제외 하고 그 중에서 얻 을 수 있 는 지식 도 있 습 니 다.

HashMap 의 배열 은 table 배열 에 저 장 된 것

table 배열 은 resize 방법 으로 초기 화 되 었 으 며,new Map 은 배열 을 초기 화 하지 않 습 니 다

Map 은 table 배열 이 아래 표 시 된 0 에서 점점 정렬 되 기 때문에 그 는 무질서 하 다

.

keyset().iterator,values.iterator,entry Set.iterator 는 본질 적 인 차이 가 없고 같은 교체 기

를 사용 합 니 다.

여러 가지 옮 겨 다 니 는 방법 중 교체 기만 remove 할 수 있 습 니 다.증강 형 for 순환 바 텀 도 교체 기 이지 만 이 문법 당 은 remove 방법

을 숨 겼 습 니 다.

매번 교체 기 방법 을 호출 할 때마다 new 하나의 교체 기 를 사용 하지만 하나만 수정 할 수 있 습 니 다

Map.foreach 는 Stream.foreach 와 똑 같이 보이 지만 실제 실현 은 다르다

첨부:네 가지 원본 코드

private static void forEach(HashMap map) {
    for (Iterator<map.entry<string, integer="">> it = map.entrySet().iterator(); it.hasNext();){
        Map.Entry<string, integer=""> item = it.next();
        // System.out.print(item.getKey());
        // do something
    }
}


private static void forEach0(HashMap<string, integer=""> map) {
    for (Map.Entry entry : map.entrySet()) {
        System.out.print(entry.getKey());
    }
}

private static void forEach1(HashMap<string, integer=""> map) {
    map.forEach((key, value) -> {
        System.out.print(key);
    });

}

private static void forEach2(HashMap<string, integer=""> map) {
    map.entrySet().stream().forEach(e -> {
        System.out.print(e.getKey());
    });

}

첨부:전체 테스트 클래스 와 테스트 결과+이상 한 문제

public class MapForEachTest {

    public static void main(String[] args) {
        HashMap<string, integer=""> map0 = new HashMap<string, integer="">(100000);
        HashMap<string, integer=""> map1 = new HashMap<string, integer="">();
        initData(map0);
        initData(map1);

        
        testIterator(map0);
        testIterator(map1);
        testFor(map0);
        testFor(map1);
        testMapForeach(map0);
        testMapForeach(map1);
        testMapStreamForeach(map0);
        testMapStreamForeach(map1);

    }



    private static void testIterator(HashMap map) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < 100; i++) {
            forEach(map);
        }
        long end = System.currentTimeMillis();
        System.out.println("");
        System.out.println("HashMap Size: " + map.size() +  "       : " + (end - start) + " ms");
    }

    private static void testFor(HashMap map) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < 100; i++) {
            forEach0(map);
        }
        long end = System.currentTimeMillis();
        System.out.println("");
        System.out.println("HashMap Size: " + map.size() +  "    For   : " + (end - start) + " ms");
    }

    private static void testMapForeach(HashMap map) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < 100; i++) {
            forEach1(map);
        }
        long end = System.currentTimeMillis();
        System.out.println("");
        System.out.println("HashMap Size: " + map.size() +  " MapForeach   : " + (end - start) + " ms");
    }


    private static void testMapStreamForeach(HashMap map) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < 100; i++) {
            forEach2(map);
        }
        long end = System.currentTimeMillis();
        System.out.println("");
        System.out.println("HashMap Size: " + map.size() +  " MapStreamForeach   : " + (end - start) + " ms");
    }

    private static void forEach(HashMap map) {
        for (Iterator<map.entry<string, integer="">> it = map.entrySet().iterator(); it.hasNext();){
            Map.Entry<string, integer=""> item = it.next();
            System.out.print(item.getKey());
            // do something
        }
    }


    private static void forEach0(HashMap<string, integer=""> map) {
        for (Map.Entry entry : map.entrySet()) {
            System.out.print(entry.getKey());
        }
    }

    private static void forEach1(HashMap<string, integer=""> map) {
        map.forEach((key, value) -> {
            System.out.print(key);
        });

    }

    private static void forEach2(HashMap<string, integer=""> map) {
        map.entrySet().stream().forEach(e -> {
            System.out.print(e.getKey());
        });

    }

    private static void initData(HashMap map) {
        map.put("a", 0);
        map.put("b", 1);
        map.put("c", 2);
        map.put("d", 3);
        map.put("e", 4);
        map.put("f", 5);
    }

}

테스트 결과:

만약 당신 이 위의 문장 을 진지 하 게 보 았 다 면 테스트 결과 에 이상 한 점 이 있 음 을 발견 할 수 있 을 것 입 니 다.
MapStreamForeach 의 소모 시간 이 줄 어 든 것 같 습 니 다.
나 는 너 에 게 이것 이 데이터 의 원인 이 아니 라 고 말 할 수 있다.나의 테스트 결 과 를 보면 직접적인 원인 은 Map.foreach 를 먼저 실 행 했 기 때문이다.만약 에 네가 MapForeach 와 MapStreamForeach 를 실행 순 서 를 바 꾸 면 나중에 실 행 된 시간 이 더 적 다 는 것 을 알 게 될 것 이다.
이상 은 자바 에서 맵 의 성능 문 제 를 분석 하 는 상세 한 내용 입 니 다.자바 맵 의 성능 에 관 한 자 료 는 다른 관련 글 을 주목 하 세 요!