c언어 해시 테이블(Hash table)의 적당한 테이블 사이즈 구하는 방법

해시 테이블(Hash table)을 사용 하다 보면 충돌이 빈번하게 발생하게 되는데

테이블의 사이즈만 잘 구하더라도 충돌을 최소화 하여 테이블을 효율적으로 사용 할 수 있습니다. 

방법 

2의 제곱수에서 가장 거리가 먼 소수를 이용하여 테이블 크기를 구하면 됩니다. 

소스 코드

#include <stdio.h>
 
int primeNumArr[10000];
int cur = 0;
// 소수 구하기
void makePrimeNum() {
    primeNumArr[cur++] = 1;
    int j;
    for (int i = 1; i < 100000; i++) {
        for (j = 2; j <= i; j++) {
            if (i % j == 0) {
                break;
            }
        }
        if (i == j) {
            primeNumArr[cur++] = i;
        }
    }
    printf("primeNumArr size : %d \n", cur);
}
 
// 2의 제곱 구하기
int exponentiation(int num) {
    int value = 2;
    for (int i = 0; i < num-1; i++) {
        value *= 2;
    }
    return value;
}
 
int main() {
    makePrimeNum();
 
    for (int i = 3; i < 15; i++) {
        int num1 = exponentiation(i);
        int num2 = exponentiation(i+1);
        
        int num3 = num1 + (num1 / 2);
        int tableSize;
        for (int j = 0; j <= cur; j++) {
            if (num3 < primeNumArr[j]) {
                tableSize = primeNumArr[j];
                break;
            }
        }
        printf("2의%d승 / 2의%d승 사이의 테이블 크기 : %d \n", i, i + 1, tableSize);
    }
    return 0;
}

출력

출력 값으로 테이블의 크기로 잡고 사용 해보면 충돌을 최소화 하여 사용 할 수 있습니다. 

물론 해시 테이블에 들어가는 Key값에 따라서 달라질 수 도 있겠지만,

문자열을 자릿수를 접어서 키를 사용하는 경우에는 충돌이 최소화 됩니다. 

(문자열 자릿수 접는 것 : 문자 열의 문자들을 아스키 코드 값으로 변경하여 덧셈 한 것)