해싱 필요한 이유 - 기본 개념

해싱이라는 것은 기본적으로 흩어뜨려 놓는다는 뜻입니다.

자료를 흩어놓음으로써 메모리는 더 많이 차지하지만 더 빨리 찾을 수 있지요.

예를 들어 100개의 자료가 있고 그 중에서 어떤 한 개의 자료를 찾는다고 할 때

최대 100번까지 찾아봐야 합니다.

하지만 해싱을 이용한다면 최대 10이나 5번만에도 자료를 찾을 수 있습니다.

메모리를 많이 사용하면 많이 사용할 수록 빨리 찾을 수 있지요.

예를 들어 번호로 이름을 찾는 경우를 생각해 보지요.

struct data {

    int              number;

    char          name[128];

    char          *next;

}

와 같은 구조체가 있다고 했을 때 해싱을 사용하지 않으면 다음과 같이 구현되지요.

struct data *head;

int add_nohash(int number,char *name)

{

    struct data *tmp;

    tmp = (struct data*)malloc(sizeof(struct data));

    if( tmp == NULL ) return -1;

    tmp->number = number;

    strcpy(tmp->name,name);

    tmp->next = head;

    head = tmp;

}

char *find_nohash(int number)

{

    struct data *tmp = head;

    while( tmp ) {

          if( tmp->number == number ) return tmp->name;

          tmp = tmp->next;

    }

     return NULL;

}

find()함수를 보시면 아시겠지만 데이터가 100개 있다면

최악의 경우 100번 루프를 돌아야지만 원하는 정보를 찾을 수 있습니다.

위의 함수를 해싱을 사용하여 구현하면 다음과 같습니다.

struct data *hash[10];

int add_hash(int number,char *name)

{

    int index;

    struct data *tmp;

    index = number % 10;

    tmp = (struct data*)malloc(sizeof(struct data));

    if( tmp == NULL ) return -1;

    tmp->number = number;

    strcpy(tmp->name,name);

    tmp->next = hash[index];

    hash[index] = tmp;

}

char *find_hash(int number)

{

    int index = number % 10;

    struct data *tmp;

    tmp = hash[index];

    while( tmp ) {

          if( tmp->number == number ) return tmp->name;

          tmp = tmp->next;

    }

     return NULL;

}

각각의 함수를 비교해 보시면 아시겠지만

add_nohash에서는 하나의 리스트로 데이터를 관리하는데 비해서

add_hash에서는 10개의 리스트로 데이터를 관리하게 됩니다.

한 마디로 데이터를 흩어뜨려 놓는 것이지요..

10개의 리스트로 데이터가 흩어지기 때문에 찾는 횟수도 그만큼 줄게 됩니다.

대신 hash를 사용하지 않을 때는 head라는 변수만 필요했는데

hash를 사용함으로서 head보다 10배가 큰 hash[]라는 변수를 사용해야 하지요..

이해를 돕기 위하여 다음과 같은 데이터가 있다고 합시다.

번호             이름

101              김일동

302              김이동

303              김삼동

104              김사동

304              김오동

202              김육동

해쉬를 사용하지 않는 경우 데이터 구조는 아래와 같습니다.

head : 101->302->303->104->304->202

이때 304번에 대한 이름을 찾기 위해서는 5번 비교를 해야 합니다.

해쉬를 사용하는 경우 데이터 구조는 아래와 같습니다.

hash[1] : 101

hash[2] : 302->202

hash[3] : 303

hash[4] : 104->304

이 때 304번을 찾으려면 304를 10으로 나누고 그 나머지인 4에 대한 리스트

hash[4]에서 찾으면 되지요. 이때는 2번만에 찾을 수 있습니다.

이것이 hash를 사용하는 이유입니다.