java

Java 자바 Set – HashSet, TreeSet, LinkedHashSet 정리

by

소개

자바에서 Set은 중복을 허용하지 않는 데이터 집합을 의미합니다. List와 달리 동일한 요소를 여러 번 포함할 수 없으며, 순서와 관계없이 각 요소가 유일함을 보장합니다. 이러한 특징 덕분에 Set은 중복 데이터가 없어야 할 때 매우 유용합니다. 자바 컬렉션 프레임워크에는 대표적으로 HashSet, TreeSet, LinkedHashSet이 있으며, 각각 고유한 장단점을 갖고 있습니다. 이번 글에서는 이 세 가지 Set 구현체의 차이점, 성능, 내부 동작 원리 등을 자세히 다뤄보겠습니다.

Java 자바 Set - HashSet, TreeSet, LinkedHashSet 정리

Set 인터페이스와 특징

Set 인터페이스는 자바 컬렉션 프레임워크의 중요한 구성 요소로, 중복을 허용하지 않는 집합을 표현합니다. 이는 수학적인 집합과 유사한 개념으로, 각 요소는 고유해야 합니다. Set 인터페이스를 구현하는 클래스들은 다음과 같은 공통적인 특징을 갖습니다.

  • 중복 불가: 동일한 요소는 한 번만 저장되며, 이는 데이터의 무결성을 유지하고 메모리 사용을 최적화하는 데 도움이 됩니다.
  • null 값: Set은 하나의 null 값을 저장할 수 있습니다. 그러나 특정 구현체는 이에 대한 처리 방식이 다를 수 있습니다.
  • 효율적인 검색: 각 Set 구현체는 고유한 방식으로 요소를 저장하고 검색합니다. 빠른 검색, 정렬된 저장, 순서 유지 등 다양한 요구 사항에 따라 선택할 수 있습니다.

주요 메서드

모든 Set 구현체들은 공통적인 주요 메서드들을 제공합니다.

  • add(E e): 주어진 요소를 Set에 추가합니다. 만약 요소가 이미 존재하면 추가되지 않습니다.
  • remove(Object o): 주어진 요소를 Set에서 제거합니다. 요소가 존재하지 않으면 아무 작업도 하지 않습니다.
  • contains(Object o): Set에 주어진 요소가 있는지 여부를 반환합니다. (true 혹은 false)
  • size(): Set에 있는 요소의 개수를 반환합니다.
  • isEmpty(): Set이 비어 있는지 여부를 반환합니다.
  • clear(): Set의 모든 요소를 제거합니다.
  • iterator(): Set에 포함된 요소들을 순회하기 위한 Iterator를 반환합니다.

HashSet – 해시 기반의 Set

HashSet은 Set 인터페이스의 가장 일반적인 구현체로, 해시 테이블을 사용하여 요소를 저장합니다. 주요 특징은 다음과 같습니다.

  • 중복 허용 안 함: 내부적으로 요소들의 고유성을 유지하기 위해 hashCode()와 equals() 메서드를 사용합니다. 두 객체의 해시 값이 같고 equals() 메서드가 true를 반환할 때만 중복으로 간주되어 추가되지 않습니다.
  • 정렬되지 않음: HashSet은 요소의 순서를 보장하지 않습니다. 즉, 저장된 순서와 관계없이 요소들이 출력될 수 있습니다.
  • 성능: 요소를 추가하거나 검색하는 작업은 평균적으로 O(1)의 시간 복잡도를 가집니다. 해시 충돌이 많이 발생하거나 부적절한 hashCode() 구현이 있다면 성능 저하가 발생할 수 있습니다.
  • 해시 충돌: 해시 충돌이 발생하면 HashSet은 동일한 해시 값의 요소들을 연결 리스트 또는 트리 구조로 저장하여 해결합니다. 자바 8 이후부터는 충돌이 일정 이상 발생하면 연결 리스트 대신 트리 구조로 변환되어 검색 성능을 향상시킵니다.
  • 용도: 중복을 허용하지 않으면서도 빠른 검색 속도가 필요한 경우 적합합니다.
Java
import java.util.HashSet;
import java.util.Set;

public class HashSetExample {
    public static void main(String[] args) {
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Orange");
        hashSet.add("Apple"); // 중복이므로 추가되지 않음

        for (String fruit : hashSet) {
            System.out.println(fruit);
        }
    }
}
Java

위 코드에서 “Apple”은 두 번 추가되었지만 중복이므로 한 번만 저장됩니다.

TreeSet – 정렬된 Set

TreeSet은 이진 검색 트리인 TreeMap을 기반으로 구현된 Set으로, 요소들이 자동으로 정렬됩니다. 주요 특징은 다음과 같습니다.

  • 정렬된 요소: 요소들은 자연스러운 순서(기본적으로 Comparable 인터페이스를 구현한 경우) 또는 사용자 지정 Comparator에 의해 정렬됩니다.
  • 시간 복잡도: 삽입, 삭제, 탐색 작업 모두 O(log n)의 시간 복잡도를 가집니다. 이는 이진 트리의 높이에 의존하기 때문입니다.
  • 범위 검색: TreeSet은 subSet(), headSet(), tailSet()과 같은 메서드를 통해 특정 범위의 요소들을 손쉽게 검색할 수 있습니다.
  • null 값 처리: TreeSet은 정렬이 필요한 특성상 null 값을 허용하지 않습니다. null이 들어오면 NullPointerException이 발생합니다.
  • 용도: Set의 요소들이 정렬된 상태로 유지되어야 하거나 특정 범위의 데이터를 효율적으로 검색할 필요가 있을 때 적합합니다.
Java
import java.util.Set;
import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        Set<Integer> treeSet = new TreeSet<>();
        treeSet.add(20);
        treeSet.add(5);
        treeSet.add(15);
        treeSet.add(10);

        for (Integer number : treeSet) {
            System.out.println(number);
        }
    }
}
Java

위 예제에서 TreeSet은 요소들을 자동으로 오름차순 정렬하여 출력합니다: 5, 10, 15, 20.

LinkedHashSet – 순서 유지 Set

LinkedHashSet은 요소들이 추가된 순서를 유지하는 Set 구현체로, 내부적으로 해시 테이블과 이중 연결 리스트를 사용합니다. 주요 특징은 다음과 같습니다.

  • 삽입 순서 유지: 요소들은 삽입된 순서대로 저장됩니다. 따라서 HashSet과 달리 순서가 보장됩니다.
  • 시간 복잡도: 평균적으로 삽입과 검색의 시간 복잡도는 O(1)입니다. 이는 해시 테이블에 기반하기 때문입니다.
  • 메모리 사용: 순서 유지를 위해 링크 정보를 저장해야 하므로 HashSet보다 더 많은 메모리를 사용합니다.
  • null 값 허용: LinkedHashSet은 null 값을 허용하며, 중복되지 않는 한 저장될 수 있습니다.
  • 용도: 중복을 허용하지 않으면서 요소의 순서가 중요한 경우 적합합니다.
Java
import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("Banana");
        linkedHashSet.add("Apple");
        linkedHashSet.add("Grape");
        linkedHashSet.add("Banana"); // 중복이므로 추가되지 않음

        for (String fruit : linkedHashSet) {
            System.out.println(fruit);
        }
    }
}
Java

위 예제에서 요소들은 삽입된 순서대로 출력됩니다: “Banana”, “Apple”, “Grape”.

HashSet, TreeSet, LinkedHashSet 비교

특징HashSetTreeSetLinkedHashSet
순서 유지유지하지 않음정렬된 순서 유지삽입 순서 유지
시간 복잡도 (삽입/검색)O(1)O(log n)O(1)
정렬 여부없음자동 정렬없음
null 값 허용 여부가능 (1개)불가가능 (1개)
메모리 사용적음중간많음
  • HashSet은 빠른 검색이 필요하지만 요소의 순서가 중요하지 않을 때 적합합니다.
  • TreeSet은 요소들이 정렬된 상태로 유지되어야 할 때 사용되며, 범위 검색 기능이 필요할 때 유리합니다.
  • LinkedHashSet은 요소들이 삽입된 순서를 유지하면서 중복을 제거해야 할 때 가장 적합합니다.

내부 구현의 차이점

  • HashSet: 내부적으로 HashMap을 사용합니다. 각 요소는 HashMap의 키로 저장되며, 값은 항상 동일한 더미 객체입니다. 이 덕분에 중복된 요소는 저장되지 않고 고유한 해시 값을 갖도록 관리됩니다.
  • TreeSet: 내부적으로 TreeMap을 사용합니다. 이진 검색 트리 구조를 사용하여 요소를 정렬하며, 요소들의 정렬 순서를 유지합니다. 균형 잡힌 트리 구조로, 시간 복잡도는 O(log n)을 유지합니다.
  • LinkedHashSet: 내부적으로 HashMap과 연결 리스트를 사용하여 요소의 삽입 순서를 유지합니다. 이는 해시 기반의 빠른 검색 성능과 연결 리스트를 통한 순서 유지를 결합한 구조입니다.

Set 사용 시 고려사항

  • 중복 데이터 관리: Set은 중복 요소를 제거하는 데 유용합니다. 예를 들어, 데이터베이스에서 중복된 레코드를 제거할 때 HashSet을 사용할 수 있습니다.
  • 정렬된 데이터 필요: 데이터를 정렬된 상태로 유지해야 할 때 TreeSet을 사용하는 것이 좋습니다. 단, 추가적인 시간 복잡도를 고려해야 합니다.
  • 순서 유지 필요: 순서가 중요한 데이터를 관리할 때는 LinkedHashSet을 사용하여 삽입 순서를 유지할 수 있습니다.
  • 성능 고려: 요소의 추가와 검색이 자주 발생하는 경우 HashSet이 성능 면에서 유리하지만, 특정 상황에서는 메모리 사용량과 해시 충돌을 고려해야 합니다.

결론

Set 인터페이스의 구현체들인 HashSet, TreeSet, LinkedHashSet은 각각의 사용 목적과 상황에 따라 선택됩니다. 요소의 순서가 중요하지 않고 빠른 검색이 필요하다면 HashSet이 적합하고, 자동 정렬과 범위 검색이 필요한 경우 TreeSet, 삽입된 순서를 유지하면서 중복 제거가 필요하다면 LinkedHashSet을 사용하면 됩니다. 각 Set의 특징과 성능을 잘 이해하고 상황에 맞게 활용하는 것이 중요합니다.

Leave a Comment