컬렉션 Comparable, Comparator 인터페이스 구현

Comparable과 Comparator

TreeSet 객체가 TreeMap의 키는 저장과 동시에 자동 오름차순으로 정렬됩니다. 숫자 타입일 경우는 값으로, 문자열 경우에는 유니코드로 정렬합니다. TreeSet, TreeMap은 정렬을 위해 java.lang.Comparable 구현 객체를 필요로 합니다. Integer, Double, String 모두 Comparable 인터페이스를 구현하고 있습니다. 사용자 정의 클래스도 Comparable을 구현하면 자동 정렬이 가능합니다.

 

리턴타입	메서드	설명
int	compareTo(T o)	주어진 객체와 같으면 0 리턴 주어진 객체보다 적으면 음수 리턴 주어진 객체보다 크면 양수 리턴

 

 

TreeSet, TreeMap 생성자의 매개값으로 정렬자(Comparator)를 제공하면 Comparable 비구현 객체도 정렬시킬 수 있습니다.

TreeSet<E> treeSet = new TreeSet<E>(new AscendingComparator());
TreeMap<E> treeMap = new TreeMap<E>(new DescendingComparator());

 

Comparator 인터페이스 구현한 객체를 말하는데 Comparator 인터페이스는 아래 메서드가 정의되어 있습니다.

리턴타입	메서드	설명
int	compare(T o1, T o2)	o1과 o2가 동등하다면 0 리턴 o1이 o2보다 앞에 오게 하려면 음수 리턴 o1이 o2보다 뒤에 오게 하려면 양수 리턴

 

LIFO와 LIFO 컬렉션

후입선출(LIFO)은 나중에 넣은 객체가 먼저 빠져나가는 자료구조다. 반대로 선입선출(FIFO)은  먼저 넣은 객체가 먼저 빠져나가는 구조입니다. 컬렉션 프레임워크에는 LIFO 자료구조를 제공하는 스택(Stack) 클래스와 FIFO 자료구조를 제공하는 큐(Queue) 인터페이스를 제공하고 있습니다.

 

Stack

리턴타입	메서드	설명
E	push(E item)	주어진 객체를 스택에 넣는다
E	peek()	스택의 맨 위 객체를 가져온다. 객체를 스택에서 제거하지 않는다
E	pop()	스택의 맨 위 객체를 가져온다. 객체를 스택에서 제거한다.

 

Queue

FIFO 자료구조에서 사용되는 메서드를 정의하고 있습니다.

리턴타입	메서드	설명
boolean	offer(E e)	주어진 객체를 넣는다
E	peek()	객체 하나를 가져온다. 객체를 큐에서 제거하지 않는다.
E	poll()	객체 하나를 가져온다. 객체를 큐에서 제거한다.

Queue 인터페이스를 구현한 대표적 클래스는 LinkedList입니다. LinkedList는 List 인터페이스를 구현했기 때문에 List 컬렉션이기도 합니다.

 

LinkedList 객체를 Queue 인터페이스 타입으로 변환한 코드

Queue<E> queue = new LinkedList<E>();

 

Queue<Message> messageQueue = new LinkedList<Message>();
messageQueue.offer(new Message("1", "A"); // 메시지 저장
messageQueue.offer(new Message("2", "B");
messageQueue.offer(new Message("3", "C");

messageQueue.poll(); // 메시지 큐에서 한개 꺼내기

 

동기화된 컬렉션

컬렉션 프레임워크 대부분의 클래스들은 싱글 스레드 환경에서 사용할 수 있게 설계되었습니다. 그래서 여러 스레드가 동시에 컬렉션에 접근하면 의도하지 않게 요소가 변경될 수 있는 불안전 상태가 됩니다.

Vector, Hashtable은 동기화된 메서드로 구성되어 있어 멀티 스레드 환경에서 안전하게 요소를 처리할 수 있지만 컬렉션 프레임워크는 비동기화된 메서드를 동기화된 메서드로 래핑하는 Collections synchronizedXXX() 메서드를 제공하고 있습니다. 매개값으로 비동기화된 컬렉션을 대입하면 동기화된 컬렉션을 리턴합니다.

 

리턴타입	메서드(매개변수)	설명
List<T>	synchronizedList(List<T> list)	List를 동기화된 List로 리턴
Map<K,V>	synchronizedMap(Map<K, V> m)	Map을 동기화된 Map으로 리턴
Set<T>	synchronizedSet(Set<T> s)	Set을 동기화된 Set으로 리턴

 

ArrayList를 Collections.synchronizedList() 메서드를 사용해서 동기화된 List로 변환하는 모습

 

(멀티스레드에 안전하지 않음)

스레드1 -> O (0.. n)

스레드2 -> O (0.. n)

 

(멀티스레드에 안전)

List<T> list = Collections.synchronizedList(new ArrayList<T>());

스레드 1 -> O (0.. n)

스레드 2 -> X (0.. n)

 

HashSet을 Collections.synchronizedSet() 메서드를 사용해서 동기화된 Set으로 변환하는 모습

 

(멀티스레드에 안전하지 않음)

스레드1 -> O (데이터 집합)

스레드2 -> O (데이터 집합)

 

(멀티스레드에 안전)

Set<E> set = Collections.synchronizedSet(new HashSet<E>());

스레드 1 -> O (데이터 집합)

스레드 2 -> X (데이터 집합)

 

HashMap을 Collections.synchronizedMap() 메서드를 사용해서 동기화된 Map으로 변환하는 모습

 

(멀티스레드에 안전하지 않음)

스레드1 -> O (key, value)

스레드2 -> O (key, value)

 

(멀티스레드에 안전)

Map<E> map = Collections.synchronizedMap(new HashMap<E>());

스레드 1 -> O (key, value)

스레드 2 -> X (key, value)

 

병렬 처리를 위한 컬렉션

동기화된 컬렉션은 멀티 스레드 환경에서 하나의 스레드가 요소를 안전하게 처리하도록 돕지만 전체 요소는 빠르게 처리하지 못합니다. 하나의 스레드가 요소를 처리할 때 전체 잠금이 발생해서 다른 스레드는 대기 상태가 됩니다. 그래서 멀티 스레드가 병렬적으로 컬렉션의 요소들을 처리할 수 없습니다.

 

자바에서는 멀티 스레드가 컬렉션의 요소를 병렬적으로 처리할 수 있도록 특별한 컬렉션을 제공합니다.

java.util.concurrent 패키지의 ConcurrentHashMap, ConcurrentLinkedQueue입니다.

 

ConcurrentHashMap을 사용하면 스레드에 안전하고 멀티 스레드가 요소를 병렬적으로 처리할 수 있습니다. 이것이 가능한 이유는 ConcurrentHashMap은 부분 잠금을 사용하기 때문입니다. 컬렉션에 10개의 요소가 저장되어 있다면 1개를 처리할 동안 전체 10개 요소를 다른 스레드가 처리하지 못하도록 하는 것이 전체 잠금이면, 처리하는 요소가 포함된 부분만 잠금하고 나머지 부분은 다른 스레드가 변경할 수 있도록 하는 것이 부분 잠금입니다.

 

ConcurrentLinkedQueue는 Lock-Free 알고리즘을 구현한 컬렉션입니다. 여러 스레드가 동시에 접근할 경우 잠금을 사용하지 않고도 최소한 하나의 스레드가 안전하게 요소를 저장하거나 얻도록 해줍니다.

 

Map<K,V> map = new ConcurrentHashMap<K,V>();
Queue<E> queue = new ConcurrentLinkedQueue<E>();