HashMap과 TreeMap은 언제 사용할까?

자바는 수많은 제네릭 컬렉션을 지원한다.

그 덕에 우리는 개발할 때 List, Stack, Map, Set 등을 간편하게 활용할 수 있다.

 

그런데 제네릭 컬렉션 중 많은 종류는 클래스가 아닌 인터페이스 형식으로 지원된다.

같은 자료 구조라고 하더라도 다른 방식으로 구현될 수 있기 때문이다.

 

가장 대표적인 자료 구조인 List 또한 ArrayList, LinkedList 등 여러 구현체가 있다.

 

이번 포스트에서 알아볼 Map 또한 HashMap과 TreeMap 등의 구현체들이 있다.

이러한 구현체들은 저마다 존재 이유가 있어서, 그 특징을 알고 상황에 맞게 사용할 수 있어야 한다.

 

그리고 그 특징을 알기 위한 가장 좋은 방법은 각 구현체가 어떻게 인터페이스를 구현하는지 이해하는 것이다.

이번 포스트에서는 Map 인터페이스를 구현하는 HashMap과 TreeMap이 Map의 기능들을 어떻게 구현하는지, 그리고 그 구현 방법에 의해 발생하는 특징은 무엇인지 살펴보자.

---

Map 인터페이스

Map의 구현체를 살펴보기 전, Map 자체에 대해 이해해 보도록 하자.

Map의 특징

Map은 다음과 같은 특징을 갖는다.

1. Key-Value 쌍

Map은 데이터를 key-value 쌍으로 저장하는 자료 구조이다. 각각의 값(value)은 고유한 키(key)를 통해 식별된다.

학생 정보를 저장하는 Map:
{
    "홍길동": 95,
    "김철수": 88,
    "이영희": 92
}

위 예시에서 "홍길동", "김철수", "이영희"는 각각 학생 이름(key)을 나타내고, 95, 88, 92는 각 학생의 점수(value)를 나타낸다.

2. 유일한 Key

Map에서 각 키는 반드시 유일해야 한다. 동일한 키를 가진 데이터가 여러 개 존재할 수 없다. 만약 동일한 키로 새로운 값을 추가하면 기존 값은 새로운 값으로 덮어씌워진다.

기존 Map: { "홍길동": 95 }
새로운 값 추가: { "홍길동": 98 }
결과 Map: { "홍길동": 98 }

위 예시에서 "홍길동"의 키를 갖는 새로운 데이터를 추가함으로써, 기존에 있던 홍길동의 점수가 98로 변경되었다.

3. 순서가 특정되지 않음

Map은 저장되는 데이터의 순서를 보장하지 않는다. 데이터를 추가한 순서대로 값을 가져오거나 특정 위치의 값을 참조할 수 없다.

Map: { "홍길동": 95, "김철수": 88, "이영희": 92 }

위 Map에서 "홍길동", "김철수", "이영희" 순서로 값을 가져올 수 있다는 보장이 없다.

Map의 핵심 연산

Map의 구현체들은 위 특징들을 지키면서 다음의 연산을 지원해야 한다.

1. put(key, value)

put(key, value) 연산은 Map에 새로운 key-value 쌍을 추가하거나, 기존 키에 대한 값을 변경하는 데 사용된다.

• 새로운 key-value 쌍 추가: 만약 주어진 키가 Map에 존재하지 않으면, 새로운 key-value 쌍이 Map에 추가된다.
• 기존 값 변경: 만약 주어진 키가 이미 Map에 존재하면, 해당 키에 연결된 기존 값은 새로운 값으로 덮어씌워진다.

2. get(key)

get(key) 연산은 주어진 키에 해당하는 값을 Map에서 찾아 반환한다.

• 값 존재: 만약 주어진 키가 Map에 존재하면, 해당 키에 연결된 값이 반환된다.
• 값 미존재: 만약 주어진 키가 Map에 존재하지 않으면, null이 반환된다.

3. remove(key)

remove(key) 연산은 주어진 키에 해당하는 key-value 쌍을 Map에서 제거한다.

---

HashMap 클래스

HashMap은 해시 테이블(Hash Table)을 기반으로 동작하는 Map 인터페이스의 대표적인 구현체이다. 빠른 데이터 검색, 삽입, 삭제를 제공하며 다양한 활용 분야에서 사용된다.

구현 방식

해시 함수

HashMap은 해시 함수를 통해 데이트를 분류한다. 해시 함수는 데이터를 고정된 크기의 값으로 변환하는 함수이다. 이렇게 변환된 값을 해시 값(Hash Value) 또는 해시 코드(Hash Code)라고 한다.

해시 버킷

해시 함수로 얻은 해시 값을 인덱스로 사용하여, 데이터를 버킷(Bucket)이라는 배열에 저장한다.

충돌 해결

해시는 필연적으로 충돌이 발생한다. 즉, 서로 다른 두 데이터가 같은 해시 값을 뱉을 수 있다. 이를 해결하기 위해 각 버킷에 연결 리스트 (Linked List)를 두어 충돌된 데이터들을 관리한다.

시간 복잡도

데이터의 해시 값을 이용해 배열에 접근하므로 삽입, 검색, 삭제 연산 모두 O(1)의 시간 복잡도를 기대할 수 있다.

 

하지만 최악의 경우, 모든 데이터에 대해 해시 충돌이 발생하게 되면 모든 데이터가 연결 리스트로 관리되게 되어 O(n)의 시간 복잡도를 가진다.

사용하는 상황

HashMap은 모든 연산에 상수 시간을 기대할 수 있는 매우 빠른 자료 구조이다.

하지만 해시 충돌 시 빠른 연산의 장점이 사라지므로 데이터의 해시값 분포가 잘 되어있는지를 생각해야 한다.

---

TreeMap 클래스

TreeMap은 Map 인터페이스를 구현한 또 다른 자료 구조로, 균형 이진 탐색 트리(Red-Black Tree)를 기반으로 동작한다.

균형 이진 탐색 트리

TreeMap은 데이터를 저장할 때 키를 기준으로 균형 이진 탐색 트리에 삽입한다. 이진 탐색 트리는 왼쪽 자식 노드의 키는 부모 노드의 키보다 작고, 오른쪽 자식 노드의 키는 부모 노드의 키보다 크거나 같은 특징을 가진다. 균형 이진 탐색 트리는 트리의 높이를 최소화하여 탐색, 삽입, 삭제 연산의 효율성을 높인다.

정렬된 Map

TreeMap은 키를 기준으로 정렬된 상태를 유지한다. 따라서 데이터를 추가한 순서와 상관없이 키의 순서대로 값을 가져올 수 있다. 이는 HashMap과 가장 큰 차이점 중 하나이다.

시간복잡도

평균적으로 O(log n)의 시간 복잡도를 가진다. 균형 이진 탐색 트리의 특성상 탐색, 삽입, 삭제 연산 시 트리의 높이만큼 비교 연산을 수행하기 때문이다.

 

이는 평균적으로 상수 시간의 시간 복잡도를 갖는 HashMap보다는 느리지만, TreeMap은 최악의 경우에도 O(log n)의 시간 복잡도를 보장한다.

사용하는 상황

TreeMap은 키를 기준으로 정렬된 상태를 유지하므로, 정렬 상태가 중요할 때 사용할 수 있다.

또, 이를 이용해 특정 범위 내의 키를 가진 데이터를 빠르게 찾을 수 있다.

---

결론

위 내용을 정리하면 다음과 같다.

	HashMap	TreeMap
구현 방식	해시 테이블 (Hash Table)	균형 이진 탐색 트리 (Red-Black Tree)
정렬	순서를 보장하지 않음	키를 기준으로 정렬 상태 유지
연산 평균 시간 복잡도	O(1)	O(log n)
연산 최악 시간 복잡도	O(n)	O(log n)
장점	빠른 연산 속도	정렬 유지, 범위 검색에 유리
단점	순서를 보장하지 않음 해시 충돌 시 성능 저하	평균 연산 속도가 상대적으로 느림

 

따라서 다음의 기준에 따라 HashMap과 TreeMap 중 어떤 것을 사용할 지 결정할 수 있다.

HashMap을 사용하는 것이 좋은 경우

• 데이터의 순서가 중요하지 않은 경우
• 빠른 삽입, 삭제, 검색 속도가 중요한 경우
• 데이터의 규모가 크고 해시 충돌이 적을 것으로 예상되는 경우

TreeMap을 사용하는 것이 좋은 경우

• 데이터를 정렬된 상태로 유지해야 하는 경우
• 특정 범위 내의 키를 가진 데이터를 빠르게 찾아야 하는 경우 (범위 검색)
• 데이터의 순위 정보를 관리해야 하는 경우