C언어 해시테이블 구현

1 개요

C언어 해시 구현

C언어 해시 테이블 구현

• djb2 해시 구현

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

#define MAX_KEY 64
#define MAX_DATA 128
#define MAX_TABLE 4096

typedef struct {
    char key[MAX_KEY + 1];
    char data[MAX_DATA + 1];
} Hash;
Hash tb[MAX_TABLE];

unsigned long hash(const char *str) {
    unsigned long h = 5381;
    int c;
    while ((c = *str++)) {
        h = (((h << 5) + h) + c) % MAX_TABLE;
    }
    return h % MAX_TABLE;
}

int add(const char *key, char *data) {
    unsigned long h = hash(key);
    while (tb[h].key[0]) {
        if (strcmp(tb[h].key, key) == 0) {
            return 0;
        }
        h = (h + 1) % MAX_TABLE;
    }
    strcpy(tb[h].key, key);
    strcpy(tb[h].data, data);
    return 1;
}

int find(const char *key, char *data) {
    unsigned long h = hash(key);
    int cnt = MAX_TABLE;
    while (tb[h].key[0] && cnt--) {
        if (strcmp(tb[h].key, key) == 0) {
            strcpy(data, tb[h].data);
            return 1;
        }
        h = (h + 1) % MAX_TABLE;
    }
    return 0;
}

void printDataForKey(const char *key) {
    char d[MAX_DATA + 1];
    int found = find(key, d);
    if (!found) {
        printf("not found\n", key);
        return;
    }
    printf("%s\n", d);
}

int main() {
    memset(tb, 0, sizeof(tb));

    add("John Smith", "521-8976");
    add("Lisa Smith", "521-1234");
    add("Sandra Dee", "521-9655");
    
    printDataForKey("John Smith"); // 521-8976
    printDataForKey("Lisa Smith"); // 521-1234
    printDataForKey("Sam Doe");    // not found
    printDataForKey("Sandra Dee"); // 521-9655
    printDataForKey("Ted Baker");  // not found
}

2 같이 보기

• 해시 테이블
• C언어 맵 구현
• C언어 트리 구현
• C언어 우선순위큐 구현
• C++ map