오늘은 어제에 이어서 해시함수에 대하여 알아보려고 합니다.

개요

해싱 검색에서 가장 중효한 것이 키값의 위치를 계산하는 해시 함수라고 합니다.

어떤 해시 함수를 사용하느냐에 따라 검색의 효율이 달라집니다.

좋은 해시 함수 조건

• 비교 연산을 하는 것보다 계산하는 속도가 빨라야 하므로, 해시 함수는 계산이 쉬워야 합니다.

• 같은 버킷에 할당받는 키값이 많으면 오버플로우가 발생하므로 충돌이 적어야 합니다.

• 해시 테이블에 고르게 분포되도록 해야 합니다.

종류

• 중간 제곱 함수

키값을 제곱한 결과값에서 중간에 있는 적당한 비트를 주소로 사용하는 방법입니다.

제곱한 값의 중간 비트들은 대개 키의 모든 값과 관련되있기 때문에 서로 다른 키값은 서로 다른 중간 제곱 함수를 갖습니다.

• 제산 함수

나머지 연산자를 사용하는 방법으로, 키값을 해시 테이블의 크기로 나눈 나머지를 해시 주소로 씁니다.

• 승산 함수

곱하기 연산를 사용하는 방법으로, 키값과 정해진 실수를 곱한 결과에서 소수점 이하 부분만을 테이블의 크기와 곱하여 정수 값을 주소로 씁니다.

• 접지 함수

키의 비트 수가 해시 테이블 인덱스의 비트 수보다 큰 경우에 주로 사용하는 방법입니다. 키값이 있을 때 해시 테이블 인덱스의 비트 수와 같이 크기를 분할하고 분할한 부분을 더합니다. 더하는 순간에 이 방식에 따라 이동 접지 함수와 경계 접지 함수로 나뉩니다.

• 숫자 분석 함수

키값을 이루고 있는 각 자리수의 분포를 분석하여 해시 주소로 사용하는 방식입니다.

각 키값을 적절한 선택 진수로 변환하고 각 자릿수의 분포를 분석하여 가장 편중된 분산을 가진 자릿수는 생략하고, 가장 고르게 분포된 자릿수부터 해시 테이플 주소의 자릿수만큼 뽑아서 만든 수를 역순으로 바꾸어서 주소로 사용합니다.

• 진법 변환 함수

키값이 10진수가 아닌 다른 진수일 때, 10진수로 변환하고 해시 테이플 주소로 필요한 자릿수만큼 하위 자리 수로 사용하는 방식입니다.

• 진법 추출 함수

해시 테이블의 크기가 2^k일 때 키값을 이진 비트로 놓고 임의의 위치에 있는 비트들을 추출하여 주소로 사용하는 방식입니다.

이 방식에는 충돌날 가능성이 높다고 합니다.

다음편에는 해시 오버플로우에 대하여 포스팅될 예정입니다.