간단한 String Hash 구현

다른 곳에 있는 코드를 가져옴~!

hashtable에 값을 넣을 때, hash value가 충돌난 경우, 

현재 hash값에 있는 구조체를 node의 다음으로 연결한 후,

hashtable에 node 넣는 것을 잊지 말자. 

        // 현재 hash값에 있는 구조체는 다음(뒤)으로 연결!!!

        node->next = hashtable[hashval];

        // hashtable에 값 입력

        hashtable[hashval] = node;

#include <iostream>
 
using namespace std;
#define HASHSIZE 16
 
typedef struct LinkedList nlist;
struct LinkedList {
    LinkedList * next;
    char* key;
    char* val;
};
nlist *hashtable[HASHSIZE];
 
unsigned hashing(char* key) {
    unsigned hashval = 0;
    for (; *key != '\0'; key++) {
        hashval = *key + hashval * 31;
    }
    return hashval % HASHSIZE;    //hashtable안에 들어갈 index 
}
bool isSame(char* a, char *b) {
    int i = 0;
    while (a[i] != '\0') {
        if (a[i] != b[i])
            return false;
        i++;
    }
    if (b[i] != '\0')
        return false;
    return true;
}
nlist* lookup(char* key) {
    nlist *node;
    for (node = hashtable[hashing(key)]; node != NULL; node=node->next) {
        if (isSame(node->key, key))
            return node;
    }
    return NULL;
     
}
char* strcpy(char *a) {
    char* newStr;
    newStr = (char*)malloc(sizeof(a)/sizeof(char) +1);
    int i = 0;
    while (a[i] != '\0') {
        newStr[i] = a[i];
        i++;
    }
    newStr[i] = '\0';
    return newStr;
}
void storeTohash(char* key, char* val) {
    nlist *node;
    unsigned hashval;
 
    if ((node = lookup(key)) == NULL) {//hash 입력
        node = (nlist*)malloc(sizeof(*node));
        if (node == NULL || key == NULL)
            return;
        node->key = strcpy(key);
        hashval = hashing(key);
 
        /* 아래 두 라인의 순서가 바뀌면 안된다!!! */
        // 현재 hash값에 있는 구조체는 다음(뒤)으로 연결!!!
        node->next = hashtable[hashval];
        // hashtable에 값 입력
        hashtable[hashval] = node;
    }
    else {
        ;
    }
    if (val == NULL)
        return;
    node->val = strcpy(val);
}
 
int main() {
    char *name[] = { "John Smith", "Lisa Smith", "Sam Doe", "Sandra Dee", "Ted Baker", "James Dean" };
    char *phone[] = { "521-1234", "521-8976", "521-5030", "521-9655", "418-4165", "425-1020" };
    int n = sizeof(name) / sizeof(name[0]);
    for (int i = 0; i < n; i++) {
        cout << hashing(name[i]) << " : " << name[i] << endl;
        storeTohash(name[i], phone[i]);
    }
    cout << "** Hash Table List **" << endl;
    nlist *head, *ptr;
    for (int i = 0; i < HASHSIZE; i++) {
        head = hashtable[i];
        for (ptr = head; ptr != NULL; ptr = ptr->next) {
            cout << i << ": " << ptr->key << " , " << ptr->val << endl;
        }
    }
    cout << "** Hash Table Search ** " << endl;
    ptr = lookup("Ted Baker");
    cout << "Found: " << ptr->key << ": " << ptr->val << endl;
    return 0;
}