Set, Queue, Map

 

 

 

 

 

 

Set

---

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

자바에서 Set을 인터페이스를 구현한 주요 클래스는 HashSet, TreeSet, LinkedHashSet이 있다. 

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

 

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

 

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

 

http://ko.wikipedia.org/wiki/레드-블랙_트리

 

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>	셋 데이터를 처리하는 것에 관련된 메소드 지정

 

💡List에는 정의되어 있지만, Set에는 정의되어 있지 않는 메소드는 어떤 것이 있을까?

Set은 순서가 없다. 따라서, 순서가 매개 변수로 넘어가는 메소드나, 수행 결과가 데이터의 위치와 관련된 메소드는 Set 인터페이스에서는 필요가 없다. 그러므로 get(int index)나 indexOf(Object o)와 같은 메소드들은 Set에 존재하지 않는다. 

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

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

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

 

 

Queue

---

LinkedList는 List 인터페이스뿐만 아니라 Queue와 Deque 인터페이스도 구현하고 있다. 즉, LinkedList 자체가 List이면서도 Queue, Deque도 된다.

 

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

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

 

💡LinkedList는 왜 쓰는 것일까?

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

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

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

 

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>	큐를 처리하는 것과 관련된 메소드 지정

 

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이라는 클래스도 있다.

 

Hashtable

---

Hashtable 클래스는 Map 인터페이스를 구현하기는 했지만, 일반적인 Map 인터페이스를 구현한 클래스들과는 다르다.

이 두 종류의 다른 점을 간단하게 정리하면 다음과 같다.

- Map은 컬렉션 뷰(Collection View)를 사용하지만, Hashtable은 Enumeration객체를 통해서 데이터를 처리한다.
- 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 패키지 소속이다)

 

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>	맵의 기본 메소드 지정

 

TreeMap

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

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

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