[면접 대비] C를 사용한 해시 맵 구현

size_t hash_65599(const char* string, size_t len)
{
    size_t i;
    size_t hash;

    hash = 0;
    for(i = 0; i < len; ++i){
        hash = 65599 * hash + string[i];
    }

    return hash ^ (hash >> 16);
}

충돌까지 고려한 해시 맵 예

int add(const char* key, int value, size_t (*hash_func)(const char*, size_t))
{  
    size_t i;
    size_t start_index;
    size_t hash_id;

    hash_id = hash_func(key, strlen(key));
    start_index = hash_id % BUCKET_SIZE;
    i = start_index;

    do{
        if(s_keys[i] == NULL){
            // 새 키-값을 삽입
            return TRUE
        }
        if(strcmp(s_key[i], key) == 0){
            return TRUE;
        }
        i = (i+1) % BUCKET_SIZE;
    } while(i != start_index);
    return FALSE;
}

충돌이 없을 때 해시 맵 예

int add_fast(size_t hash_key, const char* value)
{
    size_t i;
    size_t start_index;

    start_index = hash_key % BUCKET_SIZE;
    i = start_index;

    do{
        if(s_keys[i] == INT_MIN){
            // 새 키-값을 삽입
            return TRUE
        }
        if(s_keys[i] == hash_key){
            retunr TRUE;
        }
        i = (i+1) % BUCKET_SIZE;
    } while(i != start_index);
    return FALSE;
}

여러 데이터형과 해시 함수

hash_function.c

#include <stddef.h>
#include "hash_function.h"

size_t hash_int(int value)
{
    return value;
}

size_t hash_float(float value)
{
    return *((size_t*)&value);
}

size_t hash_data(const void* data, size_t length)
{
    const char* p;
    size_t i;
    size_t hash;

    p = data;
    hash = 0;
    for(i = 0; i<length; ++i){
        hash = 65599 * hash + *p++;
    }

    return hash ^ (hash >> 16);
}

main.c

#include <stdio.h>
#include <string.h>

#include "hash_function.h"

typedef struct{
    unsigned char age;
    unsigned int id;
    char name[64];
} employee_t;

int main(void)
{
    employee_t person;
    size_t hash;
    float fvalue;

    hash = hash_int(10);
    printf("int        %u\n", hash);

    hash = hash_int(-10);
    printf("int        %u\n", hash);

    hash = hash_int('A');
    printf("char    %u\n", hash);

    hash = hash_float(3.2f);
    printf("flaot    %u\n", hash);

    hash = hash_data("Pope Kim", strlen("Pope Kim"));
    printf("string    %u\n", hash);

    fvalue = 3.2f;
    hash = hash_data(&fvalue, sizeof(float));
    printf("float    %u\n", hash);

    memset(&person, 0, sizeof(employee_t));
    person.age = 23;
    person.id = 183213;
    strcpy(person.name, "Pope Kim");

    hash = hash_data(&person, sizeof(employee_t));
    printf("struct    %u\n", hash);

    return 0;
}