Java 컬렉션 프레임워크에서 제공하는 주요 인터페이스인 List, Set, Map의 구현체들은 각각 다른 성능 특성을 가지고 있습니다.
이러한 성능 차이를 이해하면 적절한 자료구조를 선택하여 애플리케이션의 효율성을 높일 수 있습니다.
List 구현체 성능 비교
| 연산 | ArrayList | LinkedList |
|---|---|---|
| 조회(get) | O(1) – 빠름 | O(n) – 느림 |
| 삽입(add) | 끝에 추가: O(1), 중간/시작: O(n) | 끝에 추가: O(n), 시작/중간: O(1) |
| 수정(set) | O(1) – 빠름 | O(n) – 느림 |
| 삭제(remove) | 끝에서 삭제: O(1), 중간/시작: O(n) | 위치를 알 경우: O(1) |
| 탐색(contains/indexOf) | O(n) | O(n) |
| 크기 확인(size) | O(1) | O(1) |
성능 고려사항
-
ArrayList: 랜덤 접근이 빠르지만 중간에 삽입/삭제가 느림
-
LinkedList: 시작이나 중간에 삽입/삭제가 빠르지만 랜덤 접근이 느림
Set 구현체 성능 비교
| 연산 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 삽입(add) | O(1) – 빠름 | O(1) – 빠름 | O(log n) – 느림 |
| 삭제(remove) | O(1) – 빠름 | O(1) – 빠름 | O(log n) – 느림 |
| 조회(contains) | O(1) – 빠름 | O(1) – 빠름 | O(log n) – 느림 |
성능 고려사항
-
HashSet: 순서가 필요 없는 고유 요소 컬렉션에 최적화, 빠른 조회/삽입
-
LinkedHashSet: HashSet과 유사한 성능이지만 삽입 순서 유지
-
TreeSet: 정렬된 순서를 유지하지만 트리 구조로 인해 연산이 느림
Map 구현체 성능 비교
| 연산 | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
| 삽입(put) | O(1) – 빠름 | O(1) – 빠름 | O(log n) – 느림 |
| 삭제(remove) | O(1) – 빠름 | O(1) – 빠름 | O(log n) – 느림 |
| 조회(get) | O(1) – 빠름 | O(1) – 빠름 | O(log n) – 느림 |
| 크기 확인(size) | O(1) | O(1) | O(1) |
성능 고려사항
-
HashMap: 순서가 필요 없는 키-값 매핑에 최적화, 대부분의 연산이 O(1)로 매우 빠름
-
LinkedHashMap: HashMap과 유사한 성능이지만 삽입 순서 유지
-
TreeMap: 키를 기준으로 정렬된 순서를 유지하지만 트리 구조로 인해 연산이 느림
상황별 최적 컬렉션 선택 가이드
-
랜덤 접근이 필요한 경우:
-
ArrayList 사용 (O(1) 접근 시간)
-
-
빈번한 삽입/삭제가 필요한 경우:
-
LinkedList 사용 (양 끝에서 O(1) 성능)
-
-
순서 없이 고유성만 필요한 경우:
-
HashSet 사용 (O(1) 성능)
-
-
정렬된 순서가 필요한 경우:
-
TreeSet 또는 TreeMap 사용 (O(log n) 성능)
-
-
키-값 쌍이 필요하고 순서가 중요하지 않은 경우:
-
HashMap 사용 (삽입/조회에 O(1) 성능)
-
스탠포드 대학의 자료에 따르면, HashMap은 10만 개의 항목이 있더라도 get()과 put() 연산이 거의 즉시 접근 가능한 성능을 제공하기 때문에 키-값 저장이 필요한 대부분의 상황에서 가장 적합한 선택입니다.
적절한 컬렉션 구현체를 선택함으로써 애플리케이션의 성능을 크게 향상시킬 수 있으며, 각 구현체의 특성을 이해하는 것이 효율적인 Java 프로그래밍의 핵심입니다.