티스토리 뷰
해쉬 테이블(Hash Tables)
일반적인 검색트리는 원소 하나를 저장하고 검색하는 데 평균적으로 
해시(Hash) 테이블은 원소의 값에 의해 결정되는 자료구조이다. 즉, 저장된 자료와의 비교를 통해 자리를 찾지 않고 단 한번의 계산으로 자리를 찾는다.
해쉬 함수
임의의 원소를 해시 테이블에 저장하려면 먼저 해당 원소의 해시값을 계산한다. 해시값은 해시 함수에 의해 계산된다. 해시 함수는 키값을 입력으로 받아 해시 테이블 상의 주소를 리턴하며 다음의 두 가지 성질을 가지도록 만들어야 한다.
- 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
- 계산이 간단해야 한다.
첫 번째 성질이 가장 중요한데 이 성질을 잘 만족해야 서로 다른 두 원소가 한 주소를 놓고 충돌할 확률이 작아지기 때문이다. 두 번째 성질은 지나치게 복잡한 계산을 필요로 하는 경우가 거의 드물기 때문에 신경쓰지 않아도 된다.
가장 이상적인 해쉬함수는 원소들을 동일하게 분포하게 하는 것이나 현실에서는 불가능한 것으로 키들이 가진 특정한 패턴에 대해서 독립적인 해쉬함수가 바람직하다.
해쉬 함수를 만드는 대표적인 두 가지 방법이 있는데 첫째는 나누기방법, 둘때는 곱하기 방법이다. 널리 쓰이는 MD5, SHA-256 와 같은 해쉬 알고리즘들은 여러 방법들을 잘 이용하여 첫 번째 성질을 만족한다.
① 나누기 방법(Division Method)
나누기 방법은 원소를 해쉬 테이블의 크기로 나누어 나머지의 값을 테이블의 주소로 사용하여 저장하는 방법이다.
위의 예제는 해쉬 테이블의 크기가 13 일때 해쉬함수에 25, 13, 16, 5 ,7 의 입력값이 주어진 경우이다. 25는 25mod13=12 이므로 12번째 인덱스에 저장이되었고 13은 13mod13=0 이므로 0번째 인덱스에 저장되었다.
나누기 방법의 해쉬 함수의 식은 다음과 같다.
해쉬 테이블의 크기 m은 2의 멱수에 가깝지 않은 소수를 택하는 것이 좋다. 해쉬값은 입력 원소의 모든 비트를 이용하는 것이 확률적으로 좋은 분포를 갖도록 하는데 유리하다.
② 곱하기 방법(Multiplication Method)
나누기 방법은 해쉬 테이블 크기보다 큰 수를 해쉬 테이블 크기 범위에 들어오도록 수축시킨다. 곱하기 방법은 이와 반대로 먼저 입력값을 0과 1 사이의 소수로 대응시킨 다음 해시 테이블 크기 m을 곱하여 0~m-1 사이로 팽창시킨다. 이 방법에서는 해쉬 함수의 특성을 결정짓는 0<A<1 의 범위의 상수 A를 미리 준비해야 한다. 임의의 원소 x에 대해 다음과 같은 과정을 거쳐 x의 주소를 결정한다.
- x에 A를 곱한 다음 소수부만 취한다.
- 방금 취한 소수부에 m을 곱하여 그 정수부를 취한다.
정리하면, 해쉬 함수는 다음과 같다.
예를 들어, 크기 m이 65,536인 해시 테이블에서 A=0.6180339887로 정해져 있다고 하고 해쉬값을 구하면, xA = 1,025,390 x 0.6180339887 = 633,725.871673093이 된다. 이 값에서 소수부만 추출하면 0.871673093이 되고, 이 값에 해쉬 테이블의 크기인 65,536을 곱하면 57,125.967... 이 된다. 이 수에서 정수부만 취하면 57,125가되어 원소 1,025,390에 대한 해쉬 주소는 57,125가 된다.
곱하기 방법은 나누기 방법과는 달리 해쉬 테이블의 크기 m을 아무렇게나 잡아도 상관 없다. 따라서 컴퓨터의 이진수 환경에 맞게 
해쉬 테이블은 이처럼 저장 주소를 단번에 계산할 수 있지만 한 가지 중요한 장애물이 있다. 예를들어, 해쉬 함수가 h(x) = x mod 13 이라 하면 h(15) = 2 가 되어 2번 인덱스에 저장이 된다. 이 후 28의 입력값이 들어온다면 h(28) = 2 가 되는데 이미 2번 주소에는 원소 15가 자리를 차지하고 있다. 이런 상황을 충동(Collision)이라 한다. 충돌을 처리하는 방법에는 여러가지가 존재한다.
해슁에서의 충동해결(Collision Resolution)은 다음 글에서 다루도록 하겠습니다.
다음 글 - 해슁에서의 충동해결(Collision Resolution)
참고자료 : 쉽게 배우는 알고리즘 - 한빛아카데미