HashMap에서 7개의 키가 충돌하면 어떤 일이 일어나는가 — 컬렉션 선택의 기준
HashMap에 7개의 키를 넣었다. 버킷 하나에 8번째 충돌이 발생하는 순간, 내부 데이터 구조가 연결 리스트에서 레드블랙 트리로 바뀐다. (HashMap JavaDoc) 대부분의 개발자는 이 사실을 모른 채 HashMap을 쓴다. 그래야 할까? — 대부분의 경우 그래도 된다. 하지만 성능이 갑자기 저하되거나, 메모리가 예상보다 많이 쓰일 때, 이 내부 구조를 아는 것이 문제 해결의 열쇠가 된다.
왜 ArrayList는 0.001초인데 LinkedList는 1초 걸릴까? 정답은 "메모리에 어떻게 배치되어 있는가"에 있다. 이 글은 List, Set, Map, Queue 각각이 내부적으로 어떻게 동작하는지를 풀어간다.
컬렉션 프레임워크 전체 구조
flowchart TD
COL["Collection<E>"] --> LST["List<E>"]
COL --> SET["Set<E>"]
COL --> QUE["Queue<E>"]
LST --> AL["ArrayList"]
LST --> LL["LinkedList"]
SET --> HS["HashSet"]
SET --> TS["TreeSet"]
HS --> LHS["LinkedHashSet"]
QUE --> PQ["PriorityQueue"]
QUE --> DQ["Deque<E>"]
DQ --> AR["ArrayDeque"]
MAP["Map<K,V> (Collection 아님)"] --> HM["HashMap"]
MAP --> TM["TreeMap"]
HM --> LHM["LinkedHashMap"]
Map은Collection인터페이스를 상속하지 않는다. (Map API) Map은 키-값 쌍을 다루는 별도의 루트 인터페이스다.keySet(),values(),entrySet()으로 Collection 뷰를 제공한다.
List — 순서가 있고 중복 허용
ArrayList vs LinkedList
| 구현체 | 내부 구조 | get(i) | add(e) | add(0, e) | 메모리 |
|---|---|---|---|---|---|
| ArrayList | 동적 배열 | O(1) | O(1)* | O(n) | 적음 |
| LinkedList | 이중 연결 리스트 | O(n) | O(1)** | O(1) | 많음(노드당 참조 2개) |
*ArrayList의add(e)는 평균 O(1)이지만, 내부 배열이 가득 차면 크기를 두 배로 늘리며 복사하므로 가끔 O(n)이 된다.**LinkedList의add(e)는 tail 참조가 있으면 O(1)이다.
실용적 가이드: 99%의 경우 ArrayList를 쓴다. LinkedList는 다음 조건에서만 의미가 있다:
- 헤드/테일에서 빈번한 삽입·삭제 (큐/덱 용도) — 그래도 이 목적이라면
ArrayDeque가 더 빠르다 - 인덱스 접근이 거의 없고, 순차 순회만 하는 대규모 리스트
ArrayList가 LinkedList보다 메모리 캐시 친화적이다(데이터가 연속된 메모리에 있음). 따라서 이론적 복잡도가 같아도 실제 성능은 ArrayList가 유리한 경우가 많다.
ArrayList의 중요한 함정 — subList와 구조적 수정
// Java 25
List<Integer> original = new ArrayList<>(List.of(1, 2, 3, 4, 5));
List<Integer> sub = original.subList(1, 4); // [2, 3, 4] — 뷰(view), 복사본 아님
original.add(6); // 구조적 수정
// sub.get(0); // ConcurrentModificationException!
// subList는 원본의 뷰이므로, 원본이 구조적으로 변경되면 무효화됨
subList()는 새 리스트를 만드는 것이 아니라 원본의 뷰를 반환한다. (List.subList API) 원본을 수정하면 뷰가 깨진다. 복사본이 필요하면new ArrayList<>(original.subList(1, 4))로 감싼다.
Set — 중복 불가
| 구현체 | 순서 | 정렬 | 성능 | 내부 구조 |
|---|---|---|---|---|
| HashSet | 없음 | 없음 | O(1) 평균 | HashMap |
| LinkedHashSet | 삽입 순서 | 없음 | O(1) | HashMap + 연결 리스트 |
| TreeSet | 정렬됨 | 자연순/Comparator | O(log n) | 레드블랙 트리 |
// Java 25
Set<String> hash = new HashSet<>(List.of("banana", "apple", "cherry"));
Set<String> linked = new LinkedHashSet<>(List.of("banana", "apple", "cherry"));
Set<String> tree = new TreeSet<>(List.of("banana", "apple", "cherry"));
System.out.println(hash); // 순서 무관 (해시값 기준)
System.out.println(linked); // [banana, apple, cherry] (삽입 순서)
System.out.println(tree); // [apple, banana, cherry] (정렬)
HashSet은 내부적으로HashMap의 키만 사용한다. (HashSet 소스) 값에는 더미 객체를 넣는다. 그래서 HashSet의 성능 특성이 HashMap과 동일하다.
Map — 키-값 쌍
HashMap 내부 구조 — 이 글의 핵심
HashMap은 버킷(bucket) 배열 + 각 버킷의 연결 리스트/트리로 구성된다.
flowchart LR
K["key.hashCode()"] --> H["hash() 변환"]
H --> IDX["index = hash & (capacity - 1)"]
IDX --> B0["버킷 0"]
IDX --> B1["버킷 1: Entry → Entry → Entry"]
IDX --> B2["버킷 2: Entry → Entry"]
IDX --> BN["버킷 N"]버킷이 비어 있으면 즉시 저장(O(1)). 충돌이 발생하면(같은 버킷에 여러 엔트리), 연결 리스트로 관리한다.
treeification(트리화, Java 8+): 한 버킷의 엔트리가 8개 이상이고, 전체 버킷 용량이 64 이상이면, 연결 리스트가 레드블랙 트리로 전환된다. (HashMap JavaDoc) 트리는 최악의 경우 O(n) → O(log n)으로 개선한다. 트리 노드가 6개 이하로 줄면 다시 연결 리스트로 되돌린다.
treeification 조건: 버킷당 엔트리 ≥ 8(
TREEIFY_THRESHOLD) AND 전체 용량 ≥ 64(MIN_TREEIFY_CAPACITY). 용량이 64 미만이면 트리화 대신 리사이즈(rehash)를 수행한다. 키 타입이Comparable를 구현하면 트리 정렬에 사용되고, 그렇지 않으면System.identityHashCode()를 사용한다.
HashMap의 load factor와 resize
| 설정 | 기본값 | 의미 |
|---|---|---|
initialCapacity |
16 | 초기 버킷 수 |
loadFactor |
0.75 | 버킷 사용률이 이 값에 도달하면 resize (두 배) |
// Java 25 — 초기 용량 명시적 지정 (프로덕션 권장)
// 예: 약 1000개의 엔트리가 예상됨
Map<String, Integer> map = new HashMap<>(1340, 0.75f); // 1000 / 0.75 ≈ 1334 → 올림
HashMap은 resize 시 모든 엔트리를 새 배열로 재해시(rehash) 해야 한다. 이것은 O(n) 비용이다. 초기 용량을 예상 데이터 크기에 맞게 설정하면 resize를 피할 수 있다 — 프로덕션에서는 항상 예상 크기를 명시하는 것이 좋다.
LinkedHashMap — 삽입 순서 또는 접근 순서
// Java 25 — 접근 순서(access-order) 모드 → LRU 캐시 구현 가능
LinkedHashMap<String, Integer> cache = new LinkedHashMap<>(16, 0.75f, true);
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
cache.get("A"); // A에 접근 → A가 가장 최근으로 이동
System.out.println(cache.keySet()); // [B, C, A]accessOrder = true로 설정하면, get() 호출 시 해당 엔트리를 가장 최근 위치로 이동시킨다. removeEldestEntry()를 override하면 LRU(Least Recently Used) 캐시를 쉽게 구현할 수 있다.
TreeMap — 정렬된 Map
// Java 25
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "three");
map.put(1, "one");
map.put(2, "two");
System.out.println(map.keySet()); // [1, 2, 3]
System.out.println(map.firstKey()); // 1
System.out.println(map.lastKey()); // 3
System.out.println(map.subMap(1, 3)); // {1=one, 2=two} (1 ≤ key < 3)
System.out.println(map.descendingMap()); // {3=three, 2=two, 1=one}TreeMap은 레드블랙 트리 기반이다. 범위 검색(subMap, headMap, tailMap), 정렬된 순회가 필요할 때 쓴다. 성능은 HashMap보다 느리다(O(log n) vs O(1)).
Queue / Deque
| 구현체 | 용도 | 성능 특징 |
|---|---|---|
| ArrayDeque | 스택, 큐, 덱 | 배열 기반. LinkedList보다 빠름. |
| PriorityQueue | 우선순위 큐 | 힙(heap) 기반. offer/poll O(log n) |
| LinkedList (Deque 구현) | 큐/덱 | 연결 리스트. ArrayDeque가 더 빠름 |
// Java 25 — ArrayDeque를 스택으로
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
stack.push("C");
System.out.println(stack.pop()); // C (LIFO)
// Java 25 — PriorityQueue
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll()); // 1 (최소값 우선)
java.util.Stack은 레거시다 —synchronized오버헤드가 있고, 단일 스레드에서도 느리다. 스택이 필요하면ArrayDeque를 쓴다. (Deque API)
불변 컬렉션 (Java 9+ — List.of, Map.of)
// Java 25 — 팩토리 메서드로 불변 컬렉션 생성
List<String> immutable = List.of("a", "b", "c");
Map<String, Integer> map = Map.of("one", 1, "two", 2);
// immutable.add("d"); // UnsupportedOperationExceptionList.of, Set.of, Map.of로 생성된 컬렉션은 불변이다. (List.of API) 추가, 삭제, 수정이 모두 UnsupportedOperationException을 던진다.
null을 허용하지 않는다.List.of(null)은NullPointerException을 던진다. 기존Arrays.asList()는null을 허용하지만, 요소 추가/삭제는 불가(크기 변경 불가, 요소 수정은 가능).
반복자(Iterator)와 ConcurrentModificationException
컬렉션을 순회하면서 요소를 삭제하면 ConcurrentModificationException이 발생한다 — fail-fast 동작이다.
// Java 25 — 잘못된 방식: 순회 중 직접 삭제
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5));
for (Integer n : nums) {
if (n % 2 == 0) {
// nums.remove(n); // ConcurrentModificationException!
}
}
// Java 25 — 올바른 방식 1: Iterator.remove()
Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
if (it.next() % 2 == 0) {
it.remove(); // 안전하게 삭제
}
}
// Java 25 — 올바른 방식 2: removeIf (Java 8+)
nums.removeIf(n -> n % 2 == 0); // 가장 간결
fail-fast는
modCount필드로 구현된다. 컬렉션의 구조적 변경(추가/삭제)마다modCount가 증가하고, 반복자는 순회 시작 시점의modCount를 기억하여 불일치 시 예외를 던진다. (ArrayList 소스 - modCount)
반면 CopyOnWriteArrayList, ConcurrentHashMap은 fail-safe다 — 순회 중 수정이 허용되지만, 반복자는 복사본(snapshot)을 기반으로 동작하므로 최신 변경 사항이 반영되지 않을 수 있다.
실습 — HashMap treeification 체감
// Java 25 — HashCollisionDemo.java
import java.util.HashMap;
import java.util.Map;
public class HashCollisionDemo {
public static void main(String[] args) {
Map<BadKey, Integer> map = new HashMap<>();
// hashCode()가 항상 같은 값을 반환하는 키 — 모두 같은 버킷에 충돌
for (int i = 0; i < 12; i++) {
map.put(new BadKey(i), i);
}
System.out.println("맵 크기: " + map.size());
System.out.println("조회: " + map.get(new BadKey(5)));
// 내부 구조는 볼 수 없지만, 성능으로 간접 확인 가능
long start = System.nanoTime();
for (int i = 0; i < 12; i++) {
map.get(new BadKey(i));
}
long elapsed = System.nanoTime() - start;
System.out.printf("12회 조회: %d ns%n", elapsed);
}
// hashCode가 항상 같은 값 → 모든 키가 같은 버킷에 충돌
static class BadKey {
final int value;
BadKey(int value) { this.value = value; }
@Override public int hashCode() { return 1; } // 모두 같은 버킷
@Override public boolean equals(Object o) {
return o instanceof BadKey b && value == b.value;
}
@Override public String toString() { return "BadKey(" + value + ")"; }
}
}java HashCollisionDemo.java맵 크기: 12
조회: 5
12회 조회: 약 10000~50000 ns (환경에 따라 다름)확인할 것: 모든 키가 같은 버킷에 충돌해도, Java 8+에서는 트리화가 일어나 O(log n) 성능을 보장한다. Java 7 이하에서는 O(n)이었다. 좋은 hashCode() 구현의 중요성에도 불구하고, treeification이 최악의 경우를 방어한다.
Collections.synchronizedList는 내부적으로 모든 메서드를synchronized로 감싼다. 읽기가 많고 쓰기가 적은 환경에서는CopyOnWriteArrayList(복사-온-라이트)가 더 나을 수 있다. 상황에 따라 선택한다.
Collections 유틸리티 — 정렬, 탐색, 불변 래핑
// Java 25
List<Integer> nums = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));
Collections.sort(nums); // 정렬 (TimSort, O(n log n))
System.out.println(nums); // [1, 1, 2, 3, 4, 5, 6, 9]
int idx = Collections.binarySearch(nums, 5); // 이진 탐색 (정렬 필요)
Collections.reverse(nums); // 역순
Collections.shuffle(nums); // 무작위 섞기
List<Integer> readOnly = Collections.unmodifiableList(nums); // 불변 래핑
Collections.sort()는 Java 8+부터List.sort()로 위임한다. 내부적으로 배열로 복사 → TimSort → 다시 리스트에 기록하는 방식이다. (List.sort API)List.of()는 불변이므로sort()를 호출하면UnsupportedOperationException이 발생한다 — 가변 리스트에서만 정렬 가능.
요약 — 이 글의 결론
- List는 99%의 경우 ArrayList. LinkedList는 이론적 장점이 있지만, 메모리 캐시 효율에서 ArrayList가 유리하다. 큐/덱은 ArrayDeque.
- Set은 순서가 필요 없으면 HashSet, 정렬이 필요하면 TreeSet. LinkedHashSet은 삽입 순서를 보존한다.
- HashMap은 충돌 8개부터 트리화된다. 좋은
hashCode()구현이 여전히 중요하지만, treeification이 최악의 경우를 O(log n)으로 방어한다. - 초기 용량을 예상 데이터 크기에 맞게 설정한다. resize(rehash)는 O(n) 비용이다. 프로덕션에서는
new HashMap<>(expectedSize / 0.75 + 1)로 미리 계산한다. - 불변 컬렉션은
List.of/Map.of로. 가변이 필요할 때만ArrayList/HashMap으로 감싼다.
생각해 볼 문제
HashMap의 버킷이 8개 이상 충돌했지만 전체 용량이 64 미만이라면 어떻게 되는가? 트리화가 일어나는가?Collections.synchronizedList(new ArrayList<>())vsCopyOnWriteArrayList의 차이를 읽기/쓰기 빈도 관점에서 설명하라.ConcurrentHashMap이HashMap과 다르게null키/값을 금지하는 이유는 무엇인가?record Person(String name)을HashMap의 키로 사용할 때,hashCode/equals가 어떻게 동작하는가?List.of()로 생성한 리스트의getClass()는ArrayList.class인가? 실제 클래스명을 확인해 보자.
참고
- HashMap API (Java 25) - 접근 2026-07-10
- List.of API (Java 25) - 접근 2026-07-10
- Deque API (Java 25) - 접근 2026-07-10
- Collections Framework Overview (Java 25) - 접근 2026-07-10
- HashSet 소스 코드 - 접근 2026-07-10
'Develop Artifacts > Java' 카테고리의 다른 글
| Java - 12. lambda functional (0) | 2026.07.12 |
|---|---|
| Java - 11. generics (0) | 2026.07.12 |
| Java - 09. exception (0) | 2026.07.12 |
| Java - 08. record sealed enum (0) | 2026.07.12 |
| Java - 07. interface and abstract (0) | 2026.07.12 |
