포스트

Java (3) - Collection: HashMap은 왜 빠른가

ArrayList와 LinkedList의 삽입 시간을 재고 HashMap의 버킷 구조를 확인한 뒤 hashCode를 망가뜨려 O(1)이 O(n)이 되는 것을 다룹니다.

게시
By 송민아
22 분읽는 시간
Java (3) - Collection: HashMap은 왜 빠른가

자바 기초 시리즈의 3편입니다. 전체 목차는 0편에 있습니다.

2편에서 HashSet이 hashCode로 자리를 먼저 정한다고 했습니다. 이번 편은 그 자리가 어떻게 정해지는지와 자리 정하기가 망가지면 얼마나 느려지는지를 봅니다.

먼저 더 단순한 컬렉션부터 시작합니다.

ArrayList와 LinkedList

교과서 설명은 이렇습니다.

  ArrayList LinkedList
내부 구조 배열 앞뒤로 이어진 노드
인덱스 조회 O(1) O(n)
중간 삽입/삭제 O(n) O(1)

그래서 “삽입이 많으면 LinkedList“라고 배웁니다. 재보면 그렇지 않은 경우가 많습니다.

확인 1: 10만 건으로 재본다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import java.util.*;

public class Coll {
    static long ms(Runnable r) {
        long t = System.nanoTime();
        r.run();
        return (System.nanoTime() - t) / 1_000_000;
    }

    public static void main(String[] args) {
        int N = 100_000;

        List<Integer> al = new ArrayList<>();
        List<Integer> ll = new LinkedList<>();
        for (int i = 0; i < N; i++) { al.add(i); ll.add(i); }

        System.out.println("=== 맨 앞에 삽입 10만 번 ===");
        System.out.println("ArrayList  = " + ms(() -> {
            List<Integer> l = new ArrayList<>();  for (int i=0;i<N;i++) l.add(0, i); }) + "ms");
        System.out.println("LinkedList = " + ms(() -> {
            List<Integer> l = new LinkedList<>(); for (int i=0;i<N;i++) l.add(0, i); }) + "ms");

        System.out.println("=== 맨 뒤에 삽입 10만 번 ===");
        System.out.println("ArrayList  = " + ms(() -> {
            List<Integer> l = new ArrayList<>();  for (int i=0;i<N;i++) l.add(i); }) + "ms");
        System.out.println("LinkedList = " + ms(() -> {
            List<Integer> l = new LinkedList<>(); for (int i=0;i<N;i++) l.add(i); }) + "ms");

        System.out.println("=== 가운데 삽입 10만 번 ===");
        System.out.println("ArrayList  = " + ms(() -> {
            List<Integer> l = new ArrayList<>();  for (int i=0;i<N;i++) l.add(l.size()/2, i); }) + "ms");
        System.out.println("LinkedList = " + ms(() -> {
            List<Integer> l = new LinkedList<>(); for (int i=0;i<N;i++) l.add(l.size()/2, i); }) + "ms");

        System.out.println("=== 인덱스 조회 10만 번 ===");
        System.out.println("ArrayList  = " + ms(() -> {
            long s=0; for (int i=0;i<N;i++) s += al.get(i); }) + "ms");
        System.out.println("LinkedList = " + ms(() -> {
            long s=0; for (int i=0;i<N;i++) s += ll.get(i); }) + "ms");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

=== 맨 앞에 삽입 10만 번 ===
ArrayList  = 655ms
LinkedList = 5ms
=== 맨 뒤에 삽입 10만 번 ===
ArrayList  = 3ms
LinkedList = 4ms
=== 가운데 삽입 10만 번 ===
ArrayList  = 299ms
LinkedList = 7797ms
=== 인덱스 조회 10만 번 ===
ArrayList  = 3ms
LinkedList = 5525ms

세 번째 블록이 예상과 반대입니다. 가운데 삽입인데 LinkedList가 26배 느립니다.

이유는 LinkedList의 O(1)에 붙는 단서에 있습니다. 삽입 자체는 O(1)이지만, 삽입할 자리까지 가는 게 O(n)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[ ArrayList.add(중간, x) ]

   [0][1][2][3][4][5][6][7]
              ▲
              │ 자리 찾기는 O(1) (배열이라 바로 계산)
              └─▶ 뒤의 원소를 한 칸씩 민다  O(n)
                  하지만 이건 메모리 블록 통째 복사라 매우 빠르다


[ LinkedList.add(중간, x) ]

   [0]→[1]→[2]→[3]→[4]→[5]→[6]→[7]
    ●───────────────▶ 자리 찾기가 O(n) (한 칸씩 따라가야 한다)
                      노드마다 다른 메모리 주소로 점프
              ▲
              └─▶ 연결만 바꾸는 건 O(1)

ArrayList의 O(n)은 “배열 복사”고 LinkedList의 O(n)은 “포인터 따라가기” 입니다. 같은 O(n)이지만 실제 속도는 몇십 배 차이납니다. 배열 복사는 CPU가 잘하는 일이고, 흩어진 메모리를 점프하는 건 CPU가 못하는 일이기 때문입니다.

LinkedList가 압도적인 건 첫 번째 블록, 맨 앞 삽입뿐입니다. 여기서는 자리를 찾을 필요가 없습니다.

숫자는 제 환경에서 나온 예시입니다. 장비와 JVM 상태에 따라 달라집니다. 봐야 할 건 가운데 삽입에서 순서가 뒤집힌다는 것이지 655나 7797 같은 값이 아닙니다.

결론은 단순합니다. 잘 모르겠으면 ArrayList를 씁니다. LinkedList가 유리한 건 앞뒤로만 넣고 빼는 큐·덱 용도인데, 그 용도라면 ArrayDeque가 보통 더 빠릅니다.

HashMap의 구조

HashMap은 배열 하나입니다. 배열의 각 칸을 버킷이라고 부릅니다.

1
2
3
4
5
6
7
8
9

   table (기본 크기 16)

   [0]  ●──▶ null
   [1]  ●──▶ ("apple", 1) ──▶ ("cherry", 3)      ← 충돌하면 이어 붙는다
   [2]  ●──▶ null
   ...
   [12] ●──▶ ("elderberry", 5)
   ...
   [15] ●──▶ ("durian", 4)

키를 넣을 때 몇 번 칸에 넣을지를 계산합니다. 여기가 O(1)의 정체입니다.

1
2
3
4
5

   ① key.hashCode()          객체가 정한 정수
   ② h ^ (h >>> 16)          상위 16비트를 하위로 섞는다 (spread)
   ③ 결과 & (table 길이 - 1) 나머지 연산과 같은 효과
   ────────────────────────
   → 버킷 번호

②가 왜 있냐면, ③이 하위 비트만 보기 때문입니다. 테이블 길이가 16이면 & 15라서 하위 4비트만 씁니다. 해시 값의 상위 비트가 아무리 잘 흩어져 있어도 하위 4비트가 몰려 있으면 소용이 없습니다. 그래서 상위 비트를 하위로 한 번 섞어줍니다.

③이 %가 아니라 &인 이유는 테이블 길이가 항상 2의 거듭제곱이기 때문입니다. 그래서 & (n-1)이 % n과 같은 결과를 내고, 훨씬 빠릅니다.

확인 2: 버킷 번호를 직접 계산한다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class Bucket {
    static int spread(int h) { return h ^ (h >>> 16); }

    public static void main(String[] args) {
        String[] keys = {"apple", "banana", "cherry", "durian", "elderberry"};
        int n = 16;

        System.out.printf("%-12s %12s %12s %8s%n", "key", "hashCode()", "spread", "버킷");
        for (String k : keys) {
            int h = k.hashCode();
            int s = spread(h);
            System.out.printf("%-12s %12d %12d %8d%n", k, h, s, s & (n - 1));
        }

        System.out.println();
        System.out.println("\"Aa\" 버킷 = " + (spread("Aa".hashCode()) & 15));
        System.out.println("\"BB\" 버킷 = " + (spread("BB".hashCode()) & 15));
    }
}

1
2
3
4
5
6
7
8
9

key            hashCode()       spread       버킷
apple            93029210     93030097        1
banana        -1396355227  -1396317280        0
cherry        -1361513063  -1361552575        1
durian        -1320500043  -1320520193       15
elderberry      683702092    683696012       12

"Aa" 버킷 = 0
"BB" 버킷 = 0

apple과 cherry가 둘 다 1번 버킷입니다. 해시 값은 전혀 다른데 하위 4비트가 같았습니다. 이게 2편에서 본 충돌이고, 같은 버킷에 두 개가 이어 붙습니다.

여기까지가 get()이 O(1)인 이유의 전부입니다.

1
2
3
4
5

   map.get("cherry")
     ① "cherry".hashCode()   ── 계산 한 번
     ② spread 후 & 15 = 1    ── 계산 한 번
     ③ table[1] 로 바로 점프  ── 배열 인덱스 접근
     ④ 그 버킷 안에서 equals  ── 보통 1~2개

원소가 100만 개여도 ①②③은 똑같습니다. ④에 걸리는 것만 몇 개인지가 성능을 결정합니다.

자리 정하기가 망가지면

④에 전부 몰리면 어떻게 되는지 봅니다.

확인 3: 모든 hashCode를 1로 만든다

2편에서 return 1;도 규약 위반은 아니라고 했습니다. 결과는 맞습니다. 재보면 이렇습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import java.util.*;

public class Hash {
    static class GoodKey {
        final int id;
        GoodKey(int id) { this.id = id; }
        @Override public boolean equals(Object o) {
            return o instanceof GoodKey && ((GoodKey) o).id == id;
        }
        @Override public int hashCode() { return Integer.hashCode(id); }
    }

    static class BadKey {
        final int id;
        BadKey(int id) { this.id = id; }
        @Override public boolean equals(Object o) {
            return o instanceof BadKey && ((BadKey) o).id == id;
        }
        @Override public int hashCode() { return 1; }        // 전부 1
    }

    public static void main(String[] args) {
        int N = 50_000;

        Map<GoodKey, Integer> good = new HashMap<>();
        Map<BadKey, Integer> bad = new HashMap<>();
        for (int i = 0; i < N; i++) { good.put(new GoodKey(i), i); bad.put(new BadKey(i), i); }

        System.out.println("good.size() = " + good.size());
        System.out.println("bad.size()  = " + bad.size());

        long t1 = System.nanoTime();
        for (int i = 0; i < N; i++) good.get(new GoodKey(i));
        long g = (System.nanoTime() - t1) / 1_000_000;

        long t2 = System.nanoTime();
        for (int i = 0; i < N; i++) bad.get(new BadKey(i));
        long b = (System.nanoTime() - t2) / 1_000_000;

        System.out.println("hashCode 제대로 = " + g + "ms");
        System.out.println("hashCode 전부 1 = " + b + "ms");
    }
}

1
2
3
4

good.size() = 50000
bad.size()  = 50000
hashCode 제대로 = 3ms
hashCode 전부 1 = 7408ms

크기는 둘 다 5만으로 정확합니다. 결과는 맞습니다. 조회에 걸린 시간만 2400배 차이납니다.

1
2
3
4
5
6
7
8
9

[ hashCode 제대로 ]                [ hashCode 전부 1 ]

  [0] ●──▶ ■                        [0] ●──▶ null
  [1] ●──▶ ■ ■                      [1] ●──▶ ■■■■■■■■■■■■■■■ ... 5만 개
  [2] ●──▶ ■                        [2] ●──▶ null
  ...                               ...
  [n] ●──▶ ■ ■                      [n] ●──▶ null

  버킷당 1~2개 → equals 1~2번        버킷 하나에 전부 → equals 최대 5만 번

HashMap이 LinkedList가 됐습니다. hashCode가 하는 일은 “자리를 흩뿌리는 것”이고, 그게 안 되면 O(1)이 아니라 O(n)입니다.

hashCode를 재정의하지 않는 것보다 잘못 재정의하는 게 더 위험한 이유입니다. 안 하면 2편처럼 결과가 틀려서 금방 발견되지만, 이건 결과가 맞아서 안 보입니다. 데이터가 늘어날수록 느려지기만 합니다.

자바 8의 트리화

같은 버킷에 너무 많이 쌓이면 자바 8부터는 그 버킷을 연결 리스트에서 균형 이진 트리로 바꿉니다. 대략 한 버킷에 8개가 넘고 테이블 크기가 64 이상일 때입니다. 그 버킷 안에서의 탐색이 O(n)에서 O(log n)이 됩니다.

그런데 위 결과는 트리화가 있는데도 2400배 느렸습니다. 트리로 바꾸려면 원소들을 순서대로 줄 세울 수 있어야 하는데, BadKey는 해시가 전부 같고 Comparable도 아니라 줄을 세울 기준이 없었기 때문입니다.

키에 Comparable만 붙여서 다시 재보면 이렇게 달라집니다.

1
2
3
4

static class BadKey implements Comparable<BadKey> {
    // hashCode 는 여전히 return 1
    @Override public int compareTo(BadKey o) { return Integer.compare(id, o.id); }
}

1

hashCode 전부 1 + Comparable = 15ms

7408ms가 15ms가 됐습니다. 트리화가 제대로 동작한 것입니다.

그렇다고 Comparable을 붙여서 해결할 문제는 아닙니다. 트리화는 최악을 덜 나쁘게 만드는 안전장치지 정상 경로가 아닙니다. 고쳐야 할 건 hashCode입니다.

여러 스레드에서 쓰면

HashMap은 스레드 안전하지 않습니다. 문서에도 그렇게 적혀 있습니다. 그런데 안 지켜도 잘 도는 것처럼 보일 때가 많아서 넘어가기 쉽습니다.

확인 4: 스레드 16개로 동시에 넣는다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import java.util.*;
import java.util.concurrent.*;

public class Race {
    static void run(Map<Integer, Integer> map, String name) throws Exception {
        int threads = 16, perThread = 10_000;
        ExecutorService pool = Executors.newFixedThreadPool(threads);
        CountDownLatch latch = new CountDownLatch(threads);

        for (int t = 0; t < threads; t++) {
            final int base = t * perThread;
            pool.submit(() -> {
                try {
                    for (int i = 0; i < perThread; i++) map.put(base + i, i);
                } finally { latch.countDown(); }
            });
        }
        latch.await(30, TimeUnit.SECONDS);
        pool.shutdown();

        System.out.println(name + " 기대 크기 = " + (threads * perThread)
                + ", 실제 크기 = " + map.size());
    }

    public static void main(String[] args) throws Exception {
        for (int r = 0; r < 3; r++) run(new HashMap<>(), "HashMap          ");
        for (int r = 0; r < 3; r++) run(new ConcurrentHashMap<>(), "ConcurrentHashMap");
    }
}

키는 스레드마다 겹치지 않게 나눠줬습니다. 덮어쓸 일이 없으니 16만 개가 그대로 들어가야 합니다.

1
2
3
4
5
6

HashMap           기대 크기 = 160000, 실제 크기 = 140380
HashMap           기대 크기 = 160000, 실제 크기 = 117754
HashMap           기대 크기 = 160000, 실제 크기 = 123082
ConcurrentHashMap 기대 크기 = 160000, 실제 크기 = 160000
ConcurrentHashMap 기대 크기 = 160000, 실제 크기 = 160000
ConcurrentHashMap 기대 크기 = 160000, 실제 크기 = 160000

2만~4만 개가 사라졌고, 매번 다른 만큼 사라집니다. 예외는 한 건도 안 났습니다.

여러 스레드가 동시에 재고 수량 같은 값을 갱신할 때 결과가 매번 다르게 남는 것과 같은 모양입니다. 대상이 DB의 한 행이든 HashMap의 내부 배열이든 원리는 같습니다.

원인도 같습니다. put() 한 번이 읽고 → 자리 계산하고 → 쓰는 여러 단계로 쪼개져 있고, 그 사이에 다른 스레드가 끼어듭니다. 특히 원소가 늘어 테이블 크기를 두 배로 늘리는(리사이징) 순간에 두 스레드가 동시에 들어오면 한쪽이 만든 결과가 통째로 버려집니다.

ConcurrentHashMap은 버킷 단위로만 잠가서 이걸 막습니다. 맵 전체를 잠그는 게 아니라 건드리는 칸만 잠그기 때문에, 다른 버킷을 쓰는 스레드는 안 기다립니다.

대안으로 Collections.synchronizedMap(new HashMap<>())도 있습니다. 이건 모든 메서드를 통째로 잠급니다. 안전하지만 스레드가 많아지면 전부 줄을 섭니다. 새로 쓰는 코드라면 ConcurrentHashMap이 기본입니다.

무엇을 고를까

필요한 것 고르는 것 이유
순서대로 담고 인덱스로 꺼낸다 ArrayList 대부분의 경우 기본값
앞뒤로만 넣고 뺀다 ArrayDeque LinkedList보다 빠르다
중복을 없앤다 HashSet equals/hashCode 필요
중복 없이 넣은 순서를 유지한다 LinkedHashSet  
중복 없이 정렬된 순서로 본다 TreeSet Comparable 필요, O(log n)
키로 값을 찾는다 HashMap  
키로 찾되 넣은 순서를 유지한다 LinkedHashMap  
키로 찾되 정렬된 순서로 본다 TreeMap  
여러 스레드가 같이 쓴다 ConcurrentHashMap  

순서 이야기는 직접 보는 게 빠릅니다.

1
2
3
4
5
6
7
8

String[] keys = {"durian", "apple", "cherry", "banana", "elderberry"};

Map<String, Integer> hash   = new HashMap<>();
Map<String, Integer> linked = new LinkedHashMap<>();
Map<String, Integer> tree   = new TreeMap<>();
for (int i = 0; i < keys.length; i++) {
    hash.put(keys[i], i); linked.put(keys[i], i); tree.put(keys[i], i);
}

1
2
3
4

넣은 순서    = [durian, apple, cherry, banana, elderberry]
HashMap       = [banana, apple, cherry, elderberry, durian]
LinkedHashMap = [durian, apple, cherry, banana, elderberry]
TreeMap       = [apple, banana, cherry, durian, elderberry]

HashMap의 순서는 넣은 순서도 아니고 정렬된 순서도 아닙니다. 버킷 번호 순서라서 사람이 보기엔 무작위입니다. 확인 2에서 계산한 버킷 번호(banana=0, apple=1, cherry=1, elderberry=12, durian=15)와 정확히 같은 순서입니다.

HashMap의 순회 순서에 의존하는 코드를 쓰면 안 됩니다. 지금 우연히 원하는 순서로 나와도, 원소가 늘어 테이블이 커지면 순서가 바뀝니다. 순서가 필요하면 LinkedHashMap이나 TreeMap을 명시적으로 씁니다.

내가 헷갈렸던 지점

정리

  • LinkedList의 중간 삽입은 삽입 자체만 O(1)이고 자리를 찾는 게 O(n) 이다. 가운데 삽입 10만 번에서 ArrayList가 26배 빨랐다. 잘 모르겠으면 ArrayList 를 쓴다
  • HashMap은 배열 하나고, hashCode() → 상위 비트 섞기 → & (길이-1)로 버킷 번호를 정한다. 원소가 몇 개든 이 계산량은 같다. 그게 O(1)의 전부다
  • 테이블 길이가 2의 거듭제곱인 이유는 % n 대신 & (n-1) 을 쓰기 위해서고, 상위 비트를 섞는 이유는 하위 비트만 쓰기 때문이다
  • 모든 키의 hashCode를 1로 만들면 결과는 맞는데 조회가 2400배 느려진다. 규약 위반이 아니라서 테스트로는 안 잡힌다. 자바 8의 트리화는 안전장치일 뿐이고, 키가 Comparable이 아니면 그 안전장치도 잘 안 듣는다
  • HashMap을 여러 스레드에서 쓰면 16만 개 중 2만~4만 개가 조용히 사라진다. 예외는 안 난다. 공유해야 하면 ConcurrentHashMap 을 쓴다
  • HashMap의 순회 순서는 버킷 번호 순서다. 넣은 순서도 정렬 순서도 아니고, 테이블이 커지면 바뀐다. 순서가 필요하면 LinkedHashMap이나 TreeMap을 쓴다

4편에서 List<String>의 String이 컴파일하면 사라진다는 것을 봅니다. 그리고 그 때문에 못 하게 되는 것들을 봅니다.

Java, 기초
java collection hashmap arraylist linkedlist concurrenthashmap
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.