Java Map 완전 정복: HashMap, LinkedHashMap, TreeMap 비교와 키 설계 핵심 가이드

Java 개발을 하다 보면 Map은 정말 자주 사용하게 되는 자료구조입니다. 특히 HashMap은 거의 매일 쓰게 되는데요, 막상 "왜 HashMap을 쓰는 거야?"라고 물어보면 명확하게 대답하기 어려운 경우가 많습니다. 저도 처음엔 그냥 데이터를 key-value로 저장하는 거구나 정도로만 알고 있었는데, 공부하면서 내부 구조와 각 Map의 특징을 알게 되니 훨씬 더 효율적으로 사용할 수 있더라고요.
 
특히 커스텀 객체를 키로 사용할 때 제대로 동작하지 않아서 한참 헤맸던 경험도 있습니다. 그래서 오늘은 저와 같은 고민을 하시는 분들께 도움이 되고자, HashMap, LinkedHashMap, TreeMap의 차이점과 함께 키 설계의 핵심을 정리해봤습니다.

HashMap: 빠른 검색의 핵심, 해싱의 마법

HashMap은 내부적으로 해시 테이블을 사용합니다. 데이터를 저장할 때 key 값으로 hashCode() 메서드를 호출하고, 그 값을 이용해 어느 버킷(bucket)에 저장할지를 결정합니다.

 
HashMap은 기본적으로 16개의 버킷으로 시작하고, loadFactor(기본값 0.75)를 기준으로 12개 이상 차면 자동으로 2배 확장됩니다. 해시 충돌이 발생하면 연결 리스트로 이어붙이고, Java 8 이후에는 일정 개수 이상 충돌 시 Red-Black Tree로 변환하여 성능을 O(log N)까지 보장합니다.
 
이 덕분에 평균적으로 데이터 검색, 삽입, 삭제 모두 O(1)의 우수한 성능을 보여줍니다.

LinkedHashMap: 순서가 필요할 때의 선택

LinkedHashMap은 HashMap을 상속받아 구현된 자료구조로, 삽입 순서 또는 접근 순서를 유지합니다. 내부적으로 이중 연결 리스트(doubly linked list)를 사용하기 때문에 순서가 보장됩니다.
 

또한 최근 사용된 항목만 유지하는 LRU 캐시 구현에도 자주 사용됩니다. 생성자에서 accessOrder를 true로 주고, removeEldestEntry() 메서드를 오버라이드하면 간단히 캐시가 완성됩니다.

LinkedHashMap<K, V> cache = new LinkedHashMap<>(capacity, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
};

 
HashMap보다 약간의 메모리 오버헤드가 있지만, 순서가 중요한 곳에서는 매우 유용합니다.

TreeMap: 정렬이 필요하다면

TreeMap은 Red-Black Tree 기반으로 구현되어 있으며, key를 기준으로 자동 정렬이 이루어집니다. 기본적으로는 key의 자연 순서를 사용하지만, Comparator를 지정하면 커스텀 정렬도 가능합니다.

TreeMap<String, Integer> map = new TreeMap<>(Collections.reverseOrder());
TreeMap<Person, String> map = new TreeMap<>((p1, p2) -> p1.getAge() - p2.getAge());

 
정렬, 범위 조회(firstKey, lastKey, subMap 등)에 유용하지만, 다른 Map보다 성능은 느리며 null key는 허용되지 않습니다. 시간복잡도는 O(log N)입니다.

세 가지 Map 비교

구분	HashMap	LinkedHashMap	TreeMap
정렬	없음	삽입/접근 순서	Key 자동 정렬
시간복잡도	O(1)	O(1)	O(log n)
null 키	허용 (1개)	허용 (1개)	불허
메모리	가장 적음	중간	가장 많음
사용 사례	일반적인 경우	순서 필요시	정렬 및 범위 검색

키 설계의 중요성: equals()와 hashCode()

HashMap을 올바르게 사용하려면 equals()와 hashCode()의 관계를 이해해야 합니다. 두 객체가 논리적으로 같다면 equals()가 true를 반환해야 하고, 이때 반드시 같은 hashCode()를 반환해야 합니다.

class Person {
    String name;
    int age;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

 

만약 equals()만 재정의하고 hashCode()를 재정의하지 않으면, 동일한 내용을 가진 객체라도 다른 버킷에 저장되어 데이터를 찾지 못하게 됩니다. 특히 커스텀 클래스를 키로 사용할 때는 반드시 두 메서드를 세트로 구현해야 합니다.

성능 최적화 팁

• 초기 용량(capacity)을 예상 데이터량에 맞춰 설정해 리사이징을 줄이세요.
• 기본 loadFactor(0.75)는 대부분의 경우 최적입니다. 불필요하게 변경하지 마세요.
• 멀티스레드 환경에선 ConcurrentHashMap을 사용하세요.
• null 키는 TreeMap에서 에러를 유발하므로 가급적 사용하지 않는 것이 좋습니다.

int expectedSize = 100;
int capacity = (int) (expectedSize / 0.75f) + 1;
Map<String, String> map = new HashMap<>(capacity);

 
HashMap, LinkedHashMap, TreeMap은 각각 다른 장점을 가지고 있습니다. 일반적인 데이터는 HashMap, 순서가 필요하면 LinkedHashMap, 정렬이 필요하면 TreeMap을 사용하세요.
 

그리고 커스텀 객체를 Key로 쓸 때는 반드시 equals()와 hashCode()를 올바르게 정의해야 예기치 않은 버그를 피할 수 있습니다. Map의 내부 동작을 이해하면 성능과 안정성 모두 놓치지 않는 코드를 작성할 수 있습니다.

Java HashSet, TreeSet, LinkedHashSet 완벽 정리 - 특성과 정렬 방법