Set

김성호·2023년 3월 17일
0

자료구조

목록 보기
4/7

Set이란

중복된 원소를 허용하지 않는 추상 데이터 타입(ADT)입니다. 모든 원소는 유일해야 하며, 순서에 따라 정렬되지 않습니다. Set은 일반적으로 검색, 삽입, 삭제 연산이 빠르기 때문에 데이터를 빠르게 저장하고 검색할 때 유용합니다.

Set의 연산

  1. 추가(add) 연산
    Set에 새로운 원소를 추가합니다. 중복된 원소를 추가하면 무시됩니다.

  2. 삭제(remove) 연산
    Set에서 지정된 원소를 삭제합니다. 원소가 Set에 없으면 아무 작업도 수행하지 않습니다.

  3. 크기(size) 연산
    Set에 저장된 원소의 개수를 반환합니다.

  4. 포함 여부(contains) 연산
    Set에 지정된 원소가 포함되어 있는지 여부를 반환합니다.

  5. 교집합, 합집합, 차집합 연산
    두 Set의 교집합, 합집합, 차집합을 반환합니다.

Set의 활용

  1. 중복 제거
    Set은 중복된 값을 허용하지 않기 때문에, 중복된 값을 제거하기 위해 사용됩니다. 예를 들어, 리스트에서 중복된 값을 제거하기 위해서는 리스트를 Set으로 변환한 후 다시 리스트로 변환하는 방법을 사용할 수 있습니다.

  2. 검색 속도 향상
    Set은 검색, 삽입, 삭제 연산이 빠르기 때문에, 검색 속도가 중요한 애플리케이션에서 많이 활용됩니다. 예를 들어, 웹 페이지에서 중복된 URL을 제거하고 유일한 URL만 가져오기 위해서는 Set을 사용할 수 있습니다.

  3. 집합 연산
    Set은 집합 연산에도 많이 활용됩니다. 예를 들어, 두 개의 집합에서 공통된 원소를 찾는 연산, 두 개의 집합에서 차집합을 구하는 연산 등을 수행할 때 Set을 사용할 수 있습니다.

  4. 데이터 처리
    Set은 데이터 처리에도 많이 활용됩니다. 예를 들어, 특정한 조건을 만족하는 데이터를 추출할 때 Set을 사용할 수 있습니다. 또한, Set은 Map과 함께 사용하여 데이터를 처리할 때 유용합니다. Map의 키를 Set으로 추출한 후 반복문을 사용하여 Map의 값을 처리할 수 있습니다.

  5. 알고리즘
    Set은 알고리즘에서도 많이 활용됩니다. 예를 들어, 그래프에서 연결된 노드를 찾는 알고리즘인 DFS(Depth First Search)와 BFS(Breadth First Search)에서 Set을 사용하여 방문한 노드를 기록할 수 있습니다.

Set의 구현

Java에서 Set은 다양한 방법으로 구현됩니다.

  1. HashSet
    HashSet은 가장 일반적으로 사용되는 Set 구현 중 하나입니다. HashSet은 해시 함수를 사용하여 원소를 저장하므로, 삽입, 삭제, 검색 연산의 평균 시간 복잡도가 O(1)입니다. Java에서 HashSet은 java.util 패키지에 속해 있습니다.
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("orange");
set.add("apple"); // 중복된 값이므로 저장되지 않음

for (String s : set) {
  System.out.println(s);
}
  1. TreeSet
    TreeSet은 이진 검색 트리를 기반으로 한 Set 구현 중 하나입니다. TreeSet은 저장된 원소들을 정렬된 상태로 유지하므로, 정렬된 데이터를 저장하고 검색할 때 유용합니다. Java에서 TreeSet은 java.util 패키지에 속해 있습니다.
Set<Integer> set = new TreeSet<>();
set.add(3);
set.add(1);
set.add(2);

for (int i : set) {
  System.out.println(i);
}
  1. LinkedHashSet
    LinkedHashSet은 해시 테이블과 연결 리스트를 결합한 구조를 가지고 있습니다. 이 구조는 HashSet과 비슷하지만, 삽입 순서를 기억하므로, 삽입 순서를 유지하면서 중복된 원소를 제거할 때 사용됩니다. Java에서 LinkedHashSet은 java.util 패키지에 속해 있습니다.
Set<Integer> set = new LinkedHashSet<>();
set.add(3);
set.add(1);
set.add(2);
set.add(3); // 중복된 값이므로 저장되지 않음

for (int i : set) {
  System.out.println(i);
}
  1. EnumSet
    EnumSet은 열거형 상수를 원소로 가지는 Set 구현 중 하나입니다. EnumSet은 비트 벡터를 사용하여 구현되므로, 빠른 성능을 제공합니다. Java에서 EnumSet은 java.util 패키지에 속해 있습니다.
enum Color {
  RED, BLUE, GREEN
}

Set<Color> set = EnumSet.of(Color.RED, Color.GREEN);
set.add(Color.BLUE);
set.add(Color.BLUE); // 중복된 값이므로 저장되지 않음

for (Color c : set) {
  System.out.println(c);
}

HashSet과 HashMap

Java에서 HashSet은 내부적으로 HashMap을 통해 구현됩니다.
아래의 코드는 HashSet의 연산 메소드를 HashMap을 통해 구현한 것입니다.

import java.util.HashMap;
import java.util.Set;

public class HashSetUsingHashMap<T> {
    private HashMap<T, Boolean> map;

    public HashSetUsingHashMap() {
        map = new HashMap<>();
    }

    public boolean add(T key) {
        if (map.containsKey(key)) {
            return false;
        }
        map.put(key, true);
        return true;
    }

    public boolean remove(T key) {
        if (!map.containsKey(key)) {
            return false;
        }
        map.remove(key);
        return true;
    }

    public boolean contains(T key) {
        return map.containsKey(key);
    }

    public Set<T> keySet() {
        return map.keySet();
    }

    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.isEmpty();
    }

    public void clear() {
        map.clear();
    }
}

HashSet은 HashMap에서 value를 전부 null로 설정하고 key에 데이터를 저장하여 구현합니다.

HashMap<String, Object> map = new HashMap<>();
map.put("value1", null);
map.put("value2", null);
map.put("value3", null);

HashSet<String> set = new HashSet<>(map.keySet());

둘 다 Hash연산을 거치기 때문에 bucket index가 존재하고 내부적으로 비슷하게 동작합니다. HashSet은 중복되지 않는 value(= key-value중 key)만 저장하고, HashMap은 key-value 쌍을 저장합니다. 따라서, HashSet은 데이터가 많아질수록 검색 시간이 길어지는 문제가 있지만, HashMap은 key-value 쌍을 저장하여 검색과 수정에 더욱 유리합니다.

Python에서 Set은 해시 테이블을 사용해 구현됩니다. Set의 원소는 해시 테이블에서 key로 사용되고, 해당 key의 value는 None으로 설정됩니다. 따라서 Python의 set은 Java의 HashSet과 유사한 구조를 가지지만, 구현 방식이 다르기 때문에 Java의 HashSet과 완전히 동일하게 작동하지는 않습니다.

profile
개발공부하는사람

0개의 댓글