[📰 위클리페이퍼] HashSet? O(n) vs O(log n)?

📌 HashSet

🧐 HashSet이란?

"중복이 없는 집합(Set)"을 아주 효율적으로 구현한 대표적인 컬랙션
-> 내부적으로는 HashMap을 사용함

public class HashSet<E> {
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();
}

• HashSet에 저장하는 값(E) → HashMap의 key
• HashMap의 value → 전부 동일한 더미 객체(PRESENT)

set.add("A");

내부적으로는

map.put("A", PRESENT);

🧐 HashSet의 중복 판단 기준

🔍 hashCode()

• 객체를 어느 버킷에 넣을지 결정
• 빠른 1차 필터 역할

🔍 equals()

• 같은 버킷 안에서 진짜 같은 객체인지 확인
• 최종 중복 판정

결론

hashCode()가 같고 eqauals() 가 true -> 중복

💻 HashSet이 중복 체크에 효율적인 이유

• 평균 시간 복잡도 O(1)

  해시 기반 접근 -> 순차 탐색X
  = 리스트처럼 처음부터 끝까지 안 봄

• hashCode로 탐색 범위를 극단적으로 줄임

  List -> 최대 N번 비교
  HashSet -> 특정 버킷만 확인

• equals는 "필요할 때만" 호출됨

  hashCode가 다르면 equals조차 안 한다는 뜻

📌 O(n) vs O(log n)

🧐 O(n) vs O(log n)?

O(n) : 데이터가 늘어나면 그만큼 더 많이 일을 함
O(log n) : 데이터가 늘어나도 조금만 더 일을 함

🔍 O(n): 한 명씩 전부 확인

운동장에 100만 명이 서 있고, 그중 한 명을 찾기 위해 처음부터 끝까지 확인하는 것

ex) 출석부로 이름 찾기, 리스트에서 특정 값 찾기 (선형 탐색)

🔍 O(log n): 절반씩 줄이기

사전(정렬된 상황)에서 이름 찾기

ex) 이분 탐색, 트리 탐색, Hash 구조의 내부 로직 일부

💻 100만 개 데이터에서 연산 횟수 비교

📌 기준

• n = 1,000,000
• log2(1,000,000) ~= 20