Collection Framework - Set

Set Interface

Set인터페이스는 중복을 허용하지 않고 입력순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용된다. Set인터페이스를 구현한 클래스로는 HashSet, TreeSet등이 있다. HashSet은 HashMap을 사용하여 데이터를 저장하고, TreeSet은 이진검색트리를 이용하여 데이터를 저장한다.

HashSet

HashSet은 Set인터페이스의 특징대로 중복된 요소를 저장하지 않으며, 입력순서를 보장하지 않는다. add, addAll을 통해서 데이터를 저장하고 만약 중복 된 데이터를 추가하는 경우 false를 반환한다.

내부적으로는 HashMap을 이용하여 데이터를 저장한다.

LinkedHashSet

HashSet은 저장순서를 보장하지 않지만, LinkedHashSet은 저장 순서를 보장한다. Set의 기본특성인 중복불가, 순서보장X에는 조금 예외가 잇는 구현체이다. LinekdHashSet이 입력순서를 보장하는 이유는 HashSet은 HashMap을 통해 데이터를 저장하는 반면, LinkedHashSet은 LinkedHashMap을 통해서 데이터를 저장하기 때문이다.

TreeSet

TreeSet은 이진검색트리 자료구조를 이용하여 데이터를 저장한다. 이진검색트리는 정렬, 검색, 범위검색에 뛰어난 성능을 보장하는 자료구조 이다. 실제 TreeSet은 이진검색트리의 성능을 향상시킨 '레드-블랙 트리로 구현되어 있다. 그리고 역시 Set의 특성에 맞게 중복된 데이터를 추가 할 수 없고 입력순서를 보장하지 않는다. (사실 이진검색트리 자체가 추가하는 경우 알아서 데이터의 크기 순으로 저장한다)

내부적으로는 TreeMap을 통해서 데이터를 저장한다.

equals와 hashCode : 중복된 데이터 확인

Set인터페이스는 중복을 불허한다. 그렇다면 어떻게 추가 된 요소가 이미 있는 요소인지 비교할까. Set인터페이스 혹은 다른 여러 자료구조는 입력하는 데이터 클래스의 equals()와 hashCode()를 통해서 같은 객체인지 비교한다. 주의할 점은 equals를 통해서 비교하는 클래스도 있고, hashCode도 함께 체크하는 클래스도 있다.

public class Human implements Comparable<Human>{
    int age;
    String name;
    
    public Human(int a, String b) {
        age = a;
        name = b;
    }
 
    @Override
    public int hashCode() {
        return age;
    }
 
    @Override
    public int compareTo(Human o) {
        if(this.age > o.age) return 1;
        else if(this.age < o.age) return -1;
        return 0;
    }
    
}

예를들어 HashSet은 동일한 hashCode를 리턴하더라도 두 객체를 다르게 판단하여 추가가 가능하다.

public static void main(String[] args) {
        Human h1 = new Human(1, "이지수1");  
        Human h2 = new Human(2, "이지수2");  
        Human h3 = new Human(2, "이지수2"); 
        
        HashSet<Human> set = new HashSet<Human>();
        set.add(h1);
        set.add(h2);
        set.add(h3);
        
        System.out.println(set.size());
        System.out.println(set);
}

결과 : size = 3

반면, TreeSet은 동일한 hashCode를 리턴하면 두 객체를 같은 객체로 판단한다.

public static void main(String[] args) {
        Human h1 = new Human(1, "이지수1");  
        Human h2 = new Human(2, "이지수2");  
        Human h3 = new Human(2, "이지수2"); 
        
        TreeSet<Human> set = new TreeSet<Human>();
        set.add(h1);
        set.add(h2);
        set.add(h3);
        
        System.out.println(set.size());
        System.out.println(set);
}

결과 : size = 2 

위 처럼 사용자가 equals와 hashCode를 Override하여 다른 객체를 동일 객체로 판단하게 하는 것이 가능하다.

Comparator와 Comparable : 크기비교

Comparable : 기본 정렬을 구현하는데 사용.

Comparator : 기본 정렬기준 외에 다른 기준이 필요한 경우 사용.

Comparable

TreeSet에서는 입력한 데이터의 정렬이 이진검색트리를 통하여 자동으로 정렬된 상태로 저장된다. 또한 Collections.sort(List<T> list) 메소드를 이용하여 List를 정렬하는 것도 가능하다. 그렇다면 정렬의 기준은 무엇일까. 일반적으로 Collection들은 입력 된 데이터가 Comparable임을 가정하고 정렬을 수행한다. Comparable 인터페이스는 compareTo 메소드를 구현해야 하고, compareTo를 Override하여 어느 객체가 더 큰지 리턴하는 것이 가능하다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class Human implements Comparable<Human>{     int age;     String name;          public Human(int a, String b) {         age = a;         name = b;     }       @Override     public int hashCode() {         return age;     }       @Override     public int compareTo(Human o) {         if(this.age > o.age) return 1;         else if(this.age < o.age) return -1;         return 0;     }      } Colored by Color Scripter

cs

위에 예시로 제시 된 자료 내용을 구현하는 경우 age의 순서에 따라 저장될 것이다. 즉 순서를 고려한 정렬에서는 입력된 데이터 클래스의 compareTo메소드를 통하여 정렬기준을 잡는다.

Comparator

추가적으로 Comparator를 직접 구현하는 방법이있다. 

public static void main(String[] args) {
 
        TreeSet<Integer> set = new TreeSet<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -1*o1.compareTo(o2);
            }
        });
        
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        set.add(5);
        
        System.out.println(set);
}

결과 : 5, 4, 3, 2, 1

TreeSet을 구현하면서 생성자로 Comparator를 지정하였다. 기본 Comparator인터페이스의 메소드인 compare를 리턴하는 과정에서 -1을 곱하여 역순으로 정렬한 소스이다.

Summary

Class	구현	입력순서	정렬순서
HashSet	HashMap을 통해 구현	무시	없음
TreeSet	이전검색Tree를 통해 구현	무시	자동순차정렬
LinkedHashSet	LinkedHashMap을 통해 구현	유지	없음

관련글 보기

Collection Framework

List Interface : ArrayList, LinkedList, Stack and Queue

Set Interface : HashSet, LinkedHashSet, TreeSet, Comparable, Comparator

Map Interface : HashMap, LinkedHashMap, TreeMap