[Java] Set 컬렉션 클래스

Set 컬렉션 클래스

• 인스턴스 저장 순서를 유지하지 않는다.
• 동일 인스턴스의 중복 저장을 허용하지 않는다.

컬렉션 클래스	설명
HashSet<E>	해시 자료구조를 기반으로 인스턴스를 저장, 정렬 x
TreeSet<E>	트리 자료구조를 기반으로 인스턴스를 저장, 정렬 o

public class SetCollection_Feature {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("cat");
        set.add("dog");
        set.add("pig");
        set.add("dog"); // 동일 인스턴스 저장 x
        System.out.println("저장된 인스턴스 수: " + set.size());

        // for-each문을 이용한 전체 출력
        for(String s : set)
            System.out.print(s + " ");
        System.out.println();

        // 반복자를 이용한 전체 출력
        for (Iterator<String> itr = set.iterator(); itr.hasNext();)
            System.out.print(itr.next() + " ");
        System.out.println();
    }
}

// 실행 결과
저장된 인스턴스 수: 3
cat dog pig 
cat dog pig

 

 

HashSet

• HashSet 클래스는 해시 알고리즘(hash algorithm)을 사용해 검색 속도가 매우 빠르다.
• HashSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 동일한 요소는 저장하지 않는다.
  • 이때 동일한 요소인지 판단하는 과정은?
    • 해당 요소에서 hashCode()를 호출해 반환된 해시값으로 검색할 범위를 결정한다.
    • 해당 범위 내의 요소들을 equals()로 비교한다.
    • 따라서  HashSet에서 중복 없이 새로운 요소를 추가하기 위해서는 hashCode()와 eqauls() 메소드를 상황에 맞게 오버라이딩해야 한다.

/* (오버라이딩 전) */

class Num {
    private int num;
    public Num(int num) { this.num = num; }

    @Override
    public String toString() {
        return String.valueOf(num);
    }
}

class SetCollection_HashSetEquals {
    public static void main(String[] args) {
        HashSet<Num> set = new HashSet<>();
        set.add(new Num(7799));
        set.add(new Num(9955));
        set.add(new Num(7799)); // 동일 인스턴스로 간주하지 않음
        System.out.println("저장된 인스턴스 수: " + set.size());

        for(Num n : set)
            System.out.print(n.toString() + " ");
        System.out.println();
    }
}

// 실행 결과
저장된 인스턴스 수: 3
9955 7799 7799

오버라이딩 후 실행 결과를 보면 동일한 인스턴스를 중복 저장하지 않음을 확인 할 수 있다.

 

해시 알고리즘

해시 알고리즘(hash algorithm)은 나머지를 기준으로 데이터를 분류 해놓고, 확인 대상인 데이터의 나머지 연산결과에 따라 속하는 부류를 찾아 그 부류 내에서 탐색을 진행하기 때문에 탐색의 속도가 매우 빠르다.

• 분류 대상 : 3, 5, 7, 12, 25, 31
  확인 대상 : 5
  적용 해시 알고리즘 : num % 3
• 분류 결과
  
• 탐색 단계
  1. 정수 5의 해시 값을 계산하여 탐색 부류를 결정
     → Object 클래스에 정의된 hashCode 메소드의 반환 값을 기반으로 부류 결정
     → 이로써 3, 7, 12, 25, 31은 탐색 대상에서 제외
  2. 선택된 부류 내에 정수 5가 존재하는지 확인
     → equals 메소드를 호출하여 동일한지 비교

 

해시 알고리즘 정의하기

class Car {
    private String model;
    private String color;

    public Car(String model, String color) {
        this.model = model;
        this.color = color;
    }

    @Override
    public String toString() {
        return model + " : " + color;
    }

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

    @Override
    public boolean equals(Object obj) {
        String m = ((Car)obj).model;
        String c = ((Car)obj).color;

        if(model.equals(m) && color.equals(c))
            return true;
        else
            return false;
    }
}

class SetCollection_HashCode {
    public static void main(String[] args) {
        HashSet<Car> set = new HashSet<>();

        set.add(new Car("HY_MD_301", "RED"));
        set.add(new Car("HY_MD_301", "BLACK"));
        set.add(new Car("HY_MD_302", "RED"));
        set.add(new Car("HY_MD_302", "WHITE"));
        set.add(new Car("HY_MD_301", "BLACK"));

        System.out.println("인스턴스 수: " + set.size());

        for (Car c : set)
            System.out.println(c.toString());
    }
}

// 실행 결과
인스턴스 수: 4
HY_MD_301 : RED
HY_MD_302 : RED
HY_MD_301 : BLACK
HY_MD_302 : WHITE

 

해시 알고리즘 일일히 정의하기 어렵다면?

• 클래스를 정의할 때마다 hashCode() 메소드를 정의하는 것은 번거로운 일이다.
• 따라서 자바에서는 hash() 메소드를 제공한다.

public static int hash(Object...values)

• java.util.Objects에 정의된 메소드
• 전달된 인자를 기반으로 해시 값을 반환한다.
• hash() 메소드는 하나 이상의 인자를 조합하여 하나의 해쉬 값을 만들어 반환해주기 때문에, 특별한 경우가 아니라면 직접 해쉬 알고리즘을 만들지 않고 다음과 같이 hash( ) 메소드를 오버라이딩 해서 사용하면 된다.

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

 

 

TreeSet

• TreeSet 클래스는 트리(Tree)라는 자료구조를 기반으로 인스턴스를 저장한다.
  • 트리라는 자료구조의 특성상 정렬된 상태로 인스턴스가 저장된다.
  • 이때 정렬은 오름차순(작은→큰)을 기준으로 한다.
• 데이터를 추가하거나 제거하는 등 기본 동작 시간이 매우 빠르다.

class SetCollection_TreeSetSorted {
    public static void main(String[] args) {
        TreeSet<Integer> tree = new TreeSet<>();

        // add 메소드를 통한 요소 저장
        tree.add(3);
        tree.add(1);
        tree.add(2);
        tree.add(4);	
        System.out.println("인스턴스 수: " + tree.size()); // size 메소드를 통한 요소의 총 개수

        // for-each문을 통한 전체 출력
        for (Integer n : tree)
            System.out.print(n + " ");
        System.out.println();

        // remove 메소드를 통한 요소 삭제
        tree.remove(2);
        System.out.println("인스턴스 수: " + tree.size()); // size 메소드를 통한 요소의 총 개수

        // Iterator 반복자를 통한 전체 출력
        for (Iterator<Integer> itr = tree.iterator(); itr.hasNext();)
            System.out.print(itr.next() + " ");
        System.out.println();
    }
}

// 실행 결과
인스턴스 수: 4
1 2 3 4 
인스턴스 수: 3
1 3 4

 

만약 기본 오름차순이 아닌 내림차순을 원한다면 다음과 같이 TreeSet을 생성하면된다.

TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());

 

Comparable 인터페이스 기반 정렬 기준 제시

• 숫자의 경우 크고 작음에 대한 비교 기준이 있지만, 숫자가 아닌 경우 크고 작음에 대한 비교가 어렵기 때문에 정렬 기준에 대한 정의를 해줘야 한다.
• comparerable<T> 인터페이스의 compareTo() 메소드 구현을 통해 크고 작음의 기준을 정해줄 수 있다.
• TreeSet 인스턴스는 compareTo() 메소드의 호출 결과를 바탕으로, 저장된 인스턴스들이 정렬된 상태를 유지하게 한다.
• 따라서 TreeSet<T>에 저장할 인스턴스들은 모두 Comparable<T> 인터페이스를 구현한 클래스의 인스턴스이어야 한다.

💡 Comparable 인터페이스

public interface Comparable<T> {
    public int compareTo(T o); // 추상 메소드
}

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

class Person implements Comparable<Person> { // Comparable<T>를 구현하는 Person 클래스 정의
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return name + " : " + age;
    }

    // comparTo 메소드 오버라이딩
    @Override
    public int compareTo(Person p) {
        return this.age - p.age;
    }
}

class SetCollection_TreeSet_Comparable {
    public static void main(String[] args) {
        TreeSet<Person> tree = new TreeSet<>();

        tree.add(new Person("anne", 26));
        tree.add(new Person("jeong", 25));
        tree.add(new Person("jun", 27));

        for(Person p : tree)
            System.out.println(p + " ");
    }
}

// 실행 결과
jeong : 25 
anne : 26 
jun : 27

• compareTo 메소드 인자로 전달된 인스턴스의 나이가 더 많을 경우 음수를 반환하도록 구현
  • 즉, 나이가 많으면 오름차순 정렬 순서상 뒤쪽에 위치하게 된다.
  • 만약 나이가 많으면 앞쪽에 위치하도록 하고 싶다면 다음과 같이 수정하면 된다.
    • this.age - p.age (나이가 많으면 뒤로)
    • p.age - this.age(나이가 많으면 앞으로)

 

Comparator 인터페이스 기반 정렬 기준 제시

• 클래스에 정의되어 있던 정렬 기준을 바꾸고 싶은 경우 Comparator 인터페이스를 구현하는 클래스를 디자인하면 된다. (새로운 정렬 기준 마련)

💡 Comparator 인터페이스

public interface Comparator<T> {
    public int compareTo(T o1, T o2); // 추상 메소드
}

• o1이 o2보다 크다면 양의 정수 반환
• o1이 o2보다 작다면 음의 정수 반환
• o1과 o2가 같다면 0 반환

class Person implements Comparable<Person> {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return name + " : " + age;
    }

    @Override
    public int compareTo(Person p) {
        return this.age - p.age;
    }
}

class PersonComparator implements Comparator<Person> {
    public int compare(Person p1, Person p2) {
        return p2.age - p1.age; // 나이가 많은 사람을 앞에 세우는 연산
    }
}

class SetCollection_TreeSet_Comparator {
    public static void main(String[] args) {
        TreeSet<Person> tree = new TreeSet<>(new PersonComparator());

        tree.add(new Person("anne", 26));
        tree.add(new Person("wuga", 26));
        tree.add(new Person("jeong", 25));
        tree.add(new Person("jun", 27));

        for(Person2 p : tree)
            System.out.println(p + " ");
    }
}

// 실행 결과
jun : 27 
anne : 26 
jeong : 25

 

---

 

Reference

http://www.tcpschool.com/java/java_collectionFramework_set