[Algorithm] 유니버설 해싱 (Universal Hashing)

# 유니버설 해싱 (Universal Hashing)

* 유니버설 해싱이란?

같은 자리에 여러 개의 키가 해시되는 것을 막기 위하여 실제 저장되는 키들과 독립적인 해시 함수를 무작위로 선택하는 것

유니버설 해싱에서 실행 초기에는 주의 깊게 설계된 함수의 집합으로부터 해시 함수를 무작위로 선택한다. 이때 해시 함수를 무작위로 선택하기 때문에 이 알고리즘을 동일한 입력에 대해서도 실행할 때마다 다르게 동작할 수 있어 임의의 입력에 대해 좋은 평균적 성능을 보장한다.

* 유니버설 해시 함수 집합의 조건

Η를 키들의 전체집합 U를 {0, 1, ..., m - 1} 로 대응시키는 해시 함수들의 유한한 집합이라고 하자. 

서로 다른 키 k, l ∈ U 각 쌍에 대해 h(k) = h(l)인 해시 함수 h ∈ Η 의 개수가 많아야 |Η| / m 라면 이 집합은 유니버설 하다고 한다.

쉽게 말해서 한쪽으로 훅 쏠리는 경우가 없을 때 유니버설하다고 한다.

* 유니버설 해시 함수 집합 설계하기

우선 충분히 큰 소수 p를 선택하여 모든 가능한 키 k가 범위 0과 p - 1 사이에 존재하게 한다. 

를 집합 {0, 1, ..., p - 1}, 를 집합 {1, 2, ..., p - 1} 이라고 하자. p는 소수기 때문에 p를 이용한 나머지 연산을 할 수 있다. 키들의 정의역의 크기가 해시 테이블의 저장 공간의 수보다 크다고 가정한다. 따라서 p > m 이다.

설계 시 table size( == m) < max key value < prime number( == p)로 하면 될 듯. 연산 성능을 보장하고 싶고 메모리의 여유가 된다면 해시 테이블의 크기를 항목 개수의 두 배정도로 하는 것이 좋다고 함.

 

이제 임의의 a ∈ , b ∈  에 대해 선형 변환 후 p와 m을 이용한 나머지 연산을 하는 해시 함수  를 새롭게 정의한다.

 

 

예를 들어, p = 17, m = 6인 경우  다. 이와 같은 모든 해시 함수의 집합은 다음과 같다.

 

 

각 해시 함수  는  를  에 대응시킨다. 이런 해시 함수들은 출력 범위의 크기 m이 반드시 소수일 필요 없이 임의의 값이면 된다는 매력이 있다. a 에 대해 p - 1 가지의 선택이 있고 b에 대해 p가지의 선택이 있기 때문에  는 p(p - 1)개의 해시 함수를 포함한다.

(해시함수 집합 이 유니버셜함에 대한 증명은 생략)

 

 

* 궁금한 점

 

이렇게 하면 충돌할 확률이 현저히 적어지고, 충돌한다고 해도 일정 길이 이상 충돌하지 않는다는 것은 알겠다.

그런데 해시함수는 기본적으로 삽입 뿐만 아니라 검색과 삭제도 지원해야한다.

책에서는 동일한 입력에 대해서도 실행할 때마다 다르게 동작할 수도 있어야 한다고 했는데...

그러면 대체 검색을 어떻게 하지????????? (삭제는 말할 것도 없고)

내가 어디서 놓친 게 있는 건지 너모 너모너모너모 답답하다.....

일단 시드값 대강 주는 걸로 구현한담에 교수님께 질문 드려야겟다.. 진짜 몽총이.. 하 ,..

유니버셜은 그렇다 쳐도 퍼펙트 해싱은 어케 구현한담. 감 0..

 

->    교수님께 여쭤본 결과, 실행 중에 계속 무작위라는 뜻이 아니라, 프로그램이 돌 때마다 다르게 되는 식일 거라고 하심. 

(같은 키라도 프로그램을 오늘 돌리면 (계속)여기에, 끄고 내일 돌리면 저기에 이런 의미로 말씀하신듯?)

더해서 원서로 좀 보라는 말씀을... ^^... 죄송해요 교수님 저 영어 알러지 있어서 ^__^ 노력해보겟슴다

 

 

 

 

- 참고자료

Introduction to Algorithms, 토머스 코멘 외 3명

알고리즘 - 컴퓨터 과학의 기본, 숫자 알고리즘에서 양자 알고리즘까지, 산죠이 다스굽타 외