Map 인터페이스와 구현 클래스

게시판에서 글 제목마다 조회 수를 관리한다고 해 봅시다. array 글의 조회 수를 알고 싶을 때 필요한 것은 'array라는 제목에 연결된 숫자 하나'입니다. 앞 장의 Set은 어떤 값이 들어 있는지만 답할 수 있어서, 제목에 숫자를 붙여 둘 방법이 없습니다. 이렇게 한 값으로 다른 값을 찾아야 할 때 쓰는 자료구조가 맵(map)입니다.

이 글에서는 먼저 맵 없이 배열 두 개로 버티다가 생기는 문제를 확인합니다. 그다음 Java의 Map 인터페이스가 제공하는 기본 메서드, 없는 키와 null 값을 구분하는 방법, 키와 값을 한꺼번에 훑는 뷰를 차례로 살펴봅니다. 이어서 세 구현 클래스 HashMap, LinkedHashMap, TreeMap이 어떻게 다른지 비교해 고르는 기준을 정리하고, 게시글 저장소 안에 맵을 감추는 예제로 마무리합니다.

배열 두 개에 나눠 담으면 짝이 어긋납니다

맵을 모른다면 제목 배열과 조회 수 배열을 따로 만들고, 같은 인덱스끼리 짝이라고 정하는 방법을 떠올리기 쉽습니다. titles[0]이 thread이면 그 조회 수는 viewCount[0]인 70이라는 식입니다. 이런 배열을 병렬 배열(parallel arrays)이라고 합니다. 문제는 이 약속을 코드가 아니라 사람이 지켜야 한다는 점입니다. 다음 코드는 제목을 알파벳순으로 출력하려고 제목 배열만 정렬합니다.

import java.util.Arrays;

public final class ParallelArrayMapBug {
    public static void main(String[] args) {
        String[] titles = {"thread", "array", "hash"};
        int[] viewCount = {70, 30, 50};
        Arrays.sort(titles);
        for (int i = 0; i < titles.length; i++) {
            System.out.println(titles[i] + "=" + viewCount[i]);
        }
    }
}

array=70
hash=30
thread=50

세 줄이 모두 틀렸습니다. 원래 array의 조회 수는 30, hash는 50, thread는 70입니다. Arrays.sort(titles)는 titles 배열 안의 순서만 array, hash, thread로 바꾸고 viewCount 배열은 70, 30, 50 그대로 둡니다. 그런데 반복문은 여전히 같은 인덱스끼리 짝지어 출력하므로, 0번 칸에서 array와 70이 만나 엉뚱한 짝이 생깁니다.

더 곤란한 점은 컴파일러도, 실행 중의 검사도 이 잘못을 알려 주지 않는다는 것입니다. 타입은 모두 맞고 예외도 나지 않으니 출력을 직접 확인하기 전에는 아무도 모릅니다. 정렬뿐 아니라 삭제나 삽입도 마찬가지여서, 한쪽 배열만 고치는 순간 짝이 어긋납니다.

제목과 조회 수를 record Post(String title, int viewCount) 같은 객체 하나로 묶어 배열에 담으면 정렬해도 짝은 함께 움직입니다. 하지만 'array의 조회 수는?'이라는 질문에 답하려면 여전히 배열을 처음부터 훑어야 합니다. 짝을 묶어 두는 일과 키로 바로 찾는 일을 함께 맡기려면 맵이 필요합니다.

Map은 키와 값을 한 쌍으로 저장합니다

맵은 키(key)와 값(value)을 한 쌍으로 저장하고, 이 한 쌍을 매핑(mapping) 또는 엔트리(entry)라고 부릅니다. 키는 값을 찾을 때 쓰는 이름표이므로 한 맵 안에서 중복될 수 없습니다. 값은 중복되어도 괜찮아서, 서로 다른 두 제목의 조회 수가 똑같이 40이어도 됩니다. Java에서는 java.util.Map<K, V> 인터페이스가 맵의 메서드를 정의하며, K는 키의 타입이고 V는 값의 타입입니다.

자주 쓰는 메서드부터 실행해 보겠습니다. 다음 코드는 같은 키에 두 번 put하고, 있는 키와 없는 키를 조회한 뒤 키를 지웁니다.

import java.util.HashMap;
import java.util.Map;

public final class MapBasics {
    public static void main(String[] args) {
        Map<String, Integer> viewCount = new HashMap<>();
        System.out.println("first put=" + viewCount.put("array", 30));
        System.out.println("second put=" + viewCount.put("array", 45));
        System.out.println("get=" + viewCount.get("array"));
        System.out.println("missing=" + viewCount.get("queue"));
        System.out.println("contains=" + viewCount.containsKey("array"));
        System.out.println("removed=" + viewCount.remove("array"));
        System.out.println("size=" + viewCount.size());
    }
}

first put=null
second put=30
get=45
missing=null
contains=true
removed=45
size=0

첫 put은 array라는 키가 아직 없으므로 새 매핑을 만들고 null을 돌려줍니다. 두 번째 put은 같은 키에 45를 넣는데, 이때 매핑이 하나 더 생기지 않고 기존 값 30이 45로 바뀝니다. 그래서 put은 바뀌기 전의 값 30을 돌려주고, 이어지는 get("array")는 45를 읽습니다. 키가 중복될 수 없다는 규칙이 '같은 키에 다시 넣으면 값이 교체된다'는 동작으로 나타난 것입니다.

없는 키를 get("queue")처럼 조회하면 예외가 아니라 null이 돌아옵니다. 키가 있는지만 알고 싶을 때는 containsKey를 씁니다. remove는 매핑을 지우면서 지운 값을 돌려주므로 마지막 크기는 0이 됩니다.

키가 같은지 판단하는 방법은 구현마다 다릅니다. HashMap은 해시 장에서 배운 것처럼 키의 hashCode()로 찾아볼 칸을 고르고 equals()로 같은 키인지 확인하므로, HashSet의 원소와 똑같은 규칙이 키에 적용됩니다. 값이 같은 두 객체를 같은 키로 다루려면 키 클래스가 equals와 hashCode를 함께 재정의해야 하고, 맵에 넣은 뒤에는 키 객체의 상태를 바꾸면 안 됩니다. 넣은 뒤에 hashCode 계산에 쓰이는 필드가 바뀌면 엉뚱한 칸을 찾게 되어, 매핑이 맵 안에 있는데도 찾지 못합니다. String, Integer, 불변 값만 담은 record처럼 상태가 바뀌지 않는 타입을 키로 쓰는 이유가 이것입니다.

없는 키와 null 값 구분하기

get이 null을 돌려줬다고 해서 그 키가 없다고 단정할 수는 없습니다. HashMap은 값으로 null을 저장하는 것도 허용하기 때문입니다. 다음 코드는 queue에 null을 직접 넣어 두고, 아예 없는 키 stack과 비교합니다.

import java.util.HashMap;
import java.util.Map;

public final class NullValueLookup {
    public static void main(String[] args) {
        Map<String, Integer> counts = new HashMap<>();
        counts.put("queue", null);
        System.out.println("get queue=" + counts.get("queue"));
        System.out.println("get stack=" + counts.get("stack"));
        System.out.println("has queue=" + counts.containsKey("queue"));
        System.out.println("has stack=" + counts.containsKey("stack"));
        System.out.println("orDefault=" + counts.getOrDefault("queue", 0));
        System.out.println("putIfAbsent=" + counts.putIfAbsent("queue", 20));
        System.out.println("after=" + counts.get("queue"));
    }
}

get queue=null
get stack=null
has queue=true
has stack=false
orDefault=null
putIfAbsent=null
after=20

처음 두 줄을 보면 null이 저장된 키와 없는 키를 get으로는 구분할 수 없습니다. 둘을 가르는 것은 containsKey입니다. queue라는 키는 존재하므로 true이고, stack은 없으므로 false입니다. put의 반환값도 사정이 같아서, null이 돌아왔다면 이전 매핑이 없었는지 이전 값이 null이었는지 알 수 없습니다.

다섯째 줄은 자주 틀리는 부분입니다. getOrDefault(key, defaultValue)는 키에 대한 매핑이 아예 없을 때만 기본값을 돌려줍니다. queue에는 값이 null인 매핑이 있으므로, 기본값 0 대신 저장된 null이 돌아옵니다. 이 결과를 int count = counts.getOrDefault("queue", 0);처럼 int 변수에 받으면 자동 언박싱 과정에서 NullPointerException이 납니다.

반대로 putIfAbsent는 값이 null인 매핑을 '없는 것'으로 봅니다. 그래서 queue에 20을 저장하고 이전 값 null을 돌려줍니다. 뒤에서 볼 merge와, Map 활용: 중복 키 처리와 merge·compute에서 쓸 computeIfAbsent도 같은 방식으로 동작합니다. 같은 맵의 같은 키를 두고 메서드마다 '없음'의 기준이 다른 셈입니다.

가장 간단한 해결책은 맵에 null 값을 넣지 않는 것입니다. 값이 null일 수 없다고 정해 두면 get의 null은 언제나 '키 없음'이라는 한 가지 뜻이 되고, 메서드마다 기준이 다른 문제도 사라집니다. 이 글의 나머지 예제는 모두 이 규칙을 따릅니다. null을 '아직 집계하지 않음' 같은 의미 있는 값으로 꼭 써야 한다면, 그 코드에서는 containsKey로 키의 존재를 따로 확인해야 합니다.

merge로 조회 수 누적하기

조회 수를 누적하려면 기존 값을 읽고, 더하고, 다시 저장하는 세 단계가 필요합니다. 키가 처음 나오는 경우까지 생각하면 containsKey로 분기해 put을 두 번 쓰는 코드가 되기 쉽습니다. merge(key, value, function)은 이 과정을 한 번의 호출로 처리합니다. 키가 없거나 값이 null이면 주어진 value를 그대로 저장하고, 기존 값이 있으면 function에 기존 값과 새 값을 넘겨 계산한 결과를 저장합니다.

import java.util.HashMap;
import java.util.Map;

public final class TitleViewCountMap {
    public static void main(String[] args) {
        Map<String, Integer> viewCount = new HashMap<>();
        add(viewCount, "array", 30);
        add(viewCount, "hash", 50);
        add(viewCount, "array", 20);
        System.out.println("array=" + viewCount.get("array"));
        System.out.println("missing=" + viewCount.getOrDefault("queue", 0));
        for (Map.Entry<String, Integer> entry : viewCount.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }
    }

    private static void add(Map<String, Integer> viewCount, String title, int amount) {
        if (title == null || title.isBlank() || amount <= 0) throw new IllegalArgumentException();
        viewCount.merge(title, amount, Integer::sum);
    }
}

array=50
missing=0
array:50
hash:50

Integer::sum은 정수 두 개를 받아 합을 돌려주는 메서드를 그대로 넘기는 메서드 참조(method reference)로, (oldValue, amount) -> oldValue + amount라는 람다를 짧게 쓴 것입니다. 람다와 메서드 참조는 30장부터 자세히 다룹니다.

첫 add("array", 30)은 키가 없으므로 30을 저장하고, add("hash", 50)도 같은 방식으로 50을 저장합니다. 세 번째 add("array", 20)에서는 기존 값 30이 있으므로 Integer::sum이 30 + 20을 계산해 50을 저장합니다. 그래서 첫 줄은 array=50입니다. 둘째 줄의 getOrDefault("queue", 0)은 없는 키라서 0을 돌려주지만 맵에 queue를 추가하지는 않습니다. 기본값은 돌려받는 값일 뿐 저장되는 값이 아닙니다.

마지막 두 줄은 entrySet()으로 매핑을 하나씩 꺼내 키와 값을 함께 출력한 것입니다. HashMap은 반복 순서를 약속하지 않으므로, 이 두 줄의 순서는 JDK 버전이나 맵의 크기에 따라 달라질 수 있습니다. 순서가 왜 이렇게 나왔는지는 뒤의 구현 비교에서 살펴봅니다.

add 메서드는 맵에 손대기 전에 입력부터 검사합니다. 제목이 비어 있거나 더할 양이 0 이하이면 IllegalArgumentException을 던지므로 이 맵에는 null 값이 들어갈 일이 없습니다. 이 예제는 스레드 하나에서만 실행합니다. 여러 스레드가 같은 HashMap을 동시에 고치면 갱신이 사라지거나 맵이 망가질 수 있으므로, 그때는 동시성 컬렉션에서 다루는 ConcurrentHashMap을 씁니다.

더 깊이: 누적 값이 int 범위를 넘을 때

add는 더할 양이 양수인지는 검사하지만, 더한 결과가 int 범위 안에 있는지는 검사하지 않습니다. 기존 값이 int의 최댓값 2,147,483,647일 때 1을 더하면 Integer::sum은 오버플로를 일으켜 -2,147,483,648을 돌려줍니다. 다음 코드는 시작값이 같은 두 맵에서 Integer::sum과 Math::addExact를 비교합니다.

import java.util.HashMap;
import java.util.Map;

public final class MapMergeOverflowBoundary {
    public static void main(String[] args) {
        Map<String, Integer> raw = new HashMap<>();
        raw.put("array", Integer.MAX_VALUE);
        raw.merge("array", 1, Integer::sum);
        System.out.println("raw=" + raw.get("array"));

        Map<String, Integer> checked = new HashMap<>();
        checked.put("array", Integer.MAX_VALUE);
        try {
            checked.merge("array", 1, Math::addExact);
        } catch (ArithmeticException expected) {
            System.out.println("overflow rejected");
        }
        System.out.println("kept=" + checked.get("array"));
    }
}

raw=-2147483648
overflow rejected
kept=2147483647

첫 맵에는 음수가 조용히 저장됐습니다. 두 번째 맵에서 Math::addExact는 결과가 범위를 넘는 순간 ArithmeticException을 던집니다. Map.merge의 문서는 계산 함수가 예외를 던지면 그 예외를 그대로 전달하고 기존 매핑은 바꾸지 않는다고 정해 두었습니다. 그래서 마지막 줄의 값이 최댓값 그대로 남아 있습니다.

조회 수를 int 범위로 제한한다면 add의 Integer::sum 자리에 Math::addExact를 넣고, 범위를 넘었을 때 호출자에게 어떻게 알릴지 정하면 됩니다. 그보다 큰 수를 다뤄야 한다면 값 타입을 Long으로 바꿔야 합니다. 기존 값이 유지되는 것은 merge 호출 하나에 대한 이야기라는 점도 기억해 두세요. 여러 키를 차례로 갱신하다가 중간에 예외가 나면, 앞에서 성공한 갱신은 되돌려지지 않습니다.

keySet, values, entrySet으로 맵 훑기

맵의 내용을 반복문으로 훑을 때는 세 가지 뷰(view) 가운데 하나를 고릅니다. keySet()은 키들을 Set으로, values()는 값들을 Collection으로, entrySet()은 키와 값의 쌍인 Map.Entry들을 Set으로 보여 줍니다. 키만 검사할 때는 keySet, 값만 합산할 때는 values, 키와 값이 함께 필요할 때는 entrySet이 맞습니다. 키를 꺼낸 뒤 get으로 값을 다시 찾으면 맵을 두 번 조회하게 되므로, 둘 다 필요하다면 entrySet이 더 간단합니다.

values()의 타입이 Set이 아니라 Collection인 것은 값이 중복될 수 있기 때문입니다. 그리고 뷰라는 이름에도 이유가 있습니다. 뷰는 결과를 따로 복사해 둔 컬렉션이 아니라 원래 맵을 들여다보는 창입니다. 다음 코드는 뷰를 통해 지운 내용이 맵에 어떻게 반영되는지, 그리고 Map.copyOf로 만든 복사본과는 무엇이 다른지 비교합니다.

import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public final class BackedMapViewAndSnapshot {
    public static void main(String[] args) {
        Map<String, Integer> counts = new LinkedHashMap<>();
        counts.put("array", 40);
        counts.put("hash", 40);
        Set<String> keys = counts.keySet();
        Collection<Integer> values = counts.values();
        System.out.println("values-before=" + values.size());
        System.out.println("removed=" + keys.remove("array"));
        System.out.println("map=" + counts.size() + ", values=" + values.size());
        Map<String, Integer> snapshot = Map.copyOf(counts);
        counts.put("queue", 55);
        System.out.println("live=" + keys.size() + ", snapshot=" + snapshot.size());
        try {
            snapshot.put("new", 10);
        } catch (UnsupportedOperationException expected) {
            System.out.println("snapshot write rejected");
        }
    }
}

values-before=2
removed=true
map=1, values=1
live=2, snapshot=1
snapshot write rejected

처음에는 array와 hash의 값이 모두 40이므로 values의 크기는 2입니다. 40 두 개는 중복된 키가 아니라 서로 다른 두 키의 값입니다. 이어서 keys.remove("array")로 키 뷰에서 array를 지우면 원래 맵에서도 그 매핑이 지워집니다. 그래서 셋째 줄에서 맵과 values 뷰의 크기가 함께 1로 줄었습니다.

그다음 Map.copyOf(counts)로 복사본을 만든 뒤 원래 맵에 queue를 추가했습니다. 미리 받아 둔 keys 뷰에는 새 키가 바로 보여 크기가 2가 되지만, 복사본 snapshot은 복사한 순간의 매핑 1개를 그대로 가지고 있습니다. 또 Map.copyOf가 만든 맵은 수정할 수 없어서, 마지막 줄처럼 put을 호출하면 UnsupportedOperationException이 납니다.

Map.copyOf를 쓸 때 알아 둘 제약이 있습니다. 먼저 null 키나 null 값이 하나라도 있으면 NullPointerException을 던지므로, null을 허용하는 맵의 복사본으로는 쓸 수 없습니다. 또 반복 순서를 약속하지 않습니다. 원래 맵이 LinkedHashMap이어도 복사본의 순서는 다를 수 있고, OpenJDK 21에서는 같은 프로그램을 다시 실행하기만 해도 순서가 바뀌기도 합니다.

복사본은 매핑만 복사할 뿐 값 객체까지 복사하지는 않는다는 점도 중요합니다. 이 예제의 값은 불변인 Integer라서 문제가 없지만, 값이 수정 가능한 객체라면 복사본과 원본이 같은 객체를 함께 가리킵니다. 그런 객체를 복사본 쪽에서 고치면 원본에서도 바뀐 값이 보입니다.

반복하는 동안 맵을 고치는 규칙

뷰를 반복하는 동안 맵을 고칠 때도 규칙이 있습니다. entrySet을 반복하며 entry.setValue(...)로 값을 바꾸는 것은 허용됩니다. 매핑의 개수나 배치가 바뀌지 않기 때문입니다. 반면 반복 도중에 맵의 remove로 매핑을 지우거나 put으로 새 키를 추가하면, 대개 다음 원소를 꺼내는 순간 ConcurrentModificationException이 발생합니다. 반복 중에 지우고 싶다면 뷰의 removeIf나 반복자의 remove를 써야 합니다.

import java.util.ConcurrentModificationException;
import java.util.LinkedHashMap;
import java.util.Map;

public final class MapViewUpdates {
    public static void main(String[] args) {
        Map<String, Integer> counts = new LinkedHashMap<>();
        counts.put("array", 40);
        counts.put("hash", 120);
        counts.put("queue", 30);

        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            entry.setValue(entry.getValue() * 2);
        }
        System.out.println("doubled=" + counts);

        try {
            for (String key : counts.keySet()) {
                if (counts.get(key) < 100) {
                    counts.remove(key);
                }
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("ConcurrentModificationException, map=" + counts);
        }

        counts.values().removeIf(count -> count < 100);
        System.out.println("removeIf=" + counts);
    }
}

doubled={array=80, hash=240, queue=60}
ConcurrentModificationException, map={hash=240, queue=60}
removeIf={hash=240}

첫 반복은 setValue로 모든 값을 두 배로 만들었고 문제없이 끝났습니다. 두 번째 반복은 100보다 작은 값을 지우려고 counts.remove(key)를 호출했습니다. 첫 키 array의 값 80은 지워졌지만, 다음 키를 꺼내는 순간 반복자가 맵이 바뀐 것을 알아채고 예외를 던졌습니다. 그래서 값이 60인 queue는 지워지지 않은 채 남았습니다. 마지막 줄의 values().removeIf(...)는 뷰를 통해 조건에 맞는 매핑을 지우므로 queue까지 정리됩니다.

이 예외는 버그를 빨리 알리려는 장치일 뿐, 모든 경우에 반드시 발생한다고 문서가 약속하지는 않습니다. HashMap 문서는 이런 반복자가 '최선을 다해(best-effort)' 예외를 던질 뿐이므로 이 예외에 기대어 프로그램의 정확성을 지키면 안 된다고 밝힙니다. 실제로 OpenJDK 21에서는 반복의 마지막 차례에 그 키를 지우면, 더 꺼낼 원소가 없으므로 예외 없이 반복이 끝납니다. 예외가 나지 않았다고 해서 반복 중에 맵을 고친 코드가 올바른 것은 아닙니다.

HashMap, LinkedHashMap, TreeMap 비교하기

Map은 인터페이스이므로 실제로는 구현 클래스를 골라 객체를 만듭니다. 가장 많이 쓰는 구현은 HashMap, LinkedHashMap, TreeMap 세 가지입니다. 세 구현 모두 put과 get의 의미는 같고, 다른 것은 키를 반복하는 순서와 연산에 드는 시간입니다. 다음 코드는 같은 네 번의 put을 세 구현에 각각 실행하는데, 마지막 put은 이미 있는 키 array의 값을 40으로 바꿉니다.

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public final class MapImplementationOrder {
    public static void main(String[] args) {
        compare("hash", new HashMap<>());
        compare("linked", new LinkedHashMap<>());
        compare("tree", new TreeMap<>());
    }

    private static void compare(String name, Map<String, Integer> map) {
        map.put("thread", 70);
        map.put("array", 30);
        map.put("hash", 50);
        map.put("array", 40);
        System.out.println(name + " size=" + map.size() + " keys=" + map.keySet());
        System.out.println(name + " array=" + map.get("array"));
    }
}

hash size=3 keys=[array, thread, hash]
hash array=40
linked size=3 keys=[thread, array, hash]
linked array=40
tree size=3 keys=[array, hash, thread]
tree array=40

세 구현 모두 크기는 3이고 array의 값은 40입니다. 같은 키에 다시 넣으면 값만 바뀐다는 Map의 규칙은 구현과 상관없이 같기 때문입니다. 차이는 keySet()을 출력한 키의 순서에만 있습니다.

HashMap은 반복 순서를 약속하지 않습니다. 위의 [array, thread, hash]는 OpenJDK 21에서 이 프로그램을 실행했을 때 나온 순서일 뿐입니다. HashMap 문서는 순서를 보장하지 않을 뿐 아니라, 같은 순서가 시간이 지나도 유지된다는 보장도 없다고 밝힙니다. 그래서 HashMap의 출력 순서를 테스트의 기대값으로 고정하면 JDK 버전이나 원소 수가 바뀔 때 테스트가 깨질 수 있습니다.

LinkedHashMap은 키를 처음 넣은 순서를 기억합니다. array는 두 번째로 들어왔으므로, 마지막 put으로 값이 바뀌어도 자리는 두 번째 그대로입니다. 이미 있는 키에 다시 넣는 것은 삽입 순서에 영향을 주지 않기 때문입니다. 반면 키를 지웠다가 다시 넣으면 새로 들어온 키가 되어 맨 뒤에 붙습니다. Java 21부터는 LinkedHashMap과 TreeMap이 SequencedMap 인터페이스를 구현하므로 firstEntry(), lastEntry(), reversed()로 첫 매핑과 마지막 매핑, 거꾸로 된 순서를 바로 얻을 수도 있습니다.

TreeMap은 키를 늘 정렬된 상태로 유지합니다. 기본 정렬 기준은 키의 자연 순서(natural ordering), 즉 String이 구현한 compareTo이고, 생성자에 Comparator를 넘겨 다른 기준을 정할 수도 있습니다. 문자열의 자연 순서는 문자 코드 순서라서 대문자가 소문자보다 앞섭니다. 그래서 Zebra, array, map을 넣으면 Zebra가 맨 앞에 옵니다.

TreeMap은 같은 키인지도 equals가 아니라 비교 결과가 0인지로 판단합니다. 예를 들어 대소문자를 무시하는 String.CASE_INSENSITIVE_ORDER로 만든 TreeMap에 Map과 map을 차례로 넣으면 두 키를 같은 키로 보아 매핑이 하나만 남습니다. 이때 키는 처음 넣은 Map이 남고 값만 나중 것으로 바뀝니다.

HashMap과 LinkedHashMap은 키의 해시 값으로 찾아볼 칸을 바로 계산합니다. 그래서 해시 값이 칸마다 고르게 퍼져 있다면 원소 수와 상관없이 평균적으로 일정한 시간에 get과 put을 처리합니다. LinkedHashMap은 여기에 모든 엔트리를 잇는 이중 연결 목록을 덧붙인 구조라서, 엔트리마다 앞뒤 참조를 더 쓰는 대신 순서를 기억합니다. TreeMap은 키를 균형 잡힌 이진 탐색 트리인 레드-블랙 트리(red-black tree)에 저장하고, 문서가 get, put, remove, containsKey에 O(log n)을 보장합니다. 원소가 100만 개여도 수십 번의 비교로 끝나므로 느리지는 않지만, 해시 기반 구현보다는 오래 걸립니다.

null 키를 다루는 방식도 다릅니다. HashMap과 LinkedHashMap은 null 키 하나와 null 값을 허용합니다. 하지만 자연 순서를 쓰는 TreeMap은 null 키를 compareTo로 비교할 수 없으므로 put(null, ...)에서 NullPointerException을 던집니다.

고르는 기준은 이렇습니다. 순서가 필요 없다면 HashMap을 기본으로 씁니다. 넣은 순서대로 보여 줘야 한다면 LinkedHashMap을, 키가 항상 정렬되어 있어야 하거나 범위로 찾아야 한다면 TreeMap을 씁니다. 다만 보고서를 출력할 때만 정렬이 필요하다면 저장은 HashMap으로 하고, 출력하기 직전에 new TreeMap<>(counts)로 정렬된 복사본을 만들어도 됩니다. 정렬 상태를 늘 유지하는 비용 대신 출력할 때 한 번만 정렬 비용을 치르는 방법입니다.

TreeMap으로 범위를 찾기

정렬을 유지하는 비용을 치르는 대신 TreeMap은 정렬 순서를 이용한 조회를 제공합니다. 가장 작은 키, 어떤 값 바로 아래의 키, 특정 구간에 든 키를 모든 키를 훑지 않고 찾을 수 있습니다. 다음 코드는 게시글 번호를 키로 쓰는 TreeMap에 이런 질문을 던집니다.

import java.util.TreeMap;

public final class TreeMapRange {
    public static void main(String[] args) {
        TreeMap<Integer, String> posts = new TreeMap<>();
        posts.put(120, "thread");
        posts.put(101, "array");
        posts.put(110, "hash");
        posts.put(105, "map");
        System.out.println("all=" + posts);
        System.out.println("first=" + posts.firstKey() + ", last=" + posts.lastKey());
        System.out.println("before110=" + posts.headMap(110));
        System.out.println("from110=" + posts.tailMap(110));
        System.out.println("floor108=" + posts.floorKey(108) + ", ceiling108=" + posts.ceilingKey(108));
    }
}

all={101=array, 105=map, 110=hash, 120=thread}
first=101, last=120
before110={101=array, 105=map}
from110={110=hash, 120=thread}
floor108=105, ceiling108=110

번호를 120, 101, 110, 105 순서로 넣었지만 출력은 번호 순서입니다. firstKey()와 lastKey()는 가장 작은 키와 가장 큰 키를 돌려줍니다. headMap(110)은 110보다 작은 키만, tailMap(110)은 110 이상인 키만 모은 맵을 돌려주는데, 기준값이 headMap에서는 빠지고 tailMap에서는 포함된다는 점에 주의해야 합니다. 이 두 결과도 복사본이 아니라 원래 맵과 연결된 뷰입니다. floorKey(108)은 108 이하에서 가장 큰 키를, ceilingKey(108)은 108 이상에서 가장 작은 키를 돌려줍니다.

더 깊이: HashMap의 출력 순서가 정해지는 방식

HashMap이 [array, thread, hash] 순서로 출력한 이유는 OpenJDK 21의 구현에서 찾을 수 있습니다. 문서가 약속하는 동작이 아니라 현재 구현의 세부 사항이라는 점을 먼저 밝혀 둡니다. Set 구현을 비교한 글에서 본 것처럼 HashSet은 내부의 HashMap에 원소를 키로 저장하므로, 버킷(bucket) 번호를 정하는 계산도 똑같습니다. hashCode() 값 h의 위쪽 16비트를 아래쪽에 섞은 뒤 버킷 배열의 길이에 맞춰 아래쪽 비트만 남기는데, 기본 길이 16에서는 (h ^ (h >>> 16)) & 15입니다.

이 식으로 계산하면 array는 5번, thread는 11번, hash는 14번 버킷에 들어갑니다. 반복자는 버킷 배열을 0번부터 차례로 훑으므로 키가 이 번호 순서대로 나왔습니다. 원소가 늘어 배열이 커지면 버킷 번호를 다시 계산하므로 순서가 달라질 수 있고, 해시를 섞는 방법이나 배열 크기 정책도 JDK 버전에 따라 바뀔 수 있습니다. 문서가 순서를 약속하지 않기 때문에 구현은 이런 세부 사항을 자유롭게 바꿀 수 있습니다.

Map.of와 Map.copyOf가 만든 맵은 여기서 한 걸음 더 나아갑니다. OpenJDK는 프로그램을 실행할 때마다 새로 정하는 임의의 값으로 이런 맵의 반복 순서를 섞기 때문에, 같은 프로그램을 다시 실행하기만 해도 순서가 바뀔 수 있습니다. 예를 들어 Map.of("array", 40, "hash", 60, "set", 30)을 출력하기만 하는 프로그램을 OpenJDK 21에서 열두 번 실행하자 다섯 가지 서로 다른 순서가 나왔습니다. 순서가 중요한 결과라면 이런 맵의 순서에 기대지 말고 정렬하거나 순서를 지키는 구현에 담아야 합니다.

더 깊이: 접근 순서를 기억하는 LRU 캐시

LinkedHashMap에는 삽입 순서 대신 접근 순서를 기억하는 모드가 있습니다. 생성자 LinkedHashMap(initialCapacity, loadFactor, accessOrder)의 세 번째 인자를 true로 주면, get이나 put으로 매핑에 접근할 때마다 그 키가 맨 뒤로 옮겨집니다. 여기에 removeEldestEntry를 재정의하면 가장 오래 쓰지 않은 키를 자동으로 지우는 LRU(least recently used) 캐시를 몇 줄로 만들 수 있습니다. 가장 오래 쓰지 않은 것을 내보내는 이 규칙은 운영체제의 페이지 교체 알고리즘에서 FIFO, OPT와 비교하는 LRU와 같습니다.

import java.util.LinkedHashMap;
import java.util.Map;

public final class LruCacheDemo {
    public static void main(String[] args) {
        Map<String, String> cache = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > 3;
            }
        };
        cache.put("array", "A");
        cache.put("hash", "H");
        cache.put("queue", "Q");
        cache.get("array");
        System.out.println("after get=" + cache.keySet());
        cache.put("stack", "S");
        System.out.println("after put=" + cache.keySet());
    }
}

after get=[hash, queue, array]
after put=[queue, array, stack]

array, hash, queue를 넣은 뒤 get("array")로 array를 읽자 array가 맨 뒤로 옮겨졌습니다. 이제 가장 오래 쓰지 않은 키는 맨 앞의 hash입니다. 네 번째 키 stack을 넣으면 put이 새 매핑을 추가한 뒤 removeEldestEntry를 호출하고, 크기가 3을 넘었으므로 맨 앞의 hash가 지워집니다. 생성자의 16과 0.75f는 기본 초기 용량과 적재 계수(load factor)를 그대로 적은 값입니다.

이 캐시는 스레드 하나에서만 써야 합니다. 접근 순서 모드에서는 get조차 내부 순서를 바꾸는 수정 연산이라고 LinkedHashMap 문서가 밝히고 있기 때문입니다. 여러 스레드가 함께 쓰는 캐시라면 동기화를 따로 하거나 동시성을 고려한 캐시 라이브러리를 써야 합니다.

저장소 클래스 안에 Map 숨기기

지금까지 배운 것을 게시글 저장소에 적용해 보겠습니다. 저장소가 내부의 Map을 그대로 돌려주면, 호출자가 검사 없이 put이나 remove를 호출해 저장소의 규칙을 우회할 수 있습니다. 그래서 맵은 private 필드로 숨기고, 밖에서는 save, find, snapshot 같은 메서드로만 다루게 합니다. 다음 저장소는 같은 ID의 게시글을 두 번 저장하지 못하게 막고, 없는 ID를 조회하면 예외를 던집니다.

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.NoSuchElementException;

public final class PostRepository {
    public static void main(String[] args) {
        Repository repository = new Repository();
        repository.save(new Entry(1, "map", 45));
        repository.save(new Entry(2, "queue", 55));
        System.out.println(repository.find(2));

        try {
            repository.save(new Entry(1, "stack", 10));
        } catch (IllegalArgumentException e) {
            System.out.println("rejected: " + e.getMessage());
        }

        Map<Integer, Entry> snapshot = repository.snapshot();
        repository.save(new Entry(3, "deque", 20));
        System.out.println("snapshot size=" + snapshot.size());
    }

    private static final class Repository {
        private final Map<Integer, Entry> entries = new LinkedHashMap<>();

        void save(Entry entry) {
            if (entries.putIfAbsent(entry.id(), entry) != null) {
                throw new IllegalArgumentException("duplicate id=" + entry.id());
            }
        }

        Entry find(int id) {
            Entry found = entries.get(id);
            if (found == null) {
                throw new NoSuchElementException("id=" + id);
            }
            return found;
        }

        Map<Integer, Entry> snapshot() {
            return Map.copyOf(entries);
        }
    }

    private record Entry(int id, String title, int viewCount) {}
}

Entry[id=2, title=queue, viewCount=55]
rejected: duplicate id=1
snapshot size=2

save는 putIfAbsent의 반환값으로 중복을 판단합니다. 키가 없으면 새 매핑을 넣고 null을 돌려주지만, 키가 이미 있으면 아무것도 바꾸지 않고 기존 값을 돌려줍니다. 그래서 반환값이 null이 아니라는 것은 같은 ID가 이미 저장되어 있다는 뜻이고, 둘째 줄처럼 ID 1의 두 번째 저장이 거부됩니다. 앞에서 본 것처럼 putIfAbsent는 값이 null인 매핑을 없는 것으로 보지만, save(null)은 entry.id()에서 바로 NullPointerException이 나므로 이 맵에는 null 값이 들어갈 수 없습니다. 그래서 이 판단은 정확합니다.

find도 같은 이유로 get의 null을 '없는 ID'로 해석할 수 있습니다. snapshot은 Map.copyOf로 만든 수정할 수 없는 복사본을 돌려주므로, 셋째 줄처럼 복사본을 받은 뒤에 저장한 3번 게시글은 복사본에 나타나지 않습니다. 앞에서 본 대로 이 복사본은 반복 순서를 약속하지 않습니다. 저장한 순서까지 지켜서 돌려줘야 한다면 Collections.unmodifiableMap(new LinkedHashMap<>(entries))처럼 순서를 지키는 복사본을 수정 불가 맵으로 감싸서 돌려줍니다. 이 방법은 17장의 컬렉션 구현 선택에서 다시 다룹니다.

이 저장소가 검사하는 것은 ID가 중복되는지와 조회할 ID가 있는지뿐입니다. Entry 레코드의 본문이 비어 있으므로 ID가 양수인지, 제목이 비어 있지 않은지, 조회 수가 음수가 아닌지는 검사하지 않습니다. 이런 규칙까지 지키려면 레코드의 컴팩트 생성자나 save에 검사를 추가해야 합니다.

정리

• 맵은 키와 값을 한 쌍으로 저장하고, 키는 중복되지 않습니다. 같은 키에 다시 put하면 값이 교체되고 이전 값이 반환됩니다.
• get이 돌려준 null은 '키 없음'일 수도, 'null이 저장됨'일 수도 있습니다. containsKey로 구분하거나 처음부터 null 값을 넣지 않습니다. getOrDefault는 매핑이 없을 때만 기본값을 주고, putIfAbsent와 merge는 null 값을 없는 것으로 봅니다.
• merge는 기존 값을 읽고, 계산하고, 저장하는 누적을 한 번의 호출로 처리합니다.
• keySet, values, entrySet은 원래 맵과 연결된 뷰입니다. 반복하는 동안 매핑을 지우려면 맵의 remove 대신 뷰의 removeIf나 반복자의 remove를 씁니다.
• Map.copyOf는 수정할 수 없는 복사본을 만들지만 null을 거부하고 반복 순서를 약속하지 않습니다.
• 순서가 필요 없으면 HashMap, 삽입 순서가 필요하면 LinkedHashMap, 정렬 순서나 범위 탐색이 필요하면 TreeMap을 고릅니다. 앞의 둘은 평균 O(1), TreeMap은 O(log n)입니다.

연습 문제

1. 두 맵에서 공통 제목만 찾아 조회 수 차이를 출력하세요. 입력은 left = Map.of("array", 40, "hash", 60, "set", 30)과 right = Map.of("hash", 45, "set", 50, "queue", 20)이고, 차이는 left 값에서 right 값을 빼서 구합니다. Map.of는 키와 값을 번갈아 받아 수정할 수 없는 맵을 만드는 메서드로, Map.copyOf처럼 null을 받지 않고 반복 순서를 약속하지 않습니다. 한쪽에만 있는 키는 결과에 넣지 않고 입력 맵은 바꾸지 않으며, 결과는 키의 알파벳순으로 출력하세요.
2. 다음 코드의 출력을 예상하세요. LinkedHashMap을 HashMap이나 TreeMap으로 바꾸면 무엇이 달라지는지도 설명하세요.

import java.util.LinkedHashMap;
import java.util.Map;

public final class LinkedOrderExercise {
    public static void main(String[] args) {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("thread", 70);
        map.put("array", 30);
        map.put("hash", 50);
        map.put("array", 40);
        map.remove("thread");
        map.put("thread", 80);
        System.out.println(map);
    }
}

3. Map<String, Integer> stock = new HashMap<>();을 만들고 stock.put("pen", null);을 실행했습니다. 이어서 stock.getOrDefault("pen", 0)과 stock.merge("pen", 5, Integer::sum)을 차례로 호출하면 각각 무엇을 돌려주는지, 그 뒤 stock의 내용은 어떻게 되는지 설명하세요.

import java.util.Map;
import java.util.TreeMap;

public final class CommonMapDifferenceSolution {
    public static void main(String[] args) {
        Map<String, Integer> left = Map.of("array", 40, "hash", 60, "set", 30);
        Map<String, Integer> right = Map.of("hash", 45, "set", 50, "queue", 20);
        Map<String, Integer> difference = new TreeMap<>();
        for (Map.Entry<String, Integer> entry : left.entrySet()) {
            Integer other = right.get(entry.getKey());
            if (other != null) {
                difference.put(entry.getKey(), entry.getValue() - other);
            }
        }
        System.out.println(difference);
        System.out.println("inputs=" + left.size() + "/" + right.size());
    }
}

{hash=15, set=-20}
inputs=3/3

다음 글

ArrayDeque로 스택과 큐 다루기에서는 키로 찾는 맵에서 잠시 벗어나, 넣은 순서에 따라 꺼내는 순서가 정해지는 스택과 큐를 배웁니다. 두 자료구조를 하나로 다룰 수 있는 Deque 인터페이스와 그 기본 구현인 ArrayDeque를 사용합니다.