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

哈希表十分常用，这里做个小练习，冲突解决使用分离链接法。从哈希表的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 1

int 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;
}

更多经典实现可以参考JDK和各种脚本语言字典功能的底层实现。