HashSet 과 Big O

Jihye Gim·2026년 3월 6일
BackendHashSetJavaO(log n)ONSpring

Codeit SB11

목록 보기
6/22

<개인 학습 기록>

🇶1. HashSet의 내부 동작 방식과 중복 제거 메커니즘을 설명하고, HashSet이 효율적인 중복 체크를 할 수 있는 이유를 설명해주세요.
🇶2. O(n)과 O(log n)의 성능 차이를 실생활 예시를 들어 설명하고, 데이터의 크기가 1백만 개일 때 각각 대략 몇 번의 연산이 필요한지 비교해주세요.

HashSet

Set은 중복을 허용하지 않는 데이터 컬렉션을 의미한다.
Java에서 Set인터페이스의 대표 구현체가 바로 HashSet이다.

HashSet의 특징

  • 중복된 값 저장 불가
  • 순서 보장 없음(데이터가 입력된 순서대로 정렬되지 않음)
  • 내부적으로 HashMap을 사용해 구현됨

HashSet의 내부 구현 원리

  • HashSet은 실질적으로 HashMap을 이용해 모든 값을 '키'로 저장한다.
  • HashSet에 값을 추가 하면, 내부에서는 HashMap.put(E, PRESENT) 방식으로 처리된다.
  • 여기서 E는 원소, PRESENT는 고정된 더미(dummy)값

예시(코드)

HashSet<String> set = new HashSet<>();
set.add("apple");
set.add("banana");

내부적으로는 아래와 같이 동작한다.

HashMap<String, Object> map = new HashMap<>();
map.put("apple", DUMMY);
map.put("banana", DUMMY);

여기에서 DUMMY는 HashSet에서 정적으로 선언된 값이다.

중복 체크 원리

  • 새 값을 넣으려고 할 때,
  • 해당 값의 hashCode()를 구해서 어디 버킷(bucket)에 넣을지 결정
  • 이미 동일한 값이 해시 버킷에 존재하면(=중복), put 연산이 무시됨.
  • 따라서 HashSet에는 중복 값이 들어가지 않음.

HashSet 주요 연산 시간복잡도

  • add, remove, contains 등 대부분의 함수가 평균적으로 O(1)시간에 동작
  • 내부적으로 충돌이 많이 발생하거나, 해시 함수분포가 안 좋으면 최악의 경우 O(n)까지도 기능은 함
    (하지만 일반적으로는 O(1)성능)

HashSet vs TreeSet

  • HashSet : 해시 기반(속도가 빠르지만 정렬 안됨)
  • TreeSet : 내부적으로 이진 탐색 트리(정렬 가능하지만 속도는 O(log n))

요약

  • HashSet은 내부적으로는 HashMap을 활용해서 구현되며,
  • 값은 key로, value는 상수(dummy)로 저장,
  • 중복을 자동으로 걸러내며 빠른 데이터 검색, 추가, 삭제가 가능하다.
  • HashSet은 중복 요소를 허용하지 않고, 만약 삽입하면 이전 요소가 덮어쓰여진다.
  • HashSet은 클래스 동기화가 되지 않는다. 동기화된 HashSet을 원한다면, Collection.synchronizedSet()메서드를 사용할 수 있다.
  • HashSet은 최대 하나의 Null 요소를 가질 수 있다.

첨부 예시 코드 <How HashSet works internally in Java?>

HashSet 예시

// Java program to demonstrate HashSet
import java.util.*;

class GFG {
 	public static void main(String[] args) {
    	Set<String> hash_Set = new HashSet<String>();
        
        hash_Set.add("GEEKS");
        hash_Set.add("GeeksForGeeks");
        hash_Set.add("GEEKS");
        hash_Set.add("Example");
        
        System.out.println(hash_Set);
 	 }
}
  • HashSet<String> 타입의 hash_Set 객체를 만든다.
  • "Geeks", "GeeksForGeeks", "Geeks"(중복), "Example" 네개의 값을 추가한다.
  • 마지막에 System.out.println(hash_Set) 으로 전체 셋의 값을 출력한다.
    실행 결과 :
  • 출력순서는 보장되지 않고 경우에 따라 다를 수 있다.
    [Example, Geeks, GeeksForGeeks]
  • "Geeks"는 두번 add 했지만 한번만 포함되고, 데이터의 입력 순서는 보장되지 않는다.

HashSet의 내부 구조(테이블 구조)

(1) HashSet이 HashMap을 내부적으로 사용한다.

  • 실제로 HashSet은 아래와 같이 동작:
    - HashSet에 값을 추가 -> 내부의 HashMap에
    • key: 내가 add한 값
    • value: 고정 DUMMY객체(HashSet E)
      key는 중복 안되고, value는 모두 같다(E)
  • 내부 구조는 아래와 같이 모델링 할 수 있다.
keyvalue
"Geeks""E"
"GeeksForGeeks""E"
"Geeks""E"

(2) 코드에서의 실제 동작(key/value 저장 모습)

  • 예를 들어, 위 코드에서
    hash_set.add("Geeks");
hash_set.add("GeeksforGeeks");
hash_set.add("Geeks");
hash_set.add("Example");
  • 내부 HashMap에는 아래처럼 저장되고,
    두번째 "Geeks" 추가 시, HashMap은 이미 동일한 key가 있으니 value(DUMMY)는 덮어쓰기만 하고 새로운 엔트리는 추가하지 않는다. 이로써 중복 저장이 자동으로 방지된다.

요약해보자면,

  1. add("Geeks") -> 내부 HashMap에 key "Geeks" 추가, value는 E(dummy)
  2. add("GeeksForGeeks) -> key "GeeksForGeeks" 추가, value는 E
  3. add("Geeks") again -> key "Geeks"가 이미 존재 하므로 변화 없음
  4. add("Example") -> key "Example"추가, value는 E
    출력시 [Example, Geeks, GeeksForGeeks] 또는 [Geeks, GeeksForGeeks, Example] 등 순서는 섞일 수 있다.

    hierarchy diagram of HashSet class (HashSet Class 계층 다이어그램)


    https://javaconceptoftheday.com/java-collection-framework-hashset-class/
  • 이 그림은 Java Collection Framework에서 HashSet이 어디에 위치하는지 보여주는 UML 구조도이다.
    핵심은 상속(extends)과 구현(implements)관계를 이해하는 것이다.

  1. 반복 가능한 것 - java.lang.Iterable <>
    "for-each 반복문으로 돌릴 수 있는 객체"

    for (String s : list) {
	System.out.println(s);
} // 이게 가능한 이유가 Iterable 때문이다.

  2. java.util.Collection <>
    관계를 보면 

    Iterable
 ↑ extends
Collection

    Java에서 "데이터 모음"의 가장 기본 인터페이스
    대표 메서드로는 add(), remove(), size(), iterator()

  3. java.util.Set (Converting a Collection to a Set)
    관계를 보면

    Collection
 ↑ extends
Set

    Set의 특징으로는 중복 허용 안함, 순서 보장 안함.

    Set<Inteager> set = new HashSet<>();

set.add(1);
set.add(1);

System.out.println(set); //[1]

  4. Abstract class 등장 (*)
    Java에서는 인터페이스를 바로 구현하기 어렵기 때문에 중간에 Abstract 클래스가 들어간다.
    대표적으로 java.Abstractcollection, java.util.AbstractSet
    구조를 보면

    Collection (interface)
      ↑
AbstractCollection (abstract class)
      ↑
AbstractSet (abstract class)

    이 클래스들이 하는 일은 "공통 로직을 미리 구현해 둔다"
    예를 들어서 size(), isEmpty(), toString() 그래서 실제 구현 클래스는 핵심 로직만 구현하면 된다.

  5. java.util.HashSet (최종 구현 클래스 : HashSet)
    관계를 보면

    HashSet
 extends AbstractSet
 implements Set

    실제 구조를 코드로 보면

    public class HashSet<E>
  extends AbstractSet<E>
  implements Set<E>, Cloneable, Serializable

  6. 추가 인터페이스
    HashSet은 두개 더 구현한다.

  • Cloneable (java.lang.Cloneable) : 객체 복제 가능
    HashSet<String> copy = (HashSet<String> original.clone();
  • Serializable (java.io.Serializable) : 객체를 파일이나 네트워크로 저장 가능
    object -> byte stream
    정리하자면
    HashSet을 만들 때 Java 설계 철학으로 보자면,
    Interface -> Abstract -> Concreate class
    규칙정의 -> 기본 구현 -> 실제 구현
    이렇게 쓰는 이유는 인터페이스 기반 설계를 위해서이다.
    HashSet의 내부는
    HashSet
 ↓
HashMap
    즉, HashSet = HashMap wrapper 로 볼수 있다. 그래서 시간복잡도를 아래와 같이 확인할수 있다.
    add() O(1)
remove() O(1)
contains() O(1)


https://www.geeksforgeeks.org/dsa/analysis-algorithms-big-o-analysis/

시간 복잡도(Time Complexity)는 입력 데이터 크기 n이 커질 때 알고리즘 실행 시간이 어떻게 증가 하는지를 나타내는 성장률(growth rate) 분석이다. 표기법은 Big-O를 사용한다. 대표적으로 O(1), O(log n), O(n)이 자주 등장한다.
1. O(1) - Constant Time (상수 시간)
데이터 개수와 관계없이 항상 같은 시간이 걸리는 연산
int value = array[5]; 이 연산은 항상 동일하다./ 시간이 거의 변하지 않는다.

데이터 10개 -> 1 step
데이터 1,000개 -> 1 step
데이터 1,000,000개 -> 1 step

대표적으로 배열 인덱스 접근, 해시 조회, 스택 push/pop 이 있고, 대표적인 자료 구조로는 HashMap, HashSet이 있다.
예를 들어서

HashSet<String> set = new HashSet<>();
set.contains("apple");

평균 시간 복잡도 = O(1) / 이유는 hash table

  1. O(n) - Linear Time(선형 시간)
    데이터가 늘어나는 만큼 시간도 비례해서 증가
    예시 코드
    for(int 1=0; i<n; i++) {
   System.out.println(array[i]);
    데이터 증가
    n=10 -> 10번 실행
n=100 -> 100번 실행
n=1000 -> 1000번 실행
    대표적으로 배열 전체 탐색, 리스트 검색, 파일 전체 읽기에서 사용된다.
    List<String> list = new ArrayList<>();
 	for(String s: list) {
 		if(s.equals("apple"))
 			return true;
 }
    자료구조로는 Java ArrayList
    contains() O(n) 처음부터 끝까지 찾아야 한다.
  2. O(log n) - Logarithmic Time(로그 시간)
    문제를 계속 절반으로 줄이면서 탐색
    대표적인 알고리즘은 Binar Search 가 있다.
    데이터 16개
1 step -> 8개
2 step -> 4개
3 step -> 2개
4 step -> 1개
    그래서 log₂(16) = 4
    예시 코드
    int binarySearch(int[] arr, int targete) {
	int left = 0;
	int right = arr.length-1;

	while(left <= right) {
     int mid = (left+right)/2;
     if(arr[mid] == target)
         return mid;
     if(arr[mid] == target)
         return mid;
     if(arr[mid] < target)
         left = mid+1;
		else
			right = mid-1;
 	}
	return -1;
}
    초기에는 조금 증가하지만 n이 커질수록 증가 속도가 매우 느리다.
    대표적인 자료 구조로는 TreeMap,TreeSet이 있다. 연산은 insert,delete,search
    시간복잡도는 O(log n) 이유는 Balanced Binary Tree

성능 비교

예를 들어 데이터가 1,000,000개 있을 때

복잡도연산횟수차이
O(1)1즉시
O(log n)약 20매우 빠름
O(n)1,000,000느림

그래서 알고르즘 설계에서 `O(n) -> O(log n) -> O(1) 방향으로 개선하는 것이 중요하다.

Java 자료 구조와 시간 복잡도

자료 구조검색
ArrayListO(n)
LinkedListO(n)
HashSetO(1)
HashMapO(1)
TreeSetO(log n)
TreeMapO(log n)

  • List.contains() 이 알고리즘의 시간 복잡도는? O(n)

  • HashSet.contains() 는? O(1)
    그래서 List -> Set 으로 성능이 수천 배 좋아질 수 도 있다.
    그렇다면, HashSet이 O(1)인가? 

    Hash function 
-> bucket
-> direct access

    하지만 hash collision 발생하면 최악 -> O(n)

    요약하자면,
    O(1) -> 데이터 크기와 상관없이 일정
    O(log n) -> 데이터를 절반씩 줄이며 탐색
    O(n) -> 데이터 크기만큼 증가, n이면 최대 𝑛번 확인(데이터를 하나씩 다 봐야 한다.)

    예시 1. 도서관에서 책 찾기
    상황 : 도서관에 1,000,000권 책이 있다.
    O(n) 방식(선형 탐색) - 책이 정렬되어 있지 않다.
    찾는 방법.. 첫번째 책 확인, 두번째 책 확인, 세번째 책 확인... 찾을때 까지 계속 확인
    최악의 경우 1,000,000번 확인, 연산횟수 O(n) = 1,000,000

    O(log n) 방식(이진 탐색) - 책이 제목 순서로 정렬되어 있다.
    찾는 방법.. 1.가운데 책 확인(500,000번째) 2.찾는 책이 앞인지 뒤인지 판단 3.남은 절반에서 다시 가운데 확인

    1번째 -> 500,000
2번째 -> 250,000
3번째 -> 125,000
4번째 -> 62,500
...
20번째 -> 찾음 
연산횟수 : O(log n) = 20

    예시 2: 건물에서 사람 찾기
    상황: 회사 건물에 1,000,000명 직원이 있다.
    O(n)방식 : 사람이 무작위로 흩어져 있다.
    찾는 방법 : 1. 한명 씩 얼굴 확인.. 2. 계속 확인...
    최악의 경우 1,000,000명 확인, 연산횟수 O(n) = 1,000,000

    O(log n)방식 :사람이 사번 순서로 정렬된 방에 배치
    찾는 방법: 1.건물 가운데 층 확인 2.사번이 더 크면 위로 3.더 작으면 아래로

    1층 ~ 1,000,000층
1 -> 500,000층
2 -> 250,000층
3 -> 125,000층
...
20 -> 찾음

    연산횟수: O(log n) = 20

    <참조: https://www.geeksforgeeks.org/java/internal-working-of-sethashset-in-java/>

profile
Jihye Gim
Rookie
이전 포스트

2주차 위클리 페이퍼

다음 포스트

Enum/예외처리

0개의 댓글