Collection

Collection이란?

Collection은 Java에서 자료 구조를 다루기 위해 표준화된 인터페이스와 클래스를 제공하는 라이브러리입니다. 주요 인터페이스는 List, Set, Map으로 나뉘며 서로 다른 특징과 내부 구현 방식을 가집니다.

다음 사진은 Collection 라이브러리의 계층 구조입니다.

List

List 인터페이스의 구현체로 ArrayList와 LinkedList가 존재합니다.

ArrayList

ArrayList는 내부적으로 배열을 사용하여 요소를 저장하기 때문에, 인덱스를 기반으로 빠른 조회가 가능합니다. 하지만, 요소 추가/삭제 시 크기 조정이 필요해 예상치 못한 성능 저하를 유발할 수 있습니다. 기본적으로 10개의 크기를 가지는 배열을 생성하며, 크기가 초과될 경우 1.5배씩 증가합니다.

LinkedList

LinkedList는 내부적으로 이중 연결 리스트를 사용하며 데이터 추가 및 삭제는 O(1)의 성능으로 우수하지만, 조회 성능은 O(n)으로 느립니다. 추가로, head와 tail을 이용하여 양방향 탐색이 가능합니다.

Set

Set 인터페이스의 구현체로 HashSet, TreeSet, LinkedHashSet이 존재합니다.

HashSet

HashSet은 내부적으로 HashMap을 사용하며, Key는 Set의 요소로 저장하고, Value는 dummy 값을 저장합니다. 또한, hachCode()를 기반으로 요소를 저장하여 검색은 O(1)의 성능으로 우수하며, 순서는 보장하지 않습니다.

TreeSet

TreeSet은 내부적으로 Red-Black Tree를 사용하며 요소가 정렬된 상태를 유지하고, 검색/추가/삭제 성능은 모두 O(log n)입니다.

LinkedHashSet

LinkedHashSet은 HashSet과 유사하지만 LinkedList를 사용하여 요소의 삽입 순서를 유지하는 특징을 가지고 있습니다.

Map

Map은 구조 상의 이유로 Collection 인터페이스를 상속받지 않습니다.

Map 인터페이스의 구현체로 HashMap, TreeMap, LinkedHashMap이 존재합니다.

HashMap

HashMap은 Key-Value 쌍을 저장하는 구조로 내부적으로 Array와 Linked List(or Tree)를 사용하며 hashCode()와 equals()를 기반으로 Key를 저장합니다. 만약, 해시 충돌이 발생할 경우Linked List로 저장합니다. Java 8 부터는 충돌이 많이 발생할 경우 Red-Black Tree로 변환하여 탐색 성능을 O(log n)으로 개선합니다.

TreeMap

TreeMap은 내부적으로 Red-Black Tree를 사용하며 Key를 정렬된 상태로 유지합니다. 검색/추가/삭제 성능이 O(log n)으로 일정하지만, HashMap보다 속도는 느립니다.

LinkedHashMap

LinkedHashMap은 HashMap과 유사하지만 LinkedList를 사용하여 요소의 삽입 순서를 유지하고 있습니다.

정리

List, Set, Map을 정리하면 다음과 같습니다.

그럼, 언제 무엇을 사용하면 좋을까요?

• List -> 순서 중요, 중복 허용
• Set -> 중복 불가, 순서 필요 없음
• Map -> Key-Value 형태의 데이터 저장이 필요할 때
  • Key 정렬 여부와 순서 유지에 따라 구현체 사용
    • 정렬 필요 -> TreeMap
    • 순서 유지 -> LinkedHashMap

예상 질문

Collection 라이브러리란?

Collection은 Java에서 자료 구조를 다루기 위한 표준 인터페이스와 이에 대한 구현체를 제공하는 라이브러리입니다.

List, Set, Map의 차이는 무엇인가요?

가장 큰 차이는 순서 보장과 중복 허용에 있습니다. List의 경우 둘 다 가능하고, Set의 경우 둘 다 불가능, Map의 경우 Value에 대해서만 중복이 허용되고 나머지는 모두 불가능합니다.

List의 구현체는 뭐가 있고, 어떻게 구현되어 있나요?

주요 구현체로는 ArrayList, LinkedList가 있습니다. ArrayList의 경우 Array로 구현되어 있고, LinkedList는 Double Linked List르 구현되어 있습니다.

Set의 구현체는 뭐가 있고, 어떻게 구현되어 있나요?

주요 구현체로는 HashSet, TreeSet, LinkedHashSet이 있습니다. Set의 경우 기본적으로 HashMap으로 구현되어 있습니다. Treeset의 경우 Red-Black Tree를 활용하여 순서를 정렬된 상태를 유지하는 특징이 있고, LinkedHashSet은 LinkedList를 사용하여 요소의 삽입 순서를 유지하는 특징을 가지고 있습니다.

Map의 구현체는 뭐가 있고, 어떻게 구현되어 있나요?

주요 구현체로는 HashMap, TreeMap, LinkedHashMap이 있습니다. Map의 경우 기본적으로 Array와 LinkedList로 구현되어 있습니다. 이때, Java 8 이상부터 충돌이 잦을 경우 성능 보완을 위해 LinkedList를 Red-Black Tree로 자동 변환이 발생합니다. 그 외 구현체인 TreeMap의 경우 Red-Black Tree를 활용하여 정렬 상태를 유지, LinkedHashMap의 경우 LinkedList를 활용해 삽입 순서를 유지하는 특징을 가집니다.

추가 학습이 필요한 내용

아래는 위 개념을 공부하면서 추가 학습이 필요할 것 같은 내용들입니다. 이 내용들은 차차 정리하여 링크를 달도록 하겠습니다.

ConcurrentHashMap