자바 컬렉션 프레임워크 – 자바에서 데이터를 다루는 방법

컬렉션의 구조 및 계층도

                     Iterable
                        │
                  Collection
                        │
       ┌───────────────┬─────────────────────┐
       │               │                     │
      List            Set                 Queue
       │               │                     │
 ┌─────┴─────┐     ┌────┴────┐        ┌──────┴───────┐
 │           │     │         │        │              │
ArrayList LinkedList HashSet  SortedSet PriorityQueue Deque
 │                             │                      │
Vector                    ┌────┴────┐             ArrayDeque
                          │         │
                     LinkedHashSet TreeSet

                            Map
                             │
               ┌─────────────┴─────────────┐
               │                           │
          HashMap                     SortedMap
               │                           │
     ┌─────────┴────────┐            ┌─────┴─────┐
     │                  │            │           │
 LinkedHashMap     WeakHashMap   TreeMap      NavigableMap

자바 컬렉션은 크게 Collection 인터페이스와 Map 인터페이스로 나뉘고, 각 인터페이스 아래에 데이터의 특성에 따라 다양한 하위 인터페이스와 구현 클래스들이 위치한다.

 

• Iterable 인터페이스: Collection의 상위 인터페이스로, for-each 문을 사용할 수 있게 한다.
• Collection 인터페이스: 자바 컬렉션의 기본 인터페이스로, List, Set, Queue 같은 하위 인터페이스를 포함한다. 

주요 Collection 하위 인터페이스와 구현 클래스

• List: 요소의 순서가 있으며, 중복 요소를 허용한다.
  • ArrayList: 배열 기반의 리스트로, 요소 접근 속도가 빠르다.
  • LinkedList: 노드 연결 방식으로, 데이터 삽입/삭제가 빠르다.
  • Vector: 동기화된 리스트, ArrayList와 유사하지만 성능이 낮다.
• Set: 중복을 허용하지 않으며, 요소의 순서를 보장하지 않습니다.
  • HashSet: 요소의 순서를 보장하지 않으며, 빠른 검색 성능을 가진다.
  • LinkedHashSet: 추가된 순서를 유지하며, HashSet보다 메모리 소모가 크다.
  • TreeSet: 요소를 항상 정렬된 상태로 유지한다.
• Queue: FIFO(First-In-First-Out) 방식으로 요소를 처리하는 인터페이스이다.
  • PriorityQueue: 우선순위에 따라 요소를 정렬하여 처리한다.
  • Deque: 양방향에서 삽입/삭제가 가능한 큐로, ArrayDeque가 대표적이다.

Map 인터페이스와 구현 클래스

• Map: 키-값 쌍으로 데이터를 관리하며, 중복 키를 허용하지 않는다.
  • HashMap: 순서를 보장하지 않으며, 빠른 접근 속도를 가진다.
  • LinkedHashMap: 삽입 순서를 유지하며, 메모리 소모가 크다.
  • TreeMap: 키를 항상 정렬된 상태로 유지한다.
  • WeakHashMap: 키가 가비지 컬렉션의 대상이 될 수 있는 Map이다.

 

---

컬렉션별 특성과 사용 사례

ArrayList vs LinkedList: 어떤 것이 더 좋을까?

• ArrayList: 크기가 동적으로 조정되는 배열이다. 인덱스를 통한 요소 접근이 빠르지만, 요소의 추가/삭제가 빈번히 일어나는 경우에는 성능이 저하될 수 있다.
• LinkedList: 각 요소가 이전 요소와 다음 요소의 링크를 포함하는 구조이다. 중간에 데이터를 추가하거나 삭제하는 것이 빠르지만, 인덱스를 통해 접근할 때는 시간이 더 걸린다.

언제 무엇을 사용하면 좋을까?

• 데이터의 조회가 빈번하다면 ArrayList가 유리.
• 데이터의 추가/삭제가 빈번하다면 LinkedList가 유리.

---

HashSet과 TreeSet: 중복 없는 데이터가 필요할 때

• HashSet: 순서가 중요하지 않으며, 빠른 검색과 삽입이 필요한 경우에 사용된다.
• TreeSet: 데이터가 정렬된 상태로 유지되어야 할 때 사용됩니다. 삽입된 순서와 관계없이 항상 정렬된 상태로 유지한다.

언제 무엇을 사용하면 좋을까?

• 중복 없는 데이터가 필요하고, 정렬이 중요하지 않다면 HashSet이 더 빠르고 효율적
• 항상 정렬된 상태로 데이터를 관리하고 싶다면 TreeSet이 적합

---

HashMap과 TreeMap: 키-값 쌍 데이터를 관리하는 방법

• HashMap: 순서에 관계없이 빠르게 데이터에 접근할 수 있다. 해시 테이블 구조를 사용해, 키를 해시화하여 빠르게 저장하고 찾을 수 있다.
• TreeMap: 키를 기준으로 항상 정렬된 상태로 데이터를 관리한다. HashMap보다 삽입, 삭제, 검색 속도가 느리지만 정렬된 키를 유지할 수 있다.

언제 무엇을 사용하면 좋을까?

• 데이터의 순서가 중요하지 않고, 빠른 검색이 필요하다면 HashMap이 적합
• 항상 키를 정렬된 상태로 유지하고 싶다면 TreeMap을 사용

 

---

컬렉션과 관련된 주요 질문

ArrayList vs LinkedList: 어떤 상황에서 어떤 것을 사용하는 것이 유리한가?

ArrayList는 내부적으로 동적 배열을 사용합니다. 이는 get(index)와 같이 인덱스를 통해 특정 위치에 빠르게 접근할 수 있음을 의미합니다. 예를 들어, 인덱스 1000번에 저장된 데이터를 조회한다고 할 때, ArrayList는 한 번에 해당 위치로 이동해서 값을 읽어올 수 있습니다. 하지만 데이터 추가/삭제가 빈번히 일어나는 경우에는 주의가 필요합니다. 배열 크기를 초과하는 데이터가 추가되면 새로운 배열을 만들어 데이터를 복사하는 재할당 과정이 필요하기 때문에 성능이 저하될 수 있습니다.

LinkedList는 노드 기반의 연결 리스트입니다. 각 요소(노드)는 다음과 이전 노드를 가리키고 있습니다. 이러한 구조로 인해 리스트의 중간이나 앞에 데이터를 추가하거나 삭제하는 속도가 빠릅니다. 새로운 요소를 삽입할 때 다른 요소들을 이동시키지 않아도 되고, 노드만 연결하면 되기 때문입니다.

ArrayList는 동적 배열을 사용하여 인텍스를 통해 특정 위치에 O(1)의 시간복잡도로 빠르게 접근할 수 있습니다. ArrayList는 요소 추가와 삭제 시 배열의 크기를 조정해야 하므로, 빈번한 요소 추가와 삭제가 발생하는 경우 성능이 저하될 수 있습니다. 그래서 조회가 빈번한 상황에서 성능이 좋습니다.
LinkedList 노드 기반의 연결 리스트로 각 노드는 다음과 이전 노드를 가리킵니다. 이러한 구조 때문에 데이터를 추가하거나 삭제가 O(1)의 시간복잡도로 빠르게 이루어질 수 있습니다. 반면, 인덱스로 접근 시 처음부터 순차적으로 탐색해야해서 O(n)의 시간 복잡도를 가집니다. 그래서 삽입/삭제가 빈번한 상황에서 효율적입니다.

---

HashMap의 내부 동작 원리 (해싱, 버킷, 충돌 해결 방식 등)

HashMap은 키-값 쌍 데이터를 빠르게 저장하고 검색할 수 있는 자료구조입니다. 내부적으로 해시 테이블을 사용해 데이터를 저장하며, key.hashCode()를 이용해 데이터의 위치를 빠르게 찾아갈 수 있습니다.

1. 해싱과 버킷

HashMap에 데이터를 저장할 때, 키의 hashCode 값을 계산하여 해시 테이블의 특정 위치(버킷)에 저장합니다. 예를 들어 key="airplane"일 때, apple.hashCode()로 해시 값을 계산하고 이 값에 따라 저장 위치를 결정합니다. 이러한 방식 덕분에 단순히 키를 가지고 데이터에 바로 접근할 수 있습니다.

하지만 서로 다른 키가 같은 해시 값을 가질 때는 문제가 생깁니다. 예를 들어, key="airplane"과 key="boat"의 해시 값이 같을 경우 충돌이 발생하죠.

2. 충돌 해결 방식: 체이닝과 트리 구조

충돌이 발생할 때, HashMap은 체이닝 방식을 사용해 해당 버킷에 연결 리스트로 데이터를 추가합니다. 이로 인해 충돌이 발생하더라도 데이터를 계속 저장할 수 있지만, 같은 위치에 너무 많은 데이터가 모이면 성능이 저하됩니다.

자바 8에서는 이 문제를 해결하기 위해 충돌이 많이 발생하는 경우 연결 리스트를 트리 구조로 변환하는 기능이 추가되었습니다. 연결 리스트의 노드 수가 일정 수준 이상이 되면 이진 트리로 전환하여, 데이터 검색 시간을 O(log N)로 줄일 수 있게 했습니다. 이렇게 하면 많은 충돌이 발생해도 검색 성능이 크게 저하되지 않도록 보장할 수 있습니다.

HashMap은 키-값 쌍 데이터를 해싱을 통해 빠르게 저장하고 단순히 키를 통해 데이터를 바로 검색할 수 있습니다.
충돌 발생 시에는 체이닝 방식으로 연결 리스트를 사용해 충돌을 해결합니다.
자바 8부터는 충돌이 많이 발생할 경우 연결 리스트 대신 트리 형태로 변환하여 성능을 개선합니다.