개방 주소법은 특정 버킷에서 충돌이 발생하면, 비어있는 버킷을 찾는 방법이다. 이 비어있는 버킷에 항목을 저장하게 된다. 해시테이블에서 비어있는 공간을 찾는 것을 조사라고 합니다.
선형조사법은 처음 충돌이 발생한 곳을 기점으로 비어있는 공간을 계속해서 조사하는 방법입니다. 다시 시작한 지점을 돌아오게 된다면 비어있는 공간이 없다고 판단하게 됩니다.
클러스터링 문제를 앓고있습니다. 클러스터링 문제는 충돌이 시작한 곳에 집중되게 하는 현상으로 탐색 효율성을 저하시킵니다.
#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;
}
}
printf("%d",index);
return 0;
}
선형조사법은 1씩 증가했던 것과 달리 이차조사법은 제곱수씩 증가하며 조사하는 방법입니다.
조사되는 위치는 h(k), h(k) + 1, h(k) + 4, h(k) + 9 ..... 이런식으로 됩니다.
이 방법은 선형조사법의 문제점인 클러스터링 문제를 크게 완화시킬 수 있지만 이 방법도 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*k))%n; //제곱수씩 조사할 위치를 찾습니다.![](https://velog.velcdn.com/images/comodoking_0128/post/5bfc0d73-4cd0-45e4-9ebe-e2554ee2c713/image.webp)
}
}
printf("%d",index);
return 0;
}