해싱(hashing).2

앞에서 선형구조법으로 구현한 해싱을 알아보았다면 여기서는 선형구조법의 취약점을 보완한 이차조사법, 이중해싱법, 체인법을 알아보자!!

1. 이차조사법

: 이차 조사법은 선형구조법과는 다르게 충돌이 일어나면

(h(k) + i*i) mod M  for  i = 0,1, ... , M-1

이런 식으로 인덱스를 결정한다.

이 방법은 선형 조사법에서의 문제점인 군집화 현상을 크게 줄일 수 있다. 이 방법도 2차 집중 문제를 일으킬 수 있지만 1차 집중처럼 심각한 것은 아니다. 2차 집중의 이유는 동일한 위치로 사상되는 여러 탐색키들이 같은 순서에 의하여 빈 버켓을 조사하기 때문이다. 그건 이중 해싱법 으로 해결할 수 있다.

2.이중해싱법

: 이중해싱법 또는 재해싱은 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와다른 별개의 해시 함수를 이용하는 방법이다.이 방법은 항목들을 해시 테이블에 보다 균일하게 분포시킬 수 있으므로 효과적인 방법이라 할 수 있다.이중 해싱법에서는 탐색키를 참조하여 더해지는 값이 결정된다. 따라서 해시함수 값이 같더라도 탐색키가 다르면서로 다른 조사 순서를 갖는다. 따라서 이중해싱법은 이차 집중을 피할 수 있다.

예시코드 :

#include <stdio.h>
int i,k,n=8;
int doublehash(int key)
{
    if(key>20) return 4;
    else return 5;
}
int hash(int key)
{
    return key%n;
}
int main()
{
    int key;
    int list[8]={0,0,10,3,2,5,0,0};
    scanf("%d",&key);
    int index=hash(key);
    while(1)
    {
        if(list[index]==0)
        {
            list[index]=key;
            break;
        }
        else
        {
            k++;
            index=(hash(key)+doublehash(key)*k)%n;
        }
    }
    printf("%d",index);
    return 0;
}

3. 체인법

:하나의 인덱스에 여러 개의 키를 저장할 수 있도록 하는 방법이다. 인덱스은 여러 가지 방법으로 구현될 수 있겠지만 주로 연결 리스트로 구현한다. 이와 같은 오버플로우 해결 방법을 체인법ㅂ 이라고 한다.
이는 성능으로 따지면 효율적이지만 링크 공간에 필드가 필요해 공간적으로는 자리차지를 많이 한다.