拉链法解决冲突，写出散列表的创建，插入，查找函数

拉链法（Chaining）是一种常见的解决哈希表冲突的方法。当两个不同的键经过哈希函数映射到同一个槽位（bucket）时，我们会在那个槽位上维护一个链接列表，将所有映射到此槽位的键值对都添加到这个列表里。这样，在插入、删除和查找过程中，只需要遍历对应槽位的链接列表即可。

以下是使用拉链法的简单散列表（Hash Table）在C语言中的创建、插入和查找函数：

#include <stdlib.h>

// 定义链表节点
typedef struct Node {
    void* key;
    void* value;
    struct Node* next;
} ListNode;

// 散列表结构体
typedef struct HashTable {
    int size;
    int capacity;
    ListNode** buckets; // 使用动态数组存储链表头指针
} HashTable;

// 创建散列表
HashTable* createHashTable(int size) {
    HashTable* table = (HashTable*)malloc(sizeof(HashTable));
    if (!table) return NULL;
    table->size = size;
    table->capacity = size * 2; // 预留一些空间应对冲突
    table->buckets = (ListNode**)calloc(table->capacity, sizeof(ListNode*)); // 分配桶数组
    if (!table->buckets) {
        free(table);
        return NULL;
    }
    for (int i = 0; i < table->capacity; i++) {
        table->buckets[i] = NULL; // 初始化所有链表为空
    }
    return table;
}

// 插入键值对
void insert(HashTable* table, void* key, void* value) {
    int index = hashFunction(key, table->size); // 计算哈希值
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode) {
        free(table->buckets[index]);
        free(table);
        return;
    }
    newNode->key = key;
    newNode->value = value;
    newNode->next = table->buckets[index]; // 设置新节点为当前链表头
    table->buckets[index] = newNode;

    // 如果链表已经满了，尝试处理冲突
    if (newNode->next != NULL && newNode->next->next == NULL) {
        // 扩容处理
        resizeHashTable(table);
        index = hashFunction(key, table->size); // 更新索引
        newNode->next = table->buckets[index];
        table->buckets[index] = newNode;
    }
}

// 查找键值对
void* search(HashTable* table, void* key) {
    int index = hashFunction(key, table->size);
    ListNode* current = table->buckets[index];

    while (current != NULL) {
        if (current->key == key) return current->value; // 找到匹配的键则返回值
        current = current->next;
    }

    return NULL; // 键不存在则返回NULL
}

// 哈希函数示例（同前面一样，这里仅作演示）
unsigned int hashFunction(void* key, int size) {
    return (unsigned int)key % size;
}

// 扩容函数（将链表拆分成两部分，并复制到新的数组）
void resizeHashTable(HashTable* table) {
    int newCapacity = table->capacity * 2;
    ListNode** newBuckets = (ListNode**)realloc(table->buckets, newCapacity * sizeof(ListNode*));
    if (!newBuckets) return;

    for (int i = 0; i < newCapacity; i++) {
        if (table->buckets[i]) {
            while (table->buckets[i] != NULL) {
                ListNode* node = table->buckets[i];
                table->buckets[i] = table->buckets[i]->next;
                insert(newBuckets, node->key, node->value); // 逐个将旧链表的元素插入到新链表
                free(node);
            }
        } else {
            newBuckets[i] = NULL;
        }
    }
    free(table->buckets);
    table->buckets = newBuckets;
    table->capacity = newCapacity;
}