(3) 해싱(Hashing)

 앞에서 얘기한 2진탐색은 상당히 빠르게 원하는 값에 접근하는 방법이다. 그러나, 보다 빠르게
탐색할수 있는 방법이 존재한다. 이 방법은 '해싱(Hashing)' 혹은 '분산 기억법(Scatter Storage
Technique)'이라고 불리우는데, 실제적으로 가장 빠른 탐색을 제공한다.

 앞서의 명함의 예를 다시 한번 생각해 보자. 명함을 보관하는 경우,  대부분의 사람들은 명함첩을
이용한다. 명함첩에는 명함이 시작되는 첫 번째의 자음을 나타내는 표지가 달려있다. 따라서, 우
리는 앞서의 2진 탐색을 사용하지 않고도, 찾고자하는 명함이 있는 위치에 상당히 가까이 다가갈
수 있다. 이와 같이 원하는 명함이 있을 위치로 옮겨간 다음에 순차탐색이나 혹은 2진 탐색을 사
용하면 앞서의 방법보다 훨씬 빠르게 찾을 수가 있게 된다.

 이 방법이 빠른 검색을 제공하는 이유는 단순하다. 즉, 검색할 자료가 보다 잘  정리가 되어 있기
때문이다. 다시 말하면, 데이터의 값에 따라 저장되어야 할 공간이 미리 지정되어 있기 때문이다.
이 방법에서 자료의 값에 따라 저장할 공간을 결정하는 함수를 '해싱함수'라고 부르고, 해싱함수를
사용하는 탐색방법을 해싱이라고 한다.

 일반적으로 해싱방법은 사용하는 해싱함수에 따라서, 그리고 해싱함수에 의해 같은 값이 나오는
(즉, 같은 저장 영역에 존재하는 -  명함의 예에서는 같은 자음으로 시작하는)자료를  어떻게 보
관할 것인가에 따라서 구분될 수가 있다.

 해싱을 사용하여 검색하는 구체적인 예를 들어보면, 그림  4와 같이 정수형 자료가 5로 나눈 나
머지에 따라서 정리되어 있고, 그 자료가 연결된 리스트(list)의 형태로 저장되어 있다고 하자.

 그렇다면 원하는 값에 대한 검색을 위한 루틴은 다음과 같이 구현될 수 있을 것이다.
 
(리스트 4) 해싱과 순차탐색을 같이 사용한 탐색 알고리즘의 예
typedef struct DATALIST
{
        int data;
        struct DATALIST *next;
} *DATAPTR;

DATAPTR Hash_Search(int key,DATAPTR *a)
{
        DATAPTR b;

        b=a[key%5];         /*해싱이 사용된 곳*/
        while (b!=NULL)
        {
                if (key==(b->data))
                        return b;
                b=b->next;
        }
        return NULL;
}

 위의 함수는 앞의 예와는 달리 원하는 값을 검색하지 못했을 경우 NULL값을 반환하게 된다는
것에 주의하기 바란다. 리스트 4의 예에서는 해싱이 사용된 경우는 한번의 해싱으로 검색할 대상
을 1/5로  줄여놓았다.