티스토리 뷰
HashSet의 내부 동작 방식과 중복 제거 메커니즘을 설명하고, HashSet이 효율적인 중복 체크를 할 수 있는 이유를 설명해주세요.
HashSet 이란?
java.util 패키지에 속한 jcf(자바 컬렉션 프레임워크) 클래스 중 하나이다
HashSet의 특징
- Set interface의 구현체
- 저장 순서가 없다
- null값 허용
- 검색 속도가 빠르다
HashSet의 내부 동작 방식
1. hashCode()로 저장할 칸을 계산한다.
- 값을 넣기 전에 위치를 먼저 계산
2. 그 칸에 값이 없으면 저장한다.
- HashSet 자체적 저장이 아닌 내부에 있는 HashMap이 데이터를 key값으로 저장
3. 값이 있으면 equals()로 같은 값인지 확인한다.
- equals()가 true면 같은 값(중복)이므로 저장 하지 않는다
- equals()가 false면 다른 값(중복X)이므로 저장
4. 같은 값이면 무시 -> 중복 제거 완료
HashSet의 중복 제거 메커니즘과 효율적인 중복 체크를 할 수 있는 이유
hashCode(): 먼저 같은 hashCode 칸에 들어왔는지 확인 -> 빠르게 후보 좁힘
equals(): 같은 칸 안에서 실제 값이 같은지 비교 -> 진짜 중복 판정
즉, HashSet은 hashCode로 후보를 찾고, equals로 최종 확인하는 방식으로
중복을 정확하고 빠르게 제거한다.
O(n)과 O(log n)의 성능 차이를 실생활 예시를 들어 설명하고, 데이터의 크기가 1백만 개일 때 각각 대략 몇 번의 연산이 필요한지 비교해주세요.
O(n)과 O(log n) 이란?
O(n), O(log n)은 연산의 시간 복잡도를 나타내는 표기
쉽게 말하면 데이터가 많아질수록 작업이 얼마나 오래 걸리는지를 나타내는 척도
O(n) 선형 시간 (Linear Time)
특징
- 데이터가 한 개씩 늘어날수록 연산 횟수가 비례해서 증가한다
- 데이터가 많아지면 시간이 비례해서 늘어난다
실생활 예시: 책장에서 특정 책 찾기
- 책장에 책이 100권이면 최대 100번, 1,000권이면 최대 1,000번 확인
O(n log n) 선형 로그 시간 (Linearithmic Time)
특징
- 데이터가 두 배로 늘어나도 연산 횟수는 1번만 추가될 정도로 천천히 증가
- 데이터가 많아도 연산 횟수는 느리게 증가.
실생활 예시 : 전화번호부에서 이름 찾기
(전화번호부가 가나다 순으로 정렬되어 있다고 가정)
- 중간을 쪼개서 찾는 사람을 비교 -> 원하는 사람이 중간보다 앞인지 뒤인지 확인 -> 범위를 절반으로 줄이는 방식
- 전화번호부가 100쪽이면 7번 안쪽, 1,000쪽이면 10번 안쪽 정도면 찾을 수 있음
연산 횟수 비교 (n = 1,000,000)
선형 탐색(O(n)) = 100만 번 확인
선형 로그 탐색(O(log n)) = 약 20번 확인