C언어로 만든 Hash Table

C언어로 만든 Hash Table 이다.

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

#define MAX_ITEM_NAME_LEN 3
#define Max_Hash_Slot 2

typedef struct ItemTotal {
    char name[MAX_ITEM_NAME_LEN];
    int total;
    struct ItemTotal* next;
} ItemTotal;

int hash(char* str) {
    // Hash function taken from https://stackoverflow.com/a/7666577
    unsigned long hash = 5381;
    int c;

    while ((c = *str++) != '\0')
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash % Max_Hash_Slot;
}

int addItemTotal(ItemTotal** head, char* name, int total) {
    int idx = hash(name);
    ItemTotal* cur = head[idx];

    while (cur != NULL) {
        if (strcmp(cur->name, name) == 0) {
            cur->total += total;
            return 0; //return success
        }
        cur = cur->next;
    }

    ItemTotal* newTotal = (ItemTotal*)malloc(sizeof(ItemTotal));
    if (!newTotal) {
        fprintf(stderr, "Error: Cannot allocate memory for new item total\n");
        return 1; //return failure
    }

    strncpy(newTotal->name, name, MAX_ITEM_NAME_LEN);
    newTotal->total = total;
    newTotal->next = head[idx];
    head[idx] = newTotal;
    return 0; //return success
}

void printItemTotals(ItemTotal** head) {
    for (int i = 0; i < Max_Hash_Slot; i++) {
        ItemTotal* cur = head[i];
        while (cur != NULL) {
            printf("%s %d\n", cur->name, cur->total);
            cur = cur->next;
        }
    }
}

void free_hash_map(ItemTotal** hash_map) {
    for (int i = 0; i < Max_Hash_Slot; i++) {
        ItemTotal* current = hash_map[i];
        while (current != NULL) {
            ItemTotal* temp = current;
            current = current->next;
            free(temp);
        }
    }
    //free(hash_map);
}

int main() {
    ItemTotal* itemTotals[Max_Hash_Slot] = {NULL};
    char itemName[MAX_ITEM_NAME_LEN];
    int itemValue;

    char str[][4]={
      "a 1",
      "b 2",
      "a 3",
      "k 4",
      "a 5",
      "p 6",
      "k 7",
      "a 8",
      "k 1",
      "p 1"
    };
    
    int rowCnt =sizeof(str)/sizeof(str[0]);
    int i=0;
    
    for (i=0; 
              i< rowCnt && 
              sscanf(str[i], "%s %d", itemName, &itemValue) == 2; 
              i++) {
                
        addItemTotal(itemTotals, itemName, itemValue);
       
      
    }
    
    //while (scanf("%s%d", itemName, &itemValue) == 2) {
    //    addItemTotal(itemTotals, itemName, itemValue);
    //}
    
    //printItemTotals(itemTotals);

    free_hash_map( itemTotals );
    
    return 0;
}

과일을 코드(a= apple, b=banana, k=kiwi, p=papaya)로 나타내고, 수량을 Hash Table을 써서 집계한는 프로그램이다.

출력 결과는 아래와 같다.  Hash Table 특성상 정렬은 되어 있지 않다.

위의에서는 코드는 MAX_ITEM_NAME_LEN와 Max_Hash_Slot을 너무 작게 해놓았다. 그래도 결과는 나오지만 Hash Table은 Table Slot의 크기를 크게하는 것이 효율적일 것이다.(메모리는 많이 차지한다.)

 

좀 크게 하면 아래와 같이 바꾸는 것도 좋을 것 같다.

#define MAX_ITEM_NAME_LEN 50
#define Max_Hash_Slot 100

 

굉장희 크게 하면 아래와 같은데, 이 경우에는 Memory Leakage에 대해서도 대비를 해야 할 것 같다.

#define MAX_ITEM_NAME_LEN 512
#define Max_Hash_Slot 65536