[java, 자료구조] 컬렉션 프레임워크 선택 기준

[Java]컬렉션 프레임워크 선택 기준

개요

어느 상황에 어떤 컬렉션 프레임워크를 쓰면 좋을지 정리
- 참고 : I : 인터페이스, C : 클래스

컬렉션 프레임워크에 대해 간단히 설명

• 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합
• 자료구조와 알고리즘을 구조화하여 클래스로 구현해 놓은 것

프레임워크 종류 정리

[I] List

중복이 가능하고, 순서가 있는 데이터의 집합

[C] ArrayList

특정 원소 조회가 많은 경우 사용하는 것을 추천
리스트 자료구조를 사용한다면 기본선택!

• 리스트 자료구조를 사용한다면 기본적으로 선택
• 배열을 이용해 만든 리스트
  • 데이터의 저장순서가 유지되고 중복을 허용
• 임의의 요소에 대한 접근성이 뛰어남 (인덱스로 조회)
  • 단방향 포인터구조로 자료에 대한 순차적인 접근에 강점 (조회가 빠르다)
• 요소의 추가/삭제 불리
  • 데이터를 뒤로 밀거나 앞으로 당겨야하기 때문(O(N))
  • but, 순차적인 추가/삭제는 빠름
• 데이터량에 따라 공간(capacity)이 자동으로 늘거나 줄음

[C] LinkedList

조회보다 삽입/삭제가 많은 경우에 사용하는 것을 추천

• 노드와 포인터를 이용해 만든 리스트 (배열이 아님)
• 데이터의 중간 삽입/삭제가 빈번한 경우 빠른 성능을 보장
• 특정 원소를 조회하는 경우, 첫 노드부터 순회해야하기 때문에 ArrayList에 비해 느리다
  (임의의 요소에 대한 접근 성능이 좋지않음)
• 포인터로 각각의 노드들을 연결하고 있어, 삽입/삭제가 빠르다
  • 단순히 기존 포인터를 끊고 새로운 노드에 연결하면 되기 때문
  • 그러나, 중간에 데이터를 삽입/삭제할 경우 그 데이터까지 순차적으로 조회해야해서 O(N)의 시간복잡도를 가진다

[C] Vector

ArrayList와 비슷하게 배열로 만들어진 리스트지만, thread-safe하다

• 한 번에 하나의 스레드만 접근이 가능하다
• get, put에 모두 syncronized가 걸려있어 스레드마다 lock이 걸리게 되고, 성능이 ArrayList보다 좋지 않다
• 구버전 자바와 호환성을 위해 남겨두었으며, 잘 쓰이진 않는다

tip : 현업에서 컬렉션에 동기화가 필요한 경우, Collections.synchronizedList() 메서드를 이용해 ArrayList를 동기화 처리하여 사용한다

[C] Stack

LIFO(Last-In-First-Out) 특성을 가진 자료구조이다.

• 후입선출 자료구조
  • 마지막에 들어온 원소가 처음으로 나간다
  • 들어올때는 push 나갈때는 pop이라는 용어 사용
• Stack은 Vector를 상속하기 때문에 문제점이 많아 잘 안쓰인다
  • 가급적 사용하지 말기 (deprecated)
  • 대신 ArrayDeque 사용

[I] Set

중복이 불가능하고, 순서가 없는 데이터의 집합

[C] HashSet

추가, 삭제, 검색, 접근성이 뛰어남

• 배열과 연결노드를 결합한 자료구조 형태
• 가장 빠른 임의 검색 접근 속도를 가진다
  • 검색에 최고 성능 (get메서드의 성능이 O(1))
• 해싱을 이용해 추가, 삭제, 검색, 접근성이 모두 뛰어나다
  • 단, 순서를 전혀 예측할 수 없음
• 중복 허용X
  • 객체를 저장하기 전에 먼저 객체의 hashCode() 메소드를 호출한다. 그리고 같다면 equals()로 두 객체를 비교해 동등성을 판단한다

[C] LinkedHashSet

중복은 허용하지 않으나, 순서를 가짐
HashSet(중복X)에 저장 순서 유지 기능을 추가

• 순서를 가지는 Set 자료
• 추가된 순서 또는 가장 최근에 접근한 순서대로 접근 가능하다

[C] TreeSet

중복 허용X, 순서를 가지지X. 그러나 정렬이 되어있다
요소 정렬이 필요할때 고려
검색(특히 범위검색)에 적합하다

• 이진트리(binary search tree)를 기반으로 한 Set 컬렉션
• 중복을 허용하지 않고, 순서도 가지지 않지만 데이터를 정렬하여 저장하고 있다는 특징이 있다
• 정렬, 검색, 범위검색에 높은 성능을 뽐낸다
  • 그래도 검색성능은 HashMap보다 떨어짐

[I] Queue

FIFO(First-In-First-Out) 구조를 가진다
들어올때는 enqueue, 나갈때는 dequeue

[C] PriorityQueue

우선순위를 가지는 큐 (우선순위 큐)

• 원소에 우선 순위(priority)를 부여하여 우선 순위가 높은 순으로 정렬되고 꺼낸다
• 수행할 작업이 여러개 있고 시간이 제한되어 있을 때, 우선순위가 높은 것부터 수행해야하는 경우 사용
  (네트워크 제어, 작업 스케줄링)
• 우선순위 큐에 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야 함
  • compareTo() 메서드 로직에 따라 자료객체의 우선순위를 결정하는 식으로 동작되기 때문
• 저장공간으로 배열을 사용하며, 각 요소를 힙(heap)형태로 저장
• null 저장 불가능

Info : 힙(heap)은 이진트리의 한 종류
우선순위가 가장 높은 자료를 루드 노드로 갱신한다.
따라서, 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있음

[I] Deque

Deque(Double-Ended Queue)는 양쪽으로 넣고 빼는게 가능한 큐
스택+큐. 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다
Deque의 조상은 Queue

[C] ArrayDeque

스택(LIFO) / 큐(FIFO) 자료구조가 필요하면 ArrayDeque 사용

• 스택으로 사용할 때 Stack 클래스보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠르다
• 사이즈에 제한 X
• null 요소는 저장되지 X

[C] LinkedList

요소의 추가/삭제 유리
임의의 요소에 대한 접근성이 좋지 않음

• LinkedList는 List 인터페이스와 Queue 인터페이스를 동시에 상속받고 있기 때문에, 스택/큐 로서도 응용 가능
• 실제로 LinkedList 클래스에 큐 동작과 관련된 메서드를 지원
  • push, pop, poll, peek, offer 등

tip : 큐(Queue)는 데이터를 꺼낼 때 항상 첫번째로 저장된 데이터를 삭제한다
따라서 ArrayList와 같은 배열 기반의 컬렉션 클래스를 사용한다면, 데이터를 꺼낼때마다 빈 공간을 채우기 위해 데이터의 이동&복사가 발생하여 비효율적이다
큐는 ArrayList보다 데이터의 추가/삭제가 용이한 LinkedList로 구현하는 것이 적합한 이유이다

[I] Map

키와 값을 가지고, (저장)순서는 기억하지 않으며
키는 중복이 불가하고, 값은 중복이 가능한 데이터의 집합

만일 기존에 저장된 데이터와 중복된 키와 값을 저장하면, 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다

tip : Map 인터페이스를 보면,
key값을 반환할 때 Set 인터페이스 타입으로 반환하고, value값을 반환할 때 Collection 타입으로 반환하는 걸 확인할 수 있다

Map 인터페이스에서 값(value)은 중복을 허용하기 때문에 Collection 타입으로 반환하고, 키(key)는 중복을 허용하지 않기 때문에 Set 타입으로 반환하는 것!

[I] Map.Entry 

• Map.Entry 인터페이스는 Map 인터페이스 안에 있는 내부 인터페이스
• Map에 저장되는 key-value 쌍의 Node 내부 클래스가 이를 구현하고 있다
• Map 자료구조를 보다 객체지향적인 설계를 하도록 유도하기 위함

[C] HashMap

해싱을 이용해 임의의 요소에 대한 추가/삭제/검색/접근성 모두 뛰어남
검색에 최고성능을 보임 ( get메서드의 성능이 O(1))

• Hashtable을 보완한 컬렉션
• 배열과 연결이 결합된 Hashing 형태로, 키와 값을 묶어 하나의 데이터로 저장
• 중복 허용X, 순서 보장X
• 키와 값으로 null이 허용된다
• 추가, 삭제, 검색, 접근성이 모두 뛰어나다
• HashMap은 비동기로 작동하기 때문에, 멀티 쓰레드 환경에서는 어울리지 않음 (대신 ConcurrentHashMap 사용)

[C] LinkedHashMap

HashMap에 저장 순서 유지 기능을 추가

• HashMap을 상속하기 때문에 흡사하나, Entry 들이 연결 리스트를 구성하여 데이터의 순서를 보장함
• 일반적으로 Map 자료구조는 순서를 가지지 않으나, LinkedHashMap은 들어온 순서대로 순서를 가진다

[C] Hashtable

HashMap + Thread-safe한 특징(동기화). 가급적 사용하지 말기

• 자바 초기 버전에 나온 레거시 클래스
• key를 특정 해시 함수를 통해 해싱한 후, 나온 결과를 배열의 인덱스로 사용하여 value를 찾는 방식으로 동작
• 키와 값으로 null값이 허용되지 않음

[C] TreeMap

요소 정렬이 필요할 때 사용
검색(특히 범위검색)에 적합하다. 그래도 검색 성능은 HashMap보다는 떨어짐

• 이진 검색 트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장 (TreeSet과 같은 원리)
• SortedMap 인터페이스를 구현하고 있어, Key값을 기준으로 정렬되는 특징을 가지고 있음
• 정렬된 순서로 키/값 쌍을 저장하므로 빠른 검색이 가능 (특히 범위 검색)
  • 단, 저장하는 동시에 정렬을 행하므로 저장시간이 다소 오래 걸림
  • 정렬 순서는 숫자 -> 알파벳 대문자 -> 알파벳 소문자 -> 한글 순

참고 사이트

• https://abhinavraj167.medium.com/an-introduction-to-collection-f9e258f32071
• https://inpa.tistory.com/entry/JCF-%F0%9F%A7%B1-Collections-Framework-%EC%A2%85%EB%A5%98-%EC%B4%9D%EC%A0%95%EB%A6%AC#%EC%BB%AC%EB%A0%89%EC%85%98_%ED%94%84%EB%A0%88%EC%9E%84%EC%9B%8C%ED%81%AC_%EC%84%A0%ED%83%9D_%EC%8B%9C%EC%A0%90
• https://devlopsquare.tistory.com/239