Chapter 11 ) 컬렉션 프레임웍 (Collections Framework)

출처 : Java의 정석

 

 

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

컬렉션 프레임웍이란, '데이터 군을 저장하는 클래스들을 표준화한 설계' 를 뜻한다.

컬렉션 프레임웍은 컬렉션, 다수의 데이터를 다루는데 필요한 다양하고 풍부한 클래스들을 제공한다.

 

인터페이스 List와 Set의 공통된 부분을 다시 뽑아서 새로운 인터페이스인 Collection을 추가로 정의.

 

 

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

컬렉션 프레임웍에서는 List와 Set의 공통된 부분을 다시 뽑아서 새로운 인터페이스인 Collection을 추가로 정의하였다. (Map은 다른 형태라서 상속 계층도에 포함 안함)

 

• List : 순서가 있는 데이터의 집합, 데이터의 중복을 허용한다. 구현 클래스 : ArrayList, LinkedList, Stack, Vector 등
• Set : 순서를 유지하지 않는 데이터의 집합, 데이터의 중복을 허용하지 않는다. 구현 클래스 : HashSet, TreeSet 등
• Map : 키(key)와 값(value)의 쌍으로 이루어진 데이터의 집합. 순서 유지하지 않으며 키는 중복을 허용하지 않고 값은 허용. 구현 클래스 : HashMap, TreeMap, Hashtable, Properties 등

 

컬렉션 프레임웍의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현하고 있으며, 구현한 인터페이스의 이름이 클래스의 이름에 포함되어 있어서 이름만으로도 클래스의 특징을 쉽게 알 수 있다. 

 

 

Collection 인터페이스

Collection 인터페이스는 컬렉션 클래스에 저장된 데이터를 일고, 추가하고 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드들을 정의하고 있다.

• List인터페이스 : 중복을 허용하면서 저장순서가 유지되는 컬렉션 구현.
• Set인터페이스 : 중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현. HashSet, TreeSet등이 있다.
• Map인터페이스 : 키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현. Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap 등이 있다.
• Map.Entry인터페이스 : Map인터페이스의 내부 인터페이스이다. Map에 저장되는 key-value쌍을 다루기 위해 내부적으로 Entry 인터페이스 정의. Map인터페이스를 구현하는 클래스에서는 Map.Entry인터페이스도 함게 구현해야한다.

 

ArrayList

List인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다.Object배열을 이용해서 데이터를 순차적으로 저장한다. 배열에 더이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장된다.

 

Vector의 용량과 capacity

v.trimToSize() : vector의 빈 공간을 없애 size와 capacity를 같게 한다.

Vector는 capacity가 부족한경우 또는 더 큰 capacity를 지정해주는 경우, 새로운 인스턴스를 생성하여 기존의 배열을 복사한다. capacity가 부족한 경우는 자동적으로 기존의 크기보다 2배의 크기로 증가된다. 

배열의 중간에 위치한 객체를 추가하거나 삭제하는 경우 다른 데이터들의 위치를 이동시켜야하기 때문에 데이터의 개수가 많을수록 작업시간이 오래걸린다.

 

 

LinkedList

배열의 단점은 다음과 같다.

• 크기를 변경할 수 없다.
• 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

 

Linked list는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.

각 노드들은 자신과 연결된 다음 요소에 대한 주소값과 데이터로 구성되어 있다.

 

class Node{
	Node next;
    Object obj;
}

 

따라서 linked list에서의 데이터 삭제 및 추가는 간단하며 속도가 빠르다.

 

• 삭제 : 삭제하고자하는 요소의 이전요소가 삭제하고자하는 요소의 다음요소를 참조하도록 한다.
• 추가 : 새로운 요소를 생성 후, 추가하고자하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경한다.

 

Double Linkedlist : 이전요소에 대한 접근이 가능하도록 한 linked list

doulbe linked list의 노드 :

class Node{
	Node next;
    Node previous;
    Object obj;
}

 

Doubly Circular LinkedList : double linked list의 첫 번째 요소와 마지막 요소를 서로 연결.

 

 

★ 정리

• 순차적으로 추가/삭제해야하는 경우에는 ArrayList가 LinkedList보다 빠르다.
• 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
• 데이터 접근시간(데이터를 읽어오는 시간)은 ArrayList가 LinkedList보다 빠르다.

 

 

Stack와 Queue

• Stack : 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO (Last In First Out)
• Queue : 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO (First In First Out)

 

스택에는 ArrayList가 적합. (순차적으로 데이터를 추가하고 삭제하므로)

큐는 LinkedList가 더 적합. (데이터의 추가/삭제가 쉬워야함)

 

자바에서는 스택은 Stack 클래스로 구현하여 제공하고 있지만 큐는 Queue인터페이스로만 정의해놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 따라서 Queue인터페이스를 구현한 클래스들 중 하나를 선택해서 사용하면 된다.

 

• Stack 활용의 예 : 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
• Queue 활용의 예 : 최근사용문서, 인쇄작업 대기목록, 버퍼

PriorQueue : Queue 인터페이스의 구현체 중 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다. (null은 저장안함)

 

 

Iterator, ListIterator, Enumeration

모두 컬렉션에 저장된 요소를 접근하는데 사용. Enumeration은 Iterator의 구버전.

 

Iterator

컬렉션에 저장된 각 요소에 접근하는 기능을 가진 Iterator 인터페이스를 정의하고, Collection 인터페이스에는 'Iteraator'를 반환하는 iterator()를 정의하고 있다.

 

boolean hasNext()	읽어올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false 반환
Object next()	다음 요소를 읽어온다. next() 호출하기 전에 hasNext()를 호출해서 읽어올 요소가 있는지 확인하는 것이 안전하다.
void remove()	next()로 읽어온 요소를 삭제한다. next()를 호출한 다음에 remove()를 호출해야 한다.

 

ArrayList에 저장된 요소들을 출력하기 위한 코드는 다음과 같다.

Collection c = new ArrayList();
Iterator it = c.iterator();

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

 

Map인터페이스를 구현한 컬렉션 클래스는 키와 값을 쌍으로 저장하고 있기 때문에 iterator()를 직접 호출할 수 없고, keySet()이나 entrySet()과 같은 메서드를 통해 키와 값을 각각 Set의 형태로 얻어온 후에 다시 iterator()를 호출해야 Iterator를 얻어올 수 있다.

 

ListIterator : Iterator에 양방향 조회기능 추가(List를 구현한 경우만 사용 가능)

 

 

Arrays

Arrays클래스에는 배열을 다루는데 유용한 메서드가 정의되어 있다.

• 배열의 복사 : copyOf(), copyOfRange()
• 배열 채우기 : fill() -모든 요소를 지정된 값으로 채움, setAll()
• 배열의 정렬과 검색 : sort(), binarySearch() - 배열에서 지정된 값이 저장된 위치(index) 반환. 정렬된 상태여야 올바른 값을 얻는다.
• 배열의 비교와 출력 : equals(), toString()
• 배열을 List로 변환 :  asList(Object... a)

 

 

Comparator와 Comparable

Comparator와 Comparable은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있다.

 

• Comparable : 기본 정렬기준을 구현하는데 사용
• Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자 사용. (ex 내림차순 정렬 등..)

 

 

HashSet

• Set인터페이스를 구현한 가장 대표적인 컬렉션이며, Set 인터페이스의 특징대로 중복된 요소를 저장하지 않는다.
• 새로운 요소를 추가할 때 add 또는 addAll 메서드를 쓰는데, 중복된 요소를 추가하고자하면 false를 반환함으로써 추가에 실패했음을 알린다.
• 저장순서를 유지하지 않음. (순서 유지하고자하면 LinkedHashSet을 사용해야한다)
• 중복을 허용하지 않지만 '1', '1' 같은 경우 하나가 String인스턴스이고 다른 하나는 Integer인스턴스이면 다른 객체로 인정.

 

오버라이딩을 통해 작성된 hashCode()는 세가지 조건을 만족해야한다.

• 실행 중인 애플리케이션 내의 동일한 객체에 대해서 여러번 hashCode()를 호출해도 동일한 int값을 반환해야한다.
• equals메서드를 이용한 비교에 의해서 true를 얻은 두 객체에 대해 각각 hashCode()의 호출 결과는 같아야한다.
• equals메서드를 호출했을 때 false를 반환하는 두 객체가 hashCode()호출에 대해 같은 값을 반환해도 괜찮지만, hashing을 사용하는 컬렉션의 성능을 향상시키기 위해 다른 int값을 반환하는게 좋다.

 

TreeSet

이진검색트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.

정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조이다. Set 인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지 않는다.

 

여러개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 루트(root)에서부터 시작해서 확장해 나갈 수 있다. 또 위 아래로 연결된 두 노드를 '부모-자식관계'에 있다고 함.

 

class TreeNode{
	TreeNode left;
    Object element;
    TreeNode right;
}

이진트리의 트리 노드는 위와 같다.

이진 검색 트리는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값을, 오른쪽에는 큰 값의 자식노드를 저장하는 이진트리이다.

따라서 왼쪽 마지막 값에서부터 오른쪽 값 까지의 값을 왼쪽노드-부모노드-오른쪽 노드 순으로 읽으면 오름차순 정렬된다.

• 노드의 추가와 삭제에 시간이 걸린다 (순차적으로 저장하지 않으므로).
• 검색(범위검색)과 정렬에 유리하다.

 

 

HashMap과 Hashtable

HashMap은 Map을 구현했으므로 키, 값을 묶어서 하나의 데이터(entry)로 저장한다. 그리고 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.

 

• 키 : 컬렉션 내의 키 중에서 유일해야한다.
• 값 : 키와 달리 데이터의 중복을 허용한다.

entrySet()을 이용해서 키와 값을 함께 읽어올 수도 있고 keySet()이나 values()를 이용해서 키와 값을 따로 읽어올 수 있다.

 

 

해싱과 해시함수

• 해싱이랑 해시함수를 이용해 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다.
• 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 원하는 데이터를 빠르게 찾을 수 있다.
• 해싱에 사용하는 자룍조는 배열과 linkedlist의 조합으로 되어있다.
• 해싱을 구현하는 과정에서 제일 중요한 것은 해시함수의 알고리즘

 

TreeMap

• 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장.
• 검색과 정렬에 적합

 

Properties

HashMap의 구버전인 Hashtable을 상속받아 구현한 것으로, hashtable은 키와 값을 (Object, Object) 형태로 저장하는데 비해 Properties는 (String, String)의 형태로 저장하는 보다 단순화된 컬렉션 클래스이다.

 

 

 

Collections

Collections는 컬렉션과 관련된 메서드를 제공한다.

fill(), copy(), sort(), binarySearch() 등의 메서드.

 

• 컬렉션의 동기화 : ArrayList, HashMap과 같은 새로 추가된 컬렉션은 동기화를 자체적으로 처리하지 않고 필요한 경우메나 java.util.Collections 클래스의 동기화 메서드를 이용해서 동기화처리가 가능하다. 사용방법은 다음과 같다.

List syncList = Collections.synchronizedList(new ArrayList(...));

 

• 변경불가 컬렉션 만들기 : unmodifiable 메서드들 사용
• 싱글톤 컬렉션 만들기 : 단 하나의 객체만을 저장하는 컬렉션. singleton~
• 한 종류의 객체만 저장하는 컬렉션 만들기 : checked~