Weekly Paper#3

1. HashSet 내부 동작과 중복 제거 메커니즘 

Java에서 HashSet은 내부적으로 HashMap<E, Object> 을 사용한다. HashMap의 실제 저장 구조는 배열과 같다. 

배열(table)
 ├── 0번 버킷 (내부에는 LinkedList가 들어감.)
 ├── 1번 버킷
 ├── 2번 버킷 -> Node -> Node -> Node (LinkedList)
 ├── ...
 └── n번 버킷

이 배열을 해시 테이블(Hash Table)이라고 부르고, 각 칸을 버킷(bucket)이라고 한다.

 

HashSet에 값 하나를 넣을 때 실제로 일어나는 일

set.add("apple");

// 1. hashCode() 실행 ex) apple.hashCode() = 93029210
int hash = "apple".hashCode();

// 2. 버킷 위치 계산 -> 해시값 그대로 사용하지 않고 해쉬 코드에 따라 index 부여

index = hash % table.length

// 3. 해당 버킷만 확인 -> 전체를 순회하지 않고, 오직 해당 버킷만 봄

// 비어 있음 -> 그냥 저장 , 이미 값이 존재함(해시 충돌) -> 이때 equals() 비교가 시작
// false -> 함께 저장, true -> 중복 (저장 C)

 

HashSet이 빠른 이유

❌  List

• 항상 처음부터 끝까지 순회
• 시간복잡도: O(n)

⭕ HashSet

• 비교 대상 수 = 1 ~ 2개
• 평균 시간 복잡도: O(1) 

해시 충돌 처리하는 방법 

• 초기 : LinkedList
• 많아지면: Red-Black Tree

 

2. HashSet이 효율적인 중복 체크를 할 수 있는 이유

해시를 이용해 비교 대상을 극단적으로 줄이기 때문이다. 

• List, Array -> O(n)
• HashSet -> hashCode를 계산하고 저장 위치 결정, 그 안에서만 비교 

즉 , 전체 n 개 중 단 하나의 버킷만 접근함!!

 

3. O(n) vs O(log n) 실생활 예시(100만 개) 및 비교

O(n) -> 데이터 수만큼 탐색 시간이 증가함

O(log n) -> 탐색 범위를 절반씩 제거하므로 데이터가 아무리 커져도 증가속도가 매우 느림