[Java] Java에서의 Set이란? - HashSet, LinkedHashSet, TreeSet

자바를 사용하면서 Set 자료구조를 한 번도 안 써본 개발자는 거의 없다고 생각합니다.

그런데 "HashSet, LinkedHashSet, TreeSet" 이 세가지가 뭐고 어떻게 다른지 공부하고 알아가볼려고 합니다.

 

 

1. Set 이란?

Set은 수학의 집합 개념을 그대로 프로그래밍에 도입한 것입니다. 가장 중요한 특징은 바로 "중복된 값이 하나도 없다"라는 점입니다.

 

 

1-1. 자바에서의 Set은?

Set 인터페이스 도식화

일단 자바에서 Set은 인터페이스이다. Set 인터페이스는 Collection 인터페이스를 상속하고 있습니다. 

Collection 인터페이스는 자바에서 다앙햔 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의합니다. List, Set, Queue 와 같은 다양한 하위 인터페이스와 함께 사용되며, 이를 통해 데이터를 관리할 수 있습니다.

 

자바에서의 Set 인터페이스는 java.util 패키지의 컬렉션 프레임워크에 속하는 인터페이스 중 하나입니다. 중복을 허용하지 않는 집합을 나타냅니다. 즉, 어떤 요소도 같은 Set 내에 두번 이상 나타날 수 없죠. 

Set 인터페이스는 HashSet, LinkedHashSet, TreeSet와 같은 여러 구현 클래스를 가지고 있습니다. 

 

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

메서드	설명
add(E e)	지정된 요소를 세트에 추가한다(이미 존재하는 경우 추가하 지 않음).
addAll(Collection<? extends E> c)	지정된 컬렉션의 모든 요소를 세트에 추가한다.
contains(Object o)	세트가 지정된 요소를 포함하고 있는지 여부를 반환한다.
containsAll(Collection<?> c)	세트가 지정된 컬렉션의 모든 요소를 포함하고 있는지 여부를 반환한다.
remove(Object o)	지정된 요소를 세트에서 제거한다.
removeAll(Collection<?> c)	지정된 컬렉션에 포함된 요소를 세트에서 모두 제거한다.
clear()	세트에서 모든 요소를 제거한다.
size()	세트에 있는 요소의 수를 반환한다.
isEmpty()	세트가 비어 있는지 여부를 반환한다.
iterator()	세트의 요소에 대한 반복자를 반환한다.
toArray()	세트의 모든 요소를 지정된 배열로 반환한다.

 

 

 

2. 자바에서의 Set 구현체

2-1. HashSet

HashSet은 내부적으로 HashMap을 사용합니다. 여기서 핵심이 되는 “해시(Hash)”는 아무 길이의 데이터를 고정된 크기의 “코드(숫자)”로 바꿔주는 함수/알고리즘 입니다.

예를 들어, “apple”이라는 문자열을 Hash 함수에 넣으면 '191209381' 같은 숫자가 나옵니다. 이 숫자를 “해시 값”이라고 부릅니다.

이 값이 바로 HashSet이 내부적으로 “배열(버킷)”에 값을 빠르게 저장할 위치를 찾는 열쇠가 되는거죠.

이 덕분에 HashSet은 값은 이미 있는지 빠르게 (O(1))로 판단할 수 있습니다.

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("apple"); // 중복, 무시됨

        System.out.println(hashSet); // [banana, apple] (순서는 입력과 다를 수 있음)

        System.out.println(hashSet.contains("apple"));  // true
        System.out.println(hashSet.contains("grape"));  // false
    }
}

 

2-2. LinkedHashSet

HashSet의 단점은 바로 데이터의 입력 순서가 전혀 보장되지 않는다는 점입니다. 만약 "중복 제거는 필요하지만, 데이터가 입력된 순서를 반드시 보존해야 하는" 상황이 있다면 LinkedHashSet을 사용하면 됩니다.

그럼 어떻게 LinkedHashSet은 입력 순서를 기억할까요? 바로 해시테이블과 이중 연결 리스트가 합쳐진 구조이기 때문입니다.

LinkedHashSet 구조 (출처: 김영한 인프런 강의)

 

사진에서 보는것과 같이 LinkedHashSet에 값을 추가할 때 노드(Node)로 추가합니다.

그 노드(Node)는 다음 값과 이전의 값의 메모리 주소를 참조하고 있죠. 즉, 입력 순서대로 연결되어 있으니 데이터 입력 순서를 알게되는 것 입니다.

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

public class LinkedHashSetExample {
    public static void main(String[] args) {
        Set<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("dog");
        linkedSet.add("cat");
        linkedSet.add("bird");
        linkedSet.add("dog"); // 중복, 무시됨

        System.out.println(linkedSet); // [dog, cat, bird] (입력 순서대로 출력)
    }
}

 

2-3. TreeSet

TreeSet은 이름처럼 트리(Tree) 구조를 사용합니다. 구체적으로 Red-Black Tree라는 균형 이진 탐색 트리로, 데이터가 삽입될 때 마다 자동으로 정렬된 상태를 유지합니다.

 

정렬 기준은 기본적으로 오름차순으로 구현 되어 있으며, 원한다면 Comparator로 커스텀 정렬도 가능합니다.

또한 TreeSet은 자동 정렬 뿐만 아니라 다양한 탐색. 범위 검색 메서드를 제공합니다.

균형 이진 탐색 트리는 아래에서 소개하겠다.

균형 이진 탑색 트리란?

일반적은 이진 탐색 트리는 각 노드 마다 왼쪽 자식은 "작은 값", 오른쪽 자식은 "큰 값"을 저장하는 트리다.

하지만, 데이터가 한쪽으로 쏠려서(예: 오름차순으로만 삽입) 트리가 “한쪽으로 길게” 자라게 되면,
사실상 연결리스트와 다를 게 없어져서 성능이 O(N)까지 떨어질 수 있다.

 

균형 이진 탐색 트리(Balanced BST)는
삽입/삭제 후에도 트리의 “높이”가 최소가 되도록
스스로 균형을 맞추는 기능이 들어간 이진 탐색 트리다.
그래서 어떤 데이터가 오더라도 항상 “O(logN)”의 시간 복잡도를 보장한다.

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

public class TreeSetExample {
    public static void main(String[] args) {
        Set<Integer> treeSet = new TreeSet<>();
        treeSet.add(7);
        treeSet.add(1);
        treeSet.add(3);
        treeSet.add(7); // 중복, 무시됨

        System.out.println(treeSet); // [1, 3, 7] (항상 오름차순)
        
        System.out.println(treeSet.first());  // 1 (가장 작은 값)
	System.out.println(treeSet.last());   // 7 (가장 큰 값)
	System.out.println(treeSet.higher(3)); // 7 (3보다 큰 값 중 가장 작은 값)
	System.out.println(treeSet.subSet(2, 7)); // [3] (2 이상 7 미만)
    }
}

 

 

3. 정리

"중복 없는 값의 집합" 만 필요하다면  HashSet이 가장 빠르고, 메모리도 적게 듭니다.

하지만 결과의 순서가 항상 다를 수 있다는 점을 유의 해야 합니다.

입력 순서까지 보존해야 한다면 LinkedHashSet을 선택하면 됩니다. 

마지막으로 데이터를 항상 자동으로 정렬까지 해야한다면 TreeSet이 유리합니다.

 

즉, HashSet, LinkedHashSet, TreeSet 이 세가지 Set 자료구조는 단순히 중복을 허용하지 않는다는 점에서 공통점은 같지만, 내부 동작 방식, 성능, 사용 목적에서는 분명한 차이가 있습니다.

 

내가 해결하려는 문제의 본질이 "순서"인가, "속도"인가, "정렬"인가 질문해보고, 가장 적합한 Set 컬렉션을 고르면 되겠습니다.

 

이상입니다.