[Algorithm] 이중해싱법 Double Hashing

🌟 이중해싱법 Double Hashing

정의:

• 충돌이 ht(k)에서 발생하면, h(key) + 일정값 k, h(key) + 일정값 k+1, ...

• 조사를 시작했던 곳으로 되돌아오면 테이블이 가득 찬 것으로 판단

조사되는 위치

h(k), h(key) + 일정값 k, h(key) + 일정값 k+1, h(key) + 일정값 * k+1, ...

구현:

#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;	// index를 일정치 * k, k를 증가하며 구함
        }
    }
    printf("%d",index);
    return 0;
}

당신의 시간이 헛되지 않는 글이 되겠습니다.
I'll write something that won't waste your time.