자바의 정석 - 컬렉션 프레임워크(Collections Framework)

컬렉션 프레임워크

컬렉션(Collection)

- 여러 객체(데이터)를 모아놓은 것을 의미

프레임워크(Framework)

- 표준화, 정형화된 체계적인 프로그래밍 방식

- 프로그램을 작성하는 방식이 비슷하기 때문에 유지보수가 쉬워진다.

- Spring Framework

컬렉션 프레임워크(Collections Framework)

- 컬렉션(다수의 객체)을 다루기 위한 표준화된 프로그래밍 방식

- 컬렉션을 쉽고 편리하게 다룰 수 있는 다양한 클래스를 제공

객체를 다룬다는 것 : 저장 / 삭제 / 검색 / 정렬

- java.util 패키기에 포함 / JDK1.2부터 제공

컬렉션 프레임워크의 핵심 인터페이스

인터페이스	특징
List	순서가 있는 데이터의 집합. 데이터의 중복 허용 ArrayList, LinkedList, Stack, Vector 등
Set	순서를 유지하지 않는 데이터의 집합. 데이터의 중복 허용X HashSet, TreeSet 등
Map	키(key)와 값(value)의 쌍으로 이루어진 데이터의 집합. 순서는 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용한다. HashMap, TreeMap, HashTable, Properties 등

List인터페이스 - 순서O, 중복O

List를 구현한 클래스 : Vector. ArrayList, LinkedList

Set인터페이스 - 순서X, 중복X

- Set을 구현한 클래스 : HashSet, TreeSet

Masp인터페이스 - 순서X, 중복(키X, 값O)

- Map을 구현한 클래스 - HashMap, TreeMap

 

ArrayList

ArrayList와 Vactor의 차이

- Vector는 자체적으로 동기화처리가 되어 있다.

- 데이터의 저장공간으로 배열을 사용한다.(배열기반)

 

ArrayList의 값 추가

- 중간에 데이터를 넣는것은 부담이 큰 작업이다. 

 

LinkedList

배열의 장단점

장점 : 배열은 구조가 간단하고 데이터를 읽는데 걸리는 시간(접근시간, access time)이 짧다.

단점: 크기를 변경할 수 없다.

- 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야함.

- 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨

단점2: 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.

- 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함

- 그러나 순차적인 데이터 추가(끝에 추가) 와 삭제(끝부터 삭제)는 빠르다.

 

배열의 단점을 보완

- 배열과 달리 링크드 리스트는 불연속으로 존재하는 데이터를 연결(link)

데이터의 삭제: 단 한 번의 참조변경만으로 가능

 

링크드 리스트의 단점

- 데이터 접근성이 나쁘다. (자신의 다음요소밖에 알지 못한다.)

- 이중 연결리스트 (연결이 2개여서 이전 / 다음 노드를 알 수 있다.)

 

ArrayList vs LinkedList - 성능 비교

1. 순차적으로 데이터를 추가/삭제 - ArrayList가 빠름

2. 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름

3. 접근시간(Access time) - ArrayList가 빠름

 

스택과 큐(Stack & Queue)

스택(Stack) : LIFO 구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.

- 밑이 막힌 상자와 같다.

- 저장은 push(), 추출은 pop()을 사용한다.

- Array로 구현하면 적합

 

큐(Queue): FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.

- 링크드 리스트로 구현하면 적합

 

스택과 큐(Stack & Queue)의 활용

스택의 활용 예 - 수식계산, 수식괄호검사, udo/redo, 뒤로/앞으로

큐의 활용 예 - 최근 사용문서, 인쇄작업 대기목록

 

iterator, ListIterator, Enumeration

- 컬렉션에 저장된 데이터를 접근하는데 사용되는 인터페이스

- hasNext() : 읽어 올 요소가 남아있는 지 확인

- next() : 다음 요소를 읽어온다.

- iterator는 한번만 사용할 수 있다.

 

순차 탐색과 이진 탐색

순차 탐색 : 순차적으로 찾는것

이진 탐색 : 정렬 기본 / 둘로 나눠가면서 찾는다.

 

다차원 배열 출력

deepToString()

System.out.println(Arrays.deepToString());

배열을 List로 변환

- asList(Obejct... a)

- 읽기 전용이기 때문에 값을 추가하거나 변경하기 위해서는 new ArrayList(Arrays.asList(1, 2, 3, 4, 5));로 새로운 ArrayList를 생성해야한다.

List list = Arrays.asList(new Integer[] {1, 2, 3, 4, 5});

Compartator 와 Comparable

- 객체 정렬에 필요한 메서드(정렬기준 제공)를 정의한 인터페이스

Comparable - 기본 정렬기준을 구현하는데 사용

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

정렬 방법은 불변이나 정렬 기준은 가변이다.

 

HashSet

- 순서 X / 중복 X

- Set인터페이스를 구현한 대표적인 컬렉션 클래스

- 순서를 유지하려면, LinkedHashSet클래스를 사용하면 된다.

- HashSet은 객체를 저장하기전에 기존에 같은 객체가 있는 확인

같은 객체가 없으면 저장하고, 있으면 저장하지 않는다

- boolean add(Object o)는 저장할 객체의 equals()와 hasCode()를 호출

equals()와 hashCode(0가 오버라이딩 되어 있어야 함

 

TreeSet

- 이진 탐색 트리(binary search tree)로 구현. 범위탐색과 정렬에 유리

- 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음

- 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

 

이진탐색트리 (binary search tree)

- 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장

- 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

- 범위 검색에 유리하다.

 

트리 순회(tree traversal)

- 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.

- 전위, 중위, 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.

전위 순회 (pre-order)

후위 순회 (post-order)

중위 순회 (in-order)

레벨 순회 (level-order)

 

HashMap과 HashTable

- 순서X,중복(키X, 값O)

- Map인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장

 

HashMap

- Map인터페이스를 구현한 대표적인 컬렉션 클래스

- 순서를 유지하려면, LinkedHashMap클래스를 사용하면 된다.

TreeMap

- 범위 검색과 정렬에 유리한 컬렉션 클래스

- HashMap보다 데이터 추가, 삭제에 시간이 더 걸림 (비교저장)

 

HashMap의 키와 값

- 해싱(hashing) 기법으로 데이터를 저장. 데이터가 많아도 검색이 빠르다.

- Map인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장

 

해싱(hashing) - 환자정보관리

키 -> 해시함수(hash function) -> 해쉬코드

해쉬함수를 이용해서 데이터를 저장하고 읽어오는 것을 해싱(hashing)이라고 한다.

어떠한 해쉬함수들이 있을까?

- 해시함수(hash function)로 해시테이블(has table)에 데이터를 저장, 검색

 

해시테이블에 저장된 데이터를 가져오는 과정

1. 키로 해시함수를 호출해서 해시코드를 얻는다.

2. 해시코드(해시함수의 반환값에 대응하는 링크드리스트를 배열에서 찾는다.

3. 링크드 리스트에서 키와 일치하는 데이터를 찾는다.

* 해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야 한다. 서로 다른 키일지라도 같은 값의 해시코드를 반환할 수도 있다.

 

Collections 클래스

- 컬렉션을 위한 메서드(static)를 제공

- Objects, Arrays, Collections

1. 컬렉션 채우기, 복사, 정렬, 검색 - fill(), copy(), sort(), binarySearch() 등

2. 컬렉션의 동기화 - synchronizedXXX()

3. 변경불가(readOnly) 컬렉션 만들기 - unmodifiableXXX();

4. 싱글톤 컬레션 만들기 - singletonXXX() - 객체 1개만 저장

5. 한 종류의 객체만 저장하는 컬렉션 만들기 - checkedXXX() -지금은 제네릭스 사용