-
해시 함수
해시 함수는 해시 테이블에서 키 값을 테이블의 인덱스로 만들어 주는 함수로 다음의 성질을 가진다.
- 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
- 계산이 간단해야 한다.
만약 데이터가 어느 한 인덱스에 몰려서 저장되게 된다면 충돌이 자주 발생하여 성능에 악영향을 미치기 때문에 입력된 데이터가 해시 테이블 전체에 골고루 나누어 저장되는 것이 상당히 중요하다.
해시 함수는 대표적으로 두 가지 방법이 존재한다.
- 나누기 방법 주어진 데이터를 해시 테이블의 크기로 나눈 나머지를 인덱스로 사용하는 방법
- 해시 테이블의 크기는 2의 멱수(2ⁿ)에 가깝지 않은 소수(prime number)를 택하는 것이 좋다.
- h(x) = x mod m
- 곱하기 방법 주어진 데이터를 0과 1 사이의 소수(decimal)로 대응시킨 뒤 해시 테이블의 크기를 곱하여 인덱스로 사용하는 방법
- 데이터를 0과 1 사이의 값으로 만들 수 있는 상수 값을 미리 준비해야 한다.
- 잘 동작하는 상수 값으로 (root 5 - 1) / 2 가 제안되어 있다.
- h(x) = └m(xA mod 1)┘