Collection Framework 핵심 요소

1. 개요

자바의 Collection Framework는 다수의 객체(데이터)를 저장, 관리(추가, 삭제, 검색 등)하기 위한 표준화된 클래스 및 인터페이스의 집합입니다. java.util 패키지에 포함되어 있으며, 데이터 구조(Data Structure)와 알고리즘을 효율적으로 구현할 수 있도록 다양한 형태의 컬렉션 클래스를 제공합니다.

2. 주요 인터페이스 구조

Collection Framework는 크게 세 가지 핵심 인터페이스(List, Set, Map)로 구성됩니다. List와 Set은 공통된 조상인 Collection 인터페이스를 상속받지만, Map은 키(Key)와 값(Value)의 쌍으로 데이터를 다루기 때문에 별도의 구조를 가집니다.

---

3. List 인터페이스

• 순서 유지 (Ordered): 데이터를 입력한 순서대로 저장합니다.
• 중복 허용 (Duplicates): 동일한 데이터의 중복 저장을 허용합니다.
• 인덱스(Index)를 사용하여 요소에 접근할 수 있습니다.

주요 구현 클래스

1. ArrayList

   • 특징: 내부적으로 동적 배열(Dynamic Array)을 사용하여 데이터를 순차적으로 저장합니다.
   • 장점: 인덱스를 통한 데이터 검색과 조회가 매우 빠릅니다. (시간 복잡도: O(1))
   • 단점: 중간에 데이터를 삽입하거나 삭제할 때, 이후의 모든 요소를 이동시켜야 하므로 성능이 저하됩니다. (시간 복잡도: O(N))
   • 동기화: 기본적으로 동기화(Thread-safe)되지 않습니다. 동기화가 필요하다면 Collections.synchronizedList() 또는 CopyOnWriteArrayList를 사용합니다.

2. LinkedList

   • 특징: 내부적으로 양방향 연결 리스트(Doubly Linked List) 구조를 사용하여 데이터를 노드(Node) 형태로 연결합니다.
   • 장점: 노드의 포인터만 변경하면 되므로 데이터 삽입 및 삭제가 매우 빠릅니다. (시간 복잡도: O(1), 단 탐색 시간은 포함하지 않음)
   • 단점: 인덱스가 없으므로 특정 위치의 데이터를 검색할 때 처음부터 순차적으로 탐색해야 하여 속도가 느립니다. (시간 복잡도: O(N))

3. Vector / Stack

   • Vector는 ArrayList와 유사하지만 모든 메서드가 동기화(Thread-safe) 되어 있어 멀티스레드 환경에서 안전하나 성능이 떨어집니다. 현재는 하위 호환성을 위해 남겨두었으며 잘 사용하지 않습니다.
   • Stack은 LIFO(Last-In-First-Out) 구조를 구현한 클래스로 Vector를 상속받습니다. 대체제로 ArrayDeque를 권장합니다.

---

4. Set 인터페이스

• 순서 없음 (Unordered): 저장되는 데이터의 순서를 보장하지 않습니다.
• 중복 불가 (Unique): 동일한 데이터의 중복 저장을 허용하지 않습니다. (내부적으로 equals()와 hashCode()를 통해 중복을 확인합니다)

주요 구현 클래스

1. HashSet

   • 특징: 내부적으로 HashMap을 사용하여 데이터를 저장하는 가장 일반적인 Set 구현체입니다. 해시 테이블(Hash Table)을 기반으로 동작합니다.
   • 성능: 추가, 삭제, 검색 성능이 가장 빠릅니다. (평균 시간 복잡도: O(1))
   • 순서: 데이터 입력 순서를 전혀 유지하지 않습니다.

2. TreeSet

   • 특징: 이진 탐색 트리(Red-Black Tree) 구조를 기반으로 데이터를 저장합니다.
   • 정렬 (Sorted): 저장과 동시에 오름차순으로 자동 정렬됩니다. 사용자 정의 정렬이 필요하면 Comparable이나 Comparator를 구현해야 합니다.
   • 성능: 데이터 추가/삭제 시 트리를 재구성해야 하므로 HashSet보다 느립니다. (시간 복잡도: O(log N))

3. LinkedHashSet

   • 특징: 해시 테이블과 연결 리스트를 결합한 구조입니다. HashSet의 특성을 가지면서도 데이터 입력 순서를 유지합니다.

---

5. Map 인터페이스

• 키-값 쌍 (Key-Value Pair): 데이터를 키(Key)와 값(Value)의 쌍(Entry)으로 저장합니다.
• 키 중복 불가, 값 중복 허용: 키는 고유해야 하므로 중복될 수 없으나, 값은 중복될 수 있습니다. (기존 키와 동일한 키로 값을 저장하면 기존 값을 덮어씁니다)

주요 구현 클래스

1. HashMap

   • 특징: 해시 테이블(Hash Table)을 사용하여 키와 값을 매핑합니다. 키의 해시(Hash) 값을 기반으로 버킷(Bucket) 인덱스를 계산하여 데이터를 저장합니다.
   • 성능: 추가, 삭제, 검색 성능이 뛰어납니다. (평균 시간 복잡도: O(1))
   • 해시 충돌 (Hash Collision): 서로 다른 키가 동일한 해시 값을 가질 경우(충돌), Java 8 이후로는 연결 리스트(Linked List)로 연결하다가 임계치(8개 이상)를 넘으면 Red-Black Tree로 구조를 변환하여 성능(O(log N))을 보장합니다.

2. TreeMap

   • 특징: 이진 탐색 트리(Red-Black Tree) 구조를 기반으로 데이터를 저장합니다.
   • 정렬 (Sorted): 키(Key)를 기준으로 자동 정렬됩니다. TreeSet과 동일한 성능 특성을 가집니다. (O(log N))

3. Hashtable

   • HashMap과 유사하지만 모든 메서드가 동기화(Thread-safe) 되어 있습니다. 성능 문제로 최신 개발에서는 권장하지 않습니다.

4. ConcurrentHashMap

   • 특징: HashMap의 멀티스레드 동기화 문제를 해결한 클래스입니다.
   • 전체 맵에 락(Lock)을 걸지 않고, 분할 락(Segment Lock, Java 8 이후로는 Node 단위의 Lock)을 사용하여 동기화 성능을 극대화했습니다. 멀티스레드 환경에서 안전하고 빠르게 사용할 수 있습니다.