다시 하자 기초! 컬렉션 프레임워크

컬렉션 프레임웍

데이터 군을 저장하는 클래스들을 표준화한 설계를 뜻한다. 다수의 데이터, 즉 데이터 그룹을, 프레임웍은 표준화된 프로그래밍 방식을 의미한다.

 

JDK1.2 이전까진 Vector, HashTable, Properties와 같은 컬렉션 클래스, 다수의 데이터를 저장할 수 있는 클래스들을 서로 다른 각자의 방식으로 처리해야 했으나, JDK1.2부터 컬렉션 프레임웍이 등장하면서 다양한 종류의 컬렉션 클래스가 추가되고 모든 컬렉션 클래스를 표준화된 방식으로 다룰 수 있도록 체계화되었다.

 

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

크게 3가지 타입이 존재한다. List, Set, Map으로 말이다.

그리고 인터페이스 List와 Set의 공통된 부분을 다시 뽑아서 새로운 인터페이스인 Collection을 추가로 정의 했다. List와 Set은 서로 공통부분이 많아서 Collection으로 정의할 수 있었지만 Map인터페이스는 이들과는 전혀 다른 형태로 컬렉션을 이루기 때문에 같은 상속계층도에 포함되지 못했다.

 

인터페이스	특징
List	순서가 있는 데이터의 집합. 데이터의 중복을 허용 예) 대기자 명단
	구현 클래스 :  ArrayList, LinkedList, Stack, Vector등
Set	순서를 유지하지 않는 데이터의 집합. 데이터의 중복을 허용하지 않는다. 예) 양의 정수 집합, 소수의 집합
	구현 클래스 : HashSet, TreeSet
Map	키(key)와 값(value)의 쌍으로 이루어진 데이터의 집합 순서는 유지되지 않으며 키는 중복을 허용하지않고, 값은 중복을 허용한다. 예) 우편번호, 지역번호(전화번호)
	구현 클래스 : HashMap, TreeMap, HashTable, Properties 등

개발 시 다루고자 하는 컬렉션을 고르기 위해 각 장단점을 잘 알고 있어야한다. 그리고 Vector나 HashTable과 같은 기존의 컬렉션 클래스들은 호환을 위해, 설계를 변경해서 남겨두었찌만 가능하면 사용하지 않는 것이 좋다. 그 대신 새로 추가된 ArrayList와 HashMap을 사용하자.

 

ArrayList

기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일하다고 볼 수 있다. 하지만 Vector는 기존에 작성된 소스와의 호환성을 위해서 남겨두었기에 가능하면 ArrayList를 사용하자.

 

ArrayList는 Object배열을 이용해서 데이터를 순차적으로 저장한다. 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장된다.

선언된 배열의 타입이 모든 객체의 최고조상인 Object이기 때문에 모든 종류의 객체를 담을 수 있다.

 

list2에서 list1과 공통되는 요소들을 찾아서 삭제하는 코드

for(int i=list2.size()-1; i>=0; i--){
 if(list1.contains(list2.get(i))
  list2.remove(i);
}

contains를 통해서 list2.get의 데이터와 일치하는게 있는지 확인하는 코드인데 주목할 점은 for문을 i=0부터 가는게 아니라 끝에서부터 뒤로 감소했다는 점이다. 왜냐하면 뒤에서부터 돌려야 중간에 삭제된 요소의 자리이동하는 불필요한 행위를 줄일 수 있기 때문이다.

 

ArrayList나 Vector같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야하기 때문에 상당히 효율이 떨어진다. 그래서 처음에 인스턴스를 생성할 때, 저장할 데이터의 개수를 잘 고려해 충분한 용량의 인스턴스를 생성하는게 좋다.

 

자바의 정석 591page의 메서드들을 직접 구현해보고 이해하도록 하자!

 

LinkedList

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠르다는 장점을 가지고 있지만 다음과 같은 단점이 있다.

 

1. 크기를 변경할 수 없다.

-크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야한다.

-실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리 낭비가된다.

 

2.비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

-차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만, 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야한다.

 

이러한 배열의 단점을 보완하기 위해서 링크드 리스트라는 자료구조가 고안되었다. 

Linked List와 배열

위와 같이 각 요소들은 자신과 연결된 다음 요소에 대한 주소값과 데이터로 구성됨. 링크드 리스트에서 데이터의 삭제는 간단하다. 삭제하고자 하는 이전의 요소가 삭제하고자 하는 요소의 다음 요소를 참조하게 변경하면 된다. 배열처럼 복사하는 과정이 없기에 처리속도가 매우 빠르다.

 

하지만 링크드 리스트는 이동방향이 단방향이기에 다음 요소에 대한 접근은 쉬워도 이전요소로 접근하는 방식은 어렵다. 이점을 보완한 것이 더블 링크드 리스트이다. 보통 더블 링크드 리스트를 많이 사용한다.

하지만 단순 링크드 리스트보다 메모리를 하나 더 사용하는 것이므로 메모리의 낭비가 될 수 있으니 둘다 알아야함.

double linked List

ArrayList와 LinkedList 성능 비교

컬렉션	읽기(접근 시간)	추가 / 삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠르다. 비효율적인 메모리 사용
LinkedList	느리다	빠르다	데이터가 많을 수록 접근성이 떨어짐

다루고자 하는 데이터의 개수가 변하지 않는다면 ArrayList가 최상이겠지만 데이터의 변경이 잦다면 LinkedList를 사용하는게 더 나은 선택이 될 것이다. 아니면 처음 작업하기 전에 데이터를 저장할 때는 ArrayList를 사용하고 작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 수 있을 것이다.

 

컬렉션 프레임웍에 속한 대부분의 컬렉션 클래스들은 이처럼 서로 변환이 가능한 생성자를 제공하므로 이를 이용하면 간단히 다른 컬렉션 클래스로 데이터를 옮길 수 있다.

 

LinkedList에서 for문보다 Iterator가 유리한 이유

생활 코딩 설명

listIterator 내부 클래스로 구현

Stack과 Queue

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

 

ex) Queue q = new LinkedList();와 같은 방식으로 객체를 생성해서 사용하면 된다.

스택 구현방법은 606page를 참고하자

 

스택의 활용 예 - 수식 계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로

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

PriorityQueue

Queue인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이 있다. 그리고 null은 저장할 수 없다. null을 넣으면 NullPointerException이 발생한다. 

저장공간으로 배열을 사용하며, 각 공간을 힙(heap)이라는 자료구조의 형태로 저장한다. 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징이 있다. 숫자가 작을수록 우선순위가 더 높다.

 

*자료구조 힙(heap)은 앞서 배운 JVM의 힙(heap)과 이름만 같을 뿐, 전혀 다른것이다.

Deque(Double-Ended Queue)

Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Deque은 양쪽 끝에 추가/삭제가 가능. 조상은 Queue로 구현체로는 ArrayDeque와 LinkedList 등이 있다. 덱은 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로도, 큐로도 사용이 가능한 자료구조다.

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()	-
peekLast()	-	peek()

 

Enumeration -> Iterator -> ListIterator

위의 3개 모두 컬렉션에 저장된 요소를 접근하는데 사용 되는 인터페이스이다. Enumeration은 Iterator의 구버젼이며, ListIterator는 Iterator의 기능을 향상 시킨 것이다.

 

iterator()는 Collection인터페이스에 정의된 메서드이므로 Collection인터페이스의 자손인 List와 Set에도 포함되어 있다. 그래서 List나 Set인터페이스를 구현하는 컬렉션은 iterator()가 각 컬렉션의 특징에 알맞게 작성되어 있다. iterator()를 호출하여 Iterator를 얻은 다음 반복문, 주로 while문을 사용해서 컬렉션 클래스의 요소들을 읽어올 수 있다.

 

List클래스들은 저장순서를 유지하기 때문에 Iterator로 읽어와도 순서를 유지하지만 Set클래스들은 유지하지 않는다.

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

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

 

keySet() : map에 있는 key값만 다 가져오는 것.

entrySet() : map에 있는 데이터 key와 value를 둘다 가져온다.

 

 

Map map = new HashMap();

...

Iterator it = map.keySet().iterator();

1. map.entrySet()의 실행결과가 Set이므로

-Iterator list = map.entrySet().iterator(); -> Iterator list = Set인스턴스.iterator();

 

2. map.entrySet()를 통해 얻은 Set인스턴스의 iterater()를 호출해서 Iterator인스턴스를 얻는다

-Iterator list = Set인스턴스.iterator(); -> Iterator list = Iterator인스턴스;

 

3. 마지막으로 Iterator인스턴스의 참조가 list에 저장된다.

ListIterator와 Enumeration

Enumeration은 컬렉션 프레임웍이 생기기전에 사용하던 것으로 Iterator의 구버전이다. 이전 버전으로 작성된 소스와의 호환을 위해 남겨두고 있을 뿐이므로 가능하면 Iterator를 사용하자.

 

ListIterator는 Iterator를 상속받아서 기능을 추가한 것으로, 컬렉션의 요소에 접근할때 Iterator는 단방향으로만 이동할 수 있는데 반해 ListIterator는 양방향으로의 이동이 가능하다. 다만 ArrayList나 LinkedList와 같이 List계열에서만 가능

 

HashSet

HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이며, Set인터페이스의 특징대로 HashSet은 중복된 요소를 저장하지 않는다. HashSet에 새로운 요소를 추가할 때는 add메서드나 addAll메서드를 사용하는데, 만일 HashSet에 이미 저장되어 있는 요소와 중복된 요소를 추가하고자 한다면 이 메서드들은 false를 반환함으로써 중복된 요소이기 때문에 추가에 실패했다는 것을 알린다. 이러한 HashSet을 이용하면 컬렉션 내의 중복 요소들을 쉽게 제거할 수 있다.

 

그리고 만약 중복을 제거하는 동시에 저장한 순서를 유지하고자 한다면 HashSet대신 LinkedHashSet을 사용해야한다.

 

TreeSet

TreeSet은 이진검색트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 검색트리는 정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조이며 TreeSet은 이진 검색트리의 성능을 향상시킨 레드-블랙트리로 구현되어있 다. 그리고 Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.

 

이진 트리는 링크드리스트처럼 여러 개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 루트라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나갈 수 있다.

이진 트리의 노드를 코드로 표현하면 다음과 같다.

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

이진 검색 트리에 데이터 저장하는 방식

TreeSet에 저장되는 객체가 Comparable을 구현하던가 아니면, Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야한다. 그렇지 않으면 TreeSet에 객체를 저장할 때 예외가 발생함.

트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하고 삭제하는 경우 트리의 일부를 재구성해야하므로 링크드 리스트보다 데이터의 추가/삭제 시간은 더 걸린다. 대신 배열이나 링크드 리스트보다 검색과 정렬기능이 더 뛰어나다.

 

이진 검색트리의 특징

-모든 노드는 최대 두 개의 자식노드를 가질 수 있다.

-왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽자식노드의 값은 부모노드의 값보다 커야한다.

-노드의 추가 삭제에 시간이 걸린다.(순차적으로 저장하지 않으므로)

-검색(범위검색)과 정렬에 유리하다.

-중복된 값을 저장못한다.

HashMap과 HashTable

이 둘의 관계는 Vector와 ArrayList와 같아서 HashMap에 대해서만 설명하겠다. 

특징으로는 해싱을 사용해야 하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.

HashMap은 키와 값을 각각 Object타입으로 저장한다. 하지막 주로 키는 String을 대문자 또는 소문자로 사용한다.

키값은 저장된 값을 찾는데 사용되는 것이기에 컬렉션 내에서 유일해야한다.

 

Hashtable은 키나 값으로 null을 허용하지 않지만, HashMap은 허용한다. 그래서 map.put(null,null)이나 map.get(null);이 을 할 수 있다.

 

해싱과 해시함수

해싱이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.

 

해싱에서 사용하는 자료구조는 다음과 같이 배열과 링크드 리스트의 조합으로 이루어져 있다.

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장하게 된다. 이해를 돕기 위해 간호사가 환자의 데이터를 쉽게 얻는 방법으로 주민번호 앞자리를 기준으로 데이터를 분류해서 10개의 서랍에 나눠 담는 방법을 생각해 그 사람의 데이터를 쉽게 찾도록 했다.

정리

1. 검색하고자 하는 값의 키로 해시함수를 호출한다.

2. 해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 링크드 리스트를 찾는다.

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

이미 배운바와 같이 링크드 리스트는 검색에 불리한 조건이기 때문에 링크드 리스트의 크기가 커질수록 검색속도가 떨어지게 되므로 하나의 서랍에 데이터의 수가 많을수록 검색에 시간이 더 걸리는 것과 같다.

그래서 실생화는 맞지 않지만 하나의 서랍에 많은 데이터가 저장되어 있는 것보단 서랍에 하나의 데이터만 저장되어 있는 것이 더 빠른 검색결과를 얻을 수 있다.

 

하나의 링크드 리스트에 최소한의 데이터만 저장되려면, 저장될 데이터의 크기를 고려해서 HashMap의 크기를 적절하게 지정해줘야하고 해시함수가 서로 다른 키에 대해서 중복된 해시코드의 반환을 최소화해야한다. 그래야 HashMap에서 빠른 검색시간을 얻을 수 있다. 그렇기에 해싱을 구현하는 과정에서 제일 중요한 것은 해시함수의 알고리즘이다.

 

실제로는 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서 Object클래스에 정의된 hashCode()를 해시함수로 사용한다. Object클래스에 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일한 훌륭한 방법이다.

 

String클래스의 경우 Object로부터 상속받은 hashCode()를 오버라이딩해서 문자열의 내용으로 해시코드를 만들어 낸다. 그래서 서로 다른 String인스턴스일지라도 같은 내용의 문자열을 가졌다면 hashCode()를 호출하면 같은 해시코드 얻음

HashSet에서 이미 설명한 것과 같이 서로 다른 두 객체에 대해 equals()로 비교한 결과가 true인 동시에 hashCode()의 반환값이 같아야 같은 객체로 인식한다. HashMap도 같은 방식이며, equals()를 재정의 한다면 반드시 hashCode()도 같이 재정의해서 두 객체의 해시코드의 결과값이 같도록 해주어야한다.

안그러면 equals()호출 결과가 true지만 해시코드가 다른 두 객체를 서로 다른 것으로 인식하고 따로 저장할 것이다.

 

TreeMap

검색에 관한한 대부분의 경우에서 HashMap이 TreeMap보다 더 뛰어나므로 HashMap을 사용하는 것이 좋다.

 

Properties

Hashtable을 상속받아 구현한 것으로 (String,String)의 형태로 저장하는 보다 단순화된 컬렉션클래스다.

주로 애플리케이션의 환경설정과 관련된 속성을 저장하는데 사용되며 데이터를 파일로부터 읽고 쓰는 편리한 기능을 제공한다. 그래서 간단한 입출력은 Properties를 활용하면 몇 줄의 코드로 쉽게 해결된다.

 

Collections

Arrays가 배열과 관련된 메서드를 제공하는 것 처럼 Collections는 컬렉션과 관련된 메서드를 제공한다. fill(), copy(), sort(), binarySearch() 등의 메서드는 두 클래스 모두 포함되어 있으며 같은 기능을 한다.

*java.util.Collection은 인터페이스고 java.util.Collections는 클래스이다.

 

컬렉션의 동기화

멀티 쓰레드 프로그래밍에서는 하나의 객체가 여러 쓰레드가 동시에 접근할 수 있기 때문에 데이터의 일관성을 유지하기 위해서는 공유되는 객체에 동기화가 필요하다. Vector와 Hashtable같은 구버전의 클래스들은 자체적으로 동기화 처리가 되어 있는데, 멀티쓰레드 프로그래밍이 아닌 경우에는 불필요한 기능이 되어 성능을 떨어 뜨리는 요인이 된다. 그래서 추가된 ArrayList같은 애들은 자체적으로 처리하지않고 필요한 경우에만 동기화 메서드를 이용해서 동기화처리가 가능하도록 변경하였다. 그래서 가급적이면 ArrayList의 사용을 권장.

static Collection synchronizedCollection(Collection c)
static List synchronizedList(List list)
...

 

변경불가 컬렉션 만들기

컬렉션에 저장된 데이터를 보호하기 위해서 컬렉션을 변경할 수 없게, 즉 읽기 전용으로 만들어야 할 때가 있다. 주로 멀티 쓰레드 프로그래밍에서 여러 쓰레드가 하나의 컬렉션을 공유하다보면 데이터가 손상될 수 있는데, 이를 방지하려면 아래의 메서드들을 이용하자.

static Set unmodifiableSet(Set s)
static Map unmodifiableMap(Map m)
...

 

싱글톤 컬렉션 만들기

인스턴스를 new연산자가 아닌 메서드를 통해서만 생성할 수 있게 함으로써 생성할 수 있는 인스턴스의 개수를 제한하는 방법에 대해서 6장에서 배웠다. 이러한 기능을 제공하는 것이 바로 singleton으로 시작하는 메서드다.

static List singletonList(Object o)
static Set singleton(Object o)
static Map singletonMap(Object o)
...

매개변수로 저장할 요소를 지정하면, 해당 요소를 저장하는 컬렉션을 반환한다. 그리고 반환된 컬렉션은 변경할 수 없다.