자바 컬렉션

1. 자바 컬렉션

자바에서 컬렉션은 목록성 데이터를 처리하는 자료구조를 통칭한다. 먼저 자료구조라는 것부터 살펴보자.

자료 구조는 영어로 "Data Structure"라고 한다. 다시 말해서, 어떤 정보를 담는 것을 의미하는데, 하나의 데이터가 아닌 여러 데이터를 담을 때 사용한다. 자바에서의 데이터를 담는 자료 구조는 크게 다음과 같이 분류할 수 있다.

• 순서가 있는 목록(List) 형
• 순서가 중요하지 않는 셋(Set) 형
• 먼저 들어온 것이 먼저 나가는 큐(Queue) 형
• 키-값(key-value)으로 저장되는 맵(Map) 형

2. Collection Interface

자바에서는 "목록"과 "셋", "큐"는 Collection이라는 인터페이스를 구현하고 있다. Collection 인터페이스는 java.util 패키지에 선언되어 있는데, 여러 개의 객체를 하나의 객체에 담아 처리할 때 공통적으로 사용되는 여러 메소드들을 선언해 놓았다. 이 목록에서 유일하게 "맵"만이 Collection과 관련 없는 별도의 인터페이스로 선언되어 있다.

자바의 컬렉션과 관련된 클래스들을 하나의 그림으로 나타내면 다음과 같다.

먼저 "목록"과 "셋", "큐"의 기본이 되는 Collection 인터페이스에 대해서 살펴보자. Collection 인터페이스는 다음과 같이 선언되어 있다.

public interface Collection<E> extends Iterable<E>

이 Collection 인터페이스 선언문에서 특이한 것은 Iterable<E>이라는 인터페이스를 확장(extends) 했다는 점이다. Iterable 인터페이스에 선언되어 있는 메소드는 단지 하나다.

리턴 타입	메소드 이름 및 매개 변수
Iterator<T>	iterator()

iterator()라는 메소드만 Iterable 인터페이스에 선언되어 있고, 이 메소드는 Iterator라는 인터페이스를 리턴한다. 참고로, Iterator라는 인터페이스에는 초기 데이터가 있는지 확인하는 hashNext() 메소드, 현재 위치를 다음 요소로 넘기고 그 값을 리턴해주는 next()라는 메소드, 데이터를 삭제하는 remove() 메소드가 있다.

결론적으로, Collection 인터페이스가 Iterable 인터페이스를 확장했다는 의미는, Iterable 인터페이스를 사용하여 데이터를 순차적으로 가져올 수 있다는 의미이다.

3. List

배열과 비슷한 "목록"에 대해서 알아보자. "목록"은 List 인터페이스로부터 시작되며, 이 List 인터페이스는 방금 배운 Collection 인터페이스를 확장하였다. Collection을 확장한 다른 인터페이스와 List 인터페이스의 가장 큰 차이점은 배열처럼 "순서"가 있다는 것이다.

List 인터페이스를 구현한 클래스들은 매우 많다. 그 많은 클래스들 중에서 java.util 패키지에서는 ArrayList와 Vector, Stack, LinkedList를 많이 사용한다.

이 중에서 ArrayList와 Vector 클래스의 사용법은 거의 동일하고 기능도 거의 비슷하다. 이 두 클래스는 "확장 가능한 배열"이라고 생각하면 된다. 두 클래스의 탄생 시기를 비교해 보면 Vector는 JDK 1.0부터 있었고, ArrayList는 JDK 1.2부터 추가되었다. 그리고, ArrayList의 객체는 여러 명이 달려들어서 값을 변경하려고 하면 문제가 발생할 수 있고, Vector는 그렇지 않다. 어려운 말로 하면 ArrayList는 Thread safe하지 않고, Vector는 Thread safe하다.

그 다음에 잇는 Stack이라는 클래스는 Vector라는 클래스를 확장하여 만들었다. 이 클래스를 만든 가장 큰 이유는 LIFO를 처리하기 위함이다. LIFO는 Last In First Out의 약자로, 가장 마지막에 추가한 값을 가장 처음 빼 내는 것이다. 프로그래밍 언어에서 "스택"이라는 의미는 보통 메소드가 호출된 순서를 기억하는 장소를 말한다.

그 다음엔 LinkedList라는 클래스가 있는데, 이 클래스는 "목록"에도 속하지만, "큐"에도 속한다.

1. ArrayList 클래스

컬렉션, 쓰레드, IO, 네트워크 등의 관련 클래스를 사용할 때는 한 번 정도 그 클래스의 상속 관계를 살펴보는 것이 좋다. 왜냐하면, 그 클래스의 API에 있는 메소드나 상수만 사용할 수 있는 것이 아니고, 부모 클래스에 선언되어 있는 메소드도 사용할 수 있기 때문이다. 게다가, 컬렉션 관련 클래스의 선언부만 보더라도, 그 클래스가 목록에 속하는지, 셋에 속하는지를 알 수 있다.

그러면 가장 먼저 ArrayList 클래스의 상속 관계를 살펴보자.

java.lang.Object
  ㄴ java.util.AbstractCollection<E>
    ㄴ java.util.AbstractList<E>
      ㄴ java.util.ArrayList<E>

당연한 말이지만, ArrayList의 가장 상위 부모는 Object 클래스다. 그 다음에는 AbstractCollection, AbstractList의 순으로 확장했다. Object를 제외한 나머지 부모 클래스들의 이름 앞에는 Abstract가 붙어 있다. 즉, 이 클래스는 abstract 클래스다. abstract 클래스는 일반 클래스와 비슷하지만, 몇몇 메소드는 자식에서 구현하라고 abstract로 선언한 메소드들이 있는 클래스를 말한다. 따라서 AbstractCollection은 Collection 인터페이스 중 일부 공통적인 메소드를 구현해 놓은 것이며, AbstractList는 List 인터페이스 중 일부 공통적인 메소드를 구현해 놓은 것이라고 기억하면 된다.

ArrayList가 구현한 모든 인터페이스들은 다음과 같다.

Serializable, Cloneable, Iterable<E>, Collection<E>, RandomAccess

인터페이스	용도
Serializable	원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정
Cloneable	Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미한다.
Iterable<E>	객체가 "foreach" 문장을 사용할 수 있음을 지정
Collection<E>	여러 개의 객체를 하나의 객체에 담아 처리할 때의 메소드 지정
List<E>	목록형 데이터를 처리하는 것에 관련된 메소드 지정
RandomAccess	목록형 데이터에 보다 빠르게 접근할 수 있도록 임의로(random하게) 접근하는 알고리즘이 적용된다는 것을 지정

이와 같은 인터페이스들을 ArrayList가 구현했다는 것은 각 인터페이스에서 선언한 기능을 ArrayList에서 사용할 수 있다는 말이다.

또한 앞에서도 이야기 했지만, Vector는 쓰레드에 안전(Thread safe)하고, ArrayList는 쓰레드에 안전하지 않다. 따라서, ArrayList를 여러 쓰레드에서 덤벼도 안전하게 만들려면 다음과 같이 객체를 생성해야 한다.

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

2. Stack 클래스

List 인터페이스를 구현한 또 하나의 클래스인 Stack 클래스에 대해 살펴보자. 일반적으로 웹을 개발할 때는 별로 많이 사용하지는 않지만, 마지막에 들어온 데이터를 가장 처음에 꺼내는 LIFO 기능을 구현하려고 할 때 필요한 클래스다.

하지만 LIFO 기능을 위해서 이 클래스를 사용하는 것은 권장하지 않는다. 왜냐하면 이 클래스보다 더 빠른 ArrayDeque라는 클래스가 존재하기 때문이다. 하지만, ArrayDeque는 쓰레드에 안전하지 못하다. 약간 성능은 떨어지지만, 쓰레드에 안전한 LIFO 기능을 원한다면 이 Stack 클래스를 사용하면 된다.

먼저 간단하게 Stack 클래스의 상속관계를 살펴보자.

java.lang.Object
  ㄴ java.util.AbstractCollection<E>
    ㄴ java.util.AbstractList<E>
      ㄴ java.util.Vector<E>
        ㄴ java.util.Stack<E>

Stack 클래스의 부모 클래스는 Vector인 것을 볼 수 있다. 즉, Vector 클래스에서 제공하는 모든 메소드를 사용할 수 있다.

그리고, Stack 클래스에서 구현한 인터페이스는 Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess로 ArrayList 클래스에서 구현한 인터페이스와 모두 동일하다.

Stack 클래스는 자바에서 상속을 잘못 받은 예이다. 이 클래스가 JDK 1.0부터 존재했기 때문에 원래의 취지인 LIFO를 생각한다면 Vector에 속해서는 안 된다. 하지만, 자바의 하위 호환성을 위해 이 상속관계를 계속 유지하고 있다고 생각하면 된다.

3. Set

Set은 순서에 상관 없이, 어떤 데이터가 존재하는지를 확인하기 위한 용도로 많이 사용된다. 다시 말해서, 중복되는 것을 방지하고, 원하는 값이 포함되어 있는지를 확인하는 것이 주 용도다. 이처럼 어떤 값이 존재하는지, 없는지 여부만 중요할 때 Set을 사용하면 된다.

자바에서 Set을 인터페이스를 구현한 주요 클래스는 HashSet, TreeSet, LinkedHashSet이 있다. 각각의 특징은 다음과 같다.

• HashSet : 순서가 전혀 필요 없는 데이터를 해시 테이블(hash table)에 저장한다. Set 중에 가장 성능이 좋다.
• TreeSet : 저장된 데이터의 값에 따라서 정렬되는 셋이다. red-black이라는 트리(tree) 타입으로 값이 저장되며, HashSet 보다 약간 성능이 느리다.
• LinkedHashSet : 연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다. 저장된 순서에 따라서 값이 정렬된다. 대신 성능이 이 셋 중에서 가장 나쁘다.

이러한 성능 차이가 발생하는 이유는 바로 데이터 정렬 때문이다. HashSet은 별도의 정렬 작업이 없어 제일 빠르다.

red-black 트리는 각 노드의 색을 붉은 색 혹은 검은 색으로 구분하여 데이터를 빠르고, 쉽게 찾을 수 있는 구조의 이진(binary) 트리를 말한다.

1. HashSet 클래스

먼저 HashSet 클래스의 상속 관계를 보자.

java.lang.Object
  ㄴ java.util.AbstractCollection<E>
    ㄴ java.util.AbstractSet<E>
      ㄴ java.util.HashSet<E>

AbstractCollection을 확장한 것은 ArrayList와 동일하다. 하지만, HashSet은 AbstractSet을 확장했다. AbstractSet 클래스는 이름 그대로 abstract 클래스이다. 구현되어 있는 메소드는 Object 클래스에 선언되어 있는 equals(), hashCode() 메소드와 이 클래스에서 추가한 removeAll() 뿐이다.

Set은 무엇보다도 데이터가 중복되는 것을 허용하지 않으므로, 데이터가 같은지를 확인하는 작업은 Set의 핵심이다. 그리고, equals() 메소드는 hashCode() 메소드와 떨어질 수 없는 불가분의 관계이다. 따라서, equals()와 hashCode() 메소드를 구현하는 부분은 Set에서 매우 중요하다. 추가로 removeAll() 메소드는 컬렉션을 매개 변수로 받아, 매개 변수 컬렉션에 포함된 보은 데이터를 지울 때 사용한다.

상속 관계를 간단히 살펴봤으니, HashSet이 어떤 인터페이스를 구현하는지 보자.

인터페이스	용도
Serializable	원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정
Cloneable	Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미한다.
Iterable<E>	객체가 "foreach" 문장을 사용할 수 있음을 지정
Collection<E>	여러 개의 객체를 하나의 객체에 담아 처리할 때의 메소드 지정
Set<E>	셋 데이터를 처리하는 것에 관련된 메소드 지정

HastSet의 생성자에서 사용하는 로드 팩터(load factor)라는 것은 뭘까?

로드 팩터는 (데이터의 개수) / (저장 공간)을 의미한다. 만약 데이터의 개수가 증가하여 로드 팩터보다 커지면, 저장 공간의 크기는 증가되고 해시 재정리 작업(refresh)을 해야 한다. 데이터가 해시 재정리 작업에 들어가면, 내부에 갖고 있는 자료 구조를 다시 생성하는 단계를 거쳐야 하므로 성능에 영향이 발생한다.

로드 팩터라는 값이 클수록 공간은 넉넉해지지만, 데이터를 찾는 시간은 증가한다. 따라서, 초기 공간 개수와 로드 팩터는 데이터의 크기를 고려하여 산정하는 것이 좋다. 왜냐하면 초기 크기가 (데이터의 개수) / (로드 팩터) 보다 클 경우에는 데이터를 쉽게 찾기 위한 해시 재정리 작업이 발생하지 않기 때문이다. 따라서, 대량의 데이터를 여기에 담아 처리할 때에는 초기 크기와 로드 팩터의 값을 조절해 가면서 가장 적절한 크기를 찾아야만 한다.

4. Queue

LinkedList를 가장 쉽게 이해하려면 열차를 생각하면 된다.

LinkedList에서는 앞에 있는 애와 뒤에 있는 애만 기억하면된다. 다시 말해서, 10은 뒤에 있는 값이 20이라는 것만 알고, 30이 있다는 것은 생각도 안한다. 그리고 30이라는 애도 앞에 20이라는 것만 기억한다.

그렇다면 LinkedList는 왜 쓰는 것일까? 만약, 간단하게 배열과 같이 데이터를 담아서 순차적으로 뺄 경우에는 별 필요가 없을 수도 있다. 하지만, 배열의 중간에 있는 데이터가 지속적으로 삭제되고, 추가될 경우에는 LinkedList가 배열보다 메모리 공간 측면에서 훨씬 유리하다. 왜냐하면, ArrayList와 Vector는 각 위치가 정해져 있고, 그 위치로 데이터를 찾는다. 그런데, 맨 앞의 값을 삭제하면, 그 뒤에 있는 값들은 하나씩 앞으로 위치를 이동해야 제대로 된 위치의 값을 가지게 된다. 그에 반해 LinkedList는 중간에 있는 데이터를 삭제하면, 지운 데이터의 앞에 있는 데이터와 뒤에 있는 데이터를 연결하면 그만이다. 위치를 맞추기 위해 값을 이동하는 단계를 거칠 필요가 없다는 뜻이다.

그리고, LinkedList는 List 인터페이스뿐만 아니라 Queue와 Deque 인터페이스도 구현하고 있다. 즉, LinkedList 자체가 List이면서도 Queue, Deque도 된다. 이 중에서 Queue를 먼저 살펴보자.

큐는 FIFO의 용도로 사용한다. First In First Out의 약자로 먼저 들어온 애가 먼저 나가는 것을 말한다.

또한 LinkedList 클래스가 구현한 인터페이스 중에서 Java 6에서 추가된 Deque라는 것이 있다. Deque는 "Double Ended Queue"의 약자이다. Deque는 Queue 인터페이스를 확장하였기 때문에, Queue의 기능을 전부 포함한다. 대신, 맨 앞에 값을 넣거나 빼는 작업, 맨 뒤에 값을 넣거나 빼는 작업을 수행하는 데 용이하도록 되어 있다고 보면 된다.

LinkedList의 상속 관계는 다음과 같다.

java.lang.Object
  ㄴ java.util.AbstractCollection<E>
    ㄴ java.util.AbstractList<E>
      ㄴ java.util.AbstractSequentialList<E>
        ㄴ java.java.util.LinkedList<E>

ArrayList 클래스나 Vector 클래스와 상속관계는 비슷하지만, AbstractSequentialList가 부모인 것을 볼 수 있다. AbstractList와 AbstractSequentialList의 차이점은 add(), set(), remove() 등의 메소드에 대한 구현 내용이 상이하다는 정도다. LinkedList 클래스가 구현한 인터페이스의 목록을 살펴보자.

인터페이스	용도
Serializable	원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정
Cloneable	Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미한다.
Iterable<E>	객체가 "foreach" 문장을 사용할 수 있음을 지정
Collection<E>	여러 개의 객체를 하나의 객체에 담아 처리할 때의 메소드 지정
Deque<E>	맨 앞과 맨 뒤의 값을 용이하게 처리하는 큐와 관련된 메소드 지정
List<E>	목록형 데이터를 처리하는 것과 관련된 메소드 지정
Queue<E>	큐를 처리하는 것과 관련된 메소드 지정

LinkedList 클래스는 List도 되고 Queue도 된다. 두 인터페이스의 기능을 모두 구현한 특이한 클래스라고 볼 수 있다. 게다가 Deque 인터페이스도 구현하므로, 맨 앞과 맨 뒤의 데이터를 쉽게 처리할 수 있다.

4. Map

자바에서의 Map은 키(Key)와 값(Value)으로 이루어져 있다. 자바의 Map은 키와 값이 1:1로 지정된다. 그런데, 이 키는 해당 Map에서 중복되지 않는다. 만약 키가 다르고, 값이 동일하다면 맵에서는 다른 것으로 간주한다.

이처럼 Map은,
1. 모든 데이터는 키와 값이 존재한다.
2. 키가 없이 값만 저장될 수는 없다.
3. 값 없이 키만 저장될 수도 없다.
4. 키는 해당 Map에서 고유해야만 한다.
5. 값은 해당 Map에서 중복되어도 전혀 상관 없다.

Map은 java.util 패키지의 Map이라는 이름의 인터페이스로 선언되어 있고, 구현해 놓은 클래스들도 많이 있다.

Map 인터페이스를 구현한 클래스들은 매우 다양하고 많다. 그 중에서 HashMap, TreeMap, LinkedHashMap 등이 가장 유명하고, 개발자들이 애용하는 클래스다. 그리고, Hashtable이라는 클래스도 있다.

1. Hashtable

Hashtable 클래스는 Map 인터페이스를 구현하기는 했지만 일반적인 Map 인터페이스를 구현한 클래스들과는 다르다. 이 두 종류의 다른 점을 간단하게 정리하면 다음과 같다.

• Map은 컬렉션 뷰(Collection View)를 사용하지만, Hashtable은 Enumeration 객체를 통해서 데이터를 처리한다.
• Map은 키, 값, 키-값 쌍으로 데이터를 순환하여 처리할 수 있지만, HashTable은 이 중에서 키-값 쌍으로 데이터를 순환하여 처리할 수 있다.
• Map은 이터레이션을 처리하는 도중에 데이터를 삭제하는 안전한 방법을 제공하지만, HashTable은 그러한 기능을 제공하지 않는다.

크게 봤을 때 Map 인터페이스와 Hashtable 클래스의 차이는 이 정도이다.

그런데, HashMap 클래스와 Hashtable 클래스는 다음과 같은 차이가 있다.

기능	HashMap	Hashtable
키나 값에 null 저장 가능 여부	가능	불가능
여러 쓰레드 안전 여부	불가능	가능

특히, Hashtable을 제외한 나머지 Map으로 끝나는 클래스들은 여러 쓰레드에서 동시에 접근하여 처리할 필요가 있을 때에는 다음과 같이 선언해서 사용해야만 한다.

Map m = Collections.synchronizedMap(new HashMap(...));

추가로, 자바 기본 API 중에서 JDK 1.0부터 제공되는 Hashtable, Vector는 클래스가 쓰레드에 안전하게 개발되어 있다. 그 외의 JDK 1.2부터 제공되는 대부분의 Collection 관련 클래스들은 이와 같은 처리를 해야 하거나 이름에 Concurrent가 포함되어 있어야만 쓰레드에 안전하게 사용할 수 있다. 그리고, 이러한 처리가 필요한 클래스의 API에는 반드시 관련된 설명이 제공되므로 API를 참고하는 습관을 들이도록 하자(예르 ㄹ들면 JDK 1.5에 추가된 ConcurrentHashMap, ConpyWriteArrayList 등이 있으며, java.util.concurrent 패키지 소속이다).

2. HashMap

그러면, 여러 Map 인터페이스를 구현한 클래스 중에서 가장 많이 사용되는 HashMap 클래스를 자세히 알아보자.

HashMap 클래스는 다음과 같은 상속 관계를 가진다.

java.lang.Object
  ㄴ java.util.AbstractMap<K, V>
    ㄴ java.util.HashMap<K, V>

HashMap 클래스는 AbstractMap이라는 Abstract 클래스를 확장했으며, 대부분의 주요 메소드는 AbstratctMap 클래스가 구현해 놓았다. 또한 어떤 인터페이스를 구현했는지 알아보자.

인터페이스	용도
Serializable	원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정
Cloneable	Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미한다.
Map<E>	맵의 기본 메소드 지정

3. TreeMap

만약 HashMap 객체의 키를 정렬하려면 여러 가지 방법을 사용해야 한다. 이럴 때 사용할 수 있는 TreeMap이라는 클래스가 있다. 이 클래스는 저장하면서, 키를 정렬한다. 정렬되는 기본 순서는 "숫자 > 알파벳 대문자 > 알파벳 소문자 > 한글" 순이다. 이 순서는 String과 같은 문자열이 저장되는 순서를 말하는 것이다.

즉, TreeMap은 키를 정렬하여 저장하고, 키의 목록을 가져와서 출력해보면 정렬된 순서대로 제공되는 것을 볼 수 있다. 매우 많은 데이터를 TreeMap을 이용하여 보관하여 처리할 때에는 HashMap보다는 느릴 것이다. 왜냐하면, 키가 정렬되기 때문이다. 하지만, 100건, 1,000건 정도의 데이터를 처리하고, 정렬을 해야 할 필요가 있다면, HashMap 보다는 TreeMap을 사용하는 것이 더 유리하다.

이렇게, TreeMap이 키를 정렬하는 것은 SortedMap이라는 인터페이스를 구현했기 때문이다. SortedMap을 구현한 클래스들은 모두 키가 정렬되어 있어야만 한다. 키가 정렬이 되었을 때의 장점은, 가장 앞에 있는 키(firstKey()), 가장 뒤에 있는 키(lastKey()), 특정 키 뒤에 있는 키(highterKey()), 특정 키 앞에 있는 키(lowerKey()) 등을 알 수 있는 메소드를 제공해 준다는 것이다.

참고

• 자바의 신