C语言哈希表的实现过程

哈希表（Hash Table）是一种高效的数据结构，它使用哈希函数将键映射到数组中的索引位置。在C语言中，可以通过数组和指针来实现哈希表。

下面是一个简单的C语言哈希表的实现，该实现使用了链地址法（Separate Chaining）来解决哈希冲突问题：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define TABLE_SIZE 100typedef struct HashNode {

    char key[20];    int value;    struct HashNode *next;} HashNode;typedef struct HashTable {

    HashNode *table[TABLE_SIZE];

} HashTable;unsigned int hash(char *key) {    unsigned int hash_val = 0;    while (*key) {

        hash_val = (hash_val << 5) + *key++;

    }    return hash_val % TABLE_SIZE;

}

HashTable* createHashTable() {

    HashTable *ht = (HashTable*) malloc(sizeof(HashTable));    memset(ht->table, 0, sizeof(ht->table));    return ht;

}void insert(HashTable *ht, char *key, int value) {    unsigned int index = hash(key);

    HashNode *node = (HashNode*) malloc(sizeof(HashNode));    strcpy(node->key, key);

    node->value = value;

    node->next = ht->table[index];

    ht->table[index] = node;

}int find(HashTable *ht, char *key) {    unsigned int index = hash(key);

    HashNode *node = ht->table[index];    while (node != NULL) {        if (strcmp(node->key, key) == 0) {            return node->value;

        }

        node = node->next;

    }    return -1;

}void printHashTable(HashTable *ht) {    for (int i = 0; i < TABLE_SIZE; i++) {        printf("[%d]: ", i);

        HashNode *node = ht->table[i];        while (node != NULL) {            printf("%s=%d ", node->key, node->value);

            node = node->next;

        }        printf(" ");

    }

}int main() {

    HashTable *ht = createHashTable();

    insert(ht, "apple", 1);

    insert(ht, "banana", 2);

    insert(ht, "cherry", 3);    printf("apple=%d ", find(ht, "apple"));    printf("banana=%d ", find(ht, "banana"));    printf("cherry=%d ", find(ht, "cherry"));    printf("orange=%d ", find(ht, "orange"));

    printHashTable(ht);    return 0;

}

在这个例子中，我们定义了一个名为HashTable的结构体，它包含一个长度为TABLE_SIZE的指针数组，每个元素都指向一个哈希链表的头节点。另外，我们还定义了一个名为HashNode的结构体，它表示哈希链表中的一个节点。

哈希函数hash采用了一种简单的算法，将字符转换为整数，并使用取模运算得到在指针数组中的索引位置。

createHashTable函数用于创建一个新的哈希表，它使用malloc函数动态分配内存，并使用memset函数将所有指针初始化为NULL。

insert函数用于向哈希表中插入一个新的键值对，它首先计算键的哈希值，然后创建一个新的节点，并将其插入到对应的哈希链表的头部。

find函数用于查找给定键的值，它首先计算键的哈希值，然后遍历对应的哈希链表，查找是否存在该键的节点。

printHashTable函数用于打印整个哈希表的内容，它遍历所有的哈希链表，并输出每个键值对的内容。

在main函数中，我们首先创建一个新的哈希表，然后向其中插入三个键值对。接下来，我们使用find函数查找三个键的值，并输出结果。最后，我们使用printHashTable函数打印整个哈希表的内容。