문제: n-length 해쉬테이블에 m개의 오브젝트를 넣을때, 오브젝트 1개만을 포함한 슬롯의 갯수를 구하여라


(ㄴㅂㄷㄱㄷㄱ) #1

*질문이 아닌 자문자답임니다

문제:
n개의 슬롯이 있는 해쉬테이블이 있다. 이 해쉬테이블의 해싱함수는 성능이 매우 좋아서, 오브젝트를 삽입할 때마다 균등 (uniform) 하게 분포하여 해당 슬롯에 삽입한다. 같은 슬롯에 여러개의 오브젝트가 삽입 될 수 있다.

n개의 슬롯이 있는 해쉬테이블에 총 m개의 오브젝트를 삽입했을 때,
1개의 오브젝트만 포함한 슬롯의 갯수를 구하여라.

풀이:

n이 상당히 커질때 이 문제는 Poisson distribution를 이용해 근사할 수 있다.

Poisson 은 이산확률분포의 한 종류로, 특정 기간 혹은 구간에 사건이 발생하는 기댓값이 주어졌을때 (lambda), 그 사건이 k번 발생하는 확률을 구할 수 있는 아주 유용한 분포이다. 이는 Poisson(lambda, k)의 형태로, lambda 와 k 를 인수로 갖는 함수이다.

이를 해쉬테이블 문제에 적용해보자.

전체 해시 테이블에 m번의 삽입 이벤트가 발생하므로, 각 슬롯에는 m/n 번 발생하는 셈이다. 즉, lambda = m/n 이다.

오브젝트가 특정 슬롯에 ‘단 한번’ 들어와야 하므로 k = 1 이다.

Poisson(\lambda, k) = \frac{e^{ -\lambda} \lambda^k}{k!}

이므로

Poisson(m/n, 1) = \frac{me^{-\frac{m}{n}}}{n}

이다.

즉, 한 구간 (슬롯)에서 “오브젝트 삽입” 이벤트가 1번만 발생할 확률은 m/n * exp(-m/n) 이다.

총 n 개의 슬롯이 있으므로 오브젝트를 1개만 포함한 슬롯의 개수는 n * m/n * exp(-m/n) =

me^{-\frac{m}{n}}

이다.

출처: hashing - Probability of hash collision in the case of two parallel hashes - Computer Science Stack Exchange


기억 안 날 때 꺼내보려고 코톡에 올려둡니다


(sh) #2

삭제버튼이 어딧더라… :wink:


(crmerry) #3

오왕 멋지다에요?


(프로책팔이) #4

아조씨… 인성 실화…?