Java Collection Framework 정리

Collection Framework는 데이터를 효율적으로 저장하고 관리하기 위한 자바의 핵심 라이브러리다. 각 구현체는 내부 자료구조와 동작 방식에 따라 성능 특성이 다르므로, 상황에 맞는 컬렉션을 선택하는 것이 중요하다.

---

List

순서가 있고 중복을 허용하는 컬렉션이다.

ArrayList

자료구조

• 내부적으로 Object 배열(Object[] elementData)을 사용한다.
• 데이터는 연속된 메모리 공간에 순차적으로 저장된다.
• 인덱스를 통한 직접 접근이 가능한 Random Access 구조다.

조회

public E get(int index) {
    return elementData[index]; // O(1)
}

배열의 인덱스로 직접 접근하므로 조회 시간은 O(1)이다.

중간 삽입

public void add(int index, E element) {
    System.arraycopy(elementData, index, 
                     elementData, index + 1, 
                     size - index);
    elementData[index] = element;
}

• 삽입 위치 이후의 모든 요소를 한 칸씩 뒤로 이동시킨다.
• System.arraycopy()를 사용하여 네이티브 레벨에서 메모리를 복사한다.
• 시간 복잡도는 O(n)이다.

용량 확장

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5배 증가
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• 기본 초기 용량은 10이다.
• 용량이 부족하면 기존 크기의 1.5배로 증가한다.
• 새로운 배열을 생성하고 기존 데이터를 복사한다.
• 확장 과정에서 O(n)의 시간이 소요된다.

---

LinkedList

자료구조

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

• 이중 연결 리스트(Doubly Linked List) 구조다.
• 각 노드는 데이터와 이전/다음 노드에 대한 참조를 가진다.
• 첫 노드와 마지막 노드에 대한 참조를 유지한다.

조회

public E get(int index) {
    Node<E> x = first;
    for (int i = 0; i < index; i++)
        x = x.next;
    return x.item;
}

• 인덱스에 해당하는 노드까지 순차적으로 탐색한다.
• 앞/뒤 중 목표가 가까운 쪽에서 탐색을 시작한다.
• 시간 복잡도는 O(n)이다.

중간 삽입

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
}

• 새 노드를 생성하고 앞뒤 노드의 참조만 변경한다.
• 데이터 이동이 없어 삽입 자체는 O(1)이다.
• 하지만 삽입 위치를 찾는데 O(n)이 소요된다.

용량 확장

• 노드 단위로 동적 할당되므로 별도의 용량 확장 로직이 없다.
• 메모리가 허용하는 한 계속 추가할 수 있다.
• 각 노드마다 추가 메모리(prev, next 참조)가 필요하다.

---

Set

중복을 허용하지 않는 컬렉션이다.

HashSet

자료구조

private transient HashMap<E,Object> map;

• 내부적으로 HashMap을 사용한다.
• 실제 데이터는 HashMap의 Key로 저장되고, Value에는 더미 Object가 들어간다.
• 해시 테이블 기반으로 동작한다.

조회

public boolean contains(Object o) {
    return map.containsKey(o);
}

• 객체의 hashCode()로 버킷을 찾는다.
• 해당 버킷에서 equals()로 동일성을 확인한다.
• 평균 O(1), 최악의 경우 O(n)이다.

중간 삽입

• Set은 순서 개념이 없으므로 중간 삽입이 의미가 없다.

용량 확장

void resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = oldTab.length;
    int newCap = oldCap << 1; // 2배 증가
    // rehashing...
}

• 기본 초기 용량은 16이고, Load Factor는 0.75다.
• 저장된 요소 수가 (용량 * Load Factor)를 초과하면 2배로 확장한다.
• 모든 요소를 새로운 버킷에 재배치(rehashing)한다.

---

LinkedHashSet

자료구조

private transient LinkedHashMap<E,Object> map;

• 내부적으로 LinkedHashMap을 사용한다.
• 해시 테이블과 이중 연결 리스트를 결합한 구조다.
• 각 엔트리는 해시 버킷과 동시에 연결 리스트로도 연결된다.

조회

• HashSet과 동일하게 해시를 통해 O(1)에 조회한다.
• 추가적으로 삽입 순서를 유지하는 연결 리스트 정보를 가진다.

중간 삽입

• 삽입 순서를 기억하기 위해 before/after 포인터를 추가로 관리한다.
• 해시 버킷에 저장하면서 동시에 연결 리스트에도 연결한다.
• 순서 유지를 위한 추가 오버헤드가 발생한다.

용량 확장

• HashSet과 동일한 방식으로 확장된다.
• 리사이징 시 연결 리스트 순서는 유지된다.

---

TreeSet

자료구조

private transient NavigableMap<E,Object> m;

• 내부적으로 TreeMap(Red-Black Tree)을 사용한다.
• 이진 탐색 트리의 일종으로 자가 균형을 유지한다.
• 모든 요소는 정렬된 상태로 유지된다.

조회

public boolean contains(Object o) {
    return m.containsKey(o);
}

• 이진 탐색을 통해 요소를 찾는다.
• Comparable 또는 Comparator를 통해 비교하며 탐색한다.
• 시간 복잡도는 O(log n)이다.

중간 삽입

• 새 노드를 삽입한 후 Red-Black Tree 규칙을 만족하도록 재조정한다.
• 회전(rotation)과 색상 변경을 통해 균형을 맞춘다.
• 시간 복잡도는 O(log n)이다.

용량 확장

• 트리 구조는 노드 단위로 동적 할당되므로 별도의 용량 확장이 없다.
• 삽입 시 자동으로 트리가 성장한다.
• 자가 균형 알고리즘으로 트리 높이를 log n으로 유지한다.

---

Map

Key-Value 쌍으로 데이터를 저장하는 컬렉션이다.

HashMap

자료구조

transient Node<K,V>[] table;

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

• 해시 테이블 기반 구조다.
• 배열과 연결 리스트(또는 트리)의 조합이다.
• Java 8부터 한 버킷의 엔트리가 8개를 넘으면 트리로 변환된다.

조회

public V get(Object key) {
    Node<K,V> e = getNode(hash(key), key);
    return e == null ? null : e.value;
}

• Key의 hashCode를 계산하고 버킷 인덱스를 구한다.
• 해당 버킷에서 equals로 Key를 비교하여 값을 찾는다.
• O(1)이다. (8개 이상)

중간 삽입

• Map은 Key 기반이므로 중간 삽입 개념이 없다.
• put() 시 해시값으로 버킷을 찾아 저장한다.
• 충돌 시 체이닝(리스트 또는 트리)으로 연결한다.
• 동일 Key가 있으면 Value를 교체한다.

용량 확장

final Node<K,V>[] resize() {
    int oldCap = table.length;
    int newCap = oldCap << 1;
    // ... rehashing
}

• 기본 초기 용량 16, Load Factor 0.75다.
• threshold * Load Factor를 초과하면 2배로 확장한다.
• 모든 엔트리를 새 테이블에 재배치한다.

---

ConcurrentHashMap

자료구조

transient volatile Node<K,V>[] table;

static class Node<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

• HashMap과 유사하지만 동시성 제어를 위한 구조가 추가되었다.
• 세그먼트 단위 잠금 대신 버킷 단위로 CAS(Compare-And-Swap)와 synchronized를 사용한다.
• volatile 키워드로 가시성을 보장한다.

조회

public V get(Object key) {
    Node<K,V>[] tab = table;
    Node<K,V> e = tabAt(tab, (n - 1) & hash);
    // ... search
}

• 잠금 없이 조회가 가능하다(lock-free read).
• volatile 읽기를 통해 최신 값을 조회한다.
• 시간 복잡도는 HashMap과 동일하다.

중간 삽입

final V putVal(K key, V value, boolean onlyIfAbsent) {
    for (Node<K,V>[] tab = table;;) {
        if (tabAt(tab, i) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;
        } else {
            synchronized (f) {
                // ... insert
            }
        }
    }
}

• 빈 버킷에는 CAS 연산으로 삽입한다.
• 충돌 시 해당 버킷에만 synchronized를 걸어 삽입한다.
• 전체 맵이 아닌 버킷 단위로 잠금을 사용하여 동시성을 높인다.

용량 확장

• 여러 스레드가 협력하여 점진적으로 리사이징한다.
• 한 번에 전체를 리사이징하지 않고 스트라이드 단위로 나눠서 처리한다.
• 리사이징 중에도 다른 스레드의 읽기/쓰기가 가능하다.

---

LinkedHashMap

자료구조

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
}

• HashMap을 상속하고 이중 연결 리스트를 추가한 구조다.
• 각 엔트리는 해시 테이블과 연결 리스트 양쪽에 속한다.
• 삽입 순서 또는 접근 순서를 유지할 수 있다.

조회

• HashMap과 동일하게 해시를 통해 O(1)에 조회한다.
• accessOrder가 true면 조회 시 해당 엔트리를 리스트 끝으로 이동시킨다.

중간 삽입

• HashMap의 삽입 로직에 추가로 연결 리스트 연결이 이루어진다.
• before/after 포인터를 업데이트하여 순서를 유지한다.
• LRU 캐시 구현 시 유용하다.

용량 확장

• HashMap과 동일한 방식으로 확장된다.
• 리사이징 후에도 연결 리스트의 순서는 유지된다.

---

TreeMap

자료구조

private transient Entry<K,V> root;

static final class Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

• Red-Black Tree로 구현된다.
• 각 노드는 부모, 왼쪽 자식, 오른쪽 자식을 참조한다.
• Key의 자연 순서 또는 Comparator에 따라 정렬된다.

조회

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

• 이진 탐색 트리 탐색을 수행한다.
• 시간 복잡도는 O(log n)이다.

중간 삽입

• 이진 탐색 트리 규칙에 따라 적절한 위치에 삽입한다.
• 삽입 후 Red-Black Tree 속성을 유지하기 위해 회전과 색상 조정을 수행한다.
• 시간 복잡도는 O(log n)이다.

용량 확장

• 트리는 동적으로 성장하므로 별도의 용량 확장이 없다.
• 자가 균형 트리로 높이를 log n으로 유지한다.

---

정리

컬렉션	조회	삽입/삭제(끝)	삽입/삭제(중간)	정렬	동기화
ArrayList	O(1)	O(1)*	O(n)	X	X
LinkedList	O(n)	O(1)	O(n)	X	X
HashSet	O(1)	O(1)	-	X	X
LinkedHashSet	O(1)	O(1)	-	순서유지	X
TreeSet	O(log n)	O(log n)	-	O	X
HashMap	O(1)	O(1)	-	X	X
ConcurrentHashMap	O(1)	O(1)	-	X	O
LinkedHashMap	O(1)	O(1)	-	순서유지	X
TreeMap	O(log n)	O(log n)	-	O	X

*amortized(분할 상환) 시간 복잡도

컬렉션을 선택할 때는 데이터의 특성과 필요한 연산을 고려해야 한다. 조회가 빈번하면 ArrayList나 HashMap을, 삽입/삭제가 많으면 LinkedList를, 정렬이 필요하면 TreeSet이나 TreeMap을, 멀티스레드 환경이면 ConcurrentHashMap을 사용하는 것이 적절하다.

---

Colleciton Util