C语言数据结构哈希表详解

什么是哈希表？

哈希表（Hash Table）是一种采用散列函数（hash函数）将数据映射到一个固定长度的数组中，并且以 O(1) 的时间复杂度进行数据插入、查找、删除操作的数据结构。哈希表主要由以下三个组成部分构成：
- 数组：用于存储映射到对应下标上的数据。
- 散列函数：将数据映射到数组下标上的规则。
- 冲突处理方式：当不同的数据映射到同一下标时，需要采取的处理措施，如开放地址法、链地址法等。

实现哈希表的关键点

哈希表的实现过程中，有以下几个关键点需要掌握：

哈希函数的设计

哈希函数的设计决定了哈希表的效率和数据存储的均衡性，通常需要符合以下要求：
- 易于计算：计算哈希值的时间复杂度要尽量低。
- 均匀分布：将数据散列到数组中的下标需要尽量均匀，减少冲突的发生。
- 低冲突率：哈希算法计算出相同哈希值的输入应尽量少。

哈希表的扩容和缩容

当哈希表存储的数据量达到一定阈值时，需要对哈希表进行扩容，以保证哈希表的效率和空间利用率。同时，当哈希表中存储的数据量变小时，还需要对哈希表进行缩容以减少空间的浪费。

冲突的解决方式

当不同的数据映射到同一下标时，可以采取以下几种冲突解决方式：
- 开放地址法：尝试向其他的空闲位置插入元素，类似于寻找新的住址。
- 链地址法：将多个具有同一哈希值的元素存储在同一个链表中。

哈希表的实现示例

以下是一个使用链地址法实现哈希表的示例，详见代码：

#include <stdlib.h>
#include <string.h>

// 哈希表节点结构体
typedef struct HashNode {
    char* key;
    char* value;
    struct HashNode* next;
} HashNode;

// 哈希表结构体
typedef struct HashTable {
    HashNode** nodes;
    int size;
} HashTable;

// 创建哈希表
HashTable* createHashTable(int size) {
    HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));
    hashTable->nodes = (HashNode**)calloc(size, sizeof(HashNode*));
    hashTable->size = size;
    return hashTable;
}

// 计算哈希值
int hash(char* key, int size) {
    unsigned int hashValue = 0;
    for (int i = 0; i < strlen(key); i++) {
        hashValue = hashValue * 31 + key[i];
    }
    return hashValue % size;
}

// 插入键值对
void put(HashTable* hashTable, char* key, char* value) {
    int index = hash(key, hashTable->size);
    HashNode* node = hashTable->nodes[index];
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            // 如果键已经存在，更新其对应的值
            strcpy(node->value, value);
            return;
        }
        node = node->next;
    }
    // 如果键不存在，创建新的节点并插入链表头部
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = (char*)malloc(strlen(key) + 1);
    strcpy(newNode->key, key);
    newNode->value = (char*)malloc(strlen(value) + 1);
    strcpy(newNode->value, value);
    newNode->next = hashTable->nodes[index];
    hashTable->nodes[index] = newNode;
}

// 获取键对应的值
char* get(HashTable* hashTable, char* key) {
    int index = hash(key, hashTable->size);
    HashNode* node = hashTable->nodes[index];
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return NULL;
}

// 删除键值对
void removeByKey(HashTable* hashTable, char* key) {
    int index = hash(key, hashTable->size);
    HashNode* node = hashTable->nodes[index];
    HashNode* preNode = NULL;
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            if (preNode == NULL) {
                // 如果删除的节点是链表的第一个节点，需要将链表头部指向第二个节点
                hashTable->nodes[index] = node->next;
            } else {
                // 如果删除的节点不是链表的第一个节点，需要将前一个节点指向下一个节点
                preNode->next = node->next;
            }
            free(node->key);
            free(node->value);
            free(node);
            return;
        }
        preNode = node;
        node = node->next;
    }
}

// 删除哈希表
void deleteHashTable(HashTable* hashTable) {
    for (int i = 0; i < hashTable->size; i++) {
        HashNode* node = hashTable->nodes[i];
        while (node != NULL) {
            HashNode* nextNode = node->next;
            free(node->key);
            free(node->value);
            free(node);
            node = nextNode;
        }
    }
    free(hashTable->nodes);
    free(hashTable);
}

// 示例：使用哈希表存储学生信息
int main() {
    HashTable* studentTable = createHashTable(100);
    put(studentTable, "Tom", "20");
    put(studentTable, "Jerry", "19");
    put(studentTable, "Alice", "21");
    put(studentTable, "Bob", "18");

    printf("Bob's age is %s\n", get(studentTable, "Bob"));

    removeByKey(studentTable, "Alice");

    printf("Alice's age is %s\n", get(studentTable, "Alice"));

    deleteHashTable(studentTable);
    return 0;
}

在上述代码中，我们使用了链地址法解决了哈希冲突，并实现了插入、查找、删除等操作。此外，我们还根据实际需求，将该哈希表用于存储学生信息，以便更好地说明哈希表的应用场景。