[Java API] Set 인터페이스(HashSet, LinkedHashSet, TreeSet)

https://claremont.tistory.com/entry/Java-API-%EC%BB%AC%EB%A0%89%EC%85%98-%ED%94%84%EB%A0%88%EC%9E%84%EC%9B%8C%ED%81%ACCollection-Framework

[Java API] 컬렉션 프레임워크(Collection Framework)

https://claremont.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-ep4-%EC%A7%91%ED%95%A9Set

[자료구조] ep4) 집합(Set)

ㅁSet(집합): 순서가 없고 중복이 없는 자료구조

순서 X, 중복 X

 

 

컬렉션 프레임워크 - 컬렉션 인터페이스 - 세트 인터페이스

Set 인터페이스

Set 인터페이스는 java.util 패키지의 컬렉션 프레임워크에 속하는 인터페이스 중 하나이다. Set 인터페이스는 중복을 허용하지 않는 유일한 요소의 집합을 나타낸다. 즉, 어떤 요소도 같은 Set 내에 두 번 이상 나타날 수 없다. Set은 수학적 집합 개념을 구현한 것으로, 순서를 보장하지 않으며, 특정 요소가 집합에 있는지 여부를 확인하는 데에 최적화되어 있다. (순서 X, 중복 X)

Set 인터페이스는 HashSet(순서 X, 중복 X), LinkedHashSet(순서 O, 중복 X), TreeSet(순서 - 정렬, 중복 X) 등의 여러 구현 클래스를 가지고 있으며, 각 클래스는 Set 인터페이스를 구현하며 각각의 특성을 가지고 있다.

 

 

[Set 인터페이스의 주요 메서드]

 

 

https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep4-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94hashtable

[알고리즘] ep4) 해시테이블(hashtable)

ㅇHashSet: hash 자료구조를 사용해 Set을 구현

 

- HashSet의 주요 연산(추가, 삭제, 검색)은 평균 O(1) 시간 복잡도를 가진다

 

 

ㅇLinkedHashSet: HashSet + LinkedList (HashSet의 순서가 있는 버전)

 

- 그림에서 이해를 돕기 위해 단방향 화살표로 나타냈지만, 실제로는 양방향이다

- HashSet과 마찬가지로 주요 연산(추가, 삭제, 검색)은 평균 O(1) 시간 복잡도를 가진다

- 데이터의 유일성과 함께 삽입 순서를 유지해야 할 때 적합하다

 

 

https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep3-%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%AC

[알고리즘] ep3) 탐색트리

ㅇTreeSet: 이진탐색 트리를 사용해 Set을 구현 (레드-블랙 트리를 사용해 균형을 유지 -> 최악의 상황에도 O(log n) 성능)

이진탐색 트리 - 작은 값을 왼쪽에 / 큰 값을 오른쪽에

 

- 요소들은 입력되는 시점에 정렬된 순서로 저장되며, 순서의 기준은 비교자(Comparator)로 변경할 수 있다

- 주요 연산들은 O(log n) 시간 복잡도를 가진다 (HashSet보다는 느리다)

- 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용한다

class Node {
    Object item;
    Node left;
    Node right;
}

 

 

 

해시 자료구조를 사용하려면 반드시 hashCode()와 equals()를 오버라이딩 해야 한다. 참고로 자바가 제공하는 String, Integer 같은 기본 클래스들은 전부 hashCode(), equals()가 오버라이딩 되어 있어 따로 해줄 필요가 없다. 따라서 우리는 커스텀 객체에 대해서만 필요할 때 오버라이딩을 하면 된다.

 

실무에서는 Set이 필요한 경우 HashSet을 가장 많이 사용한다. 그리고 입력 순서 유지, 값 정렬 필요에 따라서 LinkedHashSet, TreeSet을 선택하면 된다.

(HashSet, LinkedHashSet, TreeSet 사용 예시 코드)

package collection.set;

import java.util.*;

public class SetMain {
    public static void main(String[] args) {
        run(new HashSet<>()); // 순서 X, 중복 X
        run(new LinkedHashSet<>()); // 순서 O, 중복 X
        run(new TreeSet<>()); // 순서 - 정렬, 중복 X
    }

    private static void run(Set<String> set) {
        System.out.println("set = " + set.getClass());
        set.add("C");
        set.add("B");
        set.add("A");
        set.add("1");
        set.add("2");

        // Set은 순서가 없으므로 get 메서드 또한 없다
        // 따라서 반복자 iterator나 for-each문을 사용해야 한다
        Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();
    }
}

 

 

 

(합집합, 교집합, 차집합 예시 코드)

package collection.set.ex2;

import java.util.HashSet;
import java.util.List;

public class SetOperationsTest {
    public static void main(String[] args) {
        HashSet<Integer> set1 = new HashSet<>(List.of(1, 2, 3, 4, 5));
        HashSet<Integer> set2 = new HashSet<>(List.of(3, 4, 5, 6, 7));

        HashSet<Integer> union = new HashSet<>();
        union.addAll(set1);
        union.addAll(set2);
        System.out.println("합집합: " + union);

        HashSet<Integer> intersection = new HashSet<>();
        intersection.addAll(set1);
        intersection.retainAll(set2);
        System.out.println("교집합: " + intersection);

        HashSet<Integer> difference = new HashSet<>();
        difference.addAll(set1);
        difference.removeAll(set2);
        System.out.println("차집합: " + difference);
    }
}

 

 

 

 

 

 

 

 

참고 및 출처: 김영한의 실전 자바 - 중급 2편

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2