[자료구조] 14. Java 셋 인터페이스 (Set Interface)

Set Interface

 

Set은 말그대로 집합이다. 기본적으로 Set 혹은 Set 계열을 구현하는 클래스들은 다음과 같은 공통점이 있다.

 

1. 중복 요소(원소)를 허용하지 않는다.
2. 저장 순서를 유지하지 않는다. (LinkedHashSet 만 예외)

가장 중요한 특징은 '중복 요소를 허용하지 않는다'는 점이다. 

 

Set의 종류

Set은 크게 HashSet, LinkedHashSet, TreeSet으로 나뉜다. 

 

HashSet

가장 기본적인 Set 컬렉션의 클래스이다. 입력 순서를 보장하지 않고 순서도 보장되지 않는다. 가장 쉽게 이해할 수 있는 예시로는 게임에서 닉네임 중복확인을 할때이다. 이는 데이터가 정렬될 필요도 없을뿐더러 빠르게 중복되는 값인지만 찾으면 되므로 유용한 방법이 될 수 있다. hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 검색할 수 있게 만든 것이다. 즉 hash 기능과 Set 컬렉션이 합쳐진 것이 HashSet이다. 그렇게 때문에 삽입, 삭제, 색인이 매우 빠른 컬렉션 중에 하나이다.

 

LinkedHashSet

Link + Hash + Set 이 결합된 형태다. LinkedList에서 보면 add() 메소드를 통해 요소들을 넣은 순서대로 연결한다. 즉, LinkedList의 첫번째 요소부터 차례대로 출력하면 입력했던 순서대로 출력된다는 것이고 이는 순서를 보장한다는 의미이다.

Set의 경우 기본적으로 입력 순서대로의 저장순서를 보장하지 않아 '중복은 허용하지 않으면서 순서를 보장받고 싶은 경우'에는 불편할 수 밖에 없다. 이를 보완하기 위한 것이 LinkedHashSet이다. 실생활에서 그나마 예를 들자면 페이지를 열때 만약 해당 페이지가 중복되는 경우 cache는 다시 적재할 필요가 없지만 새로운 페이지를 할당해야할 경우 최근에 사용되지 않은 cache를 비우고자 할때 가장 오래된 cache를 비우는 것이 현명할 것이다. 이를 LRU 알고리즘(Least Recently Used Alogorithm)이라고 하는데 이럴때 입력 순서를 알아야 오래된 캐시를 비울 수 있다. 이에 적용할 수 있는 자료구조 중 하나이다.

(현실적으로는 LRU 기법으로 LinkedHashMap이라는 자료구가 대부분을 차지하고 있다.)

 

TreeSet

TreeSet은 HashSet과 마찬가지로 입력 순서대로의 저장 순서를 보장하지 않으며 중복 데이터 또한 넣지 못한다. 다만 특별한 점은 SortedSet Interface의 이름을 보면 알 수 있듯 이를 구현한 TreeSet은 데이터의 '가중치에 따른 순서'대로 정렬되어 보장된다. 앞서 우선순위 큐를 생각해보자. 데이터들이 입력한 순서대로가 아닌 값에 따라 정렬되어 Queue에 담아진다. 마찬가지로 TreeSet은 '중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 쓴다. 정렬된 형태로 있다보니 특정 구간의 집합요소들을 탐색할 때 매우 유용하다. (Tree라는 자료구조 자체가 데이터를 일정 순서에 의해 정렬하는 구조이다. 거기에 더해진 것이 바로 Set인 중복값 방지 자료구조인 것이다.)

---

알아두어야할 점

자바에서 제공하는 Set 계열 클래스들은 기본적으로 Map으로 구현되어 있다. 겉으로는 Set이지만 내부를 보면 Map으로 생성하여 구현되고 있다. Set과 Map의 차이는 Set은 값만 가지지만 Map은 key-value(키-값) 쌍으로 이루어져있다.

 

실질적으로 HashSet은 HashMap으로 LinkedHashSet은 LinkedHashMap, TreeSet은 TreeMap으로 구현된다. 하지만 Set을 이해하기 위해 Map으로 구현하지는 않는다.

 

(이 포스팅에서 Set의 경우 Map을 생성하고 데이터를 넣을때 값은 Map의 key가 되고, value는 빈 오브젝트로 동일하게 들어간다는 점을 참고하자.)

---

<Set Interface에 선언할 메소드>

메소드	리턴타입	설명
add(E e)	boolean	지정된 요소가 없을 경우 추가한다. 이미 지정된 요소가 존재하는 경우 false를 반환한다.
remove(Object o)	boolean	지정된 객체가 집합에 존재하는 경우 해당요소를 제거한다.
contains(Object o)	boolean	지정된 요소가 집합에 있는지를 확인한다.
equals(Object o)	boolean	지정된 객체와 현재 집합이 같은지 비교한다.
isEmpty()	boolean	현재 집합이 비어있을 경우 true, 아니면 false를 반환한다.
size()	int	현재 집합에 있는 요소의 개수를 반환한다.
clear()	void	현재 집합에 있는 요소들을 모두 제거한다.

 

이후 TreeSet을 다룰때 알게되겠지만 Set 인터페이스를 상속하여 SortedSet이란 인터페이스를 구현하기도 한다. 앞으로 HashSet, LinkedHashSet, TreeSet정도를 구현해볼 것이다.

 

---

Set 인터페이스 코드

package Z_DataStructure.A_InterfaceForm;

/**
 *
 * 자바 Set Interface.
 * Set 은 HashSet, LinkedHashSet, TreeSet 에 의해 구현된다.
 *
 * @param <E> the type of elements in this Set
 */
public interface SetInterface<E> {

    /**
     * 지정된 요소가 Set 에 없는 경우 요소를 추가한다.
     *
     * @param e 집합에 추가할 요소
     * @return {@code true} 만약 Set 에 지정 요소가 포함되어있지 않아 정상적으로 추가되었을 경우,
     *          else, {@code false}
     */
    boolean add(E e);

    /**
     * 지정된 요소가 Set 에 있는 경우 해당 요소를 삭제한다.
     *
     * @param o 집합에서 삭제할 요소
     * @return {@code true} 만약 Set 에 지정 요소가 포함되어 정상적으로 삭제되었을 경우,
     *          else, {@code false}
     */
    boolean remove(Object o);

    /**
     * 현재 집합에 특정 요소가 포함되었는지를 확인한다.
     *
     * @param o 집합에서 찾을 요소
     * @return {@code true} Set 에 지정 요소가 포함되어 있을 경우,
     *          else, {@code false}
     */
    boolean contains(Object o);

    /**
     * 지정된 객체가 현재 집합과 같은 여부를 반환한다.
     *
     * @param o 집합과 비교할 객체
     * @return  {@code true} 비교할 집합과 동일한 경우,
     *          else, {@code false}
     */
    boolean equals(Object o);

    /**
     * 현재 집합이 빈 상태인지 확인
     * @return  {@code true} 비어있는 경우,
     *          else, {@code false}
     */
    boolean isEmpty();

    /**
     * 집합의 요소 개수를 반환한다. 만약 들어있는 요소가
     * {@code Integer.MAX_VALUE}를 넘을 경우 {@code Integer.MAX_VALUE}를 반환한다.
     *
     * @return 집합에 들어있는 요소 개수 반환
     */
    int size();

    /**
     * 집합의 모든 요소를 제거한다.
     * 이 작업을 수행하면 빈 집합이 된다.
     */
    void clear();
}