Map, HashMap, TreeMap 완벽 정리

 

1. Map (인터페이스)

가장 먼저 이해해야 할 것은 Map이 인터페이스(Interface)라는 점입니다. 자바 컬렉션 프레임워크에서 Map은 **키(key)**와 **값(value)**을 한 쌍으로 묶어 저장하는 데이터 구조의 규약(청사진)을 정의합니다. Map 자체는 객체로 생성할 수 없으며, 이 인터페이스를 구현하는 구체적인 클래스들(예: HashMap, TreeMap, LinkedHashMap)을 통해 기능을 사용할 수 있습니다.

핵심 특징:

• 키(Key)의 고유성: 모든 키는 유일해야 합니다. 동일한 키로 값을 추가하면 기존의 값은 새로운 값으로 덮어쓰여집니다.
• 키-값 쌍: 키를 통해 값에 빠르게 접근할 수 있습니다. 마치 사전에서 단어를 찾아 그 의미를 확인하는 것과 같습니다.
• 순서 없음: Map 인터페이스 자체는 요소의 순서를 보장하지 않습니다. (TreeMap은 예외적으로 정렬된 순서를 가집니다.)
• null 허용: 대부분의 구현체는 키나 값에 null을 허용합니다. (단, TreeMap은 키에 null을 허용하지 않습니다.)

Map 인터페이스가 제공하는 주요 메서드는 다음과 같습니다.

• put(key, value): 키와 값을 저장합니다.
• get(key): 주어진 키에 해당하는 값을 반환합니다.
• remove(key): 키에 해당하는 키-값 쌍을 삭제합니다.
• containsKey(key): 해당 키가 존재하는지 확인합니다.
• keySet(): Map에 있는 모든 키들을 Set 형태로 반환합니다.
• entrySet(): Map에 있는 모든 키-값 쌍(Entry)을 Set 형태로 반환합니다.

Map은 키를 사용하여 데이터를 조회하는 작업이 빈번할 때 매우 효율적입니다.

 

 

 

2. HashMap (빠른 비정렬 맵)

HashMap은 Map 인터페이스의 가장 대표적인 구현체입니다. 키를 기반으로 데이터를 빠르게 탐색해야 할 때 사용되며, 내부적으로 해시 테이블(Hash Table) 자료구조를 사용합니다.

내부 동작 원리:

HashMap은 키에 대해 **해시 함수(Hash Function)**를 적용하여 해시 코드를 생성하고, 이 해시 코드를 통해 배열의 인덱스(버킷)를 결정합니다.

1. 키-값 저장 시: put(key, value)를 호출하면, 먼저 키의 hashCode() 메서드를 호출하여 해시 코드를 얻습니다. 이 해시 코드를 배열의 크기에 맞게 가공하여 인덱스를 계산하고, 해당 인덱스에 키-값 쌍을 저장합니다.
2. 충돌(Collision) 처리: 여러 개의 키가 동일한 인덱스로 매핑되는 해시 충돌이 발생할 수 있습니다. HashMap은 이를 해결하기 위해 각 배열 인덱스에 연결 리스트(Linked List)나 트리(Tree)를 사용하여 충돌을 처리합니다.
3. 키-값 조회 시: get(key)를 호출하면, 저장할 때와 마찬가지로 키의 hashCode()를 통해 인덱스를 찾습니다. 해당 인덱스에 저장된 요소들 중에서 equals() 메서드를 이용해 찾는 키와 동일한 요소를 찾아 반환합니다.

주요 특징:

• 성능: 평균적으로 put, get, remove 연산의 시간 복잡도는 O(1) 입니다. 해시 함수가 키를 고르게 분산시킬 경우 매우 빠릅니다. 최악의 경우(모든 키가 동일한 해시 코드를 가질 경우)는 O(n)까지 느려질 수 있지만, 일반적으로는 발생하지 않습니다.
• 순서 없음: HashMap은 저장된 순서를 보장하지 않으며, 정렬되어 있지도 않습니다.
• null 허용: 하나의 null 키와 여러 개의 null 값을 가질 수 있습니다.
• 동기화: 스레드에 안전하지 않습니다(Non-Synchronized). 멀티스레드 환경에서 사용하려면 Collections.synchronizedMap()을 사용하거나, ConcurrentHashMap을 사용해야 합니다.

HashMap은 데이터의 삽입, 삭제, 조회가 가장 빠른 맵으로, 일반적인 용도에서 가장 많이 사용됩니다.

 

 

 

3. TreeMap (정렬된 맵)

TreeMap은 Map 인터페이스를 구현하며, 데이터를 키를 기준으로 정렬하여 저장합니다. 내부적으로는 **레드-블랙 트리(Red-Black Tree)**라는 균형 이진 탐색 트리를 사용합니다.

내부 동작 원리:

TreeMap은 키-값 쌍을 트리에 저장하며, 새로운 요소가 추가될 때마다 트리의 균형을 유지하고 정렬된 상태를 만듭니다.

1. 정렬 기준: 키의 자연적 순서(Natural Ordering) 또는 생성 시 제공된 **Comparator**에 따라 정렬됩니다. Integer, String 같은 기본 클래스는 자연적 순서가 정의되어 있습니다.
2. 탐색: 트리의 루트 노드에서 시작하여 키를 비교하며 내려가기 때문에, 삽입, 삭제, 검색에 일정한 성능을 보장합니다.

주요 특징:

• 성능: put, get, remove 연산의 시간 복잡도는 항상 O(log n) 입니다. HashMap의 평균적인 성능(O(1))보다는 느리지만, HashMap의 최악의 경우(O(n))보다는 빠르고 안정적입니다.
• 순서 보장: 키를 기준으로 오름차순으로 정렬된 상태를 항상 유지합니다.
• null 키 불가능: 키를 비교해야 하므로 null 키는 허용하지 않습니다. null 값은 허용합니다.
• 동기화: HashMap과 마찬가지로 스레드에 안전하지 않습니다(Non-Synchronized).

TreeMap은 키의 순서

 

가 중요하거나, 정렬된 데이터를 반복적으로 조회해야 할 때 유용합니다. 예를 들어, 특정 범위 내의 키-값 쌍을 찾거나(subMap), 최소/최대 키를 찾는 등의 작업에 적합합니다.

4. 핵심 비교 및 요약

구분	HashMap	TreeMap
내부 자료구조	해시 테이블(Hash Table)	레드-블랙 트리(Red-Black Tree)
성능 (시간 복잡도)	삽입, 삭제, 검색 평균 O(1)	삽입, 삭제, 검색 O(log n)
데이터 순서	보장하지 않음 (무작위)	키를 기준으로 오름차순 정렬
null 키 허용	허용 (단, 1개만)	허용하지 않음
주요 활용 사례	- 순서가 중요하지 않은 일반적인 맵 <br> - 빠른 조회/삽입/삭제가 필요한 경우	- 키의 순서가 중요한 경우 <br> - 정렬된 데이터를 반복적으로 조회해야 할 때 <br> - 범위 검색(range search)이 필요한 경우
장점	- 가장 빠른 성능 <br> - 범용적으로 사용 가능	- 항상 정렬된 상태 유지 <br> - 예측 가능한 안정적인 성능
단점	- 순서가 없어 순차 접근 시 비효율적 <br> - 해시 충돌 시 성능 저하 가능성	- HashMap보다 느림 <br> - 메모리 사용량이 상대적으로 많음

 

5. 결론: 언제 무엇을 사용해야 하는가?

• HashMap을 사용하세요: 대부분의 경우 HashMap이 가장 좋은 선택입니다. 데이터의 순서가 중요하지 않고, 가장 빠른 데이터 접근 및 조작 성능이 필요할 때 사용합니다.
• TreeMap을 사용하세요: 키를 기준으로 정렬된 상태로 데이터를 유지해야 할 필요가 있거나, 키를 기준으로 범위 검색(예: "100~200번 키에 해당하는 데이터")을 해야 할 때 사용합니다.