해쉬 함수

효과적인 해쉬함수의 조건은 주어진 데이터의 키 값을 가능한 적은 범위로 매핑하면서 해쉬총돌을 되도록 적게 만들어야 한다. 몇가지의 해쉬함수 생성방법에 대하여 알아보도록 한다.


제곱법Mid Square
: 키 값을 제곱하여 원하는 자리 수만큼 선택하여 해쉬주소로 사용하는 방법이다. n자리수의 제곱은 2n-1 ~ 2n자리의 정수가 된다. 이중에서 만일 해쉬주소가 1000개가 사용된다면 세자리 정수를 선택하면 된다. 이때 세자리 정수의 위치는 임의로 정한다. 예를 들어, 주어진 키 값의 자리수가 4자리이면 7~8자리 정수가 되고 아래의 그림에서와 같이 3자리의 임의의 위치에서 선택한다.

만일 주어진 해쉬주소의 범위가 0~200까지라면 간단히 나머지 연산자를 사용하여 변환가능하다. 예를 들어, 선택된 3자리의 정수를 변수 X에 치환하고 해쉬주소가 h라면 아래의 식을 적용한다.

h = X % 200


나눔법Division
: 키 값에 나머지 연산자(%)를 적용하여 주어진 해쉬주소 범위로 매핑하는 방식이다. 주어진 키 값이 k, 주어진 주소범위가 m이라면 해쉬주소 h(k)는:

h(k) = k % m

이 연산의 결과는 0 ~ m-1범위의 주소를 생성한다. 그러나 주어진 해쉬주소 m이 2의 제곱일(2, 4, 8, …)때는 동일주소의 생성가능성이 크므로 소수Prime Number를 선택하는 것이 해쉬충돌을 줄이는 방법이다.


폴딩법Folding
: 키 값을 몇 개의 부분으로 분할 후 합산하여 해쉬주소를 생성하는 방법이다. 주어진 키 값을 3자리씩 분할하여 단순히 3자리를 더하는 시프트 폴딩방식 또는 3자리 수를 한번은 정방향, 한번은 역방향으로 읽어 더하는 경계 폴딩방식을 사용한다. 예를 들어, 주어진 키 값이 아래와 같다면:

123456789123 => 123 456 789 123
– 시프트 폴딩: 123 + 456 + 789 + 123
– 경계 폴딩: 123 + 654 + 789 + 321

폴딩 결과가 주어진 주소범위에 맞도록 조정상수를 곱해서 크기를 조정한다.