HashSet과 TreeSet

알고리즘 문제풀이중에 HashSet을 사용하면 엄청 편하게 해결되는 문제를....

HashSet이 생각나지 않았던건 학습이 부족했었던 탓이라고 생각하여 !!

HashSet 그리고 TreeSet에 대해 추가학습하였습니다.

개념적인 부분과  비교부분은 http://swalloow.tistory.com/36 [MyCloud]   블로그를 참고하였습니다.

( 제가 보았을때 이해가 쉬웠던 블로그를 참고하여 저만의 방식으로 학습해보고 정리하였습니다.)

 HashSet

자바 컬렉션에서 제공하는 Set 인터페이스는 순서를 유지하지 않는 데이터의 집합으로,

Map 구조와 달리 중복된 값을 허용하지 않고 내부적으로 해싱을 이용해서 구현한 컬렉션입니다.
HashSet은 저장순서를 유지하지 않습니다.                

import java.util.*;

public class HashSetTest {
    public static void main(String[] a) {
        Set<Integer> set = new HashSet<>();
        Set<String> set2 = new HashSet<>();

        int[] valArr = {99,120,12, 1, 2, 2, 10, 3, 3, 5, 6, 10};
        for (int i = 0; i < valArr.length; i++) {
            set.add(valArr[i]);
        }
        System.out.print(set);

        System.out.println();

        String[] valArr2 = {"나", "다", "라", "마", "가", "차", "가", "하", "파", "파"};
        for (int i = 0; i < valArr2.length; i++) {
            set2.add(valArr2[i]);
        }
        System.out.print(set2);
    }
}

Set인터페이스를 상속받는 HashSet을 생성하였습니다.

그 후 for문을 통해 set에 Object를 추가하였습니다.

결과
[1, 2, 99, 3, 5, 6, 120, 10, 12]
[가, 다, 나, 마, 차, 하, 라, 파]

위 결과에서 볼 수 있듯이 중복을 허용하지 않는 점과 순서를 유지하지 않는점을 알 수 있습니다.

 TreeSet

TreeSet은 이진탐색트리(BinarySearchTree)의 형태로 데이터를 저장하는 컬렉션입니다.
이진탐색트리 중에서도 성능을 향상시킨 '레드-블랙 트리(Red-Black Tree)로 구현되어 있습니다.
따라서 데이터의 추가, 삭제에는 시간이 걸리지만, 검색과 정렬이 뛰어나다는 장점이 있습니다.
TreeSet은 마찬가지로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 

저장순서를 유지하지 않습니다.                            

import java.util.*;

public class TreeSetTest {
    public static void main(String[] a) {
      TreeSet<Integer> set2 = new TreeSet<>();

        ArrayList<Integer> numArr = new ArrayList<>();

        numArr.add(500);
        numArr.add(1);
        numArr.add(99);
        numArr.add(100);
        numArr.add(3);
        numArr.add(1000);

        for (int i = 0; i < numArr.size(); i++) {
            set2.add(numArr.get(i));
        }
        System.out.println(set2); //TreeSet 객체 전부를 반환
        System.out.println(set2.subSet(1,100)); // 1 이상 100미만 객체 반환
        System.out.println(set2.headSet(100)); // 100보다 작은 객체 반환
        System.out.println(set2.contains(199)); // 199 있는지 없는지에따라 true/false
        System.out.println(set2.tailSet(500)); //  500 이상의 객체 반환
    }
}

위의 TreeSet의 메소드들의 기능, 짐작하셨나요?

결과
[1, 3, 99, 100, 500, 1000]
[1, 3, 99]
[1, 3, 99]
false
[500, 1000]

subSet(E fromElement, E toElement)

 - fromElement 이상 toElement 미만의 객체를 반환합니다.

headSet(E toElement)

 - toElement보다 작은 객체를 반환합니다.

contains(Object o)

- Object를 포함하는 객체를 반환합니다.

tailSet(E fromElement)

- fromElement 이상의 객체를 반환합니다.

 HashSet과 TreeSet 비교

HashSet과 TreeSet 모두 중복을 허용하지 않고 순서가 없는 컬렉션입니다.

1. 구현 방식

 - HashSet은 해싱을 이용하여 구현
 - TreeSet은 이진탐색트리를 이용하여 구현

2. 속도 비교
 - HashSet > TreeSet
 - 해싱이 이진탐색트리보다 빠르다

3. 정렬 기능
 - HashSet < TreeSet
 - 이진탐색트리를 이용했기 때문에 데이터 정렬이 가능 (Comparator 이용)