从0到1实现C语言哈希表：底层原理与实战解析

// hash.h
typedef char *KeyType;   // 键类型：字符串指针
typedef char *ValueType; // 值类型：字符串指针

// 哈希桶节点（链表节点）
typedef struct node_s {
    KeyType key;          // 键（字符串）
    ValueType val;        // 值（字符串）
    struct node_s *next;  // 下一个节点指针（解决哈希冲突）
} KeyValueNode;

// 哈希表核心结构体
typedef struct {
    KeyValueNode *buckets[HASHMAP_CAPACITY];  // 哈希桶数组（固定容量10）
    uint32_t hash_seed;                       // 哈希函数种子（随机化防碰撞攻击）
} HashMap;

// hash.c
char *strdup1(const char *s) {
    size_t len = strlen(s) + 1;  // +1 用于存储字符串结束符'\0'
    char *p = (char *)malloc(len); 
    if (p) {
        memcpy(p, s, len);  // 深拷贝字符串内容
    }
    return p;
}

// hash.c
HashMap *hashmap_create() {
    HashMap *map = (HashMap *)calloc(1, sizeof(HashMap));  // 分配哈希表内存
    if (map == NULL) {
        printf("calloc failed in hashmap_create
");  // 内存分配失败提示
        exit(EXIT_FAILURE);  // 终止程序（避免后续操作崩溃）
    }
    // 初始化哈希种子（基于当前时间戳，保证每次运行种子不同）
    map->hash_seed = (uint32_t)time(NULL); 
    return map;
}

// hash.c
void hashmap_destroy(HashMap *map) {
    if (map == NULL) return;  // 空指针直接返回

    // 遍历所有哈希桶
    for (int i = 0; i < HASHMAP_CAPACITY; i++) {
        KeyValueNode *current = map->buckets[i];  // 当前桶的头节点
        while (current != NULL) {                 // 遍历链表
            KeyValueNode *next = current->next;   // 保存下一个节点指针
            free(current->key);   // 释放键的内存
            free(current->val);   // 释放值的内存
            free(current);        // 释放节点本身的内存
            current = next;       // 移动到下一个节点
        }
    }
    free(map);  // 释放哈希表本身的内存
}

// hash.c
ValueType hashmap_put(HashMap *map, KeyType key, ValueType val) {
    if (map == NULL || key == NULL || val == NULL) return NULL;  // 参数校验

    // 1. 计算哈希值，确定桶的位置
    uint32_t index = hash(key, map->hash_seed); 

    // 2. 遍历桶内链表，检查键是否已存在
    KeyValueNode *current = map->buckets[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {  // 键已存在
            free(current->val);                 // 释放旧值内存
            current->val = strdup1(val);         // 更新为新值（深拷贝）
            return current->val;                 // 返回新值
        }
        current = current->next;  // 移动到下一个节点
    }

    // 3. 键不存在，创建新节点并插入链表头部（头插法）
    KeyValueNode *new_node = (KeyValueNode *)calloc(1, sizeof(KeyValueNode));
    if (new_node == NULL) {  // 内存分配失败处理
        fprintf(stderr, "Memory allocation failed in hashmap_put
");
        return NULL;
    }
    new_node->key = strdup1(key);   // 深拷贝键
    new_node->val = strdup1(val);   // 深拷贝值
    new_node->next = map->buckets[index];  // 新节点指向原链表头
    map->buckets[index] = new_node;        // 头插法更新链表头

    return new_node->val;  // 返回新值
}

// hash.c
ValueType hashmap_get(HashMap *map, KeyType key) {
    if (map == NULL || key == NULL) return NULL;  // 参数校验

    // 1. 计算哈希值，确定桶的位置
    uint32_t index = hash(key, map->hash_seed); 

    // 2. 遍历桶内链表，查找目标键
    KeyValueNode *current = map->buckets[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {  // 找到目标键
            return current->val;               // 返回对应值
        }
        current = current->next;  // 移动到下一个节点
    }

    return NULL;  // 未找到键
}

// hash.c
bool hashmap_remove(HashMap *map, KeyType key) {
    if (map == NULL || key == NULL) return false;  // 参数校验

    // 1. 计算哈希值，确定桶的位置
    uint32_t index = hash(key, map->hash_seed); 

    // 2. 遍历链表，查找目标键并删除
    KeyValueNode *current = map->buckets[index];
    KeyValueNode *prev = NULL;  // 记录前一个节点指针

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {  // 找到目标键
            // 情况1：节点是链表头（prev为NULL）
            if (prev == NULL) {
                map->buckets[index] = current->next;  // 头指针指向下一节点
            } 
            // 情况2：节点是链表中间或尾部（prev不为NULL）
            else {
                prev->next = current->next;  // 前一个节点指向下一节点
            }

            // 释放节点内存
            free(current->key);   // 释放键
            free(current->val);   // 释放值
            free(current);        // 释放节点本身
            return true;          // 删除成功
        }
        prev = current;       // 记录当前节点为前一个节点
        current = current->next;  // 移动到下一个节点
    }

    return false;  // 未找到键
}

// hash.c
static uint32_t hash(const char *key, uint32_t seed) {
    uint32_t hash_val = 0;
    while (*key) {  // 遍历字符串的每个字符
        hash_val = (hash_val * 31) + (uint32_t)*key++;  // 经典多项式哈希
    }
    return (hash_val ^ seed) % HASHMAP_CAPACITY;  // 结合种子值取模
}

#include "hash.h"

int main() {
    HashMap *map = hashmap_create();  // 创建哈希表
    if (map == NULL) return 1;        // 内存分配失败处理

    // 插入键值对
    hashmap_put(map, "name", "Alice");  // 插入字符串键值对
    hashmap_put(map, "age", "25");

    // 查询键值对
    ValueType name = hashmap_get(map, "name");  // 获取"name"对应的值
    ValueType age = hashmap_get(map, "age");
    if (name) printf("Name: %s
", name);         // 输出：Name: Alice
    if (age)  printf("Age: %s
", age);          // 输出：Age: 25

    // 删除键值对
    if (hashmap_remove(map, "age")) {
        printf("'age' removed successfully.\n");  // 输出：'age' removed successfully.
    }

    // 验证删除结果
    age = hashmap_get(map, "age");
    if (age == NULL) {
        printf("'age' not found after removal.\n");  // 输出：'age' not found after removal.
    }

    hashmap_destroy(map);  // 销毁哈希表（释放所有内存）
    return 0;
}

Name: Alice
Age: 25
'remove 'age' successfully.
'age' not found after removal.