小练习 - 哈希表之分离链接法

本文主要是介绍小练习 - 哈希表之分离链接法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

哈希表十分常用，这里做个小练习，冲突解决使用分离链接法。从哈希表的C实现来看，其本质上做了这样一个映射：key -> hashtable[index] -> addr, 新插入一个数据时，key由数据本身决定，存储地址addr则是系统分配，key通过哈希函数可以算出索引，查找索引对应哈表项目得到地址。

采用分离链接法，底层数据结构主要是数组和链表。这里未考虑哈希表随着数据增加自动扩容的功能，考虑到后插入的数据可能先被访问，这里每次插入都插入到冲突链的首部，当然传入的时候要判断元素是否重复。例子如下：

#include <stdlib.h>
#include <string.h>
#include <stdio.h>typedef struct {int id;char name[10];
}Data;typedef struct _node{Data data;struct _node *next;
}Node;typedef struct {int size;Node **nodes;
} HashTable;void init(HashTable *table, int size)
{size_t len = sizeof(void*) * size;table->size = size;table->nodes = (Node**)malloc(len);memset(table->nodes, 0, len);
}int hash(HashTable *table, int key)
{return key % table->size;
}Node* find(HashTable *table, int key)
{int index = hash(table, key);Node *pos = table->nodes[index];while (pos != NULL && pos->data.id != key)pos = pos->next;return pos;
}#define OK    0
#define ERROR 1int insert(HashTable *table, Data *data)
{int index;Node *inode;Node *pos = find(table, data->id);if (pos == NULL) {index = hash(table, data->id);inode = (Node*)malloc(sizeof(Node));memcpy(&inode->data, data, sizeof(Data));inode->next = table->nodes[index];table->nodes[index] = inode;return OK;} else {return ERROR; // hash key conflict}
}int delete(HashTable *table, int key)
{Node *pos, *p, *tmp;pos = find(table, key);if (pos != NULL) {p = table->nodes[hash(table, key)];if (p->next == NULL) {free(p);table->nodes[hash(table, key)] = NULL;return OK;}while (p->next->data.id != key)p = p->next;tmp = p->next->next;free(p->next);p->next = tmp;return OK;} else {return ERROR;}
}void clear_table(HashTable *table)
{int i;Node *p = NULL, *tmp = NULL;for (i = 0; i < table->size; i++) {p = table->nodes[i];if (p != NULL) {while (p) {tmp = p->next;free(p);p = tmp;}}}free(table->nodes);
}int main()
{Node *p;HashTable tb;Data a, b, c;init(&tb, 1);a.id = 1;strcpy(a.name, "aa");b.id = 2;strcpy(b.name, "bb");c.id = 3;strcpy(c.name, "cc");insert(&tb, &a);insert(&tb, &b);insert(&tb, &c);p = find(&tb, 2);delete(&tb,2);clear_table(&tb);return 0;
}