用c语言 利用“除留取余法”构建哈希函数，“线性探测再散列”处理冲突，构建哈希表

在C语言中，我们可以利用“除留取余法”（也称为取模法或Modulo Hashing）来构建简单的哈希函数。这个方法的基本思想是将输入的关键字通过一个固定的除法运算得到的结果对哈希表大小取模，这样就能把关键字映射到哈希表的某个索引。

例如，假设哈希表的大小是`size`，我们有这样一个哈希函数：

unsigned int hashFunction(const void* key, unsigned int size) {
    const char* str = (const char*)key; // 假设key是一个字符串
    unsigned int hash = 0;

    while (*str) {
        hash += (*str++);
        hash %= size; // 取模操作
    }

    return hash;
}

接下来，我们需要处理哈希冲突，这里可以采用“线性探测再散列”策略。当两个键被哈希到相同的槽位时，我们会从该槽开始，顺序查找下一个空槽直到找到为止。如果遍历完整个哈希表仍然找不到空槽，那么就认为发生了溢出，通常需要考虑扩容或者更换其他更复杂的冲突解决策略。

下面是一个简化的示例：

typedef struct Node {
    void* data;
    struct Node* next;
} Node;

Node** createHashTable(unsigned int size) {
    Node** table = (Node**)malloc(size * sizeof(Node*));
    for (unsigned int i = 0; i < size; i++) {
        table[i] = NULL;
    }
    return table;
}

void insert(Node** table, const void* key, void* value) {
    unsigned int index = hashFunction(key, table_size);
    Node* current = table[index];
    
    while (current != NULL) {
        if (strcmp(current->data, key) == 0) {
            // 更新已存在的键值对
            current->value = value;
            break;
        }
        current = current->next;
    }
    
    if (current == NULL) {
        // 插入新节点
        Node* newNode = malloc(sizeof(Node));
        newNode->data = key;
        newNode->value = value;
        newNode->next = table[index];
        table[index] = newNode;
    }
}

// ... 其他插入、删除等操作

// 销毁哈希表时记得释放所有节点
void destroyHashTable(Node** table) {
    for (unsigned int i = 0; i < table_size; i++) {
        Node* node = table[i];
        while (node != NULL) {
            Node* temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(table);
}