[자바의정석]Chapter 11. 컬렉션 프레임웍(collections framework)

seungwon·2023년 1월 26일

Hashing List Map collections comparator iterator queue red black tree stack vector 자바의정석

자바의 정석

목록 보기

11/14

1. 컬렉션 프레임웍(Collections Framework)

데이터 군(群)을 저장하는 클래스들을 표준화한 설계

컬렉션(Collection) : 다수(多數)의 데이터，즉 데이터 그룹을, 프레임웍은 표준화된 프로그래밍 방식

List, Set, Map

인터페이스	데이터 순서	중복	구현클래스
List	유지	허용	ArrayList, LinkedList, (Stack, Vector) 등
Set	x	미허용	HashSet, TreeSet 등
Map	x	미허용	HashMap，TreeMap, (Hashtable, Properties)등

1.1 핵심 인터페이스 ~ 1.4 Stack과 Queue

Stack, Vector 보다는 ArrayList, LinkedList 사용 추천(collection framework이 만들어지기 이전부터 존재)

Collection 인터페이스

List
- 수정이 불가능해서 용량을 변경해야하는 경우 새로운 인스턴스를 생성
- ArrayList
Set
Map
- Map.Entry 인터페이스 $\\$ (Map인터페이스의 inner interface)
  ☑️ 값(value)사이에는 중복 가능 -> values() : 리턴타입이 Collection
  ☑️ key 중복 허용 x -> keySet() : 리턴타입이 Set
Queue
- PriorityQueue : 우선순위 기준으로 데이터 꺼냄(저장한 순서와 무관)
  - null 저장 x
  - 각 요소 자료구조 heap 형태로 저장
- Deque
- 등등

컬렉션 클래스 정리

ArrayList : 배열기반, 데이터의 추가와 삭제에 불리, 순차적인 추가/삭제는 제일 빠름. 임의의 요소에 대한 접근성(accessibility) 이 뛰 어 남.
HashMap : 배열+연결, 추가/삭제/검색/점근성 모두 뛰어남.특히 검색에 최고 성능
TreeMap : 연결 기반. 정렬/검색(특히 범위 검색), 검색 성능은 HashMap보다 떨어짐

1.5 Iterator, ListIterator, Enumeration

👽 Iterator

Iterator 인터페이스
iterator() : Iterator(Iterator를 구현한 클래스의 인스턴스)를 반환

☑️ 사용 예시 : ArrayList에 저장된 요소들을 출력

Collection c = new ArrayList(); // 다른 컬렉션으로 변경시 이 부분만 수정
Iterator it = c.iterator();

while(it.hasNext()) {
	System.out.println(it.next());
}

☑️ map

iterator 직접 호출 x
키와 값을 따로 Set의 형태로 얻기 -> iterator() 호출

Map map = new HashMap();
...
Iterator it = map.entrySet().iterator();

👽 Enumeration

Iterator의 구버전

👽 ListIterator

컬렉션 요소에 접근시 Iterator는 단방향이동만 가능
↔️ ListIterator : 양방향 이동 가능

1.6 Arrays

1.7 Comparator & Comparable(인터페이스)

Comparable : 기본 정렬기준을 구현하는데 사용
(= 컬렉션을 정렬sort()하는데 필요한 메서드를 정의)

Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자 할 때 사용

1.8 HashSet

1.9 TreeSet

이진 검색 트리형태로 데이터 저장
정렬된 상태 유지
- 특정 범위내의 데이터 검색이 빠름
- 데이터의 추가/삭제가 느림(연결리스트에 비해)
레드-블랙 트리로 구현되어 있음

👽 이진 탐색 트리(Binary Search Tree)

모든 노드는 최대 두 개의 자식노드를 가질 수 있다
왼쪽 자식노드의 값 < 부모노드의 값 < 오른쪽 자식 노드의 값
노드의 추가 삭제에 시간이 걸린다(∵ 순차적으로 저장x)
검색(범위검색)과 정렬에 유리하다
중복값 저장x

👽 레드-블랙 트리(Red-Black Tree = RB Tree)

자가 균형 이진 탐색 트리로서 연관 배열 등을 구현하는데 쓰이는 자료 구조
(자가 균형 이진 탐색 트리 : 노드의 삽입과 삭제가 이루어질 때 자동으로 균형 트리를 유지하는 이진 탐색 트리 - AVL, 레드-블랙 트리, 이진 힙)

☑️ 레드-블랙 트리의 조건
1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다(그러나 새로운 노드는 항상 빨간색으로 삽입)
3. 모든 리프 노드(NIL)들은 검은색이다.

$\quad$ (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 빨간색 노드의 자식은 검은색이다.
$\quad$ == No Double Red(빨간색 노드가 연속으로 나올 수 없다)
5. 모든 리프 노드에서 Black Depth는 같다.
$\quad$ == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

☑️ 데이터 삽입 과정

Double Red 해결 방법 : Restructuring, Recoloring
- Restructuring : 삼촌 노드가 검은색
- Recoloring : 삼촌 노드가 빨간색

Restructuring

새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

$\\$
$\\$

Recoloring

새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

1.10 HashMap & Hashtable

HashMap - Hashtable
== ArrayList - Vector

👽 해싱(Hashing) & 해시 함수(Hash Function)

해싱(Hashing) : 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법

해시 함수(Hash Function) : 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터 -> 고정된 길이의 데이터로 매핑하는 함수

ex) 주민번호 맨 앞자리의 생년을 기준으로 데이터 분류 - 00년대, 10년대, ...

1.11 TreeMap

HashMap vs TreeMap

	HashMap	TreeMap
유용한 상황	검색	범위검색/정렬

1.12 Properties

Hashtable을 상속받아 구현한 것

	Hashtable	Properties
데이터 저장 형태	(Object, Object)	(String, String) -> 보다 단순화된 컬렉션 클래스

1.13 Collections

컬렉션의 동기화

ArrayList, HashMap : 동기화 메서드(synchronized~)
ex)

static Collection synchronizedCollection(Collection c)
static List synchronizedList(List list) 
static Set synchronizedSet(Set s)
static Map synchronizedMap(Map m)
static SortedSet synchronizedSortedSet(SortedSet s) 
static SortedMap synchronizedSortedMap(SortedMap m)

Vector, Hashtable : 자체적으로 동기화 처리 -> 멀티쓰레드 프로그래밍이 아닌 경우 불필요, 성능을 떨어뜨리는 요인

$\\$
$\\$

변경불가 컬렉션(읽기 전용)
: 멀티 쓰레드 프로그래밍에서 여러 쓰레드가 하나의 컬렉션을 공유할 때 데이터가 손상되는 것을 방지
- unmodifiable~
  ex)
```
static Set unmodifiableSet(Set s)
static Map unmodifiableMap(Map m)
```

싱글톤 컬렉션 : 하나의 객체만을 저장하는 컬랙션
singleton~
ex)

static List singletonList(Object o)
static Set singleton(Object o) // singletonSet이 아님 
static Map singletonMap(Object key, Object value)

한 종류의 객체만 저장하는 컬렉션 만들기
checked
ex)

List list = new ArrayList();
List checkedList = checkedList (list, String, class); // String만 저장 가능
checkedList.add("abc"); // OK.
checkedList.add(new Integer(3)); // 에 러 . ClassCastException

seungwon

이전 포스트

[자바의정석]Chapter 10. 날짜와시간&형식화

다음 포스트

[자바의정석]Chapter 11. 컬렉션 프레임웍(collections framework)