[Algorithm] 선형조사법 Linear Probing

🌟 선형조사법 Linear Probing

정의:

개방 주소법: 충돌이 발생하면, 비어있는 버킷을 찾는 방법

• 충돌이 ht[k]에서 발생하면 다음 인덱스는 ht[k+1], ht[k+2]...

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

조사되는 위치:

h(k), h(k+1) % 해시테이블의 크기, h(k+2) % 해시테이블의 크기, ...

구현:

#include <stdio.h>
int i,k,n=8;
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)+k)%n;	// index를 key에서 하나씩 증가하며 구함
        }
    }
    printf("%d",index);
    return 0;
}

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