HashMap vs TreeMap

HashMap과 TreeMap은 Map의 구현체로 둘 다 key, value으로 데이터를 저장한다.

구조

• HashMap : 해시 함수를 사용하여 데이터를 저장하며 Index를 가지고 있어 조회에 강점이 있지만 데이터의 순서를 보장하지 않는다.
• TreeMap : 레드-블랙 트리(Red-Black Tree)라는 균형 이진 검색 트리를 사용하여 데이터를 저장한다. 따라서 트리의 특징인 데이터를 정렬된 상태로 저장하며 조회, 삽입, 삭제 등에서 O(log n)의 시간 복잡도를 가진다.

Null

• HashMap은 키, 값 모두 null을 허용한다.
• TreeMap은 값은 Null을 허용하지만 키는 Null을 허용하지 않는다.

성능

• HashMap은 Index를 가지고 있어 보통 조회, 삽입, 삭제에 O(1)의 속도를 가지지만 해시충돌, 중간 삽입 등의 경우에는 O(n)의 시간 복잡도를 가진다.
• TreeMap은 트리의 특성상 조회, 삭제, 삽입에 O(log n)의 시간 복잡도를 가진다.

메모리

• HashMap은 기본 크기를 가지고 있다. 즉, 데이터가 적다면 메모리가 낭비 될 수도 있다.
• Treemap은 필요한 메모리 양만 사용하기 때문에 비교적 메모리가 절약 된다.

한 줄평 : 순서, 메모리, 조회가 많은지 추가/삭제가 많은지 등을 고려해서 선택하자.

참고 -
https://www.baeldung.com/java-treemap-vs-hashmap