이중해싱법 && 체인법

이중해싱법

선형조사법은 클러스터링 문제, 이차조사법은 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;
}

체인법

선형 조사법이 탐색 시간이 많이 걸리는 이유는 충돌 때문에 해시 주소가 다른 키하고도 비교를 해야 하는데 있습니다. 만약 해시 주소가 같은 키만을 하나의 리스트로 묶어둔다면 불필요한 비교는 하지 않아도 될 것입니다.
이러한 부분 덕분에 체인법은 성능이 좋습니다.
하지만 리스트의 공간이 따로 필요하게 됩니다.