ArrayList vs LinkedList vs HashMap 내부 동작¶
PHASE 2 | Java 핵심 — 객체지향
키워드:ArrayList,LinkedList,HashMap,배열,노드,버킷,해시충돌,리해싱,로드팩터,O(1),O(n)
ArrayList¶
배열 기반의 리스트. 내부적으로 Object[] 배열을 사용한다.
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
내부 구조:
index: [0] [1] [2] [3] ...
value: [A] [B] [C] [ ] ...
시간 복잡도¶
| 연산 | 복잡도 | 이유 |
|---|---|---|
| 조회 | O(1) |
index로 바로 접근 |
| 중간 삽입/삭제 | O(n) |
뒤 요소 전부 이동 |
| 맨 뒤 삽입/삭제 | O(1) |
이동 불필요 |
자동 크기 확장 — 배열이 꽉 차면 1.5배 크기의 새 배열을 만들고 복사함.
LinkedList¶
노드 기반의 리스트. 각 노드가 다음 노드의 주소를 가지고 있다.
[A | →] → [B | →] → [C | null]
시간 복잡도¶
| 연산 | 복잡도 | 이유 |
|---|---|---|
| 조회 | O(n) |
처음부터 순서대로 탐색 |
| 중간 삽입/삭제 | O(n) |
노드 탐색 O(n) + 실제 삽입/삭제 O(1) |
| 맨 앞/뒤 삽입/삭제 | O(1) |
head/tail 참조 바로 접근 |
LinkedList가 실질적으로 빠른 경우는 맨 앞/뒤 삽입/삭제 또는
이미 노드 참조를 알고 있을 때만이다.
중간 삽입/삭제는 탐색 때문에 결국O(n)이다.
ArrayList vs LinkedList 비교¶
| ArrayList | LinkedList | |
|---|---|---|
| 내부 구조 | 배열 | 노드 연결 |
| 조회 | O(1) |
O(n) |
| 중간 삽입/삭제 | O(n) |
O(n) |
| 맨 앞/뒤 삽입/삭제 | O(1) |
O(1) |
| 메모리 | 적게 사용 | 많이 사용 (주소값 저장) |
| 실무 사용 | 대부분의 경우 | Queue/Deque 구현 등 맨 앞/뒤 삽입삭제가 빈번한 경우 |
실무에서는 대부분 ArrayList를 사용한다.
LinkedList는 중간 삽입/삭제도 탐색 때문에 O(n)이라 생각보다 이점이 적다.
맨 앞/뒤 삽입/삭제가 매우 빈번한 경우(Queue, Deque)에만 유리하다.
HashMap¶
Key-Value 쌍으로 데이터를 저장하는 자료구조.
내부적으로 배열 + 연결리스트(또는 트리) 구조다.
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
put() 동작 흐름¶
1. Key.hashCode() → 해시값 계산
2. 해시값 % 배열크기 → 버킷(index) 결정
3. 해당 버킷에 저장
hashCode("apple") % 16 = 3번 버킷에 저장
hashCode("banana") % 16 = 7번 버킷에 저장
get() 동작 흐름¶
1. Key.hashCode() → 해시값 계산
2. 해시값 % 배열크기 → 버킷 찾기
3. 버킷 안에서 equals()로 정확한 Key 찾기
4. 해당 Value 반환
hashCode()로 버킷을 찾고, equals()로 정확한 값을 찾는 구조다.
HashMap의 Key로 쓰는 객체는 equals()와 hashCode()를 반드시 재정의해야 하는 이유가 여기 있다.
Key 중복 처리¶
| 상황 | 결과 |
|---|---|
| hashCode() 같고 equals() true | 같은 Key → Value 덮어쓰기 |
| hashCode() 같고 equals() false | 다른 Key → 같은 버킷에 연결리스트로 추가 (해시 충돌) |
| hashCode() 다름 | 다른 버킷에 저장 |
해시 충돌¶
다른 Key인데 같은 버킷에 배정되는 경우다.
hashCode("abc") % 16 = 5
hashCode("xyz") % 16 = 5 ← 같은 버킷! (해시 충돌)
해결 방법: 같은 버킷에 연결리스트로 이어서 저장.
Java 8부터는 노드가 8개 이상이면 트리(레드-블랙 트리) 로 변환해서 성능을 높인다.
리해싱 (Rehashing)¶
배열 크기가 늘어나면 기존 데이터를 전부 새 배열에 다시 배치해야 한다.
이를 리해싱이라고 하며, 해시값을 기반으로 전체 데이터를 새 위치에 재배치한다.
로드 팩터(load factor) 기준으로 발생한다.
기본 설정: 초기 배열 크기 16, 로드 팩터 0.75
16 * 0.75 = 12개 차면 → 배열 32로 확장 + 전체 리해싱
// 데이터가 많을 것 같으면 초기 크기 지정
new HashMap<>(64); // 리해싱 빈도 줄임
리해싱은 비용이 크다 (
O(n)).
데이터가 많을 것 같으면 초기 크기를 크게 잡는 것이 좋다.
세 가지 한눈에 보기¶
| ArrayList | LinkedList | HashMap | |
|---|---|---|---|
| 구조 | 배열 | 노드 연결 | 배열 + 연결리스트 |
| 특화 | 조회 | 맨 앞/뒤 삽입/삭제 | Key-Value 빠른 조회 |
| 조회 | O(1) |
O(n) |
O(1) |
| 실무 | 기본 리스트 | Queue/Deque 구현 | 캐싱, 빠른 탐색 |
면접 포인트¶
Q. ArrayList와 LinkedList의 차이는?
ArrayList는 배열 기반으로 조회가 O(1)이고, LinkedList는 노드 기반으로 맨 앞/뒤 삽입/삭제가 O(1)이다.
중간 삽입/삭제는 둘 다 O(n)이며, 실무에서는 대부분 ArrayList를 사용한다.
Q. HashMap의 put()과 get() 동작 흐름은?
put(): hashCode()로 버킷을 찾고 저장한다.
get(): hashCode()로 버킷을 찾고, equals()로 정확한 Key를 찾아 Value를 반환한다.
Q. HashMap에서 equals()와 hashCode()를 재정의해야 하는 이유는?
hashCode()로 버킷을 찾고 equals()로 정확한 Key를 찾는 구조이기 때문이다.
재정의하지 않으면 같은 내용의 Key라도 다른 버킷에 저장되어 정상적으로 조회할 수 없다.
Q. 리해싱이란?
배열 크기가 늘어날 때 기존 데이터를 새 배열에 전부 재배치하는 작업이다.
기본 로드 팩터 0.75 기준으로, 배열의 75%가 차면 2배로 확장하고 리해싱이 발생한다.