Set

Set 이란?

중복을 허용하지 않고 순서를 보장하지 않는 자료구조입니다.

Set 상속 구조

HashSet

• 해시 자료 구조를 사용해서 요소를 저장
• 순서 보장 X
• 중복 허용 X
• 평균 O(1) 시간 복잡도를 가짐

데이터의 유일성만 중요하고, 순서가 중요하지 않은 경우 사용합니다.

LinkedHashSet

• HashSet에 연결 리스트를 추가한 자료구조
• 삽입 순서 보장 O
• 중복 허용 X
• 평균 O(1)의 시간 복잡도를 가짐
• 연결 링크를 유지하기 때문에 HashSet 보다는 조금 더 무거움

데이터의 유일성과 삽입 순서를 유지해야 할 때 사용합니다.

위 그림은 단일 연결 리스트이지만 자바에서 제공하는 LinkedHashSet은 이중 연결 리스트로 되어 있습니다.

TreeSet

• 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용
• 정렬 순서 보장 O
  • 객체의 경우 Comparator로 정렬 순서 변경 가능
• 중복 허용 X
• O(log n)의 시간 복잡도를 가짐

데이터의 유일성과 정렬 순서를 보장해야 할 때 사용합니다.

트리 구조

• 부모 노드와 자식 노드로 구성

이진 트리

• 자식이 2개까지 올 수 있는 트리
• 노드의 왼쪽 자손은 더 작은 값을 가지고, 오른쪽 자손은 더 큰 값을 가짐

이진 탐색 트리 순회

중위 순회 방법을 사용

1. 왼쪽 서브 트리 처리
2. 현재 노드 처리
3. 오른쪽 서브 트리 처리

위 방식을 통해 오름차순으로 순회가 가능합니다. 당연히 내림차순도 가능합니다.

HashSet, LinkedHashSet, TreeSet 한눈에 비교

public class JavaSetMain {

  public static void main(String[] args) {
    run(new HashSet<>()); // 중복 X, 순서 보장 X
    run(new LinkedHashSet<>()); // 중복 X, 입력 순 보장 O
    run(new TreeSet<>()); // 중복 X, 데이터 크기 순 정렬 O
  }

  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");

    Iterator<String> iterator = set.iterator();
    while (iterator.hasNext()) {
      System.out.print(iterator.next() + " ");
    }
    System.out.println();
  }
}

Set 최적화

• 자바의 HashSet은 데이터의 양이 배열 크기의 75%를 넘어가면 배열의 크기를 2배로 늘리고 모든 요소에 해시 인덱스를 다시 적용

참고

• https://www.inflearn.com/course/김영한의-실전-자바-중급-2