컬렉션과 자료구조

컬렉션 프레임워크

자바의 컬렉션은 크게 Collection 인터페이스를 상속받는 List, Set 계열과, 독립적인 구조를 가지는 Map 계열로 나뉩니다.

List 인터페이스 : 순서가 있고, 중복을 허용하는 선형 구조

가장 많이 사용되는 배열 형태의 자료구조입니다. 데이터를 넣은 순서가 보장됩니다.

ArrayList

내부적으로 일반 배열(Object[])을 사용하여 데이터를 순차적으로 저장합니다. 초기 용량을 넘어서면 새로운 더 큰 배열(기존의 1.5배)을 만들고 기존 데이터를 복사(Copy)하여 크기를 동적으로 늘립니다.

인덱스를 통한 데이터 조회는 $O(1)$의 속도로 극도로 빠릅니다. 하지만, 배열 중간에 데이터를 삽입하거나 삭제할 때는 뒤에 있는 데이터들을 모두 한 칸씩 밀거나 당겨야 하므로 $O(n)$의 시간이 걸립니다.

조회가 압도적으로 빠르지만, 잦은 크기 변경 시 배열 복사로 인한 메모리 및 CPU 오버헤드가 발생합니다.

LinkedList

데이터와 다음/이전 데이터의 메모리 주소(포인터)를 가진 ‘노드(Node)’들이 기차처럼 연결된 이중 연결 리스트(Doubly Linked List) 구조입니다.

리스트 양 끝에서의 데이터 삽입/삭제는 포인터만 바꿔주면 되므로 $O(1)$에 처리됩니다. 하지만 특정 인덱스를 조회하려면 첫 노드부터 순차적으로 탐색해야 하므로 $O(n)$이 소요됩니다.

이론상 중간 삽입/삭제가 빠르다고 하지만, 실제 현대 CPU 아키텍처에서는 메모리가 연속적으로 할당된 ArrayList가 CPU 캐시 히트율(Cache Hit Ratio) 이 훨씬 높기 때문에, 압도적인 데이터가 아닌 이상 실무에서는 거의 무조건 ArrayList를 우선적으로 사용합니다.

Set 인터페이스 : 순서가 없고, 중복을 불허하는 집합 구조

수학의 집합과 동일한 개념입니다. 데이터의 고유성을 보장하고 싶을 때 사용합니다.

HashSet

해시 함수(Hash Function)를 사용하여 객체의 고유한 정수값(hashCode())을 추출하고, 이를 인덱스로 삼아 데이터를 저장합니다. 내부적으로는 HashMap을 가져다 씁니다.

데이터의 삽입, 삭제, 조회가 평균적으로 $O(1)$이라는 속도를 자랑합니다.

메모리 소모가 크며, 데이터를 넣은 순서가 전혀 보장되지 않습니다.

TreeSet

이진 탐색 트리의 일종인 레드-블랙 트리(Red-Black Tree) 구조로 데이터를 저장합니다.

삽입/삭제/조회에 $O(\log n)$의 시간이 걸려 HashSet보다는 다소 느립니다.

대신 데이터가 항상 정렬된 상태(Sorted) 로 유지된다는 강력한 장점이 있습니다.

Map 인터페이스 : Key-Value 쌍으로 이루어진 사전(Dictionary) 구조

데이터를 식별할 수 있는 고유한 키(Key)와, 그 키에 매핑되는 값(Value)을 한 쌍으로 저장합니다.

HashMap

키 객체의 hashCode()를 기반으로 해시값을 계산하여 배열(버킷)의 특정 인덱스에 값을 저장합니다.

키를 통한 값 조회가 평균 $O(1)$로 매우 빠릅니다. 자바 서버 프로그래밍에서 데이터를 캐싱하거나 매핑할 때 가장 핵심적으로 쓰입니다.

TreeMap

TreeSet과 마찬가지로 레드-블랙 트리로 구현되어 있으며, ‘키(Key)’를 기준으로 데이터를 자동 정렬합니다.

HashMap의 해시 충돌(Hash Collision)과 Java 8의 최적화

해시 함수가 서로 다른 두 키에 대해 같은 해시값을 반환하는 것을 해시 충돌이라고 합니다. 자바는 이를 해결하기 위해 같은 버킷에 데이터가 충돌하면 연결 리스트(Linked List) 형태로 데이터를 이어 붙입니다(Separate Chaining).

하지만 데이터가 너무 많이 충돌하여 리스트가 길어지면 조회 성능이 $O(n)$으로 떨어집니다. 이를 막기 위해 Java 8부터는 하나의 버킷에 데이터가 8개 이상 쌓이면, 연결 리스트를 탐색 속도가 $O(\log n)$인 레드-블랙 트리(Treeify) 로 동적으로 변환하는 놀라운 최적화 기법이 적용되어 있습니다.

스레드 안전성(Thread-Safety)과 Concurrent 컬렉션

우리가 배운 ArrayList, HashMap 등은 멀티스레드 환경에서 여러 스레드가 동시에 수정하려 하면 데이터가 깨지는 치명적인 버그(Race Condition)가 발생합니다.

과거에는 메서드 전체에 synchronized 락(Lock)을 거는 Vector나 Hashtable을 썼지만, 성능이 너무 느려 현재는 도태되었습니다.

현대 자바에서는 동시성과 성능을 모두 잡은 ConcurrentHashMap 이나 CopyOnWriteArrayList 같은 java.util.concurrent 패키지의 컬렉션들을 사용하는 것이 실무 표준(Best Practice)입니다.