[ 자료구조 ] 셋(Set)이란 무엇일까?

Set은 일반적으로 집합을 의미하는데, 집합은 중복된 값을 허용하지 않는다.

 

Set은 요소의 중복을 허용하지 않고, 저장 순서를 유지하지 않는 컬렉션이다. 

대표적인 클래스는 HashSet, TreeSet이 있다. 

 

HashSet

 

HashSet은  중복을 허용하지 않고, 저장 순서를 유지하지 않는 특징을 가지고 있다.

 

그렇다면 해당 값이 중복된 값인지 어떻게 판단할까?

 

1.  add(Object o)를 통해 객체를  저장하고자 할 때
2. 저장하고자 하는 객체의 해시코드를 hashcode()메서드를 통해 얻는다.
3. Set이 저장하고 있는 모든 객체들의 해시코드를 hashcode()메서드로 얻는다.
4. 저장하고자 하는 객체의 해시코드와, Set에 이미 저장되어져 있던 객체들의 해시코드를 비교하여, 같은 해시코드가 있는지 검사한다.
   1. 같은 해시코드를 가진 객체가 존재하면 5번으로 이동
   2. 그렇지 않는다면 Set에 객체가 추가되며 add(Object o)가 true를 리턴
5. equals()메서드를 통해 객체를 비교
   1. true가 리턴되면 중복 객체로 간주되어 Set에 추가되지 않으며, add(Object o)가 false를 리턴
   2. false가 리턴되면 Set에 객체가 추가되며, add(Object o)메서드가 true를 리턴

 

예제는 다음과 같다.

import java.util.*;

public class Main {
    public static void main(String[] args) {      
        HashSet<String > sports = new HashSet<String>(); // HashSet 생성

        // HashSet에 객체 추가
        sports.add("축구");
        sports.add("농구");
        sports.add("배구");
        sports.add("야구");
        sports.add("족구");
        sports.add("발야구");
        sports.add("수영");
        sports.add("축구");
        
        Iterator<String> game = sports.iterator(); // 반복자 생성
        
        while(game.hasNext()) { // HashSet 순회 및 각 요소들을 출력
            System.out.println(game.next());
        }
    }
}

출력값

축구는 한번만 출력되며 결과 순서는 랜덤하게 출력되었다.

 

 

TreeSet

 

TreeSet은 이진 탐색 트리 형태로 데이터를 저장한다. 

 

이진 탐색 트리(Binary Search Tree)란 하나의 부모 노드가 최대 두 개의 자식 노드와 연결되는 이진 트리(Binary Tree)의 일종으로, 정렬과 검색에 특화된 자료 구조다.

 

이 때 최상위 노드를 루트라고 하며 이진트리는 왼쪽의 자식 값이 루트나 부모보다 작고, 모든 오른쪽 자식 값이 루트나 부모보다 큰 값을 가진다.  

 

TreeSet코드는 다음과 같다.

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {

        // TreeSet 생성
        TreeSet<Integer> compare = new TreeSet<>();

        // TreeSet에 요소 추가
        compare.add(3);
        compare.add(10);
        compare.add(25);
        compare.add(40);
        compare.add(17);

        System.out.println(compare);
        System.out.println(compare.first());
        System.out.println(compare.last());
        System.out.println(compare.higher(10));
    }
}