[자료구조] Set (Java) & HashSet이 정렬이 되는 이유

 

 Set (Java)

 

 

 

Set 이란?

 

Set은 수학적 집합을 표현한 중복되지 않은 요소들의 집합이다.

이를 통해 교집합, 합집합, 차집합 등을 구현할 수 있다. 

 

 

 

 

Set 특징

- 입력된 데이터의 순서를 보장하지 않는다.

- 데이터의 중복을 허용하지 않는다.

- 인덱스가 없기 때문에 Iterator를 사용해서 조회한다.

 

 

 

 

Set은 언제 사용하는지?

 

1) 중복된 데이터 제거

 

2) 특정 값이 존재 여부 확인

    - HashTable로 구현되어있기 때문에, 특정 값이 존재하는지 여부를 빠르게 조회할 수 있습니다.

 

3) 집합 연산

    - 합집합, 교집합, 차집합 등의 연산이 가능합니다.

 

 

 

 

 

Java - Set 인터페이스 구현 클래스

 

1) HashSet

- 입력 순서를 보장하지 않으며, 데이터 중복을 허용하지 않는다.

- 해시 테이블을 사용해 구현해서 데이터 크기와 상관없이 데이터 조회가 빠르다. 

    - 탐색에 특화된 자료구조로 평균 O(1)의 시간복잡도로 List보다 빠르다.

 

import java.util.HashSet;
import java.util.Set;


public class Main {
    public static void main(String[] args) {
    
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(5);
        set.add(4);
        set.add(3);

        //데이터 탐색
        boolean isContains = set.contains(3);
        System.out.println("Set에 3이 있는지? : " + isContains);

        //집합 연산
        Set<Integer> set2 = new HashSet<>();
        set2.add(4);
        set2.add(5);
        set2.add(7);
        set2.add(6);

        System.out.println("Set -> "+ set);
        System.out.println("Set2 -> "+ set2);

        //합집합
        Set<Integer> unionSet = new HashSet<>(set);
        unionSet.addAll(set2);
        System.out.println("합집합 : " + unionSet);

        //교집합
        Set<Integer> intersectionSet = new HashSet<>(set);
        intersectionSet.retainAll(set2);
        System.out.println("교집합 : " + intersectionSet);

        //차집합
        Set<Integer> differenceSet = new HashSet<>(set);
        differenceSet.removeAll(set2);
        System.out.println("차집합 : " + differenceSet);
    }
}

 

 

 

 

 

 

 

Q1) HashSet은 순서가 보장되지 않는데 출력값을 보면 순서대로 정렬이 되어있다. 정렬이 되는걸까?

 

-> 결론적으로는 정렬이 되지 않는다. HashSet은 Hash Table을 사용하기 때문에 첫 번째 테이블 인덱스부터 순차적으로 탐색하기 때문이다.

 

 

- 숫자 값을 랜덤하게 추가

Set<Integer> set = new HashSet<>();
set.add(0);
set.add(1);
set.add(5);
set.add(4);
set.add(3);
set.add(-1);
set.add(17);
set.add(16);
set.add(15);

System.out.println(set);

 

 

- 출력

 

 

 

- 해시 테이블 예시

 

------------------------------------------------------------> (좌에서 우로 출력된다)

 

 

 

 

2)LinkedHashSet

- 입력 순서를 보장하며, 데이터 중복을 허용하지 않는다.

 

import java.util.LinkedHashSet;
import java.util.Set;

public class HelloJava2 {
    public static void main(String[] arg){
        Set<Integer> set = new LinkedHashSet<>();
        set.add(101);
        set.add(105);
        set.add(104);
        set.add(103);

        //데이터 탐색
        boolean isContains = set.contains(3);
        System.out.println("Set에 3이 있는지? : " + isContains);

        //집합 연산
        Set<Integer> set2 = new LinkedHashSet<>();
        set2.add(104);
        set2.add(105);
        set2.add(107);
        set2.add(106);

        System.out.println("Set -> "+ set);
        System.out.println("Set2 -> "+ set2);

        //합집합
        Set<Integer> unionSet = new LinkedHashSet<>(set);
        unionSet.addAll(set2);
        System.out.println("합집합 : " + unionSet);

        //교집합
        Set<Integer> intersectionSet = new LinkedHashSet<>(set);
        intersectionSet.retainAll(set2);
        System.out.println("교집합 : " + intersectionSet);

        //차집합
        Set<Integer> differenceSet = new LinkedHashSet<>(set);
        differenceSet.removeAll(set2);
        System.out.println("차집합 : " + differenceSet);
    }
}

 

 

 

 

 

 

 

3) TreeSet

- 입력한 데이터의 크기가 비교 가능한 경우 오름차순으로 정렬되고, 데이터 중복을 허용하지 않는다.

- TreeSet은 이진탐색트리 중에서도 성능을 향상시킨 레드-블랙 트리로 구현되어 있다.

- 입력한 데이터가 사용자 정의 객체인 경우 Comparable을 구현하여, 정렬 기준을 설정 가능하다.

 

 

import java.util.Set;
import java.util.TreeSet;

public class Test {
    public static void main(String[] arg){
        Set<Integer> set = new TreeSet<>();
        set.add(101);
        set.add(105);
        set.add(104);
        set.add(103);

        //데이터 탐색
        boolean isContains = set.contains(3);
        System.out.println("Set에 3이 있는지? : " + isContains);

        //집합 연산
        Set<Integer> set2 = new TreeSet<>();
        set2.add(104);
        set2.add(105);
        set2.add(107);
        set2.add(106);

        System.out.println("Set -> "+ set);
        System.out.println("Set2 -> "+ set2);

        //합집합
        Set<Integer> unionSet = new TreeSet<>(set);
        unionSet.addAll(set2);
        System.out.println("합집합 : " + unionSet);

        //교집합
        Set<Integer> intersectionSet = new TreeSet<>(set);
        intersectionSet.retainAll(set2);
        System.out.println("교집합 : " + intersectionSet);

        //차집합
        Set<Integer> differenceSet = new TreeSet<>(set);
        differenceSet.removeAll(set2);
        System.out.println("차집합 : " + differenceSet);
    }
}

 

 

 

 

 

 

 

 

 

Set, List, Map의 주요 특징 정리

 

인터페이스	구현체	순서유지	중복허용	참고
Set	HashSet	X	X
	LinkedHashSet	O	X
	TreeSet	X	X	입력순서는 보장되지 않지만, 입력된 데이터에 따라 정렬되서 저장된다.
List	ArrayList	O	O
	LinkedList	O	O
Map	HashMap	X	Key:X , Value:O
	LinkedHashMap	O	Key:X , Value:O
	TreeMap	X	Key:X , Value:O	입력순서는 보장되지 않지만, 입력된 Key 데이터에 따라 정렬되서 저장된다.

 

 

 

1) 메모리 측면

 

Set은 해시값을 저장해야 하기 때문에, 메모리를 많이 차지한다.

List는 해시값이나 포인터 없이 값만 순차적으로 저장해, 메모리를 적게 쓴다.

 

 

 

2) Iteration 속도

 

List가 구현 특성 상 단순해서 더 빠르다.

HashSet은 내부 배열에 빈 공간이 존재해 데이터 Iteration 시에 오버헤드가 발생한다.

LinkedHashSet은 LinkedList로 연결해둬서 빈 공간은 없지만, 포인터가 필요해 메모리를 더 많이 쓴다.

 

 

 

 

 

 

 

 

 

 

[참고]

[간단정리] List, Set, Map 특징 및 차이점(+ 구현체 )

 

[자료구조] Set과 HashSet: 개념, List vs Set (메모리와 iteration 속도 관점에서)

 

[Java] HashSet의 비밀