[알고리즘] 해싱 함수 (Hashing Function)

해싱(Hashing)이란?
M(키들의 크기)보다 훨씬 작은 n(상이한 키의 레코드 수)의 경우 m개의 테이블 공간만을 사용하여
동적 데이터 집합을 저장하고 접근할 수 있도록 하는 방법.
간단히 예는 "문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하여 짧은 키를 사용
하여 항목을 검색함. 이는 원래의 값을 이용하여 찾는 것보다 빠르기 때문 (데이터베이스)"

해싱 함수(Hashing Function)이란?
키의 전체집합을 U라 하고 해시 테이블을 T[0..m-1]이라 할 때 해시 함수 h는 다음과 같이 키값을
테이블 주소로 변환하는 함수
h : U -> {0, 1, .... , m - 1} 키 k에 대한 h(k)를 해시값이라고 함.
즉 해싱 알고리즘을 해싱 함수라고 부름. 해싱 함수 h(k)는 어떤 키 k에 대한 테이블 주소를 계산하기
위한 방법으로, 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 내는 수식.

나눗셈법(Division method) <== 나머지 연산법
h(k) = k mod m
예를 들면 k가 123이고 m이 13이면 h(k)는 6이 된다.
여기서 주의할 점은 m의 선택에 있어서 m은 2의 멱수와 상당한 차이가 있는 소수로 선택하여야 함.

곱셈법(Multiplication method)
h(k) = [ m{kθ} ]
곱셈법의 장점은 m의 값이 중요하지 않음

유니버셜 해싱(Universal hashing)
실행시에 해싱 함수의 큰 집합으로부터 임의의 해싱 함수를 선택하여 편향된 사용이 불가능하도록
하는 방법

키 K2하고 K5가 충돌 발생

해싱에 관련된 내용을 다음을 참조하면 괜 찮을 듯..

Hashing.pdf

일반적인 간단한 해싱 함수들의 C 소스는

GeneralHashFunctions_-_C.zip

Collision에 대해서는 구현이 되어 있지 않은 듯...

간단히 해싱 함수에 대해서 정리도 할 겸 해서 포스팅 해보았습니다.

아 요즘 정말 공부하기 힘드네요.. 쩝...