哈希表的C语言链表实现

结合了数组（索引快）和链表（可灵活增删结点）的优点。

2.1 链表部分

2.1.1 链表结点的结构

typedef struct __tag_node{
int id;
struct __tag_node *pNext;
int satellite;
}Node;


2.1.2 创建链表

Node *LinkedList_Create(void)
{
Node *p = malloc(sizeof(Node));
if(p == NULL){
return NULL;
}
p->pNext = NULL;
p->id = 0; // The total quantity of nodes
return p;
}


2.1.3 销毁链表

void LinkedList_Destroy(Node *list)
{
Node *p = list->pNext; // Reserved header node
while(p){
Node *tmp = p;
p = p->pNext;
free(tmp);
}
list->pNext = NULL;
list->id = 0;
}


2.1.4 头插新结点

/**
* @brief Inserting a new node in the linked list
* @param list, The linked list will be inserted
* @param id, id number
* @param the satellite value of the id
**/
int LinkedList_InsertHead(Node *list, int id, int dat)
{
Node *p = malloc(sizeof(Node *));
if(p == NULL){
return -1;
}
p->id = id;
p->pNext = list->pNext;
list->pNext = p;
p->satellite = dat;
return 1;
}


2.1.5 根据id搜索链表

/**
* @brief search the id
* @param list, The hash table will be searched
* @param key, key
* @retval the satellite value of the id
**/
int LinkedList_Search(Node *list, int id)
{
Node *p = list->pNext;
for(Node *p = list->pNext; p; p = p->pNext){
if(id == p->id){
return p->satellite;
}
}
return 0;
}


2.2 Hash表部分

2.2.1 创建Hash表

Node **HashTable_Create(int len)
{
Node **p = malloc(len * sizeof(Node *));
for(int i = 0; i < len; i++){
p[i] = LinkedList_Create();
}
return p;
}


2.2.2 清空表中元素

void HashTable_Clear(Node **arr, int len)
{
for(int i = 0; i < len; i++){
LinkedList_Destroy(*(arr+i));
}
}


2.2.3 摧毁整个Hash表

void HashTable_Destroy(Node **arr, int len)
{
HashTable_Clear(arr, len);
for(int i = 0; i < len; i++){
free(arr[i]);
}
free(arr);
}


2.2.4 Hash函数

int HashTable_hashFunc(int key, int len)
{
return key % len;
}


2.2.5 插入哈希表

int HashTable_Insert(int key, int value, Node **table, int length)
{
if(LinkedList_InsertHead(table[HashTable_hashFunc(key, length)], key, value)){
return 1; // Success
}else{
return -1; // Failure
}
}


2.2.6 根据key搜索Hash表返回数据

/**
* @brief search the key
* @param table, The hash table will be searched
* @param length, The length of the hash table
* @retval the value of the key
**/
int HashTable_Search(int key, Node **table, int length)
{
return LinkedList_Search(table[HashTable_hashFunc(key, length)], key);
}
3 测试例程

#define __MAX_LEN_TABLE_ 10
int main(int argc, char *argv[])
{
Node **pHashTable;
pHashTable = HashTable_Create(__MAX_LEN_TABLE_);
if(HashTable_Insert(12, 125, pHashTable, __MAX_LEN_TABLE_)){
printf("Insert key = 12, value = 125 successful!\r\n");
}else{
printf("Insert key = 12 fail!\r\n");
}
if(HashTable_Insert(22, 255, pHashTable, __MAX_LEN_TABLE_)){
printf("Insert key = 22, value = 255 successful!\r\n");
}else{
printf("Insert key = 255 fail!\r\n");
}
int value = HashTable_Search(22, pHashTable, __MAX_LEN_TABLE_);
printf("value of key=22 is %d\r\n", value);
value = HashTable_Search(12, pHashTable, __MAX_LEN_TABLE_);
printf("value of key=12 is %d\r\n", value);
HashTable_Destroy(pHashTable, __MAX_LEN_TABLE_);

return 0;
}


测试结果