코드잇 백엔드 스프린트 - 5주차 위클리 페이퍼 : HashSet 와 O(n)과 O(log n)의 성능 차이

1️⃣ HashSet의 내부 동작 방식과 중복 제거 메커니즘

🔹 HashSet은 어떻게 동작하는가?

HashSet은 내부적으로 HashMap을 활용하여 데이터를 저장합니다.

• HashSet의 각 요소는 HashMap의 Key로 저장되며, Value는 더미 값(Dummy Value) (PRESENT)가 사용됩니다.
• hashCode() 를 이용해 데이터를 저장할 버킷(Bucket) 을 결정합니다.
• 같은 해시 값이 발생하면 equals() 메서드를 사용해 중복 여부를 확인합니다.

🔹 HashSet의 중복 제거 과정

1. 새로운 값을 추가(add) 하면, HashSet 내부에서 hashCode() 값을 계산하여 버킷 위치를 찾음
2. 해당 위치에 이미 값이 있으면 equals()로 비교
3. 같은 값이면 추가하지 않음(중복 제거), 다른 값이면 새로운 값으로 저장

✅ HashSet이 효율적인 이유

• 탐색, 추가, 삭제 연산이 평균적으로 O(1)
• hashCode()를 활용해 빠르게 중복 여부를 판별하여 equals() 호출을 최소화
• 배열 + 연결 리스트(혹은 트리)를 활용하여 충돌을 최소화

---

2️⃣ O(n)과 O(log n)의 성능 차이

🔹 O(n) vs O(log n) 실생활 예시

시간 복잡도 실생활 예시

O(n) (선형 탐색)	전화번호부에서 원하는 이름을 처음부터 하나씩 찾기
O(log n) (이진 탐색)	중간부터 찾고, 앞/뒤를 선택하여 탐색 범위를 절반씩 줄이기

📌 O(n) 예시 (선형 탐색)

• 전화번호부에서 특정 이름을 찾을 때 첫 페이지부터 하나씩 확인하는 방식
• 데이터가 많아질수록 검색 시간이 비례해서 증가

📌 O(log n) 예시 (이진 탐색)

• 전화번호부가 정렬되어 있다면, 중간부터 확인하고 필요 없는 절반을 버리며 탐색
• 한 번 검색할 때마다 검색 범위가 절반씩 줄어들어 매우 빠름

---

🔹 데이터 크기가 1백만 개일 때 연산 횟수 비교

데이터 크기 O(n) 연산 횟수 O(log n) 연산 횟수

1,000,000개

최대 1,000,000번 비교

log₂(1,000,000) ≈ 20번 비교

🚀 O(n)은 데이터가 커질수록 연산 횟수가 선형 증가하지만, O(log n)은 매우 적은 횟수로도 원하는 데이터를 찾을 수 있음!