[Java] - Set / HashSet / TreeSet

HashSet

• Set 인터페이스를 구현한 가장 대표적인 컬렉션이다.
• Set 인터페이스의 특징인 중복된 요소를 저장하지 않는다.
• 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야한다.
  

💡 HashSet은 내부적으로 HashMap을 이용해서 만들어졌으며, 해싱(hashing) 을 이용해서 구현했기 때문에 붙여진 것이다.

다음은 Set을 사용한 예제이다.

코드

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(1);
set.add(1);
set.add(2);
set.add(2);
set.add(3);
System.out.println(set);

결과

[1, 2, 3]

결과를 보면 중복된 값은 저장되지 않는다.

코드

Set<Integer> set = new HashSet();

for (int i = 0; set.size() < 6; i++) {
    int num = (int)(Math.random() * 45) + 1;
    set.add(num);
}

List<Integer> list = new LinkedList<>(set);
Collections.sort(list);
System.out.println(list);

결과

[3, 12, 16, 26, 33, 44]

위는 HashSet의 특징을 이용해서 로또번호를 만드는 예제이다.
Math.random()을 사용했기 때문에 실행 시 결과는 매번 다르다.
번호를 크기 순으로 정렬하기 위해 list로 변경후 Collection.sort()를 사용했다.

코드

Set<Integer> set = new HashSet<>();
int[][] board = new int[5][5];

for (int i = 0; set.size() < 25; i++) {
    set.add((int)(Math.random() * 50) + 1);
}

Iterator<Integer> it = set.iterator();

for (int[] bo : board) {
    Arrays.stream(bo)
            .map(b -> it.next())
            .mapToObj(next -> (next < 10 ? "  " : " ") + next)
            .forEach(System.out::print);
    System.out.println();
}

결과

  2  3  8  9 10
 11 12 14 15 16
 21 22 23 26 27
 28 31 32 35 37
 39 44 46 48 49

1~50 사이의 숫자를 25개 골라서 '5x5' 빙고판을 만드는 예제이다.
Math.random()을 사용했기 때문에 실행할 때 마다 결과가 다르지만
여러번 실행해보면 같은 숫자가 비슷한 위치에 나오는 사실을 발견할 수 있다.
이유는 HashSet은 저장된 순서를 보장하지 않고 자체적인 저장방식에 따라 순서가 결정되기 때문이다.

코드

public class HashSetEx {
    public static void main(String[] args) {
        Set<Person> set = new HashSet<>();

        set.add(new Person("Lee", 20));
        set.add(new Person("Lee", 20));

        System.out.println(set);
    }
}

class Person {
    String name;
    int age;

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

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

결과

[Lee:20, Lee:20]

위의 예제에서 name과 age가 같으면 두 인스턴스를 같은 것으로 인식해서 Set에 하나의 데이터를 넣고 싶다면 어떻게 해야할까?

-> equals()와 hashCode()를 오버라이딩 하면 된다.

class Person {
    String name;
    int age;

    ...

    @Override
    public boolean equals(Object o) {
        if (o instanceof Person) {
            Person tmp = (Person) o;
            return name.equals(tmp.name) && age == tmp.age;
        }
        return false;
    }

    public int hashCode() {
        return Objects.hash(name, age);
    }
}

오버라이딩을 통해 작성된 hashCode() 는 다음의 세 가지 조건을 만족해야한다.

1. 실행 중인 애플리케이션 내의 동일한 객체에 대해서 여러 번 hashCode()를 호출해도
   동일한 int값을 반환해야한다. 하지만, 실행시마다 동일한 int값을 반환할 필요는 없다.
   (단, equlas 메소드의 구현에 사용된 멤버변수의 값이 바뀌지 않았다고 가정)
2. equals 메소드를 이용한 비교에 의해서 true를 얻은 두 객체에 대해 각각 hashCode() 를 호출해서
   얻은 결과는 반드시 같아야 한다.
3. equals 메소드를 호출했을 때 false를 반환하는 두 객체는 hashCode() 호출에 대해 같은 int값을
   반환하는 경우가 있어도 괜찮지만, 해싱(hashing)을 사용하는 컬렉션의 성능을 향상시키기 위해서는
   다른 int값을 반환하는 것이 좋다.

---

TreeSet

• 이진 검색 트리(binary search tree) 라는 자료구조의 형태로 데이터를 저장
• 이진 검색 트리의 성능을 향상시킨 'Red Black tree'로 구현
• 중복된 데이터의 저장을 허용하지 않고, 정렬된 위치에 저장하므로 저장순서를 유지하지 않음
• 정렬된 순서를 유지 하기 때문에 단일 값 검색, 범위검색(range search)에 매우 빠름
• 저장위치를 찾아서 저장하고, 삭제할 경우 트리 일부를 재구성하므로 LinkedList보다 데이터 추가/삭제 시간이 더 소요
• Array, LinkedList에 비해 검색과 정렬기능이 뛰어남

이진검색트리?

• 모든 노드는 최대 두 개의 자식노드를 가진다.
• 왼쪽 자식노드의 값은 부모노드 값보다 작고 오른쪽 자식노드의 값은 부모노드 값보다 크다.
• 노드 추가/삭제에 시간이 걸린다.
• 검색(범위검색)과 정렬에 유리하다.
• 중복된 값을 저장하지 못한다.

다음은 TreeSet을 사용한 예제이다.

코드

Set<Integer> set = new TreeSet<>();

for (int i = 0; set.size() < 6; i++) {
        int num = (int)(Math.random() * 45) + 1;
        set.add(num);
}

System.out.println(set);

결과

[2, 6, 13, 16, 23, 40]

위의 HashSet 로또예제와 다르게 TreeSet은 저장할 때 이미 정렬하기 때문에 따로 정렬할 필요가 없다.

코드

TreeSet<String> set = new TreeSet<>();

String from = "b";
String to = "d";

set.add("abc");
set.add("apple");
set.add("banana");
set.add("bowl");
set.add("box");
set.add("cat");
set.add("cow");
set.add("dry");
set.add("drill");
set.add("email");
set.add("entry");
set.add("file");
set.add("feed");

System.out.println(set);
System.out.println("range search: from " + from + " to " + to);
System.out.println("result1 : " + set.subSet(from, to));

결과

[abc, apple, banana, bowl, box, cat, cow, drill, dry, email, entry, feed, file]
range search: from b to d
result1 : [banana, bowl, box, cat, cow]

subSet() 메소드를 이용하여 특정 범위를 검색할 수 있다.
위의 예제는 b~d 범위를 검색하는데 d는 포함되지 않아서 b~c로 시작하는 문자열이 검색된다.

코드

TreeSet<Integer> set = new TreeSet<>();
int[] score = {88, 95, 70, 30, 50, 60, 100, 10, 47};

for (int s : score) {
    set.add(s);
}

System.out.println("60 미만 : " + set.headSet(60));
System.out.println("60 이상 : " + set.tailSet(60));

결과

60 미만 : [10, 30, 47, 50]
60 이상 : [60, 70, 88, 95, 100]

headSet() 메소드와 tailSet() 메소드를 이용해서 특정값 보다 크거나 작은 값을 구할 수 있다.

References

• 남궁성, 『자바의 정석』, 도우출판(2016)