Collection framework

최창효·2022년 2월 18일

CS Java

자바 이해하기

목록 보기

4/8

컬렉션 프레임워크란?

다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스들의 집합입니다.
널리 알려진 자료구조들을 쉽게 사용할 수 있도록 모아둔 것이라고 생각할 수 있습니다.

컬렉션 프레임워크라는 집합소에는
설명서인 Interface들과 데이터를 담는 박스인 Class들이 들어있습니다.

장점

Collection Framework를 사용하면 다음과 같은 효과를 얻을 수 있습니다.

이미 구현되어 있는 것을 사용함으로써 코딩 시간을 단축시킬 수 있습니다.
테스트와 검증이 끝난 것들이기 때문에 그 품질이 보장되어 있습니다.
재사용성과 상호 운용성이 높습니다.
- 상호 운용성: 별다른 제약 없이 서로 호환되어 사용할 수 있는 성질
- ArrayList를 사용하다가 금방 LinkedList로 변경할 수 있습니다.

특징

대부분의 클래스 이름은 구현한 인터페이스명이 포함되어 있습니다.
- ArrayList클래스는 이름에 List가 포함되어 List인터페이스를 implements했음을 짐작할 수 있으며 그 특징을 예상해 볼 수 습니다.
인터페이스들이 모두 제네릭으로 표현되어 있습니다.
- 컴파일 단계에서 데이터 타입이 잘못되었음을 발견할 수 있습니다.
- 개발자가 의도하지 않은 타입의 객체가 저장되는 것을 방지할 수 있습니다.
- 자료를 꺼내어 사용할 때 별도의 타입 확인이 필요없습니다.
- Generic의 Convention(관습,관례)
  - E: 요소
  - T: 타입
  - K: key
  - V: 리턴값, 매핑된 값
  - N: 숫자

구성요소

(이미지 출처: https://gbsb.tistory.com/247#java-collections-algorithms)

각 자료구조의 기능을 명시해 둔 Interface와 AbstractClass들이 존재하며, 이들을 활용해 실제로 기능을 구현해 둔 Class(구현체)들이 존재합니다.
cf)인터페이스와 추상클래스의 차이
- 인터페이스는 멤버변수, 생성자를 가질 수 없습니다.
- 추상클래스는 is a 관계를 가지고 인터페이스는 has a 관계를 가집니다.
- 인터페이스가 필요한 이유
  - 구현체 입장에서 추상 클래스는 하나만 Extends 할 수 있지만, 인터페이스는 여러 개를 Implements할 수 있기 때문입니다.
- 추상 클래스가 필요한 이유
  - 구현체 입장에서 인터페이스는 자신에게 필요하지 않은 메서드까지 반드시 Overriding해야 하지만, 추상 클래스의 메서드는 반드시 재정의 할 필요가 없기 때문입니다.
- 추상클래스에서는 어느정도의 구현이 되어있는 경우가 많습니다.

// List Interface의 clear는 다음과 같습니다.
void clear(); // List를 상속받는 클래스에 따라 clear방법이 다를 수 있습니다.

// Abstract List의 clear는 다음과 같습니다.
public void clear(){
	removeRange(0,size()); //Abstract List를 상속받는 클래스는 반드시 해당 방법으로 clear()가 진행됩니다.
}

인터페이스: XXX를 만드시오. (배점 100점)
추상 클래스: 다음 빈칸을 채워 XXX를 완성하시오. (배점 50점)

구성요소 세부사항

컬렉션 인터페이스

여기서의 컬렉션 인터페이스는 iterable을 상속받고 Set,List,Queue가 상속하고 있는 Collection Interface가 아니라, Collection에 있는 모든 interface라는 의미로 '컬렉션 인터페이스'라는 용어를 사용했습니다.

Collection Interface 그룹

Collection Interface

모든 컬렉션 클래스들이 구현해야 할 메서드를 포함하고 있습니다.
- .size(), .isEmpty(), .contains(o), .add(e), .remove(o), .containsAll(c), .addAll(c), .removeAll(c), .removeIf(filter), .retainAll(c), .clear(), .equals(o), .hashCode(), .stream(), .parallelStream(), .spliterator(), .iterator(), .toArray()

List Interface

순서가 존재합니다.
인덱스를 통해 요소에 접근이 가능합니다.
중복요소를 포함할 수 있습니다.
List 인터페이스로 구현된 클래스 : ArrayList, LinkedList

Set Interface

집합의 특성을 가집니다.
- 중복요소를 포함하지 않습니다.
- 부분집합(ContainsAll), 교집합(retainAll), 합집합(addAll), 차집합(removeAll) 연산이 가능합니다.
- 기본적으로는 순서가 보장되지 않습니다.
요소를 탐색하기 위해 iterate 또는 foreach를 이용해야 합니다.
- 인덱스로 요소에 접근이 불가능합니다.
Set 인터페이스로 구현된 클래스 : HashSet, TreeSet, LinkedHashSet

Sorted Set Interface

요소를 오름차순으로 유지하는 Set입니다.
Comparator를 구현하도록 명명하고 있습니다.
Sorted Set 인터페이스로 구현된 클래스 : TreeSet

Navigable Set Interface

Sorted Set Interface를 Implements하고 있습니다.
Sorted Set의 기능과 함께 pollFirst, pollLast, descendingSet등의 추가기능이 포함되어 있습니다.

Queue Interface

먼저 들어온 요소가 먼저 빠져나가게끔(FIFO)데이터를 보관하고 있습니다.
- PriorityQueue는 Queue이지만 예외적으로 선입선출 방식으로 정렬되지 않습니다.
주요 메서드로 .offer(e),.peek(),.poll() 등이 있습니다.
Queue 인터페이스로 구현된 클래스 : LinkedList, PriorityQueue

Deque Interface

Double Ended QUEue(데크)의 줄임말입니다.
양쪽 끝에서 요소를 삽입 및 제거할 수 있습니다.
Deque 인터페이스로 구현된 클래스 : ArrayDeque, LinkedList
- PriorityQueue는 Queue의 성질만 가지고 있지 Deque의 성질을 가지고 있지 않습니다.
Queue는 add만 존재하지만 Deque는 addFirst와 addLast가 존재합니다.

Map 인터페이스 그룹

Map Interface

key와 value를 하나의 노드로 묶어서 저장하도록 명명하고 있습니다.
Key의 값은 중복될 수 없으며, 하나의 key에는 하나의 값만 존재합니다.
- 그 하나의 값에 list등의 자료구조를 사용해 하나의 key가 실질적으로는 여러 value를 가지는 것처럼 활용할 수 있습니다.
value의 값은 중복될 수 있습니다.
Map 인터페이스로 구현된 클래스 : HashMap, TreeMap, LinkedHashMap

SortedMap Interface

key의 오름차순으로 순서를 유지하는 Map입니다.
SortedMap 인터페이스로 구현된 클래스 : TreeMap

NavigableMap Interface

SortedMap Interface를 Implements하고 있습니다.

기타

Iterable Interface

Collection Interface가 Implements하고 있는 Interface입니다.
Iterable Interface를 구현한 자료구조는 순회가 가능합니다.
Iterable안에는 .iterator(),.forEach(T),.spliterator()메서드가 포함되어 있습니다.

개인적인 궁금증 - 각 Interface의 특징은 어디서 보장되는 걸까?

상세
- Set은 중복요소를 허용하지 않는다고 했습니다. 그렇다면 Set의 중복요소를 허용하지 않는다는 기능은 어디서 오는 거인지 궁금해졌습니다.
- 즉, Implements Set을 하면 자동으로 중복요소를 허용하지 않는 기능을 획득하는건지 궁금했습니다.
결론 - 그렇지 않습니다.
- 구현체에서 해당 interface의 기능에 맞는 구현을 직접 해야 합니다.
- 즉 Implements Set을 한다고 중복요소를 허용하지 않는 기능이 생기는 건 아닙니다. 구현체를 만들 때 중복요소를 허용하지 않도록 직접 구현해야 합니다.
- 인터페이스는 기능을 구현하지 않는 게 일반적이기 때문에 어찌보면 당연한 결과인가? 나만 궁금했던건가? 라는 생각이 드네요.
확인과정
아래는 Set Interface의 add입니다. add에는 아무런 기능이 없으며, 파란색으로 적힌 글에 'Adds the speicified element to this set if it is not already present'. set에 해당 element가 존재하지 않을 경우에만 Add하게끔 만들어라고 가장 먼저 얘기하고 있습니다.

아래는 Set의 구현체중 하나인 HashSet의 add입니다.

map.put()이라는 방식으로 add를 진행하고 있으며 이 put은 아래와 같은 방식으로 진행됩니다.

보시다시피 구현체에서 해당 기능(중복이면 add하지 않도록)을 구현하고 있습니다.

전교1등의 노트를 가져왔다고 전교1등이 되지는 않습니다.
결국 해당 노트에 적힌 방식대로 직접 공부를 해야 1등이 될 수 있습니다.

컬렉션 클래스

인터페이스의 명세에 따라 구현된 구현체들입니다.
구현체를 통해 우리는 객체를 생성하고 사용하는 게 가능해 집니다.

Collection 인터페이스 그룹의 클래스

ArrayList 클래스

ArrayList는 크기가 고정되어 있지 않은 배열입니다.
- 크기가 동적인 배열을 resizable-array라고 합니다.
ArrayList는 데이터를 넣는 만큼 사이즈가 늘어납니다.
- 사이즈가 늘어나는 방식은 기존의 배열(n)이 다 차면 해당 배열의 2배 크기의 배열을 만들고, 기존의 값을 새로운 배열에 옮겨주는 Doubling방식이 사용됩니다.
- Doubling방식의 소요시간은 O(n), 즉 기존 배열의 크기만큼 소요됩니다.
ArrayList의 검색(.get)시간과 입력(.add)시간은 O(1)입니다.
- 고정된 배열에서 index를 통해 검색하기 때문에 검색시간은 O(1)입니다.
  - N/2+N/4+...+2+1<N이기 때문에 O(n)보다 작다는 의미의 O(1)입니다.
- index를 기억하고 있기 때문에 입력시간은 O(1)입니다.
  - Doubling하는 경우를 포함시켜 O(n)이라고도 얘기합니다.
ArrayList의 삭제(.remove)시간은 O(n)입니다.
- 삭제 후 한칸씩 shift하는 작업이 필요하기 때문입니다.

LinkedList 클래스

Doubly linked list(이중 연결 리스트)방식으로 구현되어 있습니다.
- previous node주소 - data - next node주소가 하나의 노드입니다.
add시
- 본인 앞의 노드의 next node주소값을 자신의 next 값으로 바꿉니다.
- 앞 노드의 next node주소값을 본인으로 변경합니다.
- 본인 뒤 노드의 previous node주소값을 자신의 previous 값으로 바꿉니다.
- 뒤 노드의 previous node주소값을 본인으로 변경합니다.
remove시
- 삭제되는 노드의 next node주소값을 previous node의 next값으로 바꿉니다.
- 삭제되는 노드의 previous node주소값을 next node의 previous값으로 바꿉니다.
Head와 Tail의 정보를 모두 가지고 있습니다.
- Head는 첫번째 노드의 주소를, Tail은 마지막 노드의 주소를 담고 있습니다.
LinkedList의 입력(.add)시간과 삭제(.remove)시간은 O(1)입니다.
- O(1)은 시작이나 끝부분에 입력 혹은 삭제를 진행할 때 입니다.
- 시작과 끝 이외의 입력과 삭제는 탐색시간(O(n))+입력시간(O(1))인 O(n)이 소요됩니다.
LinkedList의 검색(.get)시간은 O(n)입니다.
- head에서부터 원하는 값을 찾을때까지 순차적으로 접근하기 때문입니다.
List와 Deque(Queue)를 모두 implements하고 있어 다양한 자료구조의 구현체로 활용됩니다.

cf) ArrayList vs LinkedList
ArrayList는 데이터 검색이 빠르며 LinkedList는 데이터 추가/삭제가 빠릅니다.
둘 중 더 좋은 List가 존재하는 게 아닙니다.
본인의 사용목적에 알맞은 클래스를 사용하시면 됩니다.

HashSet 클래스

순서가 존재하지 않으며, 중복을 허용하지 않는 자료구조 입니다.
HashMap에 자료가 저장됩니다.
- HashMap에 대한 자세한 설명은 아래에서 진행하겠습니다.
- HashMap의 Key에다가 자료를 저장하기 때문에 순서가 존재하지 않으며 중복을 허용하지 않습니다.
  - Value에는 dummy값을 넣어 사용합니다.
입력(.add)시간은 O(1)입니다.

TreeSet 클래스

binary search tree 형태로 데이터를 저장합니다.
범위검색(.subset())이 가능합니다.
정렬되어 있기 때문에 first(),last()관련 메서드들을 사용할 수 있습니다.
데이터 추가, 삭제에 HashSet보다 시간이 많이 소요됩니다.

PriorityQueue 클래스

우선순위가 높은 데이터가 먼저 나가도록 설계된 데이터 구조입니다.
heap을 통해 내부가 구현되어 있습니다.
offer와 poll에 O(logN)의 시간이 소요됩니다.
값이 들어올 때마다 heapify가 수행되어 heap을 유지합니다.
기본적으로 정수에 대해 오름차순 정렬을 제공하고 있습니다.
Comparator를 통해 정렬기준(우선순위)을 설정할 수 있습니다.

Map 인터페이스 그룹의 클래스

HashMap 클래스

key와 value쌍의 데이터를 저장합니다.
- key와 value를 node에 저장하고 있습니다.
  - node는 linkedList의 구조입니다.
- key-value를 묶은 node는 table이라는 배열에 보관됩니다.
- 배열에 담겨있지만 순서가 보장되지 않는 이유는 key값에 대해 Hashcode함수를 이용하고, 이를 index로 활용한 상태에서 index가 겹치면 LinkedList를 통해 해당 idnex에 값을 이어나가기 때문입니다.
입력과 삭제에 대한 시간복잡도는 O(1)입니다.
Collection interface그룹이 아니기 때문에 add메서드 대신 put메서드를 사용합니다.
- put(key,value)
중복된 key값을 허용하지 않는 부분을 다음과 같이 구현하고 있습니다.
사이즈를 자동으로 확장시키는 부분을 다음과 같이 구현하고 있습니다.
HashMap의 생성자를 통해 initial Capacity와 loadFactor를 지정해 줄 수 있습니다.
Map 자체에는 iteration 기능이 없기 때문에 entrySet으로 변경 후 사용해야 합니다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Map<String,Integer> map = new HashMap<String,Integer>(); //HashMap 생성
        //데이터 삽입
		map.put("one", 1);
		map.put("two", 2);
		map.put("three", 3);
		map.put("four", 3);
		
        //HashMap을 Set으로 변경 후 foreach순회
		Set<Map.Entry<String, Integer>> entries = map.entrySet();
		for (Map.Entry<String, Integer> entry : entries) {
			System.out.println(entry.getKey()+" : "+ entry.getValue());
		}
		
        //HashMap을 Set으로 변경 후 iterator()를 이용한 순회
		Iterator iter = entries.iterator();
		while (iter.hasNext()) {
			System.out.println(iter.next());
		}
	}
}

TreeMap 클래스

내부적으로 Red-Black Tree자료구조를 사용하고 있습니다.
정렬을 위한 Comparator변수가 존재합니다.
HashMap과 달리 Hashcode함수를 활용한 변경 없이 index를 활용하기 때문에 LinkedList형태로 데이터의 순서가 보장됩니다.

LinkedHashMap 클래스

FIFO구조로 데이터를 저장합니다.

Collections

Collections는 클래스입니다.
Collections는 Collection클래스들을 유용하게 활용하기 위한 장치입니다.
Collections는 sort,shuffle,search등의 메서드를 가지고 있습니다.
Collections속 메서드들은 static으로 선언되어 있기 때문에 인스턴스 생성 없이 바로 사용할 수 있습니다.

동기화

앞서 살펴본 Collection Framework의 클래스들은 대부분 동기화를 제공하지 않습니다.(thread-safe하지 못합니다.)
자바는 java.util.concurrent패키지를 통해 동기화 기능을 적용한 자료구조를 제공합니다.
- 대표 예시
  - CopyOnWriteArrayList
  - CopyOnWriteArraySet
  - ConcurrentHashMap
동기화 기능은 Collections에서도 synchronizedXXX()메서드를 통해 제공하고 있습니다.
- 대표 예시
  - synchronizedList(List list)
  - synchronizedMap(Map<K,V> m)
  - synchronizedSet(Set s)
동기화된 자료구조는 multi-thread에 적합하며, single-thread의 경우 속도가 떨어집니다.

References

최창효

기록하고 정리하는 걸 좋아하는 개발자.

이전 포스트

GC의 종류와 알고리즘

다음 포스트