해싱- 선형/이차/이중 해싱법 구현, 비교

해싱에서 충돌을 회피하는 방식에는 크게 선형조사법, 이차조사법, 이중 해싱법이 있다.

공부하면서 이 방법들에 대해서 좀더 이해하고 실제로 결과물이 어떻게 되는지를 보기 위해 직접 구현해봤다.

우선은 구현한 소스코드를 먼저 공개한다.

#include<time.h>
#include <stdio_ext.h>
#include <sys time.h>

#define TABLE_SIZE 9973
#define INPUT_SIZE 8000
#define DOUBLE_HASH_NUM 9013

int crash = 0;

int linear_probing(int* hash, int input){
        int i;
        int j = 0;
        i = input % TABLE_SIZE;

        while (1){
                if (hash[(i + j)%TABLE_SIZE] == 0){
                        return (i + j)%TABLE_SIZE;
                }
                j++;
                crash++;
        }

}


int quadratic_probing(int* hash, int input){
        int i;
        int j = 0;
        i = input % TABLE_SIZE;

        while (1){
                if (hash[(i + j * j)%TABLE_SIZE] == 0){
                        return (i + j * j)%TABLE_SIZE;
                }
                j++;
                crash++;
        }

}


int double_hashing(int* hash, int input){
        int i;
        int j = 0;
        int step;
        step = DOUBLE_HASH_NUM - input % DOUBLE_HASH_NUM; //h`()
        i = input % TABLE_SIZE;

        if (hash[i] == 0){
                return i;
        }

        else{
                while (1){
                        crash++;
                        j++;
                        if (hash[(i + j*step)%TABLE_SIZE] == 0){
                                return (i + j * step)%TABLE_SIZE;
                        }
                }
        }

}


main(){
        int hash[TABLE_SIZE];
        int input[INPUT_SIZE];
        int i;
        double timechk;
        struct timeval start, end;

        while (1){
                timechk = 0;
                char ch;

                printf("linear(l), quadratic(q), double hashing(d):");
                scanf("%c", &ch);


        int i;
        double timechk;
        struct timeval start, end;

        while (1){
                timechk = 0;
                char ch;

                printf("linear(l), quadratic(q), double hashing(d):");
                scanf("%c", &ch);


                srand(time(NULL));
                for (i = 0; i < INPUT_SIZE; i++){ //input을 초기화
                        input[i] = rand() % 100000 + 1; //1~100000까지의 숫자
                }
                for (i = 0; i < TABLE_SIZE; i++){
                        hash[i] = 0;
                }
                crash = 0;

                if (ch == 'l'){ //linear probing
                        printf("linear probing\n");
                        for (i = 0; i < INPUT_SIZE; i++){
                                int index;
                                index = linear_probing(hash, input[i]);
                                hash[index] = input[i];
                        }
                }


                if (ch == 'q'){
                        printf("quadratic probing\n");
                        for (i = 0; i < INPUT_SIZE; i++){
                                int index;
                                index = quadratic_probing(hash, input[i]);
                                hash[index] = input[i];
                        }
                }

                if (ch == 'd'){
                        printf("double hashing\n");
                        for (i = 0; i < INPUT_SIZE; i++){
                                int index;
                                index = double_hashing(hash, input[i]);
                                hash[index] = input[i];
                        }
                }

                gettimeofday(&end, NULL);
                timechk = (double)(end.tv_sec) + (double)(end.tv_usec) / 1000000.0 - (double)(start.tv_sec) - (double)(start.tv_usec) / 1000000.0;
                printf("충돌수: %d\n", crash);
                printf("시간: %f초\n", timechk);
                __fpurge(stdin);


        }

}

C언어는 어떻게 발악을 해도 항상 코드가 더러워진다... 간단한 내용도 필연적으로 길어지는듯. while(1) 안쪽에도 스위치 케이스 문을 썼으면 더 깔끔햇을텐데... 되는대로 하다보니 이미 늦었다. 어쨋든 잘 작동하니까 됐다.

워낙 유명한 알고리즘이라 딱히 주석을 넣을 필요성도 느끼지 못했다.

약간의 설명만 추가하자면 9973이라는 10000에 아주 가까운 소수개의 테이블을 가진 해시에 mod 연산 결과에 따라서 데이터를 집어넣는 시뮬레이션이다. 데이터는 랜덤값으로 만들어줬고, 이중해싱은 테이블 사이즈보다 약간 작은 소수인 9013을 사용했다.

우선 전체 테이블 사이즈의 약 80%정도인 8000개의 인풋을 넣는 시뮬레이션이다. 코드 윗쪽의 INPUT_SIZE를 8000으로 맞춰줬다.

결과는 역시 선형조사법이 가장 안좋다. 충돌수도 압도적으로 높고 시간도 가장 길었다.

특이한 점이 이중 해싱 방식이 충돌은 더 많이 일어났는데도 총 시간은 더 적게 걸렸다. 원래 그런거 같긴 한데 어쩌면 내가 구현하는 방식이 잘못되서 그런걸지도.

다음으로 테이블 사이즈의 60%정도가 찬다고 가정하고 INPUT_SIZE를 6000개정도로 줘봤다.

크게 다르지는 않은데 특이하게 이중해싱법의 충돌수가 선형조사법을 넘어섰다. 그럼에도 여전히 총 시간은 가장 적다.

다음으로 약 40%인 4000을 INPUT_SIZE로 주었다.

위 결과와 거의 비슷했다. 특이한 점은 없음.

이렇게 한번 충돌방지법들을 실제로 구현해보고 성능을 비교해보았다. 다음에는 체이닝 기법도 한번 구현해 봐야겠다.