(JAVA)HashSet, TreeSet

컬렉션의 전반적인 설명은 아래 링크를 참고하자.

https://acid7937.tistory.com/37

 

이번에는 Set을 알아볼 것이다.

 

Set은 순서가 없고 중복도 없다고 설명하였다.

순서 X 중복 X

 

이러한 특징을 가진게 주머니 혹은 가방(즉.. 이것은 집합이다) 라고 하였다.

 

개발하다가 집합과 관련되면 Set을 떠올리면 된다.

 

왼쪽 가방에는 사과, 바나나, 멜론이 있고 오른쪽 가방에는 사과, 수박, 복숭아가 있다면

 

교집합은 사과

합집합은 사과 바나나 멜론 수박 복숭아

왼쪽 - 오른쪽 차집합은 바나나 멜론 이 될것이다.

 

이것들은 Set을 사용하면 할수 있는 것이다.

 

먼저 Set이 어떻게 돌아가는지 코드를 통해 알아보자.

 

HashSet

앞서 사과 바나나 멜론이 한 가방에 있는것을 상상해 보았다.

 

String을 받는 코드를 만들었고 q를 넣으면 실행이 종료된후 출력한다.

 

사과와 바나나 멜론을 넣어보자

 

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


        HashSet<String> set = new HashSet<>();
        Scanner sc = new Scanner(System.in);
        for(;;){
            set.add(sc.next());
            if(set.contains("q")){
                break;
            }
        }
        set.remove(String.valueOf("q"));
        System.out.println(set);

            }
        }

 

실행결과는 다음과 같다.

 

사과를 3번 넣었고 바나나와 멜론도 넣었다.

 

그런데 출력 결과는 banana, apple, melon이 되는것을 확인할수 있다. 우리는 여기서 HashSet의 특징을 유추 할수가 있다.

 

HashSet은...

1) 중복이 안된다.

2) 입력 순서대로 출력이 안된다.

2-1) 출력 결과가 지 멋대로다.

 

 

지극히 당연한 소리지만 숫자도 마찬가지다.

 

Integer를 받을수 있게 코드를 변경한다음 숫자를 내 멋대로 넣어봤다.

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


        HashSet<Integer> set = new HashSet<>();
        Scanner sc = new Scanner(System.in);
        for(;;){
            set.add(sc.nextInt());
            if(set.contains(-1)){
                break;
            }
        }
        set.remove(Integer.valueOf(-1));
        System.out.println(set);

            }
        }

출력결과는 다음과 같다.

어떤가 이번에도 지 멋대로 출력을 하지 않는가?

 

 

 

또한, 우리는 HashSet을 사용하여 교집합 합집합 차집합 또한 만들수가 있다.

 

바로 retainAll, addAll, removeAll을 사용하면 간단히 해결할수 있다.

 

public class Main {
    public static void main(String[] args) {
        HashSet<String> groupA = new HashSet();
        HashSet<String> groupB = new HashSet();

        groupA.add("apple");
        groupA.add("banana");
        groupA.add("melon");
        groupB.add("apple");
        groupB.add("watermelon");
        groupB.add("peach");

        HashSet reset = (HashSet) groupA.clone();
        
        groupA.retainAll(groupB);
        System.out.println("교집합 = " + groupA);
        
        groupA = reset;
        groupA.addAll(groupB);
        System.out.println("합집합 = " + groupA);
        
        groupA = reset;
        groupA.removeAll(groupB);
        System.out.println("차집합 = " + groupA);
    }
}

출력 결과는 다음과 같다.

 

 

이처럼 우리는 일반적으로 Set이 필요한 상황이라면 HashSet을 사용하면 된다.

 

그럼 TreeSet은 뭘까.

 

TreeSet

Tree 나무라는 뜻이다. 말 그대로 TreeSet은 나무 처럼 가지를 치고 있는데 뿌리라고 생각하면 편하겠다 사진을 먼저 살펴보자.

 

 

용어를 설명하면.

 

노드(Node) : 트리 구조를 이루는 모든 개별 데이터
루트(Root) : 트리 구조의 시작점이 되는 노드
부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

 

 

TreeSet은 기본적으로 데이터를 저장할때 부모 노드를 기준으로 왼쪽 오른쪽으로 해서 두개의 값을 저장 한다.

 

사실 Tree는 Deque,Heap,BST 등등 종류가 많이 다양하고 응용하면 복잡하다.

 

여기서는 기본적인 TreeSet의 이진트리(Binary Tree) 개념만 살펴보겠다.

 

먼저 장단점을 말하면.

TreeSet의 장점으로는 검색이 빠르고 정렬에 좋고.

단점은 수정과 삭제가 느리다.

 

 

단점은 root에서 부터 스캔해야 하기 떄문에 추가 삭제 수정이 느리다 라고 기억하면 된다. 여기에서는 시간복잡도를 계산하지는 않겠다.

장점을 살펴보자. 코드로 보는게 제일 좋겠다.

 

(보통은 사람들이 보기 편한 숫자로 예제를 만드는데 숫자는 누가봐도 쉽게 알수 있지만 알파벳은 어떤식으로 자바에서 돌아가는지 예제를 궁금해 하는 사람이 있을수도 있을것 같아서 문자열로 트리를 코딩해 보았다.)

 

public class Main {
    public static void main(String[] args) {
        TreeSet<String> groupA = new TreeSet();

        groupA.add("orange");
        groupA.add("banana");
        groupA.add("apple");
        groupA.add("melon");
        groupA.add("apple");
        groupA.add("peach");
        groupA.add("watermelon");

        System.out.println(groupA.headSet("m"));
        System.out.println(groupA.tailSet("b"));
        System.out.println(groupA.subSet("a","o"));

        System.out.println("groupA = " + groupA);
    }
}

 

출력 결과는 다음과 같다.

 

HashSet과 비교하면 어떤 차이가 느껴지는가

 

눈치 빠른 사람을 알겠지만 문자열들이 알파벳 순으로 정렬이 되었다. (숫자를 이용하면 숫자 크기순으로 정렬된다.)

 

당연하지만 Set은 입력 순서를 보장 받지 못한다.

 

그리고 TreeSet은 구조상 탐색 시간에 유리한데 시간복잡도에 대해서는 나중에 알아보도록 하자.

 

메서드들을 여기서 전부 설명을 하지는 않겠지만

System.out.println(groupA.headSet("m"));

headSet을 사용하면 알파벳 m까지 문자열들을 검색할수 있다.

 

System.out.println(groupA.tailSet("b"));

tailSet을 사용하면 b 부터 z까지 숫자를 탐색한다.

 

System.out.println(groupA.subSet("a","o"));

subSet을 사용하면 알파벳의 범위를 설정한뒤 문자열들을 검색할수 있다.

 

이것들 말고도

System.out.println(groupA.higher("a"));

근처값을 찾는 이런것도 있고

System.out.println(groupA.last());

마지막 요소를 찾는 이런것도 있다.

앞서올린 메서드표를 한번 참고하자.

 

 

 

아래 숫자로 TreeSet을 한번더 이해해 보자.

 

 

 

모양이 위에서 부터 뿌리를 내리는 구조 같다.

 

그림을 잘 보면 8이랑 연결된 숫자가 3과 10이다.

 

3이랑 연결된 숫자는 1과 6이다.

 

우리는 여기서 규칙을 알수가 있는데, TreeSet은 값을 저장할때 작은수를 왼쪽에 큰수를 오른쪽에 저장한다.

 

즉, 8이 처음 들어온 숫자(root)고 3과(Child node) 10(Child node)이 들어 왔을때 자바는 비교를 한다.

 

3은 8보다 작으니 왼쪽에 저장, 10은 8보다 크니 오른쪽에 저장 이렇게 말이다.

 

이 상태에서 1,6,14가 입력 된다해도 맨위에서 부터 하나씩 타고 내려오게 된다.

 

6이 입력된다면 6이 8보다 작으니 왼쪽에, 6이 3보다 크니 오른쪽에 저장을 하게 된다는 뜻이다.

 

알파벳도 마찬가지다 a는 b보다 작고 이런식으로 말이다.(사전식 순서)

 

또한 TreeSet은 BST(binary search tree) 이진탐색트리가 기본형이다.(지금까지 설명한게 BST다) Tree의 다른 기능들과 시간복잡도들은 나중에 자료구조만 집중적으로 설명할때 같이 설명하겠다.(이 컬렉션 게시글에서 다루기에는 내용이 산으로 간다고 생각함)

 

 

 

 

마지막으로 우리는 정렬에 대해 알았는데.

 

사실 정렬은 안해주지만 Set도 입력 순서를 보장 하는 것이 있는데 그게

 

 

LinkedHashSet

이녀석은 중복은 물론 불가능하지만 입력한 순서대로 출력해준다.

 

public class Main {
    public static void main(String[] args) {
        LinkedHashSet<String> groupA = new LinkedHashSet();

        groupA.add("orange");
        groupA.add("banana");
        groupA.add("apple");
        groupA.add("melon");
        groupA.add("apple");
        groupA.add("peach");
        groupA.add("watermelon");

        System.out.println("groupA = " + groupA);
    }
}

출력 결과는 다음과 같다.

 

 

LinkedHashSet을 사용하니 출력 결과가 내가 입력한 순서와 같은걸 확인할수 있다.

 

 

 

(혹시나 정렬과 입력한 값의 순서를 헷갈리지 말자)