Hash表 数据结构

Hash 表
key: value
key 保存信息的唯一标识
将char*类型的key转化为int型作为寻找信息的方式
假设有10000个人, 分成100个表保存信息, 每个表保存100个人

使用Hash算法对key做唯一标识计算

// main.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#include "hashclass.h"int main(int argc, char* argv[]) {HashTab* t1 = createTab(10);insertHashElem(t1, "1", (void*)"河南");insertHashElem(t1, "2", (void*)"北京");insertHashElem(t1, "3", (void*)"天津");insertHashElem(t1, "13", (void*)"天津");insertHashElem(t1, "23", (void*)"天津");insertHashElem(t1, "33", (void*)"天津");insertHashElem(t1, "43", (void*)"天津");insertHashElem(t1, "4", (void*)"河北");insertHashElem(t1, "5", (void*)"安徽");char* addr = (char*)findHashElem(t1, "1");printf("%s\n", addr);resetHashElem(t1, "2", (void*)"China");addr = (char*)findHashElem(t1, "2");printf("%s\n", addr);deleteHashElem(t1, "23");if (addr = (char*)findHashElem(t1, "23")) {printf("%s\n", addr);}else {printf("没有");}clearHashElemList(t1);printf("%s\n", (char*)findHashElem(t1, "5"));system("pause");return 0;
}

// HashClass.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#include "HashClass.h"#define my_malloc malloc
#define my_free free// 哈希算法
static unsigned int
algorimthHash(const char* key) {register unsigned int h;register unsigned char* p;for (h = 0, p = (unsigned char*)key; *p; p++) {h = (32 << 5)*h + *p;}return h;
}struct HashNode {char* key;void* value;HashNode* next;
};struct HashTab {int group;HashNode** Hash_sets;
};HashTab* createTab(int n) {HashTab* tab = (HashTab*)my_malloc(sizeof(HashTab));memset(tab, 0, sizeof(HashTab));tab->Hash_sets = (HashNode**)my_malloc(sizeof(HashNode*)*n);memset(tab->Hash_sets, 0, sizeof(HashNode*)*n);tab->group = n;return tab;
}void deleteTab(HashTab* tab) {clearHashElemList(tab);if (tab->Hash_sets) {free(tab->Hash_sets);tab->Hash_sets = NULL;}free(tab);
}void insertHashElem(HashTab* tab, const char* key, void* value) {HashNode* node = (HashNode*)my_malloc(sizeof(HashNode));memset(node, 0, sizeof(HashNode));node->key = strdup(key);node->value = value;int g_index = algorimthHash(key) % tab->group;HashNode* head = tab->Hash_sets[g_index];node->next = head;tab->Hash_sets[g_index] = node;
}void resetHashElem(HashTab* tab, const char* key, void* value) {int g_index = algorimthHash(key) % tab->group;HashNode** transNode = &tab->Hash_sets[g_index];while (*transNode) {if (strcmp((*transNode)->key, key) == 0) {(*transNode)->value = value;return;}transNode = &(*transNode)->next;}HashNode* node = (HashNode*)my_malloc(sizeof(HashNode));memset(node, 0, sizeof(HashNode));node->key = strdup(key);node->value = value;*transNode = node;
}void* findHashElem(HashTab* tab, const char* key) {int g_index = algorimthHash(key) % tab->group;HashNode* transNode = tab->Hash_sets[g_index];while (transNode) {if (strcmp(transNode->key, key) == 0) {return transNode->value;}transNode = transNode->next;}return NULL;
}void deleteHashElem(HashTab* tab, const char* key) {int g_index = algorimthHash(key) % tab->group;HashNode** transNode = &tab->Hash_sets[g_index];while (*transNode) {if (strcmp((*transNode)->key, key) == 0) {HashNode* node = *transNode;*transNode = (*transNode)->next;        // 将下一个链表节点接到上一个node->next = NULL;free(node->key);free(node); }else {transNode = &(*transNode)->next;        // 将链表节点后移一次,并将二级指针的值修改为链表后移前的值}}
}void clearHashElemList(HashTab* tab) {for (int i = 0; i < tab->group; i++) {HashNode* transNode = tab->Hash_sets[i];tab->Hash_sets[i] = NULL;while (transNode) {HashNode* node = transNode;transNode = transNode->next;node->next = NULL;free(node->key);free(node);}}
}