[자바/코틀린] 컬렉션 프레임워크

자바의 컬렉션 프레임워크

컬렉션 프레임워크(collections framework)는 컬렉션(collection) 자료 구조(data structure)를 구현한 자바의 공식 라이브러리이다. 컬렉션(collection)이란 데이터(요소)를 그룹화한 것으로 추상 자료형(ADT, abstract data type)을 의미한다. 자바의 컬렉션 프레임워크는 컬렉션과 맵(map)에 대해 자료 구조와 알고리즘의 구체적인 구현과 일관성 있는 API를 제공하여 프로그래밍 시 자료 구조를 손쉽게 사용할 수 있도록 한다. 맵은 키와 키에 대한 값을 매핑하는(연관짓는) 자료 구조로서 컬렉션 중 연관 컬렉션(associative collection)에 속하며 선형 컬렉션(linear collection)과는 특성 및 구조가 다르므로 별도의 개념으로 구분하기도 한다.

자바의 컬렉션 프레임워크에서 정의하는 컬렉션의 종류는 다음과 같다. 다음 타입은 모두 인터페이스이며 Collection 인터페이스를 확장한다.

• List (리스트): 입력 순서대로 데이터를 저장하는 자료 구조이다. 데이터의 중복을 허용한다.
• Set (셋): 리스트와 유사하지만 중복을 허용하지 않는 자료 구조이다.
• Queue (큐): 선입선출(first-in-first-out, FIFO)의 특성을 갖는 큐(queue) 자료 구조이다.
  • Deque (디큐): 양쪽에서 삽입과 삭제를 수행할 수 있는 자료 구조이다. 후입선출(last-in-first-out, LIFO)의 특성을 갖는 스택(stack)과, 큐의 특성을 모두 갖고 있다. Queue 인터페이스를 확장한다.

자바의 컬렉션 프레임워크에서 정의하는 맵은 다음과 같다. 인터페이스로 정의되어 있으며 Collection 인터페이스를 확장하지는 않는다.

• Map (맵): 키와 키에 대한 값을 쌍(pair)으로 저장하는 자료 구조이다. 컬렉션과 동작 방식이 다르므로 인터페이스 메서드 정의도 다르다.

List 인터페이스의 구현체는 다음과 같다.

• ArrayList (배열 리스트): 순서가 있는 리스트를 동적 배열(dynamic array)로 구현한 리스트 구현체이다. 동적 배열이란 배열의 크기를 자동으로 조절하는 배열 자료 구조를 말한다. java.util.Arrays의 중첩 클래스인 ArrayList 구현체는 불변이며, 이름이 동일한 java.util.ArrayList 구현체는 가변이다. 배열 리스트는 데이터를 메모리에 물리적인 순서대로 저장하므로
• LinkedList (연결 리스트): 리스트를 연결 리스트(linked list)로 구현한 구현체이다. 연결 리스트는 배열 리스트와 달리 데이터를 메모리에 물리적인 순서대로 저장하지 않는다. LinkedList는 연결 리스트 중 이중 연결 리스트(doubly-linked list)를 구현하므로 데이터의 삽입 및 삭제가 양방향으로 가능하다. 마지막 데이터 삽입 연산은 객체 생성 시 메모리 사용 및 할당 오버헤드가 발생하므로 배열 리스트 보다 느릴 수 있으며 따라서 원시 타입의 데이터의 경우 연산 속도 차이가 증가하게 된다.

Set 인터페이스의 구현체는 다음과 같다

• HashSet (해시 셋): 입력 순서를 보장하지 않는 셋 구현체이다. 시간이 지나도 순서가 일정하게 유지된다는 보장을 하지 않으므로 반복 처리 시 동일한 순서로 처리되지 않을 수 있다. 내부적으로 HashMap 구현을 사용하므로 해시 함수를 사용하여 컬렉션 내에 데이터를 분산시킨다. 해시 함수(hash function)의 효율(해시 함수가 데이터를 버킷(bucket)에 얼마나 골고루 분산시키는지)에 따라 연산의 성능이 달라진다. 해시 함수가 여러 데이터를 하나의 키로 해싱하여 해시 충돌(hash collision)이 발생한다면 연산 성능이 저하된다.
  • LinkedHashSet (연결 해시 셋): HashSet을 확장하는 셋 구현체이다. 해시 테이블(hash table)과 연결 리스트를 사용하여 구현한 셋 구현체이며 해시 셋과 달리 순서가 보장된다. LinkedHashSet은 이중 연결 리스트를 구현하여 순서를 유지하며 데이터의 삽입 및 삭제가 양방향으로 가능하다. HashSet와 마찬가지로 해시 함수를 사용하여 컬렉션 내에 데이터를 분산시킨다. 연결 리스트를 유지하는데 추가 비용이 발생하므로 HashSet 보다 성능이 약간 낮을 수 있다.
• TreeSet (트리 셋): 키의 순서에 따라 정렬되는 맵 구현체인 TreeMap을 기반으로 한 셋 구현체이다. 자가 균형 이진 탐색 트리(self-balancing binary search tree)인 레드-블랙 트리(red-black tree)를 사용하여 구현하며 정렬 순서를 지정할 수 있다. 입력 순서를 보장하지는 않는다.

Queue 인터페이스의 구현체는 다음과 같다.

• LinkedList (연결 리스트): 디큐 구현체 중 하나이다. List 인터페이스 구현체인 LinkedList는 Deque 인터페이스의 구현체이기도 하다. 디큐 구현체로 사용하는 경우 양쪽에서 삽입과 삭제를 수행하는 기능이 주 목적이다.
• ArrayDeque (배열 디큐): 크기를 조정할 수 있는 배열 구현체로, 주로 스택과 큐로 사용되는 디큐 구현체 중 하나이다. 큐로 사용할 경우 삽입 연산은 LinkedList 보다 빠르다. 일반적으로 객체 생성 작업의 오버헤드로 인해 ArrayDeque의 연산 속도는 LinkedList 보다 빠르다.

Map 인터페이스 구현체는 다음과 같다.

• HashMap (해시 맵): 기본적인 맵 구현체이다. 입력 순서를 보장하지 않는다.
• LinkedHashMap (연결 해시 맵): 해시 테이블과 연결 리스트를 사용하여 구현한 맵 구현체이다. HashMap과 달리 입력 순서를 보장한다.
• TreeMap (트리 맵): 값에 따라 순서를 정렬하는 맵 구현체이다. 내부적으로 레드-블랙 트리를 사용하여 구현하며 정렬 순서를 지정할 수 있다.

자바 컬렉션 프레임워크 구현체 별 시간 복잡도 비교

• ArrayList (동적 배열)
  • 인덱싱 접근: O(1)
  • 탐색: O(N)
  • 삽입/삭제
    • 처음에 삽입/첫 데이터 삭제: O(N)
    • 중간에 삽입/중간 데이터 삭제: O(N)
    • 마지막에 삽입/마지막 데이터 삭제
      • 일반적인 경우: O(1) (분할 상환 분석)
      • 최악의 경우: O(N) (새로운 배열에 기존 데이터를 복사하는 작업이 필요한 경우)
• LinkedList (이중 연결 리스트)
  • 인덱싱 접근: O(N)
  • 탐색: O(N)
  • 삽입/삭제
    • 처음에 삽입/첫 노드 삭제: O(1)
    • 중간에 삽입/중간 노드 삭제: O(1)
    • 마지막에 삽입/마지막 노드 삭제: O(1) (마지막 노드에 대한 참조를 알고 있는 경우)
• HashSet
  • 탐색/삽입/삭제
    • 일반적인 경우: O(1)
    • 최악의 경우: O(N) (해시 함수가 모든 데이터를 하나의 키로 해싱하는 경우)
• LinkedHashSet
  • 탐색/삽입/삭제
    • 일반적인 경우: O(1)
    • 최악의 경우: O(N) (해시 함수가 모든 데이터를 하나의 키로 해싱하는 경우)
• TreeSet
  • 탐색/삽입/삭제
    • 일반적인 경우: O(log2N)
    • 최악의 경우: O(log2N)
• ArrayDeque
  • 삽입: O(1)
  • 추출: O(1)
• HashMap
  • 탐색/삽입/삭제
    • 일반적인 경우: O(1)
    • 최악의 경우: O(N) (해시 함수가 모든 데이터를 하나의 키로 해싱하는 경우)
• LinkedHashMap
  • 탐색/삽입/삭제
    • 일반적인 경우: O(1)
    • 최악의 경우: O(N) (해시 함수가 모든 데이터를 하나의 키로 해싱하는 경우)
• TreeMap
  • 탐색/삽입/삭제
    • 일반적인 경우: O(log2N)
    • 최악의 경우: O(log2N)

코틀린의 컬렉션과 맵 자료 구조

코틀린은 자바 언어와의 호환성을 위해 기본적으로 자바의 컬렉션 프레임워크가 제공하는 다양한 구현체들을 사용하며 일부 자료 구조에 대해서는 별도의 인터페이스 및 구현체를 제공한다. 코틀린은 함수형 프로그래밍에서 불변 객체 사용을 위해 여러 자료 구조에 대한 불변 객체 인터페이스를 제공하며 기본적으로 인터페이스는 불변 특성을 갖는다. 가변 객체를 사용하려면 별도의 구현체 사용이 필요하다.

리스트, 셋, 맵 구현체는 기본적으로 모두 불변이며 가변 객체가 필요한 경우 Mutable이라는 접두어가 붙은 구현체를 별도로 사용해야 한다. 다음은 코틀린이 제공하는 자료 구조 별 인터페이스와 대응하는 자바 구현체이다.

• 리스트
  • 불변: List (자바 클래스: java.util.Arrays$ArrayList)
  • 가변: MutableList (자바 클래스: java.util.ArrayList)
• 셋
  • 불변: Set (자바 클래스: java.util.LinkedHashSet)
  • 가변: MutableSet (자바 클래스: java.util.LinkedHashSet)
• 맵
  • 불변: Map (자바 클래스: java.util.LinkedHashMap)
  • 가변: MutableMap (자바 클래스: java.util.LinkedHashMap)

컬렉션 구현체는 자바에 정의된 것을 사용하지만 컬렉션 타입과 관련된 다양한 인터페이스가 별도로 정의되어 있다.

• 불변 컬렉션
  • Collection
    • List
    • Set
  • Map
• 가변 컬렉션
  • MutableCollection
    • MutableList
    • MutableSet
  • MutableMap

또한 기존 구현체에 대한 다양한 확장 함수(extension function)를 제공하여 기존 구현체의 기능을 확장한다.

참고

• https://www.databricks.com/glossary/hash-buckets
• https://kotlinlang.org/docs/collections-overview.html
• 자바 알고리즘 인터뷰 with 코틀린, 박상길 저