一、基本概念
哈希表是一种数据结构,它通过某种函数(称为哈希函数)将元素的关键码映射到表中的位置,以实现快速的插入、查找和删除操作。哈希表的查找时间复杂度为O(1),这使得它在处理大量数据时非常高效。
然而,哈希表也面临哈希冲突的问题,即不同的关键码通过哈希函数计算得到相同的位置,这种情况下需要通过解决冲突的方法来处理,如链地址法,开放地址法。
二、函数接口
hash.c
#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>HSNode_t *hashtable[HASH_SIZE] = {NULL};int hash_function(char key)
{if (key >= 'a' && key <= 'z'){return key-'a';}else if (key >= 'A' && key <= 'Z'){return key-'A';}else{return HASH_SIZE-1;}
}int insert_hashtable(HSDataTYpe data)
{int addr = hash_function(data.name[0]);HSNode_t *pnode = malloc(sizeof(HSNode_t));if (NULL == pnode){perror("fail malloc");return -1;}pnode->data = data;pnode->pnext = NULL;pnode->pnext = hashtable[addr];hashtable[addr] = pnode;return 0;
}void hash_for_each()
{for (int i = 0; i < HASH_SIZE; i++){HSNode_t *p = hashtable[i];while (p != NULL){printf("%s %s ", p->data.name, p->data.tel);p = p->pnext;}printf("\n");}
}HSNode_t *find_hashtable(char *name)
{int addr = hash_function(name[0]);HSNode_t *p = hashtable[addr];while (p != NULL){if (!strcmp(name, p->data.name)){// printf("%s %s\n", ptmp->data.name, ptmp->data.tel);return p;}p = p->pnext;}return NULL;
}void destroy_hashtable()
{for (int i = 0; i< HASH_SIZE; i++){ while (hashtable[i] != NULL){ HSNode_t *p = hashtable[i];hashtable[i] = p->pnext;free(p);}}
}
hash.h
#define HASH_SIZE 27typedef struct per
{char name[64];char tel[32];
}HSDataTYpe;typedef struct hsnode
{HSDataTYpe data;struct hsnode *pnext;
}HSNode_t;extern int insert_hashtable(HSDataTYpe data);
extern void hash_for_each();
extern HSNode_t *find_hashtable(char *name);
extern void destroy_hashtable();