[C] Hash Table 구현

lookup() 함수가 search 및 create를 동시에 수행. search하는 동작을 각 함수에서 두번할필요없이 하나로 가능. hash collision을 위해 linked list 로 chainnig 구현

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

#define HSIZE 11

struct element {
        int val;
        char *name;
        struct element *next;
};
struct element *table[HSIZE];

/* 리턴값이 unsigned int 중요. */
unsigned int hash(char *str)
{
        unsigned long long hval = 0;
        unsigned char *s = (unsigned char *)str;
        for (; *s != '\0'; s++)
                hval = hval * 31 + *s; 
        /*  
        while (*str != '\0')
                hval = hval * 31 + *str++;
        */
        return hval % HSIZE;
}

/* search and create an elelment in hash table */
struct element *lookup(char *name, int val, int create)
{
        struct element *node;
        unsigned int hashval = hash(name);
        for (node = table[hashval]; node != NULL; node = node->next)
                if (!strcmp(node->name, name))
                        return node;

        if (create) {
                node = (struct element*)malloc(sizeof(struct element));
                node->name = name;
                node->val = val;
                node->next = table[hashval];
                table[hashval] = node; /* add at the 1st position */
        }   
        return node;
}

int main(int argc, char *argv[])
{

        lookup("o", 1, 1); 
        lookup("bb", 22, 1); 
        lookup("xx", 99, 1); 
        lookup("ee", 2, 1); 
        lookup("jj", 2, 1); 
        lookup("jihun", 87, 1); 
        lookup("kim", 7, 1); 
        lookup("kernel", 30, 1); 
        lookup("kernel", 31, 1); 
    
        printf("%d\n", lookup("bb", 0, 0)->val);
        printf("%d\n", lookup("xx", 0, 0)->val);
        printf("%d\n", lookup("o", 0, 0)->val);
        printf("%d\n", lookup("jj", 0, 0)->val);
        printf("%d\n", lookup("jihun", 0, 0)->val);
        return 0;
}