Hash表 数据结构
程序员文章站
2022-07-15 14:15:29
...
Hash 表
key: value
key 保存信息的唯一标识
将char*类型的key转化为int型作为寻找信息的方式
假设有10000个人, 分成100个表保存信息, 每个表保存100个人
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);
}
}
}
上一篇: Two Sum (两数之和) - Hash Table (哈希表)
下一篇: 内存调优