위클리 페이퍼 - 3주차

HashSet의 내부 동작 방식과 중복 제거 메커니즘을 설명하고, HashSet이 효율적인 중복 체크를 할 수 있는 이유를 설명해주세요.

• HashSet이란?
  • Java의 java.util 패키지에 있는 Set 인터페이스의 구현체 중 하나로, 중복을 허용하지 않고, 순서를 보장하지 않는 컬렉션이다.

HashSet의 핵심 특징

중복허용 X	같은 값이 두 번 저장되지 않음 (equals() & hashCode()로 판단)
순서 보장 X	저장한 순서를 유지하지 않음
null 허용 O	null 값을 1개 저장 가능
검색 속도 빠름	내부적으로 HashMap 기반으로 구현되어 탐색/삽입 속도가 빠름
정렬 안됨	정렬된 상태가 필요하면 TreeSet이나 LinkedHashSet 사용

 

1. HashSet의 내부 구조

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();
}

• HashSet은 내부적으로 HashMap을 이용한다.
• 실제로 값을 key로 넣고, value는 의미 없는 더미 객체 PRESENT이다.
• 따라서, HashSet.add(E e) → 내부적으로 map.put(e, PRESENT) 호출한다.

2. 저장 시 내부 동작 과정

예 : set.add("apple") 호출 시

1. "apple" 객체의 hashCode() 값 계산
2. 해당 해시코드로 해시 버킷(bucket) 결정
3. 같은 버킷에 이미 있는 값들과 equals() 비교
4. 이미 동일한 값이 있으면 추가하지 않음
5. 없다면 HashMap에 저장 → put("apple", PRESENT)

내부 동작 과정(예 : 저장 시)

 

3. 중복 제거 메커니즘

중복 여부를 다음 두 메서드로 판단한다.

hashCode()	같은 해시값인지 확인 (빠른 후보 필터링)
equals()	실제 값이 같은지 확인 (정밀 검사)

 

• 중복 제거 조건
  • 둘 다 같아야 동일 객체(중복)로 보고 추가하지 않음.

A.hashCode() == B.hashCode()
A.equals(B) == true

 

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

 - HashSet이 효율적인 중복 체크를 할 수 있는 이유는 내부적으로 HashMap을 기반으로 구현되어 있고, 해시 함수를 활용하여 빠르게 데이터의 존재 여부를 판단하기 때문이다.

 

1. 해시 함수의 활용

• hashCode()를 통해 객체를 해시값으로 변환
• 해시값으로 배열의 특정 인덱스(버킷)를 빠르게 결정
• 시간복잡도: O(1) - 배열 인덱스 접근

2. 분산 저장 구조

• 해시값에 따라 데이터를 여러 버킷에 분산 저장
• 전체 데이터를 순회할 필요 없이 특정 버킷만 확인
• 충돌이 적을수록 더 효율적

3. 2단계 검증 시스템

• 1단계: hashCode() - 빠른 버킷 탐색
• 2단계: equals() - 정확한 동등성 비교
• 해시 충돌 시에만 equals() 비교 수행

4. 리스트 vs HashSet 비교

• ArrayList: 중복 체크 시 전체 순회 필요 → O(n)
• HashSet: 해시 기반 직접 접근 → O(1) 평균

요소	설명
해시 함수 사용	hashCode()를 이용해 위치를 빠르게 계산함으로써 탐색 시간을 단축
버킷 구조(Hash Bucket)	충돌이 발생해도 연결 리스트나 트리 구조로 빠르게 비교 가능
equals() 비교 최소화	같은 해시값만 비교하므로 전체 요소와 비교하지 않음
시간 복잡도 평균 O(1)	add(), contains() 모두 평균적으로 O(1)의 성능

HashSet 중복 체크 원리

 

나만의 언어로 정리해보기

HashSet이란?
중복X, 순서X 컬렉션
중복 제거 메커니즘
해시 코드로 같은해시 값인지 확인, equals로 실제 값이 같은지 확인. 해시코드와 equals 둘 다 같아야 중복으로 보고 추가하지 않음.
내부적으로 HashMap을 기반으로 구현되어 있고 해시 함수를 활용하여 빠르게 데이터의 존재 여부를 판단하기 때문에 중복 체크를 효율적으로 할 수 있다.

 

O(n)과 O(log n)의 성능 차이를 실생활 예시를 들어 설명하고, 데이터의 크기가 1백만 개일 때 각각 대략 몇 번의 연산이 필요한지 비교해주세요.

O(n)과 O(log n)은 알고리즘의 시간 복잡도(Time Complexity)를 나타내는 표현이다. 이걸 이해하면 코드가 얼마나 빠르게 실행되는지, 데이터가 커졌을 때 얼마나 느려질지를 예측할 수 있다. 

- 시간 복잡도(Time Complexity)란?

• 입력 크기(n)가 커질수록 실행 시간이 어떻게 증가하는지를 수학적으로 표현한 것이다.
• 정확한 시간(초)을 말하지 않고, 성장 속도(크게 늘어나는 정도)를 말한다.

- O(n) - 선형 시간

• 의미: 입력이 n개라면, n번 작업이 필요
  • 예시

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

• 입력이 10이면 10번, 100이면 100번 반복
• 시간 증가 = 데이터 증가에 정비례
• 예) 리스트 전체를 순서대로 탐색하는 경우 (선형 탐색)

- O(log n) - 로그 시간

• 의미: 입력이 n개라면, 로그(log n) 만큼만 작업이 필요
• 보통 로그는 2를 밑으로 하는 로그(log₂ n) 를 의미
  • 예시

int left = 0, right = n - 1;
while (left <= right) {
    int mid = (left + right) / 2;
    if (target == arr[mid]) break;
    else if (target < arr[mid]) right = mid - 1;
    else left = mid + 1;
}

• 입력이 1,000개여도 약 10번만 비교하면 끝난다.
• 예) 정렬된 배열에서 이진 탐색(Binary Search)

O(n)과 O(log n) 비교

n(입력 크기)	O(n) (선형 시간)	O(log n) (로그 시간)
10	10번	4번
1,000	1,000번	10번
1,000,000	1,000,000번	20번

• O(n) : 전체 데이터를 하나씩 확인 (선형 탐색 등)
• O(log n) : 매번 절반씩 나누며 탐색 (이진 탐색 등)

예시: 물건에서 특정 상품 찾기

1) O(n): 선형 탐색 - 마트에서 무작위로 진열된 물건 찾기

• 상황: 마트 진열대에 100개의 상품이 무작위로 진열되어 있고, 특정한 물건(예: “꿀사과”)을 찾는다고 가정.
• 방법: 첫 번째 상품부터 하나씩 모두 확인하면서 찾기
• 최악의 경우: 100개 전부 확인 → 100번 비교 → O(n)

→ 물건이 10배 많아지면 탐색 시간도 10배 걸림

 

2) O(log n): 이진 탐색 - 정렬된 도서관에서 책 찾기

• 상황: 도서관 책장이 가나다순으로 정렬되어 있고, “이순신 전기” 책을 찾는다고 가정
• 방법: 중간 책을 펼쳐서 앞인지 뒤인지 판단 → 절반 제거 → 반복
• 총 1024권이 있다면, 최대 10번(=log₂1024)만에 찾을 수 있음

→ 책이 10배 늘어나도 (10240권) → 14번 정도 비교 → O(log n)

 

나만의 언어로 정리해보기

O(n)과 O(log n)의 성능 차이

O(n), O(log n) : 알고리즘의 시간 복잡도(Time Complexity)
O(n) : 입력이 n개면 n번의 작업 ex)선형 탐색
O(log n) : 입력이 n개면 log n번의 작업 ex)이진 탐색

데이터 크기가 1백만 개일 때
O(n) : 1백만 번 탐색
O(log n) : 20번 탐색