해싱은 어떤 요소의 키를 가지고, 요소가 있는 배열의 인덱스 값을 구하는 알고리즘리다.
먼저, 구글에 "해싱" 이라고 겁색 해보면 아래에 있는 그림처럼 나온다.
해싱은 해시함수로 만들어진 해시테이블의 인덱스를 반환해 주는데, 이때 선형 구조법이 사용된다.
만약 0부터 6까지 인덱스가 부여된 7칸짜리 배열이 있다고 가정해보자.
그리고 순서대로 8,1,9,6,13의 위치를 알아보면
밑에 그림과 같은 결과가 나온다.
근데 또 만약에 배열이 가득 찼는데, 배열에 없는 숫자를 해싱하려고 하면 모든 칸마다 충돌이 일어나, 오버플로우가 생긴다.
이를 코드로 나타내면,
#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;
}