해쉬 알고리즘hash algorithm-균일성uniformity

Definition

해쉬함수를 평가할때 쓰이는 속성.
해쉬 출력값이 모두 같은 확율로 나올수록 좋은 해쉬 알고리즘이므로, 이를 균일성이 높다라고 표현함

Example

[input]->[output]

1번 해쉬 알고리즘

A->03
B->02
C->03

2번 해쉬 알고리즘

A->01
B->02
C->03

예제 설명

위와 같은 해쉬값이 나온다면, 2번 알고리즘의 균일성이 1번 알고리즘보다 높다라고 표현할수있음.

결론

균일성이 높을수록, 해쉬 충돌이 일어나지 않는다는 뜻이므로, O(1) 의 time complexity가 나올 가능성이 높아짐.

추가 설명

균일성이 아주 높아서 해쉬충돌이 일어나지 않는 해쉬 알고리즘이 가능한가?

결론적으로 가능하지만, 아주 제한적으로만 가능함

균일성 측정

카이제곱 검정(chi-squared test) 접합도를 측정하여 실제 측정값과 나눕니다.
예상되는 접합 / 실제 접합도

$$\frac{\sum_{j=0}^{m-1} \left ( b_{j} \right ) \left ( b_j+1 \right )/2}{\left ( n/2m \right )\left ( n+2m-1 \right )}$$

n=key의 개수
m=버킷의 개수
b(j)=버킷의 아이템 수

결과값이 신뢰구간인 0.95~1.05에 해당된다면, 이 해쉬 함수가 균일된 분포도를 가지고 있다고 할수있음.
실제 해쉬 알고리즘을 만들게 아니라면 이정도만 알아도 괜찮다고 생각함.