Map 계열: 키-값 쌍 저장, 키 중복 불가
HashMap
해시 테이블 기반의 맵으로, 키의 hashCode()를 이용하여 해시 테이블 인덱스를 계산하고
[Key, Value] 엔트리를 저장합니다. 순서는 보장되지 않습니다
성능
평균적으로 검색(get), 삽입(put), 삭제(remove) 모두 O(1)로 빠릅니다.
자바 8 이후로는 충돌 시 개별 버킷을 트리화하여 최악의 경우도 O(log n)으로 개선되었습니다.
(자바 7까지는 최악 O(n))
메모리
키와 값을 포함하는 엔트리 객체(Node)와 버킷용 배열을 갖습니다
자바 8부터는 첫 put 시점에 초기화하여 불필요한 메모리 할당을 줄이는 최적화(lazy initialization)가 도입되었습니다
장점
키로 값 검색이 빈번한 상황에 최적입니다.
캐싱, 딕셔너리 조회 등에 쓰이며, 대부분의 상황에서 자바 컬렉션 중 가장 빠른 Map 구현체입니다
단점
순서를 보장하지 않기 때문에 입력 순서나 정렬이 필요한 경우 부적합합니다
키 객체는 hashCode()/equals()를 정확히 구현해야 하며, 가변 객체를 키로 사용할 때 주의해야 합니다.
기타
멀티스레드 환경에서는 직접 사용하면 안 됩니다
현대 자바에서는 ConcurrentHashMap을 통해 구현해야 합니다
LinkedHashMap
HashMap을 상속하여 엔트리를 이중 연결 리스트로 연결함으로써 삽입 순서(또는 접근 순서)를 유지하는 맵입니다
성능
기본 연산(put/get/remove)은 HashMap과 동일하게 평균 O(1)입니다
메모리
각 엔트리가 이전/다음 엔트리의 참조 포인터 두 개를 추가로 가지므로 HashMap보다 메모리 소비가 조금 더 높습니다
장점
예측 가능한 순회 순서를 제공합니다.
LRU 캐시 구현처럼 최근 사용된 순서로 정렬해야 할 경우에 유용합니다
단점
HashMap보다 약간의 성능/메모리 오버헤드가 있습니다.
정렬된 순서가 아닌 삽입(또는 접근) 순서만 보존합니다
또한 멀티스레드 환경에서는 thread-unsafe합니다.
TreeMap
레드-블랙 트리 기반의 이진 탐색 트리 맵입니다
NavigableMap/SortedMap 인터페이스 구현체로, 키를 항상 오름차순으로 정렬하여 저장합니다
성능
TreeSet과 유사하게 삽입(put), 검색(get), 삭제(remove)가 모두 O(log n)입니다.
균형 트리 유지 비용으로 HashMap보다 느립니다
장점
키가 항상 정렬된 상태로 유지되므로, 정렬된 출력이나 범위 검색 등에 매우 유용합니다.
subMap 등의 부분 범위 데이터 추출 및 higherKey, lowerEntry 등 주변 키 탐색을 지원합니다
단점
HashMap보다 느린 성능이 단점입니다
따라서 정렬이 불필요한 경우 비효율적입니다
Hashtable
자바 1.0부터 존재한 해시 테이블 기반 Map으로, HashMap과 유사하나
모든 메소드가 synchronized되어 Thread-Safe합니다. 현재는 거의 사용되지 않습니다
성능
멀티스레드 환경을 가정하지 않으면, HashMap 대비 느립니다.
단일 락으로 심각한 병목이 발생하고, 자바 8 이후의 HashMap 개선(트리화 등)이 Hashtable에는 적용되지 않았습니다
만약 동기화된 Map이 필요하면 Hashtable 대신 ConcurrentHashMap을 사용하는 것이 권장됩니다
참고
- 자바 성능 튜닝 이야기 - 4챕터
