JAVA의 자료구조를 톺아보자

Java Collection 톺아보기

List

ArrayList를 톺아보자

ArrayList는 이름에 List가 들어가지만, 본질적으로는 배열 기반 자료구조이다.

그래서 인덱스를 통한 조회가 빠르다.

🤔 배열 공간이 꽉 찬다면?
더 큰 배열을 새로 만들고, 기존 데이터를 새 배열로 복사한다.

---

LinkedList를 톺아보자

LinkedList는 prev, next 형태의 참조로 노드 객체를 연결하는 자료구조이다.

배열처럼 인덱스로 바로 접근할 수 없기 때문에 조회가 느리다.

🤔 중간 삽입/삭제가 빠르니 무조건 좋을까?
해당 노드를 이미 알고 있다면 빠르다.
하지만 index 기준으로 삽입/삭제를 한다면, 결국 해당 위치까지 찾아가야 하므로 느리다.

---

Map

HashMap을 톺아보자

HashMap의 기본적인 본질은 배열 + 해시 + 충돌 처리이다.

내부에는 다음과 같은 배열이 존재한다.

Node<K, V>[] table;

이 배열의 각 칸을 bucket이라고 부른다.

값이 저장되는 흐름은 대략 다음과 같다.

key → hash → index → bucket

즉, 주어진 key에 대해 해시를 만들고, 그 해시를 배열 인덱스로 변환한 뒤, 해당 bucket에 데이터를 저장한다.

---

그러나 서로 다른 key가 같은 bucket에 들어가는 해시 충돌이 발생할 수 있다.

Java의 HashMap은 기본적으로 충돌을 LinkedList로 처리한다.
다만, 한 bucket에 노드가 너무 많아지면 Red-Black Tree 구조로 바뀐다.

충돌 적음 → LinkedList
충돌 많음 → Red-Black Tree

또한 HashMap의 배열 크기는 고정되어 있지 않다.
일정 비율 이상 데이터가 차면 배열 크기를 늘리는 resize가 발생한다.

기본 load factor는 0.75이다.

resize가 발생하면 배열 크기가 달라지므로, 기존 key들의 index 계산 결과도 바뀔 수 있다.
따라서 기존 노드들을 새 배열에 다시 배치하는 rehash 과정이 필요하다.

🤔 HashMap의 성능을 좌우하는 것은?
hashCode()가 핵심이다.
hashCode()가 엉망이면 모든 key가 같은 bucket에 몰릴 수 있고, 이 경우 사실상 LinkedList처럼 동작하게 되어 성능이 떨어진다.

---

HashSet을 톺아보자

HashSet은 내부적으로 HashMap을 사용해 구현된다.

다만, 저장하려는 값을 HashMap의 key로 넣고, value에는 의미 없는 더미 값을 넣는다.

HashSet의 값 → HashMap의 key
더미 객체 → HashMap의 value

---

TreeMap을 톺아보자

HashMap은 정렬을 보장하지 않는다.

반면 TreeMap은 key를 기준으로 항상 정렬된 상태를 유지한다.

🤔 정렬을 보장하지 않는다는 뜻은?
예를 들어 c, a, b를 HashMap에 넣었다고 해서 순회 결과가 a, b, c라는 보장은 없다.
하지만 TreeMap은 key 기준 정렬을 유지하므로 a, b, c 순서를 보장한다.

---

TreeMap은 내부적으로 Red-Black Tree를 사용해 구현된다.

🤔 왜 Red-Black Tree일까?
일반적인 이진 탐색 트리, 즉 BST는 데이터가 1 → 2 → 3 → 4 → 5처럼 들어오면 한쪽으로 편향될 수 있다.
이 경우 트리라기보다 사실상 연결 리스트처럼 동작하게 되고, 탐색 성능이 O(n)까지 떨어질 수 있다.
그래서 TreeMap은 자가 균형 이진 탐색 트리인 Red-Black Tree를 사용한다.

---

TreeMap은 평균적인 조회 성능만 보면 HashMap보다 느리다.
하지만 key의 정렬이 필요하다면 TreeMap을 사용한다.

🤔 언제 사용하면 좋을까?
가장 작은 key가 필요할 때
가장 큰 key가 필요할 때
특정 범위의 key가 필요할 때
현재 key보다 큰 key가 필요할 때
현재 key보다 작은 key가 필요할 때

---

TreeSet을 톺아보자

TreeSet도 HashSet처럼 내부적으로 Map을 사용한다.

다만 TreeSet은 HashMap이 아니라 TreeMap을 사용한다.

저장하려는 값을 TreeMap의 key로 넣고, value에는 의미 없는 더미 값을 넣는다.

TreeSet의 값 → TreeMap의 key
더미 객체 → TreeMap의 value

---

Queue / Stack / Deque

PriorityQueue를 톺아보자

PriorityQueue는 이름에 Queue가 들어가지만, 일반적인 선입선출 큐라기보다는 Binary Heap 기반 자료구조이다.

내부적으로는 배열을 사용한다.

Object[] queue;

기본적으로 루트에 가장 작은 값이 위치한다.

따라서 최소값을 빠르게 꺼내야 할 때 유용하다.

---

ArrayDeque를 톺아보자

ArrayDeque는 head와 tail을 이용한 원형 배열 기반 Deque이다.

앞쪽과 뒤쪽 양방향에서 삽입과 삭제가 가능하다.

Java에서는 오래된 Stack 클래스 대신 ArrayDeque를 스택처럼 사용하는 경우가 많다.

---

Stack을 톺아보자

Stack은 내부적으로 Vector를 상속한다.

Vector는 동기화된 동적 배열이다.

하지만 요즘 Java에서는 Stack과 Vector를 잘 사용하지 않는 편이다.

🤔 왜 Vector를 잘 사용하지 않을까?
단일 스레드 환경에서는 동기화가 불필요한 비용이 된다.
멀티 스레드 환경에서는 Vector보다 더 세분화되고 목적에 맞는 동시성 컬렉션들이 존재한다.
따라서 요즘은 Stack 대신 ArrayDeque를 사용하는 것이 더 일반적으로 권장된다.