Collection Framework

해당 포스팅의 내용은 Java의 정석 2권 - Chapter 11 컬렉션 프레임웍에 있는 내용을 요약한 것입니다. 해당 책으로 복습하며 정리한 내용이고 문제가 된다면 바로 해당 포스팅을 삭제하도록 하겠습니다.

컬렉션 프레임웍

Java API 문서에서는 컬렉션 프레임웍을 **’데이터 군(group)을 다루고 표현하기 위한 단일화된 구조’**라고 정의하고 있다.

JDK 1.2부터 컬렉션 프레임웍이 등장하면서 다양한 종류의 컬렉션 클래스가 추가되고 모든 컬렉션 클래스를 표준화된 방식으로 다룰 수 있도록 체계화되었다.

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

컬렉션 프리임웍에서는 컬렉션(데이터 그룹)을 크게 3가지 타입으로 구분하여 3가지 인터페이스를 정의했다. 그리고 인터페이스 중 List와 Set의 공통된 부분을 다시 뽑아서 새로운 인터페이스은 Collection을 추가로 정의하였다.

인터페이스 List와 Set을 구현한 컬렉션 클래스들은 서로 많은 공통부분이 있어서, 공통된 부분을 다시 뽑아 Collection 인터페이스를 정의할 수 있었지만 Map 인터페이스는 이들과는 전혀 다른 형태로 컬렉션을 다루기 때문에 같은 상속계층도에 포함되지 못했다.

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

Vector, Stack, Hashtable, Properties와 같은 클래스들은 컬렉션 프레임웍이 만들어지기 이전부터 존재하던 것이기 때문에 컬렉션 프레임웍의 명명법을 따르지 않는다.

Vector나 Hashtable과 같은 기존의 컬렉션 클래스들은 호환을 위해, 설계를 변경해서 남겨두었지만 가능하면 사용하지 않는 것이 좋다. 그 대신 새로 추가된 ArrayList와 HashMap을 사용하자.

Collection 인터페이스

List와 Set의 조상인 Collection 인터페이스에는 다음과 같은 메서드들이 정의되어 있다. Collection 인터페이스는 컬렉션 클래스에 저장된 데이터를 읽고, 추가하고 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드들을 정의하고 있다.

• boolean add(Object o) : 지정된 객체(o)를 Collection에 추가한다.
• boolean addAll(Collection c) : 지정된 Collection(c)의 객체들을 Collection에 추가한다.
• void clear() : Collection의 모든 객체를 삭제한다.
• boolean contains(Object o) : 지정된 객체(o)가 Collection에 포함되어 있는지 확인한다.
• boolean equals(Object o) : 동일한 Collection인지 비교한다.
• int hashCode() : Collection의 hash code를 반환한다.
• boolean isEmpty() : Collection이 비어있는지 확인한다.
• Iterator iterator() : Collection의 Iterator를 얻어서 반환한다.
• boolean remove(Object o) : 지정된 객체를 삭제한다.
• int size() : Collection에 저장된 객체의 개수를 반환한다.
• Object[] toArray() : Collection에 저장된 객체를 객체배열(Object[])로 반환한다.
• Object[] toArray(Object[] a) : 지정된 배열에 Collection의 객체를 저장해서 반환한다.

List 인터페이스

List 인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다.

• void add(int index, Object element) : 지정된 위치(index)에 객체(element) 또는 컬렉션에 포함된 객체들을 추가한다.
• Object get(int index) : 지정된 위치(index)에 있는 객체를 반환한다.
• int indexOf(Object o) : 지정된 객체의 위치(index)를 반환한다. (List의 첫 번째 요소부터 순방향으로 찾는다.)
• lastIndexOf(Object o) : 지정된 객체의 위치(index)를 반환한다. (List의 마지막 요소부터 역방향으로 찾는다.)
• ListIterator listIterator() : List의 객체에 접근할 수 있는 ListIterator를 반환한다.
• Object remove(int index) : 지정된 위치(index)에 있는 객체를 삭제하고 삭제된 객체를 반환한다.
• Object set(int index, Object element) : 지정된 위치(index)에 객체(element)를 저장한다.
• void sort(Comparator c) : 지정된 비교자(comparator)로 List를 정렬한다.
• List subList(int fromIndex, int toIndex) : 지정된 범위(fromIndex 부터 toIndex)에 있는 객체를 반환한다.

Set 인터페이스

Set 인터페이스는 중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용된다.

Map 인터페이스

Map 인터페이스는 키(key)와 값(value)을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는 데 사용된다. 키는 중복될 수 없지만 값은 중복을 허용한다. 구현 클래스로는 Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap 등이 있다.

• void clear() : Map의 모든 객체를 삭제한다.
• boolean containsKey(Object key) : 지정된 key객체와 일치하는 Map의 Key객체가 있는지 확인한다.
• boolean containsValue(Object value) : 지정된 value객체와 일치하는 Map의 Value객체가 있는지 확인한다.
• Set entrySet() : Map에 저장되어 있는 key-value 쌍을 Map.Entry 타입의 객체로 저장한 Set으로 반환한다.
• booelan equals(Object o) : 동일한 Map인지 비교한다.
• Object get(Object key) : 지정한 key객체에 대응하는 value객체를 찾아서 반환한다.
• int hashCode() : 해시코드를 반환한다.
• boolean isEmpty() : Map이 비어있는지 확인한다.
• Set keySet() : Map에 저장된 모든 Key객체를 반환한다.
• Object put(Object key, Object value) : Map에 value객체를 key객체에 연결(mapping)하여 저장한다.
• void putAll(Map t) : 지정된 Map의 모든 key-value 쌍을 추가한다.
• Object remove(Object key) : 지정한 key객체와 일치하는 key-value객체를 삭제한다.
• int size() : Map에 저장된 key-value 쌍의 개수를 반환한다.
• Collection values() : Map에 저장된 모든 value객체를 반환한다.

Map 인터페이스에서 값(value)은 중복을 허용하기 때문에 Collection 타입으로 반환하고, 키(key)는 중복을 허용하지 않기 때문에 Set 타입으로 반환한다.

Map.Entry 인터페이스

Map.Entry 인터페이스는 Map 인터페이스의 내부 인터페이스이다. 내부 클래스와 같이 인터페이스도 인터페이스 안에 인터페이스를 정의하는 내부 인터페이스(inner interface)를 정의하는 것이 가능하다.

Map에 저장되는 key-value 쌍을 다루기 위해 내부적으로 Entry 인터페이스를 정의해 놓았다.

• boolean equals(Object o) : 동일한 Entry인지 비교한다.
• Object getKey() : Entry의 key객체를 반환한다.
• Object getValue() : Entry의 value객체를 반환한다.
• int hashCode() : Entry의 해시코드를 반환한다.
• Object setValue(Object value) : Entry의 value객체를 지정된 객체로 바꾼다.

ArrayList

List 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다.

ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면은 동일하다.

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

(Vector는 capacity가 부족할 경우 자동적으로 기존의 크기보다 2배의 크기로 증가된다. 그러나 생성자 Vector(int initialCapacity, int capacityIncrement)를 사용해서 인스턴스를 생성한 경우에는 지정해준 capacityIncrement만큼 증가하게 된다.)

배열은 크기를 변경할 수 없기 때문에 ArrayList나 Vector 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야 할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야하기 때문에 상당히 효율이 떨어진다는 단점을 가지고 있다.

LinkedList

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

1. 크기를 변경할 수 없다.
   • 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사하는 작업이 필요 하다.
   • 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
   • 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
   • 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.

이러한 배열의 단점을 보완하기 위해서 링크드 리스트(linked list)라는 자료구조가 고안되었다. 배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.

링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

class Node {
    Node next;  // 다음 요소의 주소를 저장
    Object obj; // 데이터를 저장
}

링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다. 이 점을 보완한 것이 더블 링크드 리스트(이중 연결리스트, doubly linked list)이다.

더블 링크드 리스트는 링크드 리스트보다 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트보다 더 많이 사용된다.

class Node {
    Node next;     // 다음 요소의 주소를 저장
	Node previous; // 이전 요소의 주소를 저장
    Object obj;    // 데이터를 저장
}

더블 링크드 리스트의 접근성을 보다 향상시킨 것이 ‘더블 써큘러 링크드 리스트(이중 연결형 연결 리스트)’이다. 단순히 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다.

실제로 LinkedList 클래스는 이름과 달리 ‘링크드 리스트’가 아닌 ‘더블 링크드 리스트’로 구현되어 있는데, 이는 링크드 리스트의 단점인 낮은 접근성(accessability)을 높이기 위한 것이다.

1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
   만약 ArrayList의 크기가 충분하지 않으면, 새로운 크기의 ArrayList를 생성하고 데이터를 복사하는 일이 발생하게 되므로 순차적으로 데이터를 추가해도 ArrayList보다 LinkedList가 더 빠를 수 있다.
   순차적으로 삭제한다는 것은 마지막 데이터부터 역순으로 삭제해나간다는 것을 의미하며, ArrayList는 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠르다. (단지 마지막 요소의 값을 null로만 바꾸면 되기 때문이다.)

2. 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
   LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠르다. 반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 늦다. 사실 데이터의 개수가 그리 크지 않다면 어느 것을 사용해도 큰 차이가 나지는 않는다.

3. 데이터의 개수가 많아질수록 데이터를 읽어 오는 시간, 즉 접근시간(access time)은 ArrayList가 LinkedList보다 빠르다.
   배열의 경우 만일 n번째 원소의 값을 얻어 오고자 한다면 단순히 아래와 같은 수식을 계산함으로써 해결된다. (배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문이다.)

   n번째 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

   그러나, LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이 아니기 때문에 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다.

Stack과 Queue

순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합하지만, 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList와 같은 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다. 그래서 큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

• Stack의 메서드
  • boolean empty() : Stack이 비어있는지 알려준다.
  • Object peek() : Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지는 않음.
  • Object pop() : Stack의 맨 위에 저장된 객체를 꺼낸다.
  • Object push(Object item) : Stack에 객체(item)를 저장한다.
  • int search(Object o) : Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환. 못찾으면 -1을 반환.
• Queue의 메서드
  • boolean add(Object o) : 지정된 객체를 Queue에 추가한다.
  • Object remove() : Queue에서 객체를 꺼내 반환.
  • Object element() : 삭제없이 요소를 읽어온다.
  • boolean offer(Object o) : Queue에 객체를 저장.
  • Object poll() : Queue에서 객체를 꺼내서 반환. 비어있으면 null을 반환
  • Object peek() : 삭제없이 요소를 읽어 온다. Queue가 비어있으면 null을 반환

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

PriorityQueue

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

Deque(Double-Ended Queue)

Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Deque은 양쪽 끝에 추가/삭제가 가능하다. Deque의 조상은 Queue이며, 구현체로는 ArrayDeque와 LinkedList 등이 있다.

덱은 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다.

Iterator, ListIterator, Enumeration

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

Iterator

컬렉션 프레임웍에서는 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화하였다. 컬렉션에 저장된 각 요소에 접근하는 기능을 가진 Iterator인터페이스를 정의하고, Collection인터페이스에는 Iterator를 반환하는 iterator()를 정의하고 있다.

iterator()는 Collection인터페이스에 정의된 메서드이므로 Collection인터페이스의 자손인 List와 Set에도 포함되어 있다. 그래서 List나 Set인터페이스를 구현하는 컬렉션은 iterator()가 각 컬렉션의 특징에 알맞게 작성되어 있다.

• boolean hasNext() : 읽어 올 요소가 남아있는지 확인한다.
• Object next() : 다음 요소를 읽어 온다. next()를 호출하기 전에 hasNext()를 호출해서 읽어 올 요소가 있는지 확인하는 것이 안전하다.
• void remove() : next()로 읽어 온 요소를 삭제한다.

ListIterator와 Enumeration

Enumeration은 컬렉션 프레임웍이 만들어지기 이전에 사용하던 것으로 Iterator의 구버젼이라고 생각하면 된다.

ListIterator는 Iterator를 상속받아서 기능을 추가한 것으로, 컬렉션의 요소에 접근할 때 Iterator는 단방향으로만 이동할 수 있는 데 반해 ListIterator는 양방향으로의 이동이 가능하다. 다만 List인터페이스를 구현한 컬렉션에서만 사용할 수 있다.

Arrays

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

배열의 복사 - copyOf(), copyOfRagne()

copyOf()는 배열 전체를, copyOfRange()는 배열의 일부를 복사해서 새로운 배열을 만들어 반환한다. copyOfRange()에 지저왼 범위의 끝은 포함되지 안는다.

배열 채우기 - fill(), setAll()

fill()은 배열의 모든 요소를 지정된 값으로 채운다. setAll()은 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받는다. 이 메서드를 호출할 때는 함수형 인터페이스를 구현한 객체를 매개변수로 지정하던가 아니면 람다식을 지정해야 한다.

배열의 정렬과 검색 - sort(), binarySearch()

sort()는 배열을 정렬할 때, 그리고 배열에 저장된 요소를 검색할 때는 binarySearch()를 사용한다. binarySearch()는 배열에서 지정된 값이 저장된 위치(index)를 찾아서 반환하는데, 반드시 배열이 정렬된 상태이어야 올바른 결과를 얻는다. (검색한 값과 일치하는 요소가 여러 개 있다면, 이 중 어떤 것의 위치가 반환될지는 알 수 없다.)

문자열의 비교와 출력 - equals(), toString(), deepEquals(), deepToString()

toString()은 배열의 모든 요소를 문자열로 편하게 출력할 수 있다. toString은 일차원 배열에만 사용할 수 있으므로, 다차원 배열에서는 deepToString()을 사용해야 한다. deepToString()은 배열의 모든 요소를 재귀적으로 접근해서 문자열을 구성하므로 2차원뿐만 아니라 3차원 이상의 배열에 대해서도 동작한다.

equals()는 두 배열에 저장된 모든 요소를 비교해서 같으면 true, 다르면 false를 반환한다. equals()도 일차원 배열에만 사용가능하므로, 다차원 배열의 비교에는 deepEquals()를 사용해야 한다.

배열을 List로 변환 - asList(Object… a)

asList()는 배열을 List에 담아서 반환한다. 한 가지 주의할 점은 asList()가 반환한 List의 크기를 변경할 수 없다는 것이다. 저장된 내용은 변경 가능하나, 추가 또는 삭제가 불가능하다. 만약 크기를 변경할 수 있는 List가 필요하다면 다음과 같이 하면 된다.

List list = new ArrayList(Arrays.asList(1, 2, 3, 4, 5));

parallelXXX(), spliterator(), stream()

parallel로 시작하는 이름의 메서드는 빠른 결과를 얻기 위해 여러 쓰레드가 작업을 나누어 처리하도록 한다. spliterator()는 여러 쓰레드가 처리할 수 있게 하나의 작업을 여러 작업으로 나누는 Spliterator를 반환하며, stream()은 컬렉션을 스트림으로 변환한다.

Comparator와 Comparable

Comparator와 Comparable은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있으며, Comparable을 구현하고 있는 클래스들은 같은 타입의 인터페이스끼리 서로 비교할 수 있는 클래스들(주로 wrapper클래스)이 있으며, 기본적으로 오름차순으로 구현되어 있다. 그래서 Comparable을 구현한 클래스는 정렬이 가능하다는 것을 의미한다.

public interface Comparator {
    int compare(Object o1, Object o2);
    boolean equals(Object obj);
}

public interface Comparable {
	public int compareTo(Object o);
}

Comparator의 compare()와 Comparable의 compareTo()는 두 객체를 비교한다는 같은 기능을 목적으로 만들어 졌다. compareTo()는 반환값은 int지만 실제로는 비교하는 두 객체가 같으면 0, 비교하는 값보다 작으면 음수, 크면 양수를 반환하도록 구현해야한다. compare()도 객체를 비교해서 음수, 0, 양수 중의 하나를 반환하도록 구현해야한다.

Comparable : 기본 정렬기준(오름차순)을 구현하는데 사용.

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

Arrays.sort()는 배열을 정렬할 때, Comparator를 지정해주지 않으면 저장하는 객체에 구현된 내용에 따라 정렬된다.

static void sort(Object[] a) // 객체 배열에 저장된 객체가 구현한 Comparable에 의한 정렬
static void sort(Object[] a, Comparator c) // 지정한 Comparator에 의한 정렬

HashSet

HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이며, Set인터페이스의 특징대로 HashSet은 중복된 요소를 저장하지 않는다.

ArrayList와 같이 List인터페이스를 구현한 컬렉션과 달리 HashSet은 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.

HashSet은 내부적으로 HashMap을 이용해서 만들어졌으며, HashSet이란 이름은 해싱(hasing)을 이용해서 구현했기 때문에 붙여진 것이다.

HashSet의 add메서드는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은 것인지 판별하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출하기 때문에 equals()와 hashCode()를 목적에 맞게 오버라이딩해야 한다.

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

1. 실행 중인 애플리케이션 내의 동일한 객체에 대해서 여러 번 hashCode()를 호출해도 동일한 int 값을 반환해야 한다. 하지만, 실행시마다 동일한 int값을 반환할 필요는 없다.
   (String 클래스는 문자열의 내용으로 해시코드를 만들어 내기 때문에 내용이 같은 문자열에 대한 hashCode() 호출은 항상 동일한 해시코드를 반환한다. 반면에 Object클래스는 객체의 주소로 해시코드를 만들어 내기 때문에 실행할 때마다 해시코드값이 달라질 수 있다.)
2. equals메서드를 이용한 비교에 의해서 true를 얻은 두 객체에 대해 각각 hashCode()를 호출해서 얻은 결과는 반드시 같아야 한다.
3. equals메서드를 호출했을 때 false를 반환하는 두 객체는 hashCode() 호출에 대해 같은 int값을 반환하는 경우가 있어도 괜찮지만, 해싱(hashing)을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int값을 반환하는 것이 좋다.

TreeSet

TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 검색 트리는 정렬, 검색, 범위검색(range search)에 노은 성능을 보이는 자료구조이며 TreeSet은 이진 검색 트리의 성능을 향상시킨 ‘레드-블랙 트리(Red-Black tree)’로 구현되어 있다.

Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.

HashMap과 Hashtable

Hashtable과 HashMap의 관계는 Vector와 ArrayList의 관계와 같아서 Hashtable보다는 새로운 버전인 HashMap을 사용할 것을 권한다.

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

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
    transient Entry[] table;
    //...
    static class Entry implements Map.Entry {
        final Object key;
        Object value;
        //...
    }
}

HashMap은 Entry라는 내부 클래스를 다시 정의하고, 다시 Entry타입의 배열을 선언하고 있다. 키(key)와 값(value)은 별개의 값이 아니라 서로 관련된 값이기 때문에 각각의 배열로 선언하기 보다는 하나의 클래스로 정의해서 하나의 배열로 다루는 것이 데이터의 무결성적인 측면에서 더 바람직하기 때문이다.

HashMap은 키와 값을 각각 Object타입으로 저장한다. 즉 어떠한 객체도 저장할 수 있지만 키는 주로 String을 대문자 또는 소문자로 통일해서 사용하곤 한다.

• Set entrySet() : HashMap에 저장된 키와 값을 엔트리(키와 값의 결합)의 형태로 Set에 저장해서 반환
• Object get(Object key) : 지정된 키(key)의 값(객체)을 반환. 못찾으면 null 반환
• Set keySet() : HashMap에 저장된 모든 키가 저장된 Set을 반환
• Object put(Object key, Object value) : 지정된 키와 값을 HashMap에 저장
• Collection values() : HashMap에 저장된 모든 값을 컬렉션의 형태로 반환

해싱과 해시함수

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

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

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장하게 된다.

1. 검색하고자 하는 값의 키로 해시함수를 호출한다.
2. 해시함수의 계산결과인 해시코드를 이용해서 해당 값이 저장되어 있는 링크드 리스트를 찾는다.
3. 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.

링크드 리스트는 검색에 불리한 자료구조이기 때문에 링크드 리스트의 크기가 커질수록 검색속도가 떨어지게 된다.

하나의 링크드 리스트에 최소한의 데이터만 저장되려면, 저장될 데이터의 크기를 고려해서 HashMap의 크기를 적절하게 지정해주어야 하고, 해시함수가 서로 다른 키에 대해서 중복된 해시코드의 반환을 최소화해야 한다. 그래야 HashMap에서 빠른 검색시간을 얻을 수 있다.

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

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

HashSet과 마찬가지로 HashMap에서도 서로 다른 두 객체에 대해 equals()로 비교한 결과가 true인 동시에 hashCode()의 반환값이 같아야 같은 객체로 인식한다. (이미 존재하는 키에 대한 값을 저장하면 기존의 값을 새로운 값으로 덮어쓴다.)

그래서 새로운 클래스를 정의할 때 equals()를 오버라이딩해다 한다면 hashCode()도 같이 오버라이딩해서 equals()의 결과가 true인 두 객체의 해시코드가 항상 같도록 해주어야 한다.

그렇지 않으면 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 equals()의 호출결과가 true지만 해시코드가 다른 두 객체를 서로 다른 것으로 인식하고 따로 저장할 것이다.

TreeMap

TreeMap은 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다. 그래서 검색과 정렬에 적합한 컬렉션 클래스이다.

검색에 관한 대부분의 경우에서는 HashMap이 TreeMap보다 더 뛰어나므로 HashMap을 사용하는 것이 좋다. 다만 범위검색이나 정렬이 필요한 경우에는 TreeMap을 사용하자.

Properties

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

주로 애플리케이션의 환경설정과 관련된 속성(property)을 저장하는데 사용되며 데이터를 파일로부터 읽고 쓰는 편리한 기능을 제공한다.

Collections

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

컬렉션의 동기화

멀티 쓰레드 프로그래밍에서는 하나의 객체를 여러 쓰레드가 동시에 접근할 수 있기 때문에 데이터의 일관성(consistency)을 유지하기 위해서는 공유되는 객체의 동기화(synchronization)가 필요하다.

Vector와 Hashtable과 같은 구버전(JDK1.2 이전)의 클래스들은 자체적으로 동기화처리가 되어 있는데, 멀티쓰레드 프로그래밍이 아닌 경우에는 불필요한 기능이 되어 성능을 떨어뜨리는 요인이 된다.

그래서 새로 추가된 ArrayList와 HashMap과 같은 컬렉션은 동기화를 자체적으로 처리하지 않고 필요한 경우에만 java.util.Collections클래스의 동기화 메서드를 이용해서 동기화처리가 가능하도록 변경하였다.

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)

변경불가 컬렉션 만들기

컬렉션에 저장된 데이터를 보호하기 위해서 컬렉션을 변경할 수 없게 읽기전용으로 만들어야 할 때가 있다.

static Collection unmodifiableCollection(Collection c)
static List unmodifiableList(List list)
static Set unmodifiableSet(Set s)
static Map unmodifiableMap(Map m)
static SortedSet unmodifiableSortedSet(SortedSet s)
static SortedMap unmodifiableSortedMap(SortedMap m)

컬렉션 클래스 정리 & 요약

• ArrayList : 배열기반, 데이터의 추가와 삭제에 불리, 순차적인 추가/삭제는 제일 빠름. 임의의 요소에 대한 접근성이 뛰어남.
• LinkedList : 연결기반, 데이터의 추가와 삭제에 유리. 임의의 요소에 대한 접근성이 좋지 않다.
• HashMap : 배열과 연결이 결합된 형태. 추가, 삭제, 검색, 접근성이 모두 뛰어남. 검색에는 최고성능을 보인다.
• TreeMap : 연결기반, 정렬과 검색(특히 범위검색)에 적합. 검색성능은 HashMap보다 떨어짐.
• Stack : Vector를 상속받아 구현
• Queue : LinkedList가 Queue인터페이스를 구현
• Properties : Hashtable을 상속받아 구현(String, String)
• HashSet : HashMap을 이용해서 구현
• TreeSet : TreeMap을 이용해서 구현
• LinkedHashMap, LinkedHashSet : HashMap과 HashSet에 저장순서유지기능을 추가하였음.