4월_3주차. HashSet, O(n)과 O(log n)
🇶1. HashSet의 내부 동작 방식과 중복 제거 메커니즘을 설명하고, HashSet이 효율적인 중복 체크를 할 수 있는 이유
🇶2. O(n)과 O(log n)의 성능 차이를 실생활 예시를 들어 설명하고, 데이터의 크기가 1백만 개일 때 각각 대략 몇 번의 연산이 필요한지 비교
1. HashSet
: 중복 없는 데이터를 저장하는 자료구조.
: HashSet은 HashMap을 내부적으로 사용함
: Set 인터페이스 자체가 중복을 허용하지 않는 집합
- 내부 동작방식
데이터를 추가할 때, 객체의 해시코드를 호출해 해시값을 계산함
해시값을 통해 내부 버킷(배열 index)를 찾고, 해당 위치에 equals()로 동일성 확인 후 저장
중복 체크는 hashCode + equals 조합으로 판단
"Item 10: Obey the general contract when overriding equals"
"Item 11: Always override hashCode when you override equals"
HashSet<String> set = new HashSet<>();
set.add("apple"); //해시코드 계산 -> 저장
set.add("apple"); //같은 해시코드 + equals true -> 중복 -> 저장x
- 중복 제거 메커니즘
| 자료구조 | 평균 시간복잡도 | 실제 속도 | 이유 |
| HashSet | O(1) | 더 빠름 | 해시값으로 바로 위치 찾기 |
| TreeSet | O(log n) | 느림 | 트리 타고 올라가며 비교 |
hashCode() → 어디 있는지?
equals() → 같은 건지?
hashCode()로 바로 저장 위치를 계산해 거의 한 번에 위치 찾아서 비교함
ex) apple 넣으면 해시값 계산 → 배열의 인덱스 n번 → n번으로 가서 equals 비교
해시 충돌 없으면 O(1)로 비교가능
충돌 있다면
- 처음엔 LinkedList 처럼 이어 붙임
- 충돌 많아지면 → Red-Black Tree로 자동 전환
- → 이때 O(log n)이 되긴하지만 정렬된 트리보단 가볍게 작동
- 효율적인 이유
주소로 위치 찾고 O(1), 한 번만에 찾을 수 있어 중복제거 초스피드~
대부분의 경우 탐색/추가/삭제가 O(1) 상수시간에 처리됨
TreeSet은 O(log n) 이지만, HashSet은 해시 기반이라 훨씬 빠름
HashSet은 대량의 데이터에서 중복체크 빠르게 할때 매우 적합함
2. O(n)과 O(log n)
- 실생활 예시
- O(n) : 줄 서있는 1000명 중 홍길동찾기
- → 한 명, 한명 이름 물어봄, 최대 1000번 물어봄
- O(log n) : 사전에서 단어 찾기
- → 중간을 계속 쪼개면서 찾는 이진 탐색
- 백만 개 데이터일 때 비교
O(n) : 1,000,000번
O(log n) : log₂(1,000,000) ≈ 20번
→ 약 5만 배 차이, 단순 반복은 시간 오래걸리고 O(log n)구조는 훨씬 빠르게 처리가능(ex) Binary Serch Tree, TreeMap)
https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/HashSet.html
https://docs.oracle.com/javase/8/docs/api/java/util/Set.html
📘 《Effective Java》 (Joshua Bloch 저자 – 자바의 전설 같은 책!)