0x06.탐색 알고리즘(4):해쉬법

4. 해시법

이 방식은 기존의 탐색 알고리즘들과 전혀 다르게 설계되는데, 가장 빠른 속도의 알고리즘이라고 불리기도 한다. 앞서 포스팅한 알고리즘들은 키 값의 지속적인 비교를 통해 탐색 범위를 좁히는 방식이다. 비교라는 것을 잘 생각해보면 범위를 정확히 반으로 줄일 때 가장 효율이 좋다. 하지만 범위를 모호하게 비교해버리면 생각했던 것보다 많은 시간이 소요될 수 있다는 단점이 있다. 해시법은 그 전 방식들과 다르게 직설적이다.

키 값을 1에서 10까지 한정했다고 가정해보자. 가장 빠른 탐색 방법은 1부터 10을 첨자로 하는 배열을 만들어 바로 그 값을 참조하는 것이다. 물론 한정된 범위내에서만 사용이 가능하지만, 조금만 손을 봐주면 충분히 활용할 수 있다.

해시법은 키 값을 파라미터로 사용하는데, 어떤 함수를 사용해 그 값을 계산한다. 이 후, 함수의 결과값을 첨자로 이용하여 배열을 참조한다. 여기서 짚고 넘어갈 부분은 함수는 같은 키 값이 주어졌을 때 결과가 항상 같다는 것이다. 이 말은, 삽입이나 탐색을 할 때, 함수를 활용하면 배열의 같은 장소를 오차없이 참조할 수 있다는 뜻이다. 이 경우에 함수를 해시함수라고 하고, 데이터를 기억하는 배열을 해시표라고 한다.

5, 13, 18, 21, 29, 34, 41이라는 값을 테이블에 저장할 것이다.자! 다음과 같이 테이블이 있다고 가정해보자.

처음에는 테이블이 다음과 같이 비어있다. 사용할 해시함수는 테이블의 크기인 9로 나눈 나머지를 계산하는 mod를 사용할 것이다.

5부터 13, 18, 21이 순차적으로 해시함수를 통해 계산이 되고 나머지 값이 테이블에 아래와 같이 저장될 것이다.

34까지는 순조롭게 계산값을 토대로 테이블에 저장이 되었지만 마지막 값인 41에서 문제가 발생하였다. 5번값에 저장되어야 할 값이 2개가 되어 버린 것이다. 이렇게 해시함수의 값이 겹치게 되는 경우를 충돌이라고 하고, 같은 해시값을 가지는 키들을 동족(동의어)이라고 한다. 즉, 예제의 5와 41은 동의어이다.

다음과 같이 충돌이 생기면 데이터를 삽입하기 위해 빈 곳을 발견할 때까지 다른 칸(번지)를 찾아다니게 되는데, 충돌이 발생할시에 비어있는지 조사하게 되는 대체 칸(번지)의 열을 번지 계열이라고 한다. 

여기서의 테이블의 크기는 9이고, 키 값에 대한 대체 번지를 [K+2i]mod9(i=1,2,...) 수식을 사용해 구한다고 가정하면, 41의 번지 계열은 43mod9, 45mod9, 47mod9 ... 순이 되며 해당되는 칸은 7, 0, 2 ... 순으로 탐색이 된다. 결론적으로 5번째 시도에 51mod9의 결과로 6번째 칸에 저장이 된다.

번지 계열이 같음으로써 충돌이 일어나는 경우가 있는데 이러한 것을 클러스터(cluster)라고 한다. 이것은 레코드 저장시와 탐색시에 처리 효율을 저하시키는 원인이 된다.

동의어가 많다는 것은 충돌이 많이 발생한다는 것이고, 번지 계열의 계산을 많이 한다는 것으로, 그로 인해 더 많은 충돌이 발생할 수 있음을 의미한다. 그래서 해시 함수를 잘 구현하는 경우에만 탐색 속도가 줄어든다.

해시 함수는 여러 가지 키 값을 최대한 겹치지 않게 하는 것이 중요한데, 이는 같은 확률로 각 값을 가지게 하면 된다.

아래는 키가 양의 정수인 경우에 사용되는 해시함수 변환법이다

ⓐ 제산법(division method)

키를 어떤 양의 정수(일반적으로 테이블 크기보다 작은 가장 큰 소수)로 나눈 나머지를 그 키의 레코드를 저장하는 주소를 사용하는 방법

eg) 키 값이 198731이고 테이블의 크기가 7000일 때, 소수인 6997을 사용하여 198731/7000의 나머지 값인 2731이 주소값이 됨

ⓑ 제곱법(mid-square method)

키를 제곱해서 값의 중간 부분에 있는 값을 택해서 번지로 하는 방법

eg) 키 값이 198731일 때, 198731*198731=39494010361, 가운데 자리인 401이 주소값이 됨

ⓒ 접는법(folding method)

키를 여러부분으로 나눈 뒤, 각 부분의 값을 더해서 주소값을 계산하는 방법으로 세부적으로 이동 접지와 경계 접지로 나눌 수 있음

㈀ 이동 접지 : 각 부분의 오른쪽 끝을 맞춰서 더하는 방법

㈁ 경계 접지 : 하나 건너뛴 값을 역으로 나열해서 더하는 방법

135 205 243 68 2 

   이동 접지                                  경계 접지

       135                                                    135

       205                                                    502

       343                                                    343

        68                                                      86

     +   2                                                    +  2

    --------                                                 -------

       753                                                   1068

ⓓ 숫자 해석법(digit analysis method)

키에서 중복된 부분 또는 불필요한 부분을 제거하여 번지를 만드는 방법으로 테이블의 키를 모두 알고 있을 시 사용 가능한 방법

888 - 48 - 4523

888 - 51 - 1326

888 - 75 - 5432

888 - 06 - 3621

888 - 15 - 0751 

모든 키의 앞은 888로 동일하기에 비교시 생략할 수 있다. 888을 제외하면 6자리가 남는데, 테이블의 크기가 1000인 경우, 3자리만 있으면 되기에 중간 값 2자리를 우선적으로 제외한다. 마지막 4자리의 숫자값 중에서 3번째 자리의 값이 대부분 2인걸로 보아 3번째 칸을 제외시키면 453, 136, 542, 361, 071과 같이 서로다른 주소값을 얻을 수 있다.

⑴ 연쇄법

해시함수의 충돌을 완전히 피하기는 무척 어렵다. 그런 경우에 같은 해시값을 가진 데이터들을 연결 리스트 방식으로 연결함으로써 대처할 수 있다. 해시표의 각 요소들이 같은 해시값을 가진 데이터들의 연결값의 헤더를 가리키는 포인터를 넣는다. 각 리스트를 순차적으로 앞에서부터 비교하면서 탐색을 하는데 이 방법을 연쇄법이라고 한다.

위 그림에서 8을 탐색하기 위해서는 해시함수의 결과 값으로 리스트의 첫 번째 칸인 0을 얻은 뒤에 리스트의 포인터를 순차적으로 참조하여 찾는 과정을 거치게 된다.

참고로 연쇄법은 두 가지로 나눠지는데, 위와 같이 같은 해시 값을 가지는 데이터끼리만 리스트를 구성하는 방법을 분리 연쇄법이라고 하고, 해시 값을 여부와 상관없이 같은 리스트를 구성하는 방식을 분제 연쇄법이라고 한다.

연쇄법에 필요한 변수 선언은 아래와 같다.

typedef struct chain_node *list;

list hashtable[m];

① 탐색 알고리즘

void search(keytype *target, boolean *found, list *p){

   *p=hashtable[hash(*traget)];

   *found=false;

   while(*p!=NULL&&!(*found)){

       if(*target==p->key)

          *found=true;

       else

          *p=p->next;

   }

}

② 삽입 알고리즘

void insert(keytype x, othertype y){

   index h;

   list p;

   h=hash(x);

   new(p);

   p->key=x;

   p->otherinfo=y;

   p->next=hashtable[h];

   hashtable[h]=p;

}

⑵ 개방 번지법

연쇄법과 달리 해시표 그 자체에 값을 넣는 방식을 개방 번지법이라고 한다. 해시함수의 결과값이 가리키는 장소를 조사하여 값이 저장되어 있지 않으면 그 위치에 값을 쓰고, 값이 저장되어 있으면 다른 장소를 탐색하여 값을 쓴다. 여기서 말하는 다른 장소는 정해진 알고리즘에 따라 정해지는 것으로, 항상 같은 절차대로 정해지는 장소를 뜻한다.

기본 변수 선언은 다음과 같다.

#define free 0

#define used 1

struct chain_node{

   keytype key;

   othertype otherinfo;

   int mark;

}

typedef struct chain_node *list;

list hashtable[m]; 

다음에 조사할 장소를 찾는 방법으로 선형탐색을 사용하겠다. 첨자를 하나씩 늘려가며 조사하는 방식이다. 위에서의 변수 free는 저장가능한 장소를, used는 이미 사용중인 장소를 뜻한다. 또한 m은 해시표의 크기, n은 데이터의 수를 뜻한다.

① 삽입 알고리즘

void insert(keytype x, othertype y){

   index h;

   if(n>=m-1) error_routine();

   h=hash(x);

   while(hashtable[h].mark==used){

       if(x==hashtable[h].key)

          error_routine;

       h=(h+2)%m;

    }

   hashtable[h].mark=used;

   hashtable[h].key=x;

   hashtable[h].otherinfo=y;

   n++;

}

간단한 식이어서 아래의 그림으로 설명을 대신하겠다.

② 탐색 알고리즘

search(keytype target, boolean *found, index *pos){

   *pos=hash(target);

   while(hashtable[*pos].mark==used&&target!=hashtable[*pos].key){

       *pos=(*pos+1)%m;

       h=(h+1)%m;

   }

   *found=(hashtable[*pos].mark==used) ? true:false;

}