C语言 实现 HashTable

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
/**----------------------------------------哈希表节点------------------------------------**/
typedef struct _Node {
    char * key;
    int  value;
    int  hash;
    struct _Node * next;
} Node;

Node * initNode(const char * key, int  value, int hash){
    int kLen    = strlen(key);
    Node * in   = (Node *)malloc(sizeof(Node));
    in -> key   = (char *)malloc(sizeof(char) * (kLen + 1));
    strcpy(in -> key, key);
    in -> key[kLen] = ‘\0‘;
    in -> value = value;
    in -> hash  = hash;
    in -> next  = NULL;
    return in;
}
/**----------------------------------------哈希表节点结束------------------------------------**/

unsigned int String_Hash_Code(const char * ch) {
    int i = 0, ans = 0;
    for(i = 0 ; ch[i] != ‘\0‘; ++i) {
        ans = 31 * ans + ch[i];
    }
    return ans;
}

/**----------------------------------------哈希表---------------------------------------**/
typedef  struct _HashTable {
    unsigned int cnt;
    unsigned int tableLength;

    Node ** tables;
    void (*put)(struct _HashTable *this, const char *key, int value);
    int  (*get)(struct _HashTable *this, const char *key);
    void (*destroy)(struct _HashTable *this);
    void (*resize)(struct _HashTable *this);

} HashTable;

void put(HashTable *this, const char *key, int value) {
    int hash = String_Hash_Code(key);
    int pos  = hash & (this -> tableLength - 1);
    Node * head = this -> tables[pos];
    while(head != NULL) {
        if (strcmp(key, head -> key) == 0) {
            head -> value = value;
            return;
        }
        head = head -> next;
    }
    if (this -> cnt  >= (int)(this -> tableLength * 0.75)) {
        this -> resize(this);
        pos  = hash & (this -> tableLength - 1);
    }
    this -> cnt = this -> cnt + 1;
    Node * in = initNode(key, value, hash);
    in -> next  = this -> tables[pos];
    this -> tables[pos] = in;
}

int get(HashTable *this, const char *key) {
    int hash = String_Hash_Code(key);
    int pos  = hash & (this -> tableLength - 1);
    Node * head = this -> tables[pos];
    while(head != NULL) {
        if (strcmp(key, head -> key) == 0) {
            return head -> value;
        }
        head = head -> next;
    }
    return 0;
}
void resize(HashTable *this) {
    int tableLength  =  this -> tableLength << 1;
    int i;
    Node * tmp;
    Node ** tables = (Node **)malloc(sizeof(Node *) * tableLength);
    memset(tables, 0, sizeof(Node *) * tableLength);

    // 拷贝 速度
    for(i = 0; i < this -> tableLength; ++i) {
        Node * head = this -> tables[i];
        while(head != NULL) {
            tmp = head;
            head = head -> next;
            int pos =  tmp -> hash & (tableLength - 1 );
            tmp -> next = tables[pos];
            tables[pos] = tmp;
        }
    }
    // 释放掉以前的内存
    free(this -> tables);
    // 改头换面重新 做人
    this -> tables = tables;
    this -> tableLength = tableLength;
}
// 最后写 这是 C/C++ 语言最恶心的地方,切记
void destroy(HashTable *this) {
    int i = this -> tableLength;
    Node * next;
    for(i = 0; i < this -> tableLength; ++i) {
        Node * now  = this -> tables[i];
        while(now !=NULL) {
            next = now -> next;
            free(now -> key);
            now -> key = NULL;
            now -> next = NULL;
            free(now);
            now = next;
        }
    }
}

HashTable * initTable() {
    HashTable * ans = (HashTable*)malloc(sizeof(HashTable));
    ans -> cnt = 0 ;
    ans -> tableLength = 8;
    ans -> put = put;
    ans -> get = get;
    ans -> destroy = destroy;
    ans -> resize  = resize;
    Node ** tables = (Node **)malloc(sizeof(Node *) * ans -> tableLength);
    memset(tables, 0, sizeof(Node *) * ans -> tableLength);
    ans -> tables = tables;
    return ans;
}
/**----------------------------------------哈希表结束---------------------------------------**/
int main() {
    char a[32][10] = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "0",
                    "11", "12", "13", "14", "15", "16", "17", "18", "19", "20",
                    "21", "22", "23", "24", "25", "26", "27", "28", "29", "30",
                    "31", "32"
            };
    HashTable* table = initTable();
    printf("table size %d, length %d\n", table -> cnt, table -> tableLength);
    for(int i = 0; i < 32; ++i) {
        table -> put(table, a[i], i+10);
        table -> put(table, a[i], i+1);
    }
    for(int i = 0; i < 32; ++i) {
        printf("%s -> %d\n", a[i], table -> get(table, a[i]));
    }
    printf("table size %d, length %d\n", table -> cnt, table -> tableLength);
    table -> destroy(table);
    free(table);
    return 0;
}