2026-01-23

1. HashSet은 어떻게 중복을 없앨까?

HashSet은 “이미 들어온 값인지”를 아주 빠르게 확인하는 자료구조이다.
핵심 아이디어는 전부 하나씩 비교하지 않는 것이다.

쉽게 비유하면

  • HashSet은 사물함이 잔뜩 있는 학교와 비슷하다.
  • 물건을 넣을 때마다:
    1. 물건에 적힌 번호를 보고
    2. 그 번호에 해당하는 사물함으로 바로 간다.
  • 같은 물건이 이미 그 사물함에 있으면
    → “이미 있다”고 판단하고 더 넣지 않는다.

이때 중요한 점은:

  • 사물함 번호를 계산하는 과정이 hashCode
  • 진짜 같은 물건인지 확인하는 과정이 equals

즉,

  • hashCode로 “대충 위치”를 정하고
  • equals로 “진짜 같은지”를 확인한다.

그래서 HashSet은:

  • 처음부터 끝까지 전부 확인하지 않아도 되고
  • 거의 한 번에 중복 여부를 알 수 있다.

이 때문에 HashSet은 중복 체크가 매우 빠르다.

2. O(n)과 O(log n)은 뭐가 다를까?

이건 “얼마나 많이 확인해야 하느냐”의 차이다.

O(n): 하나씩 다 보는 방식

  • 예: 친구 100만 명 중에서 특정 사람 찾기
  • 맨 앞부터 이름을 하나씩 확인
  • 최악의 경우 100만 번 확인

즉, 데이터가 늘어날수록
확인 횟수도 그대로 늘어난다.

O(log n): 반씩 줄여가며 찾는 방식

  • 예: 국어사전에서 단어 찾기
  • 중간을 펼쳐보고:
    • 앞쪽이면 뒤는 전부 버림
    • 뒤쪽이면 앞은 전부 버림
  • 이렇게 계속 반으로 줄이면서 찾는다

그래서:

  • 100만 개가 있어도
  • 약 20번 정도만 확인하면 된다.

숫자로 비교하면

  • 데이터 100만 개일 때:
    • O(n) → 약 1,000,000번
    • O(log n) → 약 20번

차이가 엄청나다.

정리

  • HashSet이 빠른 이유:
    • 전부 다 보지 않고
    • “해시 번호”로 바로 위치를 찾아가기 때문
  • O(n)과 O(log n)의 차이:
    • 하나씩 전부 보느냐
    • 반씩 줄이면서 보느냐의 차이
  • 데이터가 커질수록
    • 이 차이는 압도적으로 커진다