c语言实现哈希表链式法

C语言哈希链表是一种数据结构，它结合了哈希表和链表的特点，可以高效地进行数据的插入、删除和查找操作，在C语言中，我们可以使用结构体和指针来实现哈希链表的建立，下面是详细的技术介绍：

1、定义哈希链表结构体

我们需要定义一个哈希链表的结构体，包括一个数组用于存储哈希表的桶，一个整数表示当前哈希表的大小，以及一个链表头指针用于存储哈希表中的所有节点。

include <stdio.h>
include <stdlib.h>
include <string.h>
typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;
typedef struct HashTable {
    Node **buckets;
    int size;
    int count;
} HashTable;

2、初始化哈希表

接下来，我们需要实现一个初始化哈希表的函数，该函数会创建一个指定大小的哈希表，并初始化所有桶为空。

HashTable *create_hash_table(int size) {
    HashTable *table = (HashTable *)malloc(sizeof(HashTable));
    table->buckets = (Node **)malloc(size * sizeof(Node *));
    for (int i = 0; i < size; i++) {
        table->buckets[i] = NULL;
    }
    table->size = size;
    table->count = 0;
    return table;
}

3、计算哈希值

为了将键值对存储到正确的桶中，我们需要计算键的哈希值，这里我们使用简单的取模运算来计算哈希值。

unsigned int hash(const char *key, int size) {
    unsigned int hash_value = 0;
    for (int i = 0; key[i]; i++) {
        hash_value = (hash_value * 31 + key[i]) % size;
    }
    return hash_value;
}

4、插入键值对

插入键值对时，我们需要先计算键的哈希值，然后将键值对插入到对应的桶中，如果桶已满，我们需要创建一个新的节点并将键值对插入到新的桶中，更新哈希表的大小和计数。

void insert(HashTable *table, const char *key, int value) {
    unsigned int index = hash(key, table->size);
    Node *node = (Node *)malloc(sizeof(Node));
    node->key = strdup(key);
    node->value = value;
    node->next = table->buckets[index];
    table->buckets[index] = node;
    table->count++;
}

5、查找键值对

查找键值对时，我们需要先计算键的哈希值，然后在对应的桶中查找键值对，如果找到了键值对，返回其值；否则返回-1。

int find(HashTable *table, const char *key) {
    unsigned int index = hash(key, table->size);
    Node *node = table->buckets[index];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return -1;
}

6、删除键值对

删除键值对时，我们需要先计算键的哈希值，然后在对应的桶中查找键值对，如果找到了键值对，将其从链表中删除；否则不做任何操作，更新哈希表的大小和计数，注意，这里我们没有释放节点的内存，因为链表中的其他节点可能仍然引用它，在实际应用中，可以在适当的时候释放节点的内存。

void delete(HashTable *table, const char *key) {
    unsigned int index = hash(key, table->size);
    Node **current = &table->buckets[index];
    while (*current) {
        if (strcmp(*current->key, key) == 0) {
            Node *temp = *current;
            *current = (*current)->next;
            free(temp->key); // 释放节点的内存（可选）
            table->count--; // 更新哈希表的计数（可选）
            return; // 找到并删除了键值对，直接返回（可选）
        } else {
            current = &(*current)->next; // 继续查找下一个节点（可选）
        }
    } // 如果遍历完链表都没有找到键值对，不做任何操作（可选）
}

7、释放哈希表内存