TIL - Java Hash (09.18)

📚 오늘 학습한 내용

List vs Set 비교

List

• 순서 유지, 중복 허용, 인덱스 접근 가능
• 예시: 장바구니 목록, 순서가 중요한 이벤트 목록

Set

• 유일성 보장(중복 불허), 순서 미보장, 빠른 검색 최적화
• 예시: 회원 ID 집합, 고유한 항목의 집합

해시 알고리즘의 필요성

기존 Set 구현의 문제점

// MyHashSetV0의 성능 문제
add(value) → O(n) // 중복 검사로 인한 성능 저하
contains(value) → O(n) // 전체 데이터 순회 필요

데이터 추가 시마다 중복 여부를 확인하기 위해 전체 데이터를 순회해야 하는 비효율적인 구조였다.

해시 알고리즘의 진화 과정

1단계: 데이터 값을 인덱스로 직접 사용

// 데이터 1,2,5,8을 저장
inputArray[1] = 1;
inputArray[2] = 2; 
inputArray[5] = 5;
inputArray[8] = 8;

// 검색 시 O(1) 성능
Integer result = inputArray[searchValue];

장점: O(1)의 검색 성능 단점: 입력값 범위만큼 배열 크기 필요 → 메모리 낭비 심각

2단계: 나머지 연산을 통한 해시 인덱스 생성

static int hashIndex(int value) {
    return value % CAPACITY; // 나머지 연산으로 인덱스 생성
}

// 예시: CAPACITY = 10
1 % 10 = 1
14 % 10 = 4  
99 % 10 = 9

장점: 제한된 배열 크기로 넓은 범위의 값 처리 가능 문제: 해시 충돌 발생 가능

해시 충돌과 해결방안

해시 충돌 상황

99 % 10 = 9
9 % 10 = 9   // 같은 해시 인덱스 → 충돌!

해결 방법: 연결 리스트를 이용한 체이닝

LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];

// 같은 해시 인덱스에 여러 값 저장
buckets[9] = [99, 9]  // 연결 리스트로 충돌 해결

성능 분석

해시 충돌을 고려한 성능

• 평균: O(1) - 해시 충돌이 적을 때
• 최악: O(n) - 모든 데이터가 같은 인덱스에 집중될 때

최적 성능을 위한 조건

• 데이터 수가 배열 크기의 75% 이하일 때 충돌 빈도 낮음
• 배열 크기가 클수록 충돌 확률 감소하지만 메모리 사용량 증가

구현 핵심 코드

데이터 추가

private static void add(LinkedList<Integer>[] buckets, int value) {
    int hashIndex = hashIndex(value);
    LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)
    if (!bucket.contains(value)) { // O(n) - 충돌 시
        bucket.add(value);
    }
}

데이터 검색

private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {
    int hashIndex = hashIndex(searchValue);
    LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)
    return bucket.contains(searchValue); // O(n) - 충돌 시
}

💡 핵심 인사이트

1. 해시 알고리즘의 본질: 검색 성능을 O(n)에서 O(1)로 혁신적으로 개선
2. 트레이드오프: 메모리 사용량과 성능 사이의 균형점 찾기가 중요
3. 확률적 성능: 최악의 경우는 드물며, 적절한 배열 크기 설정으로 대부분 O(1) 성능 달성 가능

🎯 다음 학습 목표

• 실제 Java HashSet 구현체의 최적화 기법 학습
• 다양한 해시 함수와 충돌 해결 방법 비교 분석
• 해시 테이블의 동적 크기 조정(리해싱) 메커니즘 이해