[Java] 컬렉션 프레임워크(Collections Framework)
자료구조의 분류
자료구조 분류법은 많은 분류법이 있지만, 대표적으로 많이 분류되는 방법은 선형 자료구조(Linear Data Structure)과 비선형 자료구조(Nonlinear Data Structure)로 나눌 수 있습니다. 이러한 분류를 보통 '형태에 따른 자료구조'라고 보고, 각 자료구조에 알맞게 구체화 된 것들을 '구현된 자료구조'라고 합니다.
먼저 선형 자료구조(Linear Data Structure)에 대해 알아보면,
선형 자료구조는 쉽게 생각해서 데이터가 일렬로 연결된 형태라고 보면 됩니다.. 우리가 흔히 쓰는 int[] 배열같은 것이라 생각하면 됩니다.. 선형 자료구조는 대표적으로 리스트(List)와 큐(Queue), 덱(Deque)이 있습니다.
비선형 자료구조(Nonlinear Data Structure)는 선형 자료구조의 반대입니다. 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결 된 형태를 생각하면 됩니다. 쉽게 생각해서 거미줄 같다고 보면됩니다. 대표적인 비선형 자료구조는 그래프(Graph)와 트리(Tree)가 있습니다.
그리고 앞으로 설명 할 자료구조 중 위 두 가지 분류에 해당되지 않는 자료구조가 있는데 집합(Set), 맵(Map)입니다.
컬렉션이란?
일정한 성질을 갖는 것을 모아 한 공간에 모아두는 것을 컬렉션이라 합니다. (ex, 동전 컬렉션 등등)
즉, 데이터의 집합이나 그룹이라 말할 수 있습니다.
컬렉션의 특징
- 필요에 따라 확장가능
- 객체만 포함함(프리미티브 타입 불가)
- 스레드에 안전하게 만들 수 있음
- 수정 불가능하게 만들 수 잇음
컬렉션의 중복되는 의미들
1.collection(소문자 c): 객체가 저장되고 반복되는 자료 구조를 나타냅니다.
2.Collection(대문자 C): Set, List, Queue가 상속받는 java.util.Collection 인터페이스입니다. ( 이는 상속입니다. 구현이 아니라. 즉, Collection를 직접 구현한 것은 없습니다. )
3.Collections(대문자 C, s로 끝남): collections에 사용할 정적 유틸리티 메소드의 모음이 있는 java.util.Collections 클래스입니다.
java.util 패키지의 Collections Framework는 위의 interface와 유틸리티와 함께 로드됩니다.
JCF(Java Collections Framework)란?
자바 컬렉션 프레임워크는 컬렉션들을 표현하고 조작하기 위한 통합 구조입니다.
즉, 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것입니다.
모든 컬렉션 프레임워크에는 다음이 포함됩니다.
인터페이스: 다양한 유형의 컬렉션들(1)을 표현합니다.(set, list, map) 이러한 인터페이스들은 프레임워크의 기초를 형성합니다.
구현: 컬렉션 인터페이스(2)들의 기본 구현
알고리즘(3): 유용한 기능을 수행하는 정적 메소드
주의, Map은 Colletion을 상속받지 않지만, Java Collections Framework에 속합니다.
자바 컬렉션 프레임워크의 장점
사용 가능한 컬렉션 인터페이스: 기본 인터페이스 중 하나를 구현하여(Collection, Set, List, or Map) 클래스가 공통 API를 준수하고보다 규칙적이고 쉽게 이해되도록합니다.
Collection 인터페이스는 add(), remove(), contains(), size(), iterator() 등 대부분의 컬렉션에 공통적인 메소드 선언이 존재합니다.
자바 컬렉션 프레임워크의 계층구조 (Collection 인터페이스와 Map 인터페이스로 나뉨)
왜 Map은 Collection이 아닐까?
Java에서는 Map을 Collection이라고 보지 않습니다.
https://docs.oracle.com/javase/8/docs/technotes/guides/collections/designfaq.html#a14
[내용 원문]
디자인 차이인데요, 매핑(mappting)이 collections라 보기 힘들고, collections 또한 mapping이라고 보기 힘들다고 합니다. 그렇기 때문에 Collection 인터페이스를 상속하는 것은 의미가 없다고 합니다.
또한 Collection 인터페이스와 Map 인터페이스의 호환성 문제도 있습니다.
첫 번째, Collection 인터페이스를 상속하여 구현된 클래스들은 모두 단일 데이터를 처리하지만, Map은 Key와 데이터가 쌍이으로 이루며 처리하기 때문에 굳이 Map만을 위해 Collection에서 Map과 관련된 메소드를 만들 필요가 없습니다. (→ 인터페이스의 의미가 모호해짐)
두 번째, Iterable 인터페이스와 Map 인터페이스간의 문제도 있습니다. Iterable은 반복 가능한 형태를 의미하는데, Map의 구조인 Key, Value에서 어떤 것을 반복자로 할것인가에 대해서도 모호합니다.
그렇기 때문에 Map은 Collection 인터페이스가 아니지만, Collection Framework에는 포함되는 것입니다.
즉, Java에서 Map은 Collection이라 보지 않습니다.
List 인터페이스
List 인터페이스는 선형 자료구조(순서가 있는 데이터의 집합) 로, 데이터의 중복을 허용합니다.
List 인터페이스의 구현 클래스
ArrayList, LinkedList, Vector( Vector를 상속받은 Stack )
1. ArrayList
ArrayList는 크기가 가변적인 선형 리스트로 저장 용량이라는 것이 존재하여 이 용량을 넘어서면 자동으로 용량을 증가함으로써 추가적으로 요소를 넣을 수 있도록 합니다.(초기 용량: 10, 동적 가변 배열)
멀티 스레드 환경에서는?
ArrayList는 기본적으로 비동기 방식이기 때문에 스레드에 안전하지 못합니다.
그렇기 때문에 멀티 스레드 환경에서는 Collections.synchronizedList()를 사용합니다..
Collections.synchronizedXXX단점은
동기화된(synchronized) 컬렉션은 멀티 스레드 환경에서 하나의 스레드가 요소를 안전하게 처리하도록 도와주지만, 전체 요소를 빠르게 처리하지는 못합니다. 왜냐하면 스레드가 작업을 할때 락이 발생하기 때문입니다.(스레드가 병렬적으로 요소들을 처리할 수 없음)
자바에서는 멀티스레드환경에서 안전하면서도, 스레드가 병렬적으로 작업을 처리할 수 있도록 java.util.concurrent 패키지에서 ConcurrentHashMap, ConcurrentLinkedQueue를 제공합니다.
이 구현체들은 부분(segment) 잠금을 사용하기 때문에 병렬적으로 작업 수행이 가능합니다.
2. LinkedList
LinkedList는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 자료구조입니다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당합니다.(이중 링크드 리스트)
ArrayList vs LinkedList
삽입 삭제가 빈번하다면 LinkedList, 조회가 우선일 시 ArrayList를 사용
3. Vector
오래된 자료구조, 호환성을 위해 남겨 놓은 레거시 클래스입니다. (ArrayList와 거의 동일)
동기화를 사용하지만 스레드 안전하지 못합니다.
즉, 사용하지 않는 것이 좋다.
4. Stack
Vector를 상속하여 사용하는 LIFO 방식의 클래스
Stack 대신 Deque를 사용하여 구현할 것을 권장함.
Queue 인터페이스
Queue 인터페이스는 FIFO(First In First Out)형식의 선형 자료구조(순서가 있는 데이터의 집합) 로, 데이터의 중복을 허용합니다.
주로 LinkedList를 이용하여 구현합니다.
LinkedList는 왜 있을까?
Deque 또는 Queue를 LinkedList 처럼 Node 객체로 연결해서 관리하길 원한다면 LinkedList를 쓰면되고, Object[] 배열로 사용하고 싶으면 ArrayDeque를 쓰면 됩니다.
자바에서 지원하는 컬렉션에서 '일반적인 큐'를 사용하고자 한다면 LinkedList로 생성하여 Queue로 선언하면 됩니다.
1. Priority Queue(우선순위 큐)
FIFO가 아닌 특정 우선순위에 따라 우선순위가 높은 요소가 먼저 삭제되는 자료구조입니다.
디폴트로 낮은 숫자가 높은 우선순위를 가집니다.
(단, 래퍼런스 타입일 경우 Compartor 또는 Comparable을 통해 정렬 방식을 구현해야함)
null을 허용하지 않습니다.
Deque 인터페이스
Queue가 삽입과 삭제가 한쪽에서만 가능하다면, Deque는 양쪽에서 삽입, 삭제가 가능한 자료구조입니다.
사용 방식에 따라 Stack이 될 수도 있고 Queue가 될 수도 있습니다.
2. ArrayDeque
사이즈 제한이 없는 가변 배열
null을 허용하지 않음
비동기 방식
원형 큐 방식으로 구현
Stack 목적으로 구현했을 때 기존의 Stack보다 빠르고, Queue 목적으로 구현 했을 때 LinkedList보다 빠릅니다. ( LinkedList 보다 단순 삽입 삭제시 ArrayDeque 가 더 빠름, https://docs.oracle.com/javase/8/docs/api/ ArrayDeque 파트)
왜 Queue를 구현할 때 ArrayDeque이 더 빠를까? (List에선 ArrayList보다 LinkedList가 삽입 삭제에 빠르다했는데.. )
http://javaqueue2010.blogspot.com/
위의 블로그에서 말하길.
Array는 LinkedList 보다 cache-locality에 조금더 친숙하다고 합니다.( LinkedList는 다음 노드가 있는 곳으로 가려고 다른 간접적인 경로를 거쳐감)
또한, ArrayDeque는 다음 노드에 대한 추가 참조를 유지할 필요가 없으므로 LinkedList보다 메모리 효율적이라고 합니다.
쉽게 말해서,
큐는 FIFO의 특성을 가지고 있습니다.
즉, 삽입은 큐의 맨 처음에, 삭제는 큐의 맨 마지막에 일어나기 때문에 중간에 삽입되거나 삭제되지 않습니다.
결국 삽입 삭제의 시간복잡도는 O(1)이므로 리스트와 별반 차이가 없기에 최적화가 잘되있는 배열이 좀더 빠릅니다.
Set 인터페이스
말 그대로 집합을 뜻합니다.
가장 큰 특징은, "데이터를 중복해서 저장할 수 없음"과 "입력 순서대로의 저장 순서를 보장하지 않는다"입니다.
→ LinkedHashSet은 입력순서대로의 저장순서를 보장합니다. 하지만 데이터를 중복해서 저장할 수 없는 것은 같습니다.
equals()메서드를 사용하여 들어온 값이 있는지 없는지 확인합니다.
1. HashSet
가장 기본적인 Set 컬렉션의 클래스입니다.
해시 알고리즘을 사용하여 검색 속도가 빠르다는 장점이 있습니다.
좀더 상세히 말하면 hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인 할 수 있습니다.
즉, Hash 기능과 Set 컬렉션이 합쳐진 것이 HashSet입니다. 그렇기 때문에 삽입, 삭제, 색인이 매우 빠른 컬렉션 중 하나입니다.
HashMap을 동해 구현되어 있습니다.
2. LinkedHashSet
앞에서 말했듯이 중복은 허용하지 않으면서 순서를 보장받고 싶을 경우 사용합니다.
LinkedHashMap을 동해 구현되어 있습니다.
3. TreeSet
HashSet과 마찬가지로 입력 순서대로의 저장 순서를 보장하지 않으며 중복 데이터 또한 넣지 못합니다. 다만 TreeSet은 중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 사용합니다. 정렬된 형태로 있다보니 특정 구간의 집합요소들을 탐색할 때 매우 유용합니다.
(Tree 라는 자료구조 자체가 데이터를 일정 순서에 의해 정렬하는 구조입니다. 거기에 더해진 것이 바로 Set인 중복값 방지 자료구조인 것입니다.)
TreeMap을 통해 구현되어 있습니다.
Map 인터페이스
Map은 값을 키에 매핑하는 객체입니다.
특징으로는.
데이터의 순서를 보장하지 않습니다.
중복된 Key 값을 가질 수 없습니다.
최대 하나의 Key에 매핑될 수 있습니다.
Key를 통해 Value에 바로 접근이 가능하므로 탐색이 빠릅니다.
equals()메서드를 사용하여 두 키가 동일한지 다른지 확인합니다.
1. HashTable
Map 인터페이스의 구현 클래스이며, 자바 초기 버전에 나온 레거시 클래스입니다.
Key와 Value가 null이면 안되고, Vector처럼 대부분의 메소드가 동기화처리 되어있다는 특징이 있습니다.
Key를 특정 해시 함수를 통해 해싱한 후 나온 결과를 배열의 인텍스로 사용하여 Value를 찾는 방식으로 동작합니다.
2. HashMap
정렬되지 않은 Map을 제공합니다.
하나의 null key와 다수의 null 값을 허용합니다.
순서에 신경쓰지 않는경우 다른 Map보다 빠르다는 장점이 있습니다.
hashCode()를 구현하면 접근 성능이 더 좋아집니다.
동기화 되지 않고 null을 허용한다는 점을 제외하면 HashTable과 거의 동일합니다. (보완했다 생각하면됨)
(싱글 스레드 환경에서 성능이 더 좋음 → 멀티 스레드 환경에선 ConcurrentHashMap을 사용)
3. LinkedHashMap
LinkedHashSet과 같이 입력순서대로의 저장순서를 보장합니다. → 순서를 보장하는 LinkedList의 구조를 이용함
삽입 삭제는 HashMap보다 느리지만, 더 빠른 조회를 할 수 있습니다.
4. TreeMap
정렬된 Map을 제공합니다.
Key를 기준으로 원하는 방식으로 정렬을 할 수 있따는 특징이 있습니다.
레드 블랙 트리로 구현이 되이있습니다.
디폴트로 낮은 숫자가 높은 우선순위를 가집니다.
(단, 래퍼런스 타입일 경우 Compartor 또는 Comparable을 통해 정렬 방식을 구현해야함)
댓글