Map, Set, List는 대부분의 프로그래밍 언어에서 자주 사용되는 대표적인 자료구조입니다.
어렴풋이 알고 있다고 생각했지만, 막상 설명해보려니 정확하게 이해하지 못하고 있다는 느낌이 들었습니다.
그래서 이번 글에서는 Map, Set, List의 동작 방식과 구현체별 차이점을 정리하면서, 순서 보장 여부와 중복 허용 여부를 명확하게 정리해두려고 합니다.
1. Map, Set, List의 기본적인 차이점
| 특징 | Map (Key-Value 저장) | Set (중복 없는 값 저장) | List (중복 허용, 순서 유지) |
| 데이터 저장 방식 | Key-Value 쌍으로 저장 | 중복 없는 단일 값(Value) 저장 | 중복을 허용하며 순서대로 값 저장 |
| 중복 허용 여부 | Key 중복 ❌, Value는 중복 가능 | 중복 ❌ | 중복 ⭕ |
| 순서 보장 여부 | 구현체에 따라 다름 | 구현체에 따라 다름 | 항상 순서 유지 ⭕ |
📌 핵심 차이점
- Map은 Key-Value 쌍으로 저장하지만, Set과 List는 단일 값 저장
- Map에서는 Key가 중복될 수 없지만, Set에서는 값 자체가 중복될 수 없음
- List는 항상 순서를 유지하지만, Map과 Set은 특정 구현체에서만 순서를 유지
2. Map은 "순서를 보장하는가?"
"Map은 기본적으로 순서를 보장하지 않지만, 특정 구현체는 순서를 유지할 수 있습니다."
| Map 구현체 | 순서 보장 여부 | 설명 |
| HashMap | ❌ 순서를 보장하지 않음 | Key-Value가 저장된 순서가 유지되지 않음 |
| LinkedHashMap | ⭕ 입력된 순서를 유지 | Key-Value가 추가된 순서대로 저장 |
| TreeMap | ⭕ Key 기준으로 정렬 | Key를 오름차순(기본) 또는 지정된 Comparator에 따라 정렬 |
📌 정확한 표현:
- "Map은 기본적으로 Key-Value 저장 방식을 사용하며, 특정 구현체(LinkedHashMap, TreeMap)만 순서를 보장합니다."
4. List는 항상 순서를 보장하는가?
→ "List는 항상 순서를 보장하며, 중복을 허용합니다."
List는 배열(Array)과 연결 리스트(Linked List)를 기반으로 동작하므로, 입력된 순서가 유지됩니다.
| List 구현체 | 순서 보장 여부 | 중복 허용 여부 | 설명 |
| ArrayList | ⭕ 순서 유지 | ⭕ 중복 허용 | 동적 배열 기반, 검색 빠름(O(1)) |
| LinkedList | ⭕ 순서 유지 | ⭕ 중복 허용 | 이중 연결 리스트 기반, 삽입/삭제 빠름 (O(1)) |
5. Map, Set, List의 구현체별 비교 정리
| 구현체 | 구조 | 순서 보장 여부 | 중복 허용 여부 |
| HashMap | 해시 테이블 | ❌ 순서를 보장하지 않음 | Key 중복 ❌, Value 중복 ⭕ |
| LinkedHashMap | 해시 테이블 + 이중 연결 리스트 | ⭕ 입력된 순서를 유지 | Key 중복 ❌, Value 중복 ⭕ |
| TreeMap | 이진 탐색 트리 (Red-Black Tree) | ⭕ Key 기준 정렬 | Key 중복 ❌, Value 중복 ⭕ |
| HashSet | 해시 테이블 | ❌ 순서를 보장하지 않음 | 중복 ❌ |
| LinkedHashSet | 해시 테이블 + 이중 연결 리스트 | ⭕ 입력된 순서를 유지 | 중복 ❌ |
| TreeSet | 이진 탐색 트리 (Red-Black Tree) | ⭕ 정렬된 순서 유지 | 중복 ❌ |
| ArrayList | 동적 배열 | ⭕ 순서 유지 | ⭕ 중복 허용 |
| LinkedList | 이중 연결 리스트 | ⭕ 순서 유지 | ⭕ 중복 허용 |
6. Map, Set, List를 선택할 때 고려할 점
✔ 중복 허용 여부
- Map은 Key 중복이 불가능하지만, Value 중복은 가능
- Set은 모든 요소가 중복될 수 없음
- List는 중복을 허용함
✔ 순서 유지 여부
- Map: 기본적으로 순서를 보장하지 않지만, LinkedHashMap과 TreeMap은 보장
- Set: 기본적으로 순서를 보장하지 않지만, LinkedHashSet과 TreeSet은 보장
- List: 항상 입력된 순서를 유지
✔ 어떤 경우에 어떤 구현체를 사용해야 할까?
- "순서가 필요 없고 빠른 검색이 필요" → HashMap, HashSet
- "입력된 순서를 유지해야 함" → LinkedHashMap, LinkedHashSet, List
- "정렬된 상태로 데이터를 유지해야 함" → TreeMap, TreeSet
7. 요약
- Map은 기본적으로 순서를 보장하지 않지만, 특정 구현체(LinkedHashMap, TreeMap)는 순서를 유지할 수 있습니다.
- Set은 기본적으로 중복을 허용하지 않으며, 특정 구현체(LinkedHashSet, TreeSet)는 순서를 유지할 수 있습니다.
- List는 항상 순서를 보장하며, 중복을 허용합니다.
- HashMap과 HashSet은 가장 빠르지만, 순서를 보장하지 않습니다.
- LinkedHashMap과 LinkedHashSet은 입력된 순서를 유지합니다.
- TreeMap과 TreeSet은 정렬된 순서를 유지합니다.
반응형
