Chapter 11 컬렉션 프레임웍
1. 컬렉션 프레임웍(Collection Framework)
컬렉션 프레임웍이란
데이터 군을 저장하는 클래스들을 표준화한 설계. JDK1.2 부터 등장
1.1 컬렉션 프레임웍의 핵심 인터페이스
컬렉션 프레임웍의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현
Collection
/ \ Map
List Set
[표11-1] 컬렉션 프레임웍의 핵심 인터페이스와 특징
| 인터페이스 | 특징 |
|---|---|
| List | 순서가 있는 데이터의 집합. 데이터의 중복을 허용 |
| Set | 순서를 유지하지 않는 데이터의 집합. 데이터의 중복을 허용하지 않음 |
| Map | 키(key)와 값(value)의 쌍(pair)으로 이루어진 데이터의 집합. 순서는 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용 |
컬렉션 클래스들의 이름 특징
- 구현한 인터페이스 이름이 클래스의 이름에 포함
- Vector, Stack, Hashable, Properties와 같은 클래스들은 컬렉션 프레임웍이 만들어지기 이전부터 존재하던 것이기 때문에 컬렉션 프레임웍의 명명법을 따르지 않음
- Vector나 Hashable과 같은 기존의 컬렉션 클래스들은 가능하면 사용하지 않는 것이 좋음
- 대신 새로 추가된 ArrayList와 HashMap 사용 권장
Collection인터페이스
Collection인터페이스란
List와 Set의 조상으로 컬렉션 클래스에 저장된 데이터를 읽고, 추가하고 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드들을 정의
[표11-2] Collection인터페이스에 정의된 메서드
| 메서드 | 설명 |
|---|---|
| boolean add(Object o), boolean addAll(Collection c) | 지정된 객체 또는 Collection의 객체들을 Collection에 추가 |
| void clear | Collection의 모든 객체를 삭제 |
| contains, containsAll | 지정된 객체 또는 Collection의 객체들이 Collection에 포함되어 있는지 확인 |
| equals | 동일한 Collection인지 비교 |
| hashCode | Collection의 hash code를 반환 |
| isEmpty | Collection이 비어있는지 확인 |
| iterator | Collection의 iterator를 얻어서 반환환 |
| remove, removeAll | 지정된 객체 또는 Collection에 포함된 객체들을 삭제 |
| retainAll | 지정된 Collection에 포함된 객체만을 남기고 다른 객체들은 Collection에서 삭제 |
| size | 저장된 객체의 개수를 반환 |
| toArray | 저장된 객체를 객체 배열(Object[])로 반환 |
List인터페이스
List인터페이스란
중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용
List
/ | \
Vector ArrayList LinkedList
|
Stack
[표11-3] List인터페이스의 메서드
| 메서드 | 설명 |
|---|---|
| void add(int index, Object element) boolean addAll(int index, Collection c) | 지정된 위치(index)에 객체(element) 또는 컬렉션에 포함된 객체들을 추가 |
| get | 지정된 위치(index)에 있는 객체 반환 |
| indexOf | 객체의 위치(index) 반환(List의 첫 번째 요소부터 순방향으로 찾음) |
| lastIndexOf | 객체의 위치(index)를 반환(List의 마지막 요소부터 역방향으로 찾음) |
| listIterator | List의 객체에 접근할 수 있는 ListIterator를 반환 |
| remove | 지정된 위치에 있는 객체를 삭제하고 삭제된 객체를 반환 |
| Object set(int index, Object element) | 지정된 위치에 객체를 저장 |
| void sort(Comparator) | 지정된 비교자(comparator)로 List정렬 |
| List subList(int fromIndex, int toIndex) | 지정된 범위에 있는 객체를 반환 |
Set인터페이스
Set인터페이스란
중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용
Set
/ |
HashSet SortedSet
|
TreeSet
Map인터페이스
Map인터페이스란
키(key)와 값(value)을 하나의 쌍으로 묶어서 저장. 키는 중복될 수 없지만 값은 중목을 허용. 중복된 키와 값을 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남음
Map
/ | \
Hashable HashMap SortedMap
| |
LinkedHashMap TreeMap
Map인터페이스에서 값(value)은 중복을 허용하기 때문에 Collection타입으로 반환하고 키(key)는 중복을 허용하지 않기 때문에 Set타입으로 반환
Map.Entry인터페이스
Map에 저장되는 key-value쌍을 다루기 위해서 Map인터페이스의 내부 인터페이스로 인터페이스 안에 인터페이스를 정의
[표11-5] Map.Entry인터페이스의 메서드
| 메서드 | 설명 |
|---|---|
| equals | 동일한 Entry인지 비교 |
| getKey | Entry의 key객체를 반환 |
| getValue | Entry의 value객체를 반환 |
| hashCode | Entry의 해시코드를 반환 |
| setValue | Entry의 value객체를 지정된 객체로 바꿈 |
1.2 ArrayList
- 가장 많이 사용되는 컬렉션 클래스
- 데이터의 저장순서가 유지되고 중복을 허용
- 기존의 Vector와 구현원리와 기능적인 측면에서 동일하지만 가능하면 Vector보다는 ArrayList를 사용
- Object배열을 이용해서 데이터를 저장하는데 배열에 저장 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장
[ArrayList의 소스코드 일부 - Object배열]
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable
{
...
transient Object[] elementData; // Object배열
...
}
ArrayList 생성 시, 실제 저장할 개수보다 약간 여유있는 크기로 하는 것이 좋다. 생성할 때 지정한 크기보다 더 많은 객체를 저장하면 자동적으로 크기가 늘어나기는 하지만 이 과정에서 처리시간이 많이 소요되기 때문이다.
[예제11-2]ArrayList생성
List list = new ArrayList(length/LIMIT + 10)); //크기를 약간 여유있게 잡는다.
ArrayList나 Vector 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야하기 때문에 상당히 효율이 떨어진다는 단점이 있다. 그래서 처음에 인스턴스를 생성할 때, 저장할 데이터의 개수를 잘 고려하여 충분한 용량의 인스턴스를 생성하는 것이 좋다.
List인터페이스 중 remove의 경우 이해하기 어려울 수도 있기 때문에 단계별로 설명한다.
- 삭제할 데이터의 아래에 있는 데이터를 한 칸씩 위로 복사해서 삭제할 데이터를 덮어쓴다.
System.arraycopy(data, 3, data, 2, 2) // data[3]에서 data[2]로 2개의 데이터를 복사하라는 의미 - 데이터가 모두 한 칸씩 위로 이동하였으므로 마지막 데이터는 null로 변경해야 한다.
data[size-1] = null; - 데이터가 삭제되어 데이터의 개수가 줄었으므로 size의 값을 1 감소시킨다.
size--;
위 과정을 통해 배워야 할 것은
배열에 객체를 순차적으로 저장할 때와 객체를 마지막에 저장된 것부터 삭제하면 System.arraycopy()를 호출하지 않기 때문에 작업시간이 짧지만, 배열의 중간에 위치한 객체를 추가하거나 삭제하는 경우 System.arraycopy()를 호출해서 다른 데이터의 위치를 이동시켜 줘야 하기 때문에 다루는 데이터의 개수가 많을수록 작업시간이 오래 걸린다는 것이다.
1.3 LinkedList
배열의 단점
1. 크기를 변경할 수 없다.
- 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사하는 작업이 필요하다.
- 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
- 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
- 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.
배열의 단점을 보완하기 위해 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다. 링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.
class Node {
Node next; // 다음 요소의 주소를 저장
Object obj; // 데이터를 저장
}
링크드 리스트의 삭제
삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.
링크드 리스트의 추가
추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다.
더블 링크드 리스트(이중 연결리스트, doybly linked list)
링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다. 이 점을 보완한 것이 더블 링크드 리스트이다. 더블 링크드 리스트는 단순히 링크드 리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드 리스트와 같다.
class Node {
Node object; // 다음 요소의 주소를 저장
Node previous;// 이전 요소의 주소를 저장
Object obj; // 데이터를 저장
}
실제로 LinkedList 클래스는 이름과 달리 링크드 리스트가 아닌 더블 써큘러 링크드 리스트로 구현했는데, 이는 링크드 리스트의 단점인 낮은 접근성을 높이기 위한 것이다.
ArrayList와 LinkedList의 차이
[예제11-5]
- 순차적으로 추가하기
- 중간에 추가하기
- 중간에서 삭제하기
- 순차적으로 삭제하기
결론1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
결론2. 중간에 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
예제에서는 ArrayList와 LinkedList의 차이를 비교하기 위해 데이터의 개수를 크게 잡았는데, 사실 데이터의 개수가 그리 크지 않다면 어느 것을 사용해도 큰 차이가 나지는 않는다. 그래도 ArrayList와 LinkedList의 장단점을 잘 이해하고 상황에 따라 적합한 것을 선택해서 사용하는 것이 좋다.
[예제11-6]
- 접근시간 테스트
배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 간단한 계산만으로 원하는 n번째 데이터의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있지만 LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다. 그래서 LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어오는 시간, 즉 접근시간이 길어진다는 단점이 있다.
[표11-8] ArrayList와 LinkedList의 비교
| 컬렉션 | 읽기(접근시간) | 추가/삭제 | 비고 |
|---|---|---|---|
| ArrayList | 빠르다 | 느리다 | 순차적인 추가삭제는 더 빠름. 비효율적인 메모리사용 |
| LinkedList | 느리다 | 빠르다 | 데이터가 많을수록 접근성이 떨어짐 |
데이터의 개수가 변하지 않을 경우라면, ArrayList가 최상의 선택이 되겠지만, 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이 될 것이다.
1.4 Stack과 Queue
Stack과 Queue의 기본 개념과 특징
스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)
큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)
그렇다면 스택과 큐를 구현하기 위해서는 어떤 컬렉션 클래스를 사용하는 것이 좋을까? 순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합하지만, 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 적합하다.
자바에서는 스택을 Stack클래스로 구현하여 제공하고 있지만 큐는 Queue인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 대신 Queue 인터페이스를 구현한 클래스들이 있어서 이 들 중의 하나를 선택해서 사용하면 된다.
PriorityQueue
Queue인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이 있다. 그리고 null은 저장할 수 없다. null을 저장하면 NullPointerException이 발생한다. 저장공간으로는 배열을 사용하며, 각 요소를 힙(heap)에 저장하며 힙은 잠시 뒤에 배울 이진 트리의 한 종류이다.
Deque(Double-Ended Queue)
Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Deque(덱 또는 디큐라고 읽음)은 양쪽 끝에 추가/삭제가 가능하다. 덱은 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다.
1.5 Iterator, ListIterator, Enumeration
Iterator, ListIterator, Enumeration은 모두 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스이다. Enumeration은 Iterator의 구버전이며, ListIterator는 Iterator의 기능을 향상 시킨 것이다.
Iterator
컬렉션에 저장된 각 요소에 접근하는 기능을 가진 Iterator인터페이스를 정의하고, Collection인터페이스에는 Iterator(Iterator를 구현한 클래스의 인스턴스)를 반환하는 iterator()를 정의하고 있다.
public interface Iterator {
dboolean hasNext();
Object next();
voud remove();
}
public interface Collection {
...
public Iterator iterator();
...
}
iterator()는 Collection인터페이스에 정의된 메서드이므로 Collection인터페이스의 자손인 List와 Set에도 포함되어 있다. 그래서 List나 Set인터페이스를 구현하는 컬렉션은 iterator()가 각 컬렉션의 특징에 알맞게 작성되어 있다. Iterator는 반복문, 주로 while문을 사용해서 컬렉션 클래스의 요소들을 읽어 올 때 사용된다. Iterator를 이용해서 컬렉션의 요소를 읽어오는 방법을 표준화하는 것은 코드의 재사용성을 높이는데 사용될 수 있다.
[표11-12] Iterator인터페이스의 메서드
| 메서드 | 설 명 |
|---|---|
| boolean hasNext() | 읽어올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환한다. |
| Object next() | 다음 요소를 읽어 온다. next()를 호출하기 전에 hasNext()를 호출해서 읽어올 요소가 있는지 확인하는 것이 안전하다. |
| void remove() | next()로 읽어 온 요소를 삭제한다. next()를 호출한 다음에 remove()를 호출해야 한다.(선택적 기능) |
ListIterator와 Enumeration
Enumeration은 컬렉션 프레임웍이 만들어지기 이전에 사용하던 것으로 Iterator의 구버전이라고 생각하면 된다. 이전 버전으로 작성된 소스와의 호환을 위해서 남겨두고 있을 뿐이므로 가능하면 Enumeration대신 Iterator를 사용하자.
Enumeration - Iterator의 구버전
ListIterator - Iterator에 양방향 조회기능추가
1.6 Arrays
Arrays클래스에는 배열을 다루는데 유용한 메서드가 정의되어 있다.
배열의 복사 - copuOf(), copyOfRange()
copyOf()는 배열 전체를,copyOfRange()는 배열의 일부를 복사해서 새로운 배열을 만들어 반환한다.
배열 채우기 - fill(), setAll()
fill()은 배열의 모든 요소를 지정된 값으로 채운다. setAll()은 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받는다
배열의 정렬과 검색 - sort(), binarySearch()
sort()는 배열을 정렬할 때, 그리고 배열에 저장된 요소를 검색할 때는 binarySearch()를 사용한다. binarySearch()는 배열에서 지정된 값이 저장된 위치(index)를 찾아서 반환하는데, 반드시 배열이 정렬된 상태이어야 올바른 결과를 얻는다. 그리고 만일 검색한 값과 일치하는 요소들이 여러 개 있다면, 이 중에서 어떤 것의 위치가 반환될지는 알 수 없다.
문자열의 비교와 출력 - equals(), toString()
toString()은 모든 요소를 문자열로 출력하는데 일차원 배열에만 사용할 수 있으므로, 다차원 배열에는 deepToString()을 사용해야 한다. equals는 두 배열에 저장된 모든 요소를 비교해서 가으같으면 true, 다르면 false를 반환한다. equals도 일차원 배열에서만 사용가능하므로, 다차원 배열의 비교에는 deepToEquals()를 사용해야 한다.
배열을 List로 변환 - asList(Object... a)
asList()는 배열을 List에 담아서 반환한다.
parallelXXX(), spliterator(), stream()
'parallel'로 시작하는 이름의 메서드들이 있는데 이 메서드들은 보다 빠른 결과를 얻기 위해 여러 쓰레드가 작업을 나누어 처리하도록 한다. spliterator()는 여러 쓰레드가 처리할 수 있게 하나의 작업을 여러 작업으로 나누는 Spliterator를 반환하며 stream()은 컬렉션을 스트림으로 변환한다.
1.7 Comparator와 Comparable
Comparator와 Comparable은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있으며, Comparator와 Comparable의 실제 소스는 다음과 같다.
public interface Comparator {
int compare(Object o1, Object o2);
boolean equals(Object obj);
}
public interface Comparable {
public int compareTo(Object o);
}
compare()와 compareTo()는 선언형태와 이름이 약간 다를 뿐 두 객체를 비교한다는 같은 목적으로 고안된 것이다. compareTo()의 반환값은 int지만 실제로 두 객체가 같으면 0, 비교하는 값보다 작으면 음수, 크면 양수를 반환하도록 구현해야 한다. 이와 마찬가지로 compare()도 객체를 비교해서 음수, 0, 양수 중의 하나를 반환하도록 구현해야 한다.
아래 코드는 Integer클래스의 일부이다. Comparable의 compareTo(Object o)를 구현해 놓은 것을 볼 수 있다. 두 Integer객체에 저장된 int값(value)을 비교해서 같으면 0, 크면 -1, 작으면 1을 반환하는 것을 알 수 있다.
public final class Integer extends Number implements Comparable {
...
public int compareTo(Object o) {
return compareTo((Integer)o);
}
public int compareTo(Integer anotherInteger) {
int thisVal = this.value;
int anotherVal = anotherInteger.value;
// 비교하는 값이 크면 -1, 같으면 0, 작으면 1을 반환한다.
return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
}
Comparable을 구현한 클래스들이 기본적으로 오름차순으로 정렬되어 있지만, 내림차순으로 정렬한다던가 아니면 다른 기준에 의해서 정렬되도록 하고 싶을 때 Comparator를 구현해서 정렬기준을 제공할 수 있다.
Comparable - 기본 정렬기준을 구현하는데 사용.
Comparator - 기본 정렬기준 외에 다른 기준으로 정렬하고자 할 때 사용.
간단한 예제를 통해서 실제로 어떻게 사용되는지 확인해 보자.
[예제11-19]
import java.util.*;
class ComparatorEx {
public static void main(String[] args) {
String[] strArr = {"cat", "Dog", "lion", tiger"};
Arrays.sort(strArr);
System.out.println(Arrays.toString(strArr));
// Dog, cat, lion, tiger
Arrays.sort(strArr, String.CASE_INSENSITIVE_ORDER);
System.out.println(Arrays.toString(strArr));
// cat, Dog, lion, tiger
Arrays.sort(strArr, new Descending());
System.out.println(Arrays.toString(strArr));
// tiger, lion, cat, Dog
}
}
class Descending implements Comparator {
public int compare(Object o1, Object o2) {
if(o1 instanceof Comparable && o2 instanceof Comparable) {
Comparable c1 = (Comparable)o1;
Comparable c2 = (Comparable) o2;
return c1.compareTo(c2) * -1; // -1을 곱해서 기본 정렬방식의 역으로 변경
}
return -1;
}
}
1.8 HashSet
HashSet이란
내부적으로 HashMap을 이용해서 만들어졌으며, Hashing 기법을 이용해서 구현한 Set인터페이스이다. https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html#HashSet--
HashSet에 요소를 추가할 때
HashSet에 요소를 추가할 때는 add 또는 addAll 메서드를 사용한다. 만약 이미 저장되어있는 요소와 중복된 요소를 추가하려고 하는 경우, 이 메서드들은 false를 반환함으로써 추가에 실패했다는 것을 알린다.
[예제 11-20]
import java.util.*;
public class Test {
public static void main(String[] args) {
Set set = new HashSet();
set.add(1);
set.add(2);
set.add(2);
set.add(3);
set.add(1);
System. out.println(set);
}
}
[1, 2, 3]
[예제 11-23]
import java.util.*;
public class Test {
public static void main(String[] args) {
HashSet set = new HashSet();
set.add("abc");
set.add("abc");
set.add(new Person ("david", 10));
set.add(new Person ("david", 10));
System.out.println(set);
}
}
class Person {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
public String toString() {
return name+":"+age;
}
}
[abc, david:10, david:10]
Person클래스는 name, age를 멤버변수로 갖는다. 위의 예제는 name, age가 같으면 같은 사람으로 인식하도록 작성하였다. 하지만 실행결과를 보면 두 인스턴스의 name, age가 같음에도 불구하고 서로 다른것으로 인식하여 'david:10'이 두번 출력되었다.
HashSet의 add메서드는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은 것인지 판별하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출하기 때문에, equals()와 haseCode()를 목적에 맞게 오버라이딩 해야한다.
[예제 11-24]
class Person {
String name;
int age;
Person (String name, int age) {
this.name = name;
this.age = age;
}
public boolean equals(Object obj) {
if(obj instanceof Person) {
Person tmp = (Person) obj;
return name.equals(tmp.name) && age==tmp.age;
}
return false;
}
public int hashCode() {
return (name+age).hashCode();
}
public String toString() {
return name+":"+age;
}
}
Person 클래스를 위와 같이 수정하고 다시 [예제 11-23]을 실행해보면 다음과 같은 실행결과가 출력된다.
[abc, david:10]
hashCode()의 조건
오버라이딩을 통해 작성된 hashCode()는 다음의 세 가지 조건을 만족시켜야 한다.
- 실행중인 어플리케이션 내의 동일한 객체에 대해서 여러번 hashCode()를 호출해도 동일한 값을 반환해야 한다. 하지만, 실행시마다 동일한 int값을 반환할 필요는 없다.
- equals 메서드를 이용한 비교에 의해 ture를 얻은 두 객체에 대해 각각 hashCode()를 호출해서 얻은 결과는 반드시 같아야한다.
- equals 메서드를 호출했을 때 false를 반환하는 두 객체는 hasCode() 호출에 대해 같은 int 값을 반환하는 경우가 있어도 괜찮지만, 해싱을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int값을 반환하는 것이 좋다.
두 객체에 대해 equals 메서드를 호출한 결과가 true이면, 두 객체의 해시코드는 반드시 같아야하지만,
두 객체의 해시코드가 같다고 해서 equals 메서드의 호출결과가 반드시 true인 것은 아니다.
1.9 TreeSet
TreeSet이란
- 이진검색트리 형태로 데이터를 저장하는 컬렉션 클래스이다.
- Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며, 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.
이진검색트리는 왼쪽 노드의 값 < 부모 노드의 값 < 오른쪽 노드의 값 순서로 저장하는 이진트리이다. 따라서, 왼쪽 노드 - 부모 노드 - 오른쪽 노드 순으로 읽어오면 오름차순으로 정렬된 순서를 얻을 수 있다. TreeSet은 이처럼 정렬된 상태를 유지하기 때문에 단일값 검색, 범위검색이 매우 빠르다.
문자열의 경우 , 정렬순서는 문자의 코드값이 기준이 된다.
공백 < 숫자 < 대문자 < 소문자
컴퓨터는 알아서 값을 비교하지 못한다.
TreeSet은 데이터를 정렬된 상태로 저장한다. TreeSet을 생성할 때 Comparator를 지정해주지 않으면 저장하는 객체에 구현된 정렬방식에 따라 정렬하여 저장하게 되고, Comparator를 지정해주면 지정된 정렬방식에 떄라 정렬하여 저장한다.
https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html
public static void main(String[] args) {
TreeSet set = new TreeSet(new Comparator() {
public int compare(Object o1, Object o2) {
if(o1 instanceof Student && o2 instanceof Student) {
Student s1 = (Student)o1;
Student s2 = (Student)o2;
return (int)(s1.getAverage() - s2.getAverage());
}
return -1;
}
});
[출처] 남궁성의 코드초보스터디
1.10 HashMap과 Hashtable
HashMap이란
- Map 인터페이스를 구현했으므로 Key, Value를 하나의 데이터로 저장한다.
- 해싱기법을 사용하기 때문에, 많은 양의 데이터를 검색하는 데 뛰어난 성능을 보인다.
HashMap, HashTable의 관계
해싱을 구현한 컬렉션 클래스는 HashSet, HashMap, HashTable이 있는데, 컬렉션 프레임웍이 도입되면서 HashTable이 HashMap으로 대체되었다. HashTable은 호환성을 위해 남겨두고 있는 것이기 때문에, HashMap을 사용할 것을 권장한다.
추가적으로 Hashtable은 key, value로 null을 허용하지 않지만, HashMap은 null을 허용한다. 그래서 HashMap에서는 map.put(null,null) 과 같이 할 수 있다.
HashMap
HashMap은 key, value를 각각 (Object, Object)형태로 저장하기 때문에 어떠한 객체도 저장할 수 있다. key는 주로 String을 대문자 또는 소문자로 통일해서 사용하곤 한다. key는 컬렉션 내에서 유일해야 하고(저장된 value를 찾는데 사용되는 것이기 때문에), value는 데이터의 중복을 허용한다.
[예제 11-30]
HashMap map = new HashMap();
map.put("myId", "1234");
map.put("aaa", "1111");
map.put("aaa", "2222");
위와 같이 HashMap을 생성하고 데이터를 저장하면
| key | value |
|---|---|
| myId | 1234 |
| aaa | 2222 |
3개의 데이터 쌍을 저장했지만 실제로는 2개의 데이터 쌍만 저장된다. 세번째로 저장한 "aaa" key는 이미 존재하기 때문에, 새로 추가되지 않고 기존의 value 값을 덮어썼다.
Map에서 value는 중복을 허용하지만, key는 중복을 허용하지 않기 때문에 저장하려는 두 데이터 중에서 어느 쪽을 key로 할 것인지 잘 결정해야한다.
해싱과 해시함수
해싱이란, 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에, 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.
해싱에서 사용하는 자료구조
배열과 링크드 리스트의 조합으로 되어있다. 저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결된 링크드 리스트에 저장하게 된다.
예를 들어, 병원에서 수많은 환자를 분류할 때 생년을 기준으로 같은 연대생끼리 같은 서랍에 분류할 수 있다.
서랍은 해싱에서 사용되는 자료구조 중 배열의 각 요소를 의미하며, 배열의 각 요소에는 링크드리스트가 저장되어있어서 실제 저장한 데이터는 링크드 리스트에 담겨지게 된다.
HashMap에 저장된 데이터를 찾는 과정
- 검색하고자 하는 값의 키로 해시함수를 호출한다.
- 해시함수의 계산결과인 해시코드를 이용해서, 해당 값이 저장되어있는 링크드리스트를 찾는다.
- 링크드리스트에서 검색한 키와 일치하는 데이터를 찾는다.
링크드리스트는 검색에 불리한 자료구조이기 때문에 크기가 커질수록 검색속도가 떨어진다. 반면에 배열은 크기가 커져도 원하는 요소가 몇번째에 있는지만 알면 빠르게 원하는 값을 찾을 수 있다.
배열의 n번째 요소의 주소 = 배열의 시작주소 + type의 size * n
1.11 TreeMap
TreeMap이란
- 이진검색트리의 형태로 key, value 데이터를 `저장한다.
- 이진검색트리를 사용하기 때문에 검색과 정렬에 적합한 컬렉션 클래스이다.
HashMap, TreeMap 일반적으로 HashMap이 더 뛰어나지만, 범위검색이나 정렬이 필요한 경우 TreeMap을 사용한다. TreeMap은 key 값들에 대한 정렬이 이루어지기 때문이다.
1.12 Properties
Properties란
- HashMap의 구버전인 Hashtable을 상속받아 구현한 것이다.
- 보다 단순화된 컬렉션 클래스이다. Hashtable(Object, Object), Properties(String, String)
Properties의 사용
주로 어플리케이션의 환경설정과 관련된 속성을 저장하는데 사용한다. 데이터를 파일로부터 읽고 쓰는 기능을 제공하기 때문에, 간단한 입출력은 고작 몇줄의 코드고 쉽게 해결이 가능하다.
Properties prop = new Properties();
prop.setProperty("timeout", "30");
prop.setProperty("language", "kr");
prop.setProperty("size", "10");
prop.setProperty("capacity", "10");
System.out.println(prop);
prop.list(System.out);
//Properties에 저장된 모든 데이터를 화면 또는 파일에 출력
Object setProperty(String key, String value)
단순히 Hashtable의 put메서드를 호출할 뿐이다. 그리고 setProperty()는 기존에 같은 키로 저장된 값이 있는 경우 그 값을 Object 타입으로 반환하며, 그렇지 않을 때는 null을 반환한다.
Stirng getProperty(String key) Stirng getProperty(String key, String defaultValue)
Properties에 저장된 값을 읽어오는 역할을 하는데, 읽어오려는 키가 존재하지 않으면 지정된 기본값을 반환한다.
1.13 Collections
Collections 란
- Collections는 컬렉션과 관련된 메서드를 제공한다.
- Collection은 인터페이스이고, Collections는 클래스이다.
컬렉션의 동기화
멀티스레드 프로그래밍에서는 하나의 객체를 여러 스레드가 공유하기 때문에, 데이터 일관성을 유지하기 위해 공유되는 객체에 대한 동기화가 필요하다.
원래 Vector, Hashtable의 클래스들은 자체적으로 동기화 처리가 되어있는데, 멀티스레드 프로그래밍이 아닌 경우에는 불필요한 기능이 되어 오히려 성능을 떨어뜨리는 요인이 되었다.
그래서 ArrayList, HashMap 컬렉션은 동기화를 자체적으로 처리하지 않고, 필요한 경우에만 java.util.collections 의 동기화 메서드를 이용해서 처리하도록 되어있다.
Collections 클래스에는 다음과 같은 동기화 메서드를 제공하고 있으므로, 동기화가 필요할 때 해당하는 것을 골라서 사용하면 된다.
static Collection syncronizedCollection(Collection c)
static List syncronizedList(List l)
static Set syncronizedSet(Set s)
static Map syncronizedMap(Map m)
static SortedSet syncronizedSortedSet(SortedSet s)
static SotredMap syncronizedSortedMap(SotredMap m)
변경불가 컬렉션 만들기
컬렉션에 저장된 데이터를 보호하기 위해 읽기전용으로 만들어야 할 때 사용한다. 주로 멀티스레드 프로그래밍에서 여러 스레드가 하나의 컬렉션을 공유하다보면 데이터가 손상될 수 있는데 이를 방지하기 위해 아래의 메서드를 사용한다.
static Collection unmodifiableCollection(Collection c)
static List unmodifiableList(List l)
static Set unmodifiableSet(Set s)
static Map unmodifiableMap(Map m)
static SortedSet unmodifiableSortedSet(SortedSet s)
static NavigableSet unmodifiableNavigableSet(Set s)
static SotredMap unmodifiableSortedMap(SotredMap m)
static NavigableMap unmodifiableNavigableMap(Map m)
싱글톤 컬렉션 만들기
인스턴스를 new연산자가 아닌 메서드를 통해서만 생성할 수 있게 함으로써 생성할 수 있는 인스턴스의 개수를 제한하는 방법이다.
static List singletonList(Object o)
static Set singleton(Object o)
static Map singletonMap(Object key, Object value)
매개변수로 저장할 요소를 지정하면, 해당 요소를 저장하는 컬렉션을 반환한다. 그리고 반환된 컬렉션은 변경할 수 없다.
한 종류의 객체만 저장하는 컬렉션 만들기
컬렉션에 모든 객체를 저장할 수 있다는 것은 장점이면서 단점이다. 컬렉션에 지정된 종류의 객체만 저장할 수 있도록 제한하고 싶을 때는 아래의 메서드를 사용한다.
staic Collection checkedCollection (Collection c, Class type)
staic List checkedList(List list, Class type)
static Set checkedSet(Set s, Class type)
static Map checkedMap(Map m, Class keyType, Class valueType)
... (p.665)
Collections 클래스의 메서드들은 static 메서드이기 때문에,
Collections.sort(computers) 이런식으로 바로 사용할 수 있다.
1.14 컬렉션 클래스 정리 & 요약
https://prashantgaurav1.files.wordpress.com/2013/12/java-util-collection.gif