Collection Framework

Collection Framework

　

만든이: 송지훈
소속: JavaCafe 부시샵
email: johnleen@hanmail.net

　

이번 강좌를 통해 자바의 자료구조인 Collection Framework 에 대해 자세하게 알아보도록 하겠다. 가장 기본적이고 중요한 부분임에도 불구하고 프로그래밍을 공부하는 많은 사람들이 소홀히 생각하는 부분이다. 이 기회에 필자의 강좌를 통해 다시 한번 자바의 컬렉션 프레임워크에 대해 깊이 있는 이해를 할 수 있었으면 한다. 이 강좌에선 1.4에 추가된 새로운 자료구조, 정확하게 2개의 Map 계열 클래스와 1개의 Set 계열 클래스, 총 3가지를 포함해서 그 이전에 존재하는 자료구조 클래스들 모두를 설명한다.

• 자바의 자료구조 Collection Framework 의 구조
• Collection Framework 인터페이스들과 클래스들
  • Collection 인터페이스
  • Set 인터페이스와 구현 클래스들
    • HashSet
    • LinkedHashSet
    • TreeSet
  • List 인터페이스와 구현 클래스들
    • ArrayList
    • LinkedList
    • Vector
    • Stack
  • Map 인터페이스와 구현 클래스들
    • HashMap
    • LinkedHashMap
    • IdentityHashMap
    • WeakHashMap
    • Hashtable
    • TreeMap
  • Enumeration 와 Iterator 인터페이스
    • Enumeration
    • Iterator
• J2SDK1.5 에서 추가될 auto-boxing 과 generic
• 자주 사용되는 컬렉션 객체들의 퍼포먼스 표
• 효율적인 컬렉션 객체들의 사용
• 아쉬움을 남긴채 강좌를 마무리하며

　

1. 자바의 자료구조 Collection Framework 의 구조

다음 그림은 java.util 패키지 안의 컬렉션 프레임워크의 인터페이스를 관계를 나타내는 UML Class Diagram 을 보여주고 있다.
아래 그림에서 실선으로 그려진 화살표는 상속(extend)을 의미한다. 또한 "::" 을 기준으로 왼쪽은 패키지, 오른쪽은 이름을 나타낸다. 네모 안의 보라색 동그라미 안에 i 라고 써있는 것은 해당 객체가 인터페이스라는 것을 의미한다. 또 컬렉션 인터페이스를 구현한 클래스들을 설명할 때 나오겠지만 점선으로 그려진 화살표는 구현(implements)을 의미하고 클래스이기 때문에 녹색 동그라미안에 C 라는 글자가 쓰여있는 것을 보게 될 것이다. (참고로 필자는 이클립스 플러그인으로 제공되는 OMANDO 라는 UML 툴을 사용했다)

그림에서 볼 수 있듯이 자바의 컬렉션 프레임워크는 크게 두가지로 구분된다. 바로 Collection 과 Map 이다. Collection 은 다시 Set 과 List 로 구분된다.

또한 아래 Class Diagram 에서 볼 수 있듯이 Collection 인터페이스를 구현한 클래스들과 연계해서 편리하게 저장된 요소(Element)들을 다룰 수 있는 2가지 인터페이스가 있다.

• Note :: 요소(Element) 는 객체로 생각해도 무방하다. 그 이유는 자바의 컬렉션 프레임워크의 구성 클래스들에 저장하거나 꺼내오는 요소의 타입이 객체의 최상위 타입인 Object 이기 때문이다. 따라서 int 등의 primary type 데이터는 랩퍼(Wrapper) 클래스로 감싸서 넣어야 한다. 예를 들어, int 의 경우엔 Integer 로 감싸서 클래스로 만들어 넣는 것이다. 아래 컬렉션 계열 인터페이스들을 보면 추가-삭제 메소드들의 파라미터와 리턴값이 모두 Object 인 것을 확인할 수 있을 것이다.
  
  
• Issue :: J2SDK1.5 에선 primary type 도 랩퍼 클래스로 감싸지 않고 자동으로 컬렉션 클래스들에 넣어도 되는 auto-boxing 기능을 제공해 줄 예정이다.(내부에서 자동으로 적절한 타입으로 변환시켜 주게 됨) 참고로 C# 에선 이미 auto-boxing 기능이 제공되고 있다. auto-boxing 에 대한 자세한 내용은 이 글의 후반부에 다루도록 하겠다.

항상 숲과 나무를 같이 볼 수 있는 시야를 갖추어야 무엇이든 제대로, 깊이 있게 이해할 수 있다. 따라서 다시 한번 위에 있는 자바의 컬렉션 프레임워크의 전체 구조를 표현한 Class Diagram 을 살펴보도록 하자. 각 인터페이스들에 대한 자세한 설명은 아래 부분에서 하도록 하겠다.

Top

2. Collection Framework 인터페이스들과 클래스들

그럼 이제 자바의 자료구조인 Collection, Set, List, Map 등은 어떤 특징에 따라 구분한 것인지를 알아보겠다. 아래의 표에 각각의 특성을 정리해놨다. 아래 표를 주의 깊게 보도록 하자.

Package	Definition
java.util.Collection	순서 없는 단순한 요소들의 집합
java.util.Set	중복을 허용하지 않는 요소들의 집합
java.util.List	순차적 나열, 순서지정이 가능한 요소들의 집합
java.util.Map	Key와 Key에 대응하는 값으로 이루어진 구조
java.util.SortedSet	값들이 정렬된 Set
java.util.SortedMap	key 가 정렬된 Map

그럼 먼저 Collection 인터페이스를 구현한 어떤 클래스들이 존재하는지 Set, List 로 나눠서 살펴보자. 아래의 표는 Collection 의 구성을 표현한 표다. 표에서 인터페이스와 해당 인터페이스를 구현한 실제 클래스들를 보여주고 있다.

Interface		Implementation
Collection	Set	HashSet	LinkedHashSet	TreeSet
	List	ArrayList	LinkedList	Vector	Stack

아래의 표는 Map 인터페이스를 구현한 클래스들이다. 역시 인터페이스와 그 구현 클래스들을 보여주고 있다.

Interface	Implementation
Map	HashMap	LinkedHashMap	IdentityHashMap	WeakHashMap	Hashtable	TreeMap

이제 해당 인터페이스와 그 구현 클래스들의 특징이 어떤 것이고 어떻게 사용되는를 자세히 살펴보도록 하겠다.

Top

2-1. Collection 인터페이스

우선 먼저 Collection 인터페이스를 살펴보도록 하자.

package java.util;     public interface Collection {         // Query Operations         int size();         boolean isEmpty();         boolean contains(Object o);         Iterator iterator();         Object[] toArray();         Object[] toArray(Object a[]);         // Modification Operations         boolean add(Object o);         boolean remove(Object o);         // Bulk Operations         boolean containsAll(Collection c);         boolean addAll(Collection c);         boolean removeAll(Collection c);         boolean retainAll(Collection c);         void clear();         // Comparison and hashing         boolean equals(Object o);         int hashCode();     }

위 코드에서 주석으로 설명된 부분에서 알 수 있듯이 기능에 따라 4가지 분류의 메소드들로 나눌 수 있다. 그럼 각 기능에 따른 메소드들을 자주 사용되는 것들 위주로 간단히 살펴보도록 하겠다.

첫번째로 쿼리(Query) 오퍼레이션들을 살펴보자. 쿼리 오퍼레이션은 컬렉션 안에 저장된 요소의 개수(size() 메소드)나 저장된 요소가 있는지(isEmpty() 메소드), 컬렉션 안에 해당 메소드 안에 파라미터로 전달한 Object 요소가 들어있는지(contains(Object o) 메소드) 등의 여부를 질의하는 메소드들의 분류다. 나중에 예제 소스에서도 살펴보겠지만 iterator() 메소드는 컬렉션 안에 저장된 요소들을 Iterator 에 순차적으로 저장한 후 그 Iterator 객체를 리턴해준다.

두번째는 변경(Modification) 오퍼레이션들이다. 메소드 이름만으로도 쉽게 알 수 있듯이 하나의 요소를 컬렉션에 추가(add(Object o)), 삭제(remove(Object o)) 하는 메소드들이다.

세번째는 대량으로 요소의 변경을 가하는 오퍼레이션들이다. 여기서 상당히 간편하게 사용될 수 있는 addAll(Collection c) 메소드가 있는데 이것은 파라미터로 들어온 컬렉션 객체가 갖고 있는 요소들 모두를 저장하는 메소드이고 removeAll(Collection c) 메소드는 반대로 파라미터로 들어온 컬렉션 객체가 갖고 있는 요소들 모두를 제거한다. 이외에 clear() 메소드는 해당 컬렉션 객체의 모든 요소를 전부 제거한다.

마지막으로 비교(Comparison) 및 해싱(Hashing)을 위한 오퍼레이션들을 정의하는 메소드다. 자주 쓰이지 않으므로 별도의 언급은 하지 않겠다.

Top

2-2. Set 인터페이스와 구현 클래스들

Set 인터페이스를 살펴보자. Collection 인터페이스를 상속하므로 큰 차이점은 없고 단지 "Set" 은 중복을 허용하지 않는 자료구조였다는 것을 다시 한번 기억하도록 하자.

package java.util;     public interface Set extends Collection {         // Query Operations         int size();         boolean isEmpty();         boolean contains(Object o);         Iterator iterator();         Object[] toArray();         Object[] toArray(Object a[]);         // Modification Operations         boolean add(Object o);         boolean remove(Object o);         // Bulk Modification Operations         boolean containsAll(Collection c);         boolean addAll(Collection c);         boolean removeAll(Collection c);         boolean retainAll(Collection c);         void clear();         // Comparison and hashing         boolean equals(Object o);         int hashCode();     }

위 코드를 보면 Collection 과 동일한 메소드만을 제공해주는 것을 볼 수 있다. 단지 구현 클래스 내부에 equals(Object o) 메소드를 이용해서 중복을 허용하지 않도록 체크하는 기능이 더해져 있다.

그럼 이제부터 Set 을 구현한 클래스들을 살펴보도록 하겠다.

2-2-1. HashSet

　

2-2-2. LinkedHashSet(1.4에서 추가)

　

2-2-3. TreeSet

　

Top

2-3. List 인터페이스와 구현 클래스들

List 인터페이스는 순서 붙일 수 있는 컬렉션이다. 이 인터페이스의 사용자는 List 내의 어디에 각 요소가 삽입될까를 정밀하게 제어 할 수 있다. 사용자는 정수값의 인덱스(List 내의 위치)에 의해 요소에 액세스(access) 하거나 List 내의 요소를 검색할 수가 있다. Set 과는 다르게, 보통 일반적으로 List는 중복하는 요소를 허가한다.

package java.util;     public interface List extends Collection {         // Query Operations         int size();         boolean isEmpty();         boolean contains(Object o);         Iterator iterator();         Object[] toArray();         Object[] toArray(Object a[]);         // Modification Operations         boolean add(Object o);         boolean remove(Object o);         // Bulk Modification Operations         boolean containsAll(Collection c);         boolean addAll(Collection c);         boolean addAll(int index, Collection c);         boolean removeAll(Collection c);         boolean retainAll(Collection c);         void clear();         // Comparison and hashing         boolean equals(Object o);         int hashCode();         // Positional Access Operations         Object get(int index);        Object set(int index, Object element);        void add(int index, Object element);        Object remove(int index);         // Search Operations         int indexOf(Object o);        int lastIndexOf(Object o);         // List Iterators         ListIterator listIterator();        ListIterator listIterator(int index);         // View         List subList(int fromIndex, int toIndex);     }

Collection 인터페이스에서 제공해주던 메소드들에 List 인터페이스의 특징인 특정 위치의 요소를 찾거나 특정 위치에 요소를 추가하는 등의 메소드들이 추가되었다. 메소드 이름이 워낙 일관되고 명확하게 잘 지어져 있기 때문에(필자가 자바를 좋아하는 이유 중 하나) 메소드 이름만으로도 대강 어떤 역할을 하는지 짐작할 수 있을 것이다. List 인터페이스에서 추가된 메소드들은 Bold 를 주어 표현해놨다.

2-3-1. ArrayList

　

2-3-2. LinkedList

　

2-3-3. Vector

　

2-3-4. Stack

　

Top

2-4. Map 인터페이스와 구현 클래스들

Map 인터페이스는 키(key)를 값(value)에 매핑(mapping) 한다. 또한 Map은 동일한 키를 복수 등록할 수 없고 각 키는 1 개의 값밖에 매핑 할 수 없다. 즉, 하나의 키 값에 대응하는 하나의 값을 갖는 자료구조다.

package java.util;     public interface Map {          // Query Operations         int size();         boolean isEmpty();          boolean containsKey(Object key);         boolean containsValue(Object value);         Object get(Object key);          // Modification Operations         Object put(Object key, Object value);         Object remove(Object key);         // Bulk Modification Operations         void putAll(Map t);          void clear();          // Views         Set keySet();         Collection values();         Set entrySet();         interface Entry {             Object getKey();             Object getValue();             Object setValue(Object value);             boolean equals(Object o);              int hashCode();         }          // Comparison and hashing         boolean equals(Object o);         int hashCode();     }

// 설명

2-4-1. HashMap

　

2-4-2. LinkedHashMap(1.4에서 추가)

　

2-4-3. IdentityHashMap(1.4에서 추가)

　

2-4-4. WeakHashMap

　

2-4-5. Hashtable

　

2-4-6. TreeMap

　

Top

2-5. Enumeration 와 Iterator 인터페이스

Collection Framework 에는 Enumeration 와 Iterator 라는 인터페이스가 있다. 사전적인 의미로는 반복, 순환이라는 뜻을 지니고 있다. 어떤 객체들의 모임이 있을 때(Collection 계열 구현 클래스들, Collection 인터페이스에 iterator() 메소드가 있었음을 기억해라) 이 객체들을 어떤 순서에 의해서 하나씩 꺼내 쓰기 위한 인터페이스라고 할 수 있다. 원래 Java 2 이전는 Enumeration 이라는 인터페이스가 많이 사용되었지만 최근에는 Iterator 인터페이스가 더 많이 사용된다. 그 이유는 각 인터페이스를 살펴보며 알아보기로 하겠다.

2-5-1. Enumeration

아래의 Enumeration 인터페이스의 코드를 보자.

package java.util;     public interface Enumeration {          boolean hasMoreElements();         Object nextElement();     }

이 인터페이스는 단지 두개의 메소드만을 제공한다. 이 인터페이스의 사용은 상당히 간단하다. hasMoreElements() 메소드로 인터페이스 안에 다음 요소가 있는지를 질의한다. 만약 true 가 리턴되었다면(다음 인덱스에 요소가 있다는 의미) nextElement() 메소드로 다음 요소를 꺼내서 사용하면 되는 것이다.

java.util.StringTokenizer 클래스가 Enumeration 인터페이스를 구현하고 있다. 따라서 StringTokenizer 클래스가 제공하는 메소드들 중에서 Enumeration 에서 정의한 2개의 메소드가 제공되는 것을 볼 수 있을 것이다.

2-5-2. Iterator

아래의 코드는 Iterator 인터페이스다.

package java.util;     public interface Iterator {          boolean hasNext();         Object next();         void remove();     }

Enumeration 과의 차이점은 단지 remove() 메소드가 추가된 것 뿐이다. hasNext() 와 next() 메소드는 이름만 약간 다를 뿐 Enumeration 인터페이스의 hasMoreElements() 와 nextElement() 와 정확히 일치하는 기능을 한다.

그럼 왜 Enumeration 대신 Iterator 를 Java 2에서 추가해서 사용할까? 그것은 Enumeration 인터페이스는 집합 내에서 요소를 제거할 방법이 없기 때문이다. 그것을 보완하기 위해 나온 것이 Iterator 인터페이스다.

Top

3. J2SDK1.5 에서 추가될 auto-boxing 과 generic

　

Top

4. 자주 사용되는 컬렉션 객체들의 퍼포먼스 표

4-1. Set 객체

	동기화	설명
HashSet	no	가장 빠른 집합. HashMap 보다 느리지만 Set 인터페이스를 구현하고 있다. HashMap 은 Set 이 아니라 Map 임.
TreeSet	no	HashSet보다 느리다. 차례대로 키를 사용할 수 있다. (키가 정렬됨)

4-2. Map 객체

	동기화	설명
HashMap	no	가장 빠른 매핑.
Hashtable	yes	HashMap 보다 느리지만 동기화한 HashMap 보다 빠르다.
TreeMap	no	Hashtable 과 HashMap 보다 느리다. 차례대로 키를 사용할 수 있다. (키가 정렬됨)

4-3. List 객체

	동기화	설명
ArrayList	no	가장 빠른 리스트.
LinkedList	no	다른 리스트보다 느리지만 큐로 이용했을 경우 더 빠를 수도 있다. 느린 이유는 ArrayList 나 Vector, Stack 과 달리 array 계열이 아니기 때문.
Vector	yes	ArrayList 보다 느리지만 동기화한 ArrayList 보다 빠르다.
Stack	yes	Vector 와 동일한 속도. LIFO 큐 기능을 제공한다.

필자생각 :: HashMap, ArrayList 에 동기화를 걸어 사용하는것 보다 동기화된 Hashtable, Vector 를 사용하는 것이 더 빠른것으로 미루어 짐작컨데 Hashtable, Vector 의 경우에는 동기화가 되어 있는 내부 메소드들이 JIT 컴파일러에 의해 최적화 되는것 같음.

Top

5. 효율적인 컬렉션 객체들의 사용

*** Vector-Hashtable vs ArrayList-HashMap ***
보통 일반적으로 Vector 와 Hashtable 을 주로 사용하고 있을 것이다.
이 컬렉션 객체들은 모든 메소드가 synchronized 되어 있기 때문에 동시에 여러 스레드가 접근 할 수 없다.

반명 동일한 기능을 하는데도 불구하고 ArrayList 와 HashMap 은 메소드가 synchronized 로 되어있지 않아서 스레드들이 해당 객체에 동시접근이 가능하다.

은행에서 현금 입출금에 관련된것처럼 반드시 미션크리티컬한 로직이 필요한 곳에선 Vector와 Hashtable을 사용하는게 바람직하고 당연하지만 필자는 초보 분들이 프로그래밍한 코드에서 멀티스레드 접근을 해도 무방한데도 불구하고 모두 Vector 아니면 Hashtable을 사용하는 것을 많이 봐왔다. 이건 특히나 jsp 처럼 시간을 다투는 프로그램에선 치명타다. 동기화가 필요한지 아닌지를 잘 판단해서 정확히 필요한 곳에만 Vector나 Hashtable을 사용하고 그 이외의 부분에선 ArrayList 나 HashMap 을 사용해야 할 것이다.

이미 다 아는 얘기라고 하실지도 모르겠지만 모르시는 분들이 너무 많아서 다시 한번 언급해봤다.

필자의 경우에는 효율을 좀 더 높이기 위해 동기화가 필요한 부분도 ArrayList 나 HashMap 에다가 락을 걸어서 멀티스레드의 폐해를 피해가는 방식을 사용하고 있다. 모든 경우에 이렇게 한다는 것은 아니고 예를 들어 데이터를 넣는 부분은 멀티스레드 접근이 허용되지만 데이터를 꺼낸 후 삭제해야 하는 부분은 동기화가 필요하다고 가정했을 때 동기화가 필요한 "데이터를 꺼낸 후 삭제" 하는부분에만 락을 걸어서 동기화 블럭을 최소화시켜서 좀 더 효율을 가져간다는 것이다.

데이터를 컬렉션 객체에 넣고(put) 가져오고(get) 삭제하는(remove) 등의 모든 부분에 동기화가 필요하다면 당연히 그냥 이미 그런 용도로 만들어진 Vector나 Hashtable 을 사용하는 것이 편하고 또 이렇게 사용 하는 것이 ArrayList 나 HashMap 의 모든 메소드에 락을 걸어 사용하는 것보다 더 빠르다.

Top

6. 아쉬움을 남긴채 강좌를 마무리하며

자바의 컬렉션 프레임워크는 매년 자바의 가장 훌륭한 라이브러리로 선정되는 파트다. 그만큼 설계적인 측면에서나 구현적인 측면에서 배울 것이 많은 부분이다. 필자는 지금까지 바로 이 자바의 컬렉션 프레임워크에 대해 설명을 했다. 하지만 아쉬움이 남는다. 그 이유는 필자가 "물고기 잡는 법"을 가르쳐 준 것이 아니라 물고기를 잡아서 준 것이기 때문이다. 즉, 어떻게 이런 자료구조(구현 클래스들)를 만들지에 대한 강좌가 아니라 단순히 만들어진 자료구조를 어떻게 이용하는지에 초점을 맞춰서 설명했다는 것이다.

필자가 독자분들에게 한가지 당부를 한다면 이미 만들어져 있는 api 를 단순히 이용하기 보다는 직접 만들어서 사용할 수 있는 능력을 키우라는 것이다. 그게 진정 창조적인 그리고 프로페셔널한 개발자가 되기 위한 길이라고 필자는 생각한다. 따라서 우선 독자분들은 컬렉션 프레임워크의 구현 클래스들이 어떻게 만들어졌는지를 직접 J2SDK 폴더 안의 src.zip 파일의 압축을 풀어서 분석해봤으면 한다. 그리고 나름대로 직접 그런 자료구조를 구현하기 위한 방법들도 생각해보고 가능하다면 직접 구현해보았으면 한다. 그럼 이제 결코 짧지 않았던 컬렉션 프레임워크 강좌를 마무리하겠다.

Top