[03] HashSet, 그리고 O(n)과 O(logn)

01. HashSet의 내부 동작 방식과 중복 제거 메커니즘

1. 내부 동작 방식

우선 HashSet은 내부적으로 HashMap 구조를 활용하여 데이터를 관리한다. HashMap과 마찬가지로 Key-Value 쌍으로 데이터를 저장할 뿐만 아니라, 사용자가 저장하려는 데이터를 Map의 Key 자리에 배치함으로써 중복을 방지한다. 즉, HashMap은 구조적으로 Key의 중복을 허용하지 않기 때문에, HashSet은 데이터를 Key에 저장함으로써 데이터의 유일성을 보장한다.

 

만약 사용자가 "codeit" 이라는 데이터를 HashSet에 저장할 때, 내부에서는 다음과 같은 프로세스가 진행된다.

 

내부 동작 방식
데이터의 주소화 (Hashing)	해시 함수를 통해 저장하고자 하는 데이터를 고유한 숫자 값인 해시 코드로 변환한다
빠른 저장 및 탐색	변환한 해시 코드 값을 인덱스로 삼아 데이터를 특정 버킷에 저장 및 탐색한다 >> 계산된 주소로 바로 접근하기 때문에 매우 빠른 저장 / 검색 연산 속도를 지원한다

 

2. 중복 제거 메커니즘

HashSet은 순서를 보장하지 않으면서 동시에 중복을 허용하지 않는 자료 구조이다. 그렇기에 HashSet은 다음과 같은 메커니즘을 통해 데이터 중복을 방지한다.

 

중복 제거 메커니즘
hashcode() 비교	새로운 데이터의 해시 코드 값을 계산하고, 저장된 객체 중 같은 해시 코드 값을 가진 객체가 있는지 확인한다
equals() 비교	해시 충돌이 발생한 경우, 실제 두 객체의 내용이 같은지 equals() 메서드를 통해 검사한다

 

이처럼 HashSet의 중복 제거 메커니즘이 효율적인 이유는 모든 데이터를 비교하는 것이 아니라, 해시 함수를 통해 데이터가 저장될 버킷만 즉시 계산하여 비교하기 때문이다. 즉, 해시 함수를 통해 비교 대상을 획기적으로 줄임으로써 평균적으로 O(1)의 중복 체크 속도를 유지한다.

 

---

 

02. O(n)과 O(logn)

	선형 시간 복잡도 O(n)	로그 시간 복잡도 O(logn)
정의	프로그램 실행 시간이 입력 데이터 개수(n)에 비례	연산을 한 번 수행할 때마다 확인해야 할 데이터 양이 절반씩 줄어듦
실생활 예시	사전 정독	업다운 게임
데이터 백만개	1,000,000번	20번