HashSet이란?(+ TreeSet, LinkedHashSet)

코딩테스트를 풀면서 배열 문제를 HashSet으로 풀 때 더 간단하고 효율적인 것을 보고 HashSet에 대해서 정리를 하고 나도 배열 문제에서 HashSet을 사용해봐야겠다고 생각했다.

 

HashSet 개념

---

HashSet은 Java의 Set 인터페이스를 구현한 컬렉션 클래스로, 중복을 자동으로 제거하며 빠르게 원소를 저장하고 검색할 수 있는 자료구조이다.

 

HashSet의 주요 특징

---

1. 중복이 허용되지 않음

• 같은 값이 여러 번 추가되면 자동으로 하나만 저장됨.

2. 순서가 보장되지 않음

• List처럼 저장 순서를 유지하지 않음.

3. 빠른 검색 속도 (O(1))

• HashSet은 내부적으로 해시 테이블(Hash Table)을 사용하여 빠른 검색과 삽입이 가능.

4. 메서드 제공

메서드	설명
add(value)	값 추가 (중복이면 무시)
remove(value)	값 삭제
contains(value)	값이 존재하는지 확인 ( true / false )
size()	저장된 원소 개수 반환
clear()	모든 원소 삭제
inEmpty()	집합이 비어 있는지 확인

 

예제 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 1️⃣ HashSet 생성
        Set<Integer> set = new HashSet<>();

        // 2️⃣ 값 추가 (add)
        set.add(10);
        set.add(20);
        set.add(30);
        set.add(10); // 중복이므로 추가되지 않음

        // 3️⃣ 포함 여부 확인 (contains)
        System.out.println("10이 포함되어 있는가? " + set.contains(10)); // true
        System.out.println("40이 포함되어 있는가? " + set.contains(40)); // false

        // 4️⃣ 크기 확인 (size)
        System.out.println("현재 크기: " + set.size()); // 3 (10, 20, 30만 저장됨)

        // 5️⃣ 값 삭제 (remove)
        set.remove(10);
        System.out.println("10 삭제 후 크기: " + set.size()); // 2

        // 6️⃣ 집합이 비어 있는지 확인 (isEmpty)
        System.out.println("Set이 비어있는가? " + set.isEmpty()); // false

        // 7️⃣ 전체 원소 출력 (반복문 사용)
        System.out.print("Set의 모든 원소: ");
        for (int num : set) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 8️⃣ 모든 원소 삭제 (clear)
        set.clear();
        System.out.println("clear() 후 크기: " + set.size()); // 0
        System.out.println("Set이 비어있는가? " + set.isEmpty()); // true
    }
}

 

실습

---

문제

https://www.acmicpc.net/problem/3052

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 중복을 제거하면서 나머지를 저장하는 HashSet 사용
        Set<Integer> remainderSet = new HashSet<>();

        for (int i = 0; i < 10; i++) {
            int n = Integer.parseInt(br.readLine());
            remainderSet.add(n % 42); // 42로 나눈 나머지를 Set에 추가
        }

        // set.size()를 이용해 중복을 제외한 나머지 개수 출력
        System.out.println(remainderSet.size());
    }
}

 

 

입력

1
2
3
4
5
6
7
8
9
10

 

과정

입력된 숫자	42로 나눈 나머지	HashSet 내용
1	1	{1}
2	2	{1, 2}
3	3	{1, 2, 3}
4	4	{1, 2, 3, 4}
5	5	{1, 2, 3, 4, 5}
6	6	{1, 2, 3, 4, 5, 6}
7	7	{1, 2, 3, 4, 5, 6, 7}
8	8	{1, 2, 3, 4, 5, 6, 7, 8}
9	9	{1, 2, 3, 4, 5, 6, 7, 8, 9}
10	10	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

• 중복이 자동으로 제거되므로 HashSet의 크기는 10

 

출력

10

 

 

TreeSet, LinkedHashSet

---

1. TreeSet (정렬된 집합)

• HashSet은 순서를 보장하지 않지만, TreeSet은 자동 정렬됨.
• 나머지를 오름차순으로 출력해야 할 경우 TreeSet이 적합.

예제 코드

Set<Integer> remainderSet = new TreeSet<>();

• 중복 제거 + 자동 정렬

 

2. LinkedHashSet (입력 순서 유지)

• LinkedHashSet은 HashSet처럼 중복을 제거하지만, 입력 순서를 유지함.
• 즉, 입력된 순서대로 나머지를 출력하고 싶다면 LinkedHashSet이 적합.

예제 코드

Set<Integer> remainderSet = new LinkedHashSet<>();

 

 

정리

---

• HashSet은 중복을 자동으로 제거하며 빠르게 저장 & 검색 가능 ( O(1) )
• 순서 유지가 필요하면 LinkedHashSet, 자동 정렬이 필요하면 TreeSet을 사용하면 됨