해시 충돌 : 생일 문제

생일 문제(영어: Birthday problem)는 사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제이다. 생일의 가능한 가짓수는 (2월 29일을 포함하여) 366개이므로 367명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.
나무위키 링크

코드

import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        int simulationCount = 100_000;
        int personCount = 23;

        int sameBirthdays = 0;

        for (int i = 0; i < simulationCount; i++) {
            int[] birthdays = new int[personCount];
            for (int j = 0; j < personCount; j++) {
                int birthday = ThreadLocalRandom.current().nextInt(1, 365 + 1);
                if (IntStream.of(birthdays).anyMatch(x -> x == birthday)) {
                    sameBirthdays++;
                    break;
                }
                // 생일이 일치하는 사람이 없으면 저장하고 다음 사람으로
                birthdays[j] = birthday;
            }
        }

        System.out.print(simulationCount + " 번 실험 중 생일이 같은 실험의 확률: ");
        System.out.print((double) sameBirthdays / simulationCount * 100);
        System.out.println("%");
    }
}

결론

이처럼 일반적인 상식과는 달리, 충돌은 생각보다 쉽게 일어나므로 충돌을 최소화하는 일은 중요하다.

Load Factor

충돌이 발생할 때, 또는 충돌이 발생하기 전에 최적화를 하려면 어떻게 할까?

충돌 일정 비율에 따라 해시함수를 재작성 또는 해시 테이블의 크기를 조정 할지를 결정한다. 이를 로드 팩터라고 한다.

Load Factor: 해시 테이블에 저장된 데이터 개수(n) 을 버킷의 개수(k) 로 나눈 것
Load Factor = n / k

• Load Factor 값은 해시 함수가 각 key를 잘 분산해주는지 효율성 측정에도 사용된다.

• 자바 8버전에서 해시 테이블을 구현체 HashMap을 대폭 개선

  • Default Load Factor = 0.75
    

  • 기본 값인 0.75는 시간과 공간 비용의 적절한 절충안 이라는 소리

• 일반적으로 Load Factor가 증가할수록 해시 테이블의 성능은 점점 감소

• 자바는 Load Factor 값이 0.75를 넘어설 경우, 동적 배열처럼 해시 테이블의 공간을 재할당한다.

• 자바에서 ArrayList의 동적 배열 기본 크기는 10이다. 해시맵은 16이다.
  -

• 자바에서 동적 배열 크기가 모두 차면 배열 크기를 1.5배 증가 시킨다. 하지만 해시맵은 해시 개수가 Load Factor 값에 75%에 도달하면 2배 더 큰 메모리 영역을 할당한다.

  • k *= 2
  • HashMap<> resize() 메소드
    

• 자바는 충돌이 일어나면 chaining, open addressing 중 chaining 방식을 이용해 HashMap 을 구현한다.
  

• 자바는 해시가 8번 충돌되면 링크드 리스트 형태를 균형 이진트리인 레드블랙 트리구조로 변경한다. 또한 레드블랙 트리 구조에서 해시 충돌된 값이 6개로 변경되면 다시 링크드 리스트로 변경한다.