[자료구조] 해시 함수 (hash function)

해시 함수

해싱에서는 키 값을 해시 테이블의 주소로 변환하는 해시 함수가 잘 설계되어있어야 탐색의 효율을 높일 수 있습니다.

좋은 효율을 가지고 있는 해시 함수는 다음과 같은 특징을 가집니다.

1. 충돌이 적어야 함
2. 해시 함수 값이 해시 테이블 주소 영역 내 고르게 분포되어야 함
3. 계산이 빨라야 함

 

제산 함수

제산 함수는 나머지 연산자를 사용해 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법입니다.

$$ h(k) = k \space mod \space M $$

여기서 $M$은 해시 테이블의 크기입니다. 해시 테이블의 크기를 어떻게 해야 해시 주소가 좋은 효율을 가지게 될까요?

답은 소수(prime number)입니다. $M$이 짝수라면 메모리 주소는 대부분 짝수이므로 해시 함수값 또한 짝수가 나올 것입니다. 소수로 하게 된다면 $0$에서 $M-1$을 골고루 사용하는 값을 만들어냅니다.

hash_index = key % M;

 

폴딩 함수

키를 몇 개의 부분으로 나누어 더하거나 비트별로 부울 연산(XOR)을 합니다. 이를 폴딩(folding)이라고 하는데, 폴딩 방식에는 대표적으로 두 가지가 있습니다.

• 이동 폴딩: 키를 여러 부분으로 나눈 값들을 더해 해시 주소로 사용
• 경계 폴딩: 키의 이웃한 부분을 거꾸로 더해 해시 주소로 사용

폴딩 함수는 키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용됩니다. 폴딩하지 않고 키값의 일부만을 주소값으로 사용하게 된다면 그 일부가 겹치는 많은 키들이 존재할 때 충돌할 가능성이 생깁니다. 따라서 이를 방지하기 위해 폴딩 함수를 사용하는 것입니다.

hash_index = (short)(key ^ (key >> 16));

 

중간 제곱 함수

중간 제곱 함수는 키를 제곱한 다음, 중간의 몇 비트를 해시 주소로 생성하는 해시 함수입니다.

 

비트 추출 방법

비트 추출 방법은 ($M=2^k$일 때) 키를 이진수로 간주해 임의의 위치의 k개 비트를 해시 주소로 사용하는 것입니다.

 

숫자 분석 방법

숫자 분석 방법은 키 각각의 위치에 있는 숫자 중 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합해 해시 주소로 사용합니다.