📚 Java 주요 자료구조 비교 정리

Java 컬렉션 프레임워크에는 다양한 자료구조가 있으며,
각각 저장 방식, 정렬 여부, 순서 유지 여부, 성능 특성이 다릅니다.
코딩테스트나 실무에서 문제에 맞는 자료구조를 선택하려면 이 차이를 이해하는 것이 중요합니다.

---

📊 자료구조 비교표

자료구조	Key/Value	내부 구조	정렬 여부	순서 유지	평균 접근 속도	특징
HashMap	Key→Value	해시 테이블	❌	❌	O(1)	빠른 검색
HashSet	값만	해시 테이블	❌	❌	O(1)	중복 없음
TreeMap	Key→Value	Red-Black Tree	✅	정렬	O(log N)	범위 검색
TreeSet	값만	Red-Black Tree	✅	정렬	O(log N)	중복 없음 + 범위검색
LinkedHashMap	Key→Value	해시 + 연결 리스트	❌	✅	O(1)	삽입 순서 유지
LinkedHashSet	값만	해시 + 연결 리스트	❌	✅	O(1)	삽입 순서 유지
PriorityQueue	값만	Binary Heap	❌ (최소/최대만 보장)	❌	O(log N)	최소/최대 반복 추출 최적
ArrayDeque	값만	배열	❌	삽입순	O(1)	양쪽 삽입/삭제 빠름

---

📝 각 자료구조 특징 정리

1. HashMap

• Key → Value 매핑
• 평균 접근 속도 O(1) (해시 충돌 시 최악 O(N))
• 순서 유지 X, 정렬 X
• 빠른 검색과 삽입이 필요한 경우 사용

2. HashSet

• 값만 저장, 중복 불가
• 내부적으로 HashMap의 Key만 사용하는 구조
• 순서 유지 X, 정렬 X
• 중복 제거 목적에 적합

3. TreeMap

• Key 기준 정렬된 상태 유지 (오름차순 기본)
• 범위 검색, 최솟값/최댓값 검색 용이
• 접근/삽입/삭제 O(log N)

4. TreeSet

• 값만 저장, 중복 불가
• 값 기준 정렬된 상태 유지
• first(), last(), higher(), lower() 메서드로 범위 검색 가능

5. LinkedHashMap

• HashMap + 이중 연결 리스트
• 삽입 순서 유지
• LRU(Least Recently Used) 캐시 구현 시 유용

6. LinkedHashSet

• HashSet + 이중 연결 리스트
• 삽입 순서 유지, 중복 불가

7. PriorityQueue

• Binary Heap 기반, 최솟값(기본) 또는 최댓값 빠르게 추출
• 전체 정렬 상태는 보장하지 않음
• 삽입/삭제 O(log N)
• 최소/최대 우선순위 작업 반복에 최적

8. ArrayDeque

• 양쪽 끝에서 O(1)로 삽입/삭제 가능
• Stack, Queue, Deque 역할 모두 가능
• 내부는 배열 기반

---

💡 자료구조 선택 가이드

• 빠른 검색 + 순서 필요 없음 → HashMap
• 중복 없는 집합 + 순서 필요 없음 → HashSet
• 정렬된 상태 유지 + 범위 검색 → TreeMap / TreeSet
• 입력 순서 유지 → LinkedHashMap / LinkedHashSet
• 최소/최대값 반복 추출 → PriorityQueue
• 양쪽 끝 조작 빠른 큐/덱 → ArrayDeque

---

📌 코딩테스트 팁:

• Key-Value 저장이 아니라 단순 값 저장이라면 Map보다 Set을 우선 고려
• 정렬된 상태가 필요하다면 Tree 계열, 필요 없다면 Hash 계열
• 최소/최대값만 필요하면 PriorityQueue가 정렬보다 효율적