chapter 23 컬렉션 프레임워크1(2)

Set<E> 인터페이스를 구현하는 컬렉션 클래스들

Set<E>을 구현하는 클래스의 특성

• 저장 순서가 유지되지 않는다.
• 데이터의 중복 저장을 허용하지 않는다.

HashSet<E> 클래스

HashSet<E>클래스의 메소드는 List<E> 클래스의 메소드들과 같지만 출력 결과를 확인해보면 저장 순서가 유지되지 않고 중복 저장이 허용되지 않음을 알 수 있다. 그렇다면 동일한 데이터로 판단하는 기준은 무엇일까?

public static void main(String[] args) {
    HashSet<Num> set = new HashSet<>();
    set.add(new Num(7799));
    set.add(new Num(7799));
    ....
}

위 코드의 실행 결과를 보면 같은 7799를 저장하는 Num 클래스의 인스턴스를 다른 인스턴스로 간주하는 것을 알 수 있다. HashSet<E>이 판단하는 동일 인스턴스의 기준은 Object 클래스에 정의되어 있는 다음 두 메소드의 호출 결과를 근거로 한다.

public boolean equals(Object obj)
public int hashCode()

위의 두 메소드가 어떻게 사용 되는지 이해하기 위해서는 해쉬 알고리즘에 대한 이해가 필요하다.

 

해쉬 알고리즘과 hashCode 메소드

HashSet<E> 클래스를 잘 활용하기 위해서는 해쉬 알고리즘을 이해하고 있어야 한다.

예를 들어 num % 3 이라는 코드가 있다고 하자. 간단한 코드지만 이것도 해쉬 알고리즘으로 사용될 수 있다. 이 알고리즘을 적용하여 수들을 나머지 연산의 결과 0과 1 그리고 2를 기준으로 세 집합으로 나눌 수 있다. 이렇게 세 개의 부류로 나뉜 상태에서, 정수 5의 존재 여부를 확인한다고 하면 연산 결과가 0과 1인 부류는 탐색 대상에서 제외할 수 있는 것이다. 즉, 탐색 대상이 줄어버린 것이다. 이것이 해쉬 알고리즘을 사용하는 이유이다. 

 

위에 든 예시처럼 비슷한 과정을 거쳐 동일 인스턴스의 존재 여부를 확인하는 클래스가 HashSet<E>이다. 

• 탐색 1단계 Objet 클래스에 정의된 hashCode 메소드의 반환 값을 기반으로 부류 결정
• 탐색 2단계 선택된 부류 내에서 equals 메소드를 호출하여 동등 비교

Object 클래스의 정의되어 있는 hashCode와 equals 메소드는 다음과 같이 정의되어 있다.(참고로 Object 클래스의 hashCode 메소드는 인스턴스가 저장된 주솟값을 기반으로 반환 값이 만들어진다.)

• "인스턴스가 다르면 Object 클래스의 hashCode 메소드는 다른 값을 반환한다."
• "인스턴스가 다르면 Object 클래스의 equals 메소드는 false를 반환한다."

따라서 위의 코드에서 7799를 담고있는 두 인스턴스가 서로 다른 인스턴스로 간주가 된 것이다.

 

참고로 String 클래스는 문자열의 내용 비교가 이뤄지도록 hashCode와 equals를 적절히 오버라이딩 하고 있다.

 

HashCode 메소드의 다양한 정의

다음과 같이 둘 이상의 값을 지니는 클래스의 경우 내용 비교를 위한 hashCode와 equals 메소드는 어떻게 정의하는 것이 좋을까?

class Car {
    private String model;
    private String color;
    ...
}

이 클래스는 두 개의 참조변수를 가지고 있으니, 다음과 같은 hashCode 메소드의 정의를 생각해볼 수 있다.

@Override
public int hashCode() {
    return (model.hashCode() + color.hashCode()) / 2;
}

그런데 클래스를 정의할 때마다 hashCode 메소드를 정의하는 것은 번거롭다. 그래서 자바에서는 다음 메소드를 제공하고 있다.

public static int hash(Object...values)
	// java.util.Objects에 정의된 메소드, 전달된 인자 기반의 해쉬 값 반환

위 메소드의 매개변수 선언에는 '가변 인자 선언'이 포함되어 있는데, 이는 전달되는 인자의 수를 메소드 호출 시마다 달리할 수 있는 선언이다. 그리고 이 hash 메소드를 이용하여 위 예제의 hashCode 메소드를 오버라이딩 할 수 있다.

@Override
public int hashCode() {
    return Objects.hash(model, color);	// 전달인자 model, color 기반 해쉬 값 반환
}

 

TreeSet<E> 클래스의 이해와 활용

TreeSet<E> 클래스는 '트리(Tree)'라는 자료구조를 기반으로 인스턴스를 저장한다. 이는 정렬된 상태가 유지되면서 인스턴스가 저장됨을 의미한다.

TreeSet<E> 인스턴스가 정렬 상태를 유지하면서 인스턴스를 저장하기 떄문에 TreeSet<E>의 반복자는 다음의 특징을 갖는다.

"인스턴스들의 참조 순서는 오름차순을 기준으로 한다."

따라서 클래스를 정의할 때에는 다음 인터페이스의 구현을 통해서 크고 작음에 대한 기준을 정해줘야 한다.

public interface Comparable<T>
	// 이 인터페이스에 위치한 유일한 추상 메소드 int compareTo(T o)

 

인스턴스의 비교 기준을 정의하는 Comparable<T> 인터페이스의 구현 기준

Comparable<T> 인터페이스를 구현할 때 정의해야 할 추상 메소드는 다음과 같다.

int compareTo(T o)

그리고 이 메소드의 정의 방법은 다음과 같으며, 이는 자바에서 결정한 일종의 약속이다.

• 인자로 전달된 o가 작다면 양의 정수 반환
• 인자로 전달된 o가 크다면 음의 정수 반환
• 인자로 전달된 o과 같다면 0을 반환

 

Comparator<T> 인터페이스를 기반으로 TreeSet<E>의 정렬기준 제시하기

public interface Comparator<T>
	// int compare(T o1, T o2) 의 구현을 통해 정렬 기준을 결정할 수 있다.

이 인터페이스를 구현한 클래스의 인스턴스는 TreeSet<E>의 다음 생성자를 통해 전달할 수 있다.

public TreeSet(Comparator<? super E> comparator)

그러면 이렇게 생성된 TreeSet<E> 인스턴스는 생성자로 전달된 인스턴스의 compare 메소드 호출 결과를 기준으로 정렬을 진행한다. compare 메소드의 정의 기준은 다음과 같다.

int compare(T o1, T o2)
	// o1이 o2보다 크면 양의 정수, 작으면 음의 정수, 같으면 0 반환

 

중복된 인스턴스를 삭제하려면

List<E>를 구현하는 컬렉션 클래스는 인스턴스의 중복 삽입을 허용한다. 그런데 저장된 인스턴스들 중에서 중복 삽입된 인스턴스들을 하나만 남기고 모두 지워야 한다면 매우 번거롭다. 따라서 다음 방법을 사용하면 좋다.

 HashSet<String> set = new HashSet<>(list);
 list = new ArrayList<>(set);

 

Queue<E> 인터페이스를 구현하는 컬렉션 클래스들

스택(Stack)과 큐(Queue)의 이해

스택은 '가장 먼저 저장된 데이터'가 가장 마지막에 빠져나오는 자료구조이다(LIFO). 큐는 들어간 순으로 빠져나오는 자료구조이다(FIFO).

 

Queue<E> 인터페이스와 큐(Queue)의 구현

Queue<E> 인터페이스의 메소드는 다음과 같다.

boolean add(E e)	넣기
E remove()		꺼내기
E element()		확인하기

remove는 인스턴스의 참조 값을 반환하면서 해당 인스턴스를 삭제한다. element는 인스턴스의 참조 값을 반환하지만 삭제하지 않는다.

위의 세 메소드는 꺼낼 인스턴스가 없을 때 혹은 저장 공간이 부족할 때 예외를 발생시킨다. 다음 세 메소드는 동일한 상황에서 예외를 발생시키지 않고 해당 상황을 알리기 위한 특정 값을 반환한다.

boolean offer(E e)	넣기, 넣을 공간이 부족하면 false 반환
E poll()		꺼내기, 꺼낼 대상 없으면 null 반환
E peek()		확인하기, 확인할 대상이 없으면 null 반환

일반적으로 offer, poll, peek을 사용한다.

 

스택(Stack)의 구현

자바는 기본 자료구조 대부분을 지원하고 스택 자료구조도 컬렉션 클래스 Stack<E>를 통해 지원하고 있다.

public class Stack<E> extends Vector<E>

그러나 Stack<E>는 (이 클래스가 상속하는 Vector<E>도) 자바 초기에 정의된 클래스로써 지금은 이전 코드와의 호환성 유지를 위해 존재하는 클래스일 뿐이다.(성능의 저하 발생) 대신에 자바 6에서 스택을 대신할 수 있는 '덱(Deque)'이라는 자료구조가 포함되었다.

public interface Deque<E> extends Queue<E>

덱은 양방향 큐로 덱을 스택처럼 사용하는 것이 가능하다.(큐도 가능)

// 앞으로 넣고, 꺼내고, 확인
void addFirst(E e)	넣기
E removeFirst()		꺼내기
E getFirst()		확인하기

// 뒤로 넣고, 꺼내고, 확인
void addLast(E e)	넣기
E removeLast()		꺼내기
E getLast()		확인하기

마찬가지로 이들은 꺼낼 대상이 없거나 공간이 부족해서 넣지 못할 때 예외를 발생시킨다.

// 앞으로 넣고, 꺼내고, 확인
void offerFirst(E e)	넣기, 공간이 부족하면 false
E pollFirst()		꺼내기, 꺼낼 대상 없으면 null
E peekFirst()		확인하기, 확인할 대상 없으면 null

// 뒤로 넣고, 꺼내고, 확인
void offerLast(E e)	넣기, 공간이 부족하면 false
E pollLast()		꺼내기, 꺼낼 대상 없으면 null
E peekLast()		확인하기, 확인할 대상 없으면 null

 

덱을 스택처럼 사용할 때 코드상에서 이것이 덱인지 스택인지 구분이 어려울 뿐만 아니라 스택으로 사용하려 했는데 앞으로 넣고 뒤로 꺼내는 실수를 할 수도 있다. 따라서 스택이 필요한 경우에는 다음과 같이 별도의 클래스를 정의하여 사용하는 것이 권장된다.

import java.util.Deque;
import java.util.ArrayDeque;

interface DIStack<E> {
    public boolean push(E item);
    public E pop();
}

class DCStack<E> implemnts<DIStack<E> {
    private Deque<E> deq;
    
    public DCStack(DEQUE<E> d) {
    	deq = d;
    }
    public boolean push(E item) {
    	return deq.offerFirst(item);
    }
    public E pop() {
    	return deq.pollFirst();
    }
}

 

Map<K, V> 인터페이스를 구현하는 컬렉션 클래스들

Map<K, V>를 구현하는 컬렉션 클래스의 인스턴스들은 Key와 Value가 한 쌍을 이루는 형태로 데이터를 저장한다.

 

Key-Value 방식의 데이터 저장 

Map<K, V>를 구현하는 클래스는 Value를 저장할 때, 이를 찾을 때 사용하는 Key를 함꼐 저장하는 구조이다. 때문에 Key는 중복될 수 없다. 반면 Key만 다르다면 Value는 종복이 되어도 상관없다.

 

HashMap<K, V> 클래스

Map<K, V>를 구현하는 대표 클래스로 HashMap<K, V>와 TreeMap<K, V>가 있다. 

import java.util.HashMap;

class HashMapCollection {
    public static void main(String[] args) {
    	HashMap<Integer, String> map = new HashMap<>();
        
        // Key-Value 기반 데이터 저장
        map.out(45, "Brown");
        map.out(37, "James");
        
        // 데이터 탐색
        System.out.println("45번: " + map.get(45));
        
        // 데이터 삭제
        map.remove(37);
    }
}

위의 코드에서 알 수 있듯이 Key도 Value도 인스턴스여야 한다.

 

HashMap<K, V>의 순차적 접근 방법

HashMap<K, V> 클래스는 Iterable<T> 인터페이스를 구현하지 않으니 for-each문을 통해서, 혹은 '반복자'를 얻어서 순차적 접근을 할 수 없다. 대신 다음 메소드를 이용할 수 있다.

public Set<K> keySet()

이 메소드는 Set<E>을 구현하는 컬렉션 인스턴스를 생성하고, 여기에 모든 Key를 담아서 반환한다.

import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;

class HashMapIteration {
    public static void main(String[] args) {
    	HashMap<Integer, String> map = new HashMap<>();
        
        map.out(45, "Brown");
        map.out(37, "James");
        map.out(23, "Martin");
        
        // Key만 담고 있는 컬렉션 인스턴스
        Set<Integer> ks = map.keySet();
        
        // 전체 Key 출력
        for(Integer n : ks)
        	System.out.print(n.toString() + '\t');
            
        // 전체 Value 출력(for-each)
        for(Integer n : ks)
        	System.out.print(map.get(n).toString() + '\t');
            
        // 전체 Value 출력(반복자 기반)
        for(Iterator<Integer> itr = ks.iterator(); itr.hasNext(); )
        	System.out.print(map.get(itr.next()) + '\t');
    }
}

 

TreeMap<K, V>의 순차적 접근 방법

위 코드에서 컬렉션 클래스만 TreeMap<K, V>으로 바꿔서 실행한다면 출력결과가 Key에 해당하는 나이 정보가 오름차순으로 출력된다. 이렇듯 대상 컬렉션 인스턴스에 따라서 반환되는 반복자의 성력은 달라진다.