链式哈希

代码仓库shanchuann/CPP-Learninng

引言

哈希表作为经典的散列类存储数据结构，通过哈希函数完成关键字与存储地址的直接映射，可在平均时间复杂度下实现常数级的查找、插入与删除操作，在分布式缓存、数据库索引、键值存储系统等工程领域具备广泛应用价值。哈希冲突是哈希表设计中不可规避的关键技术问题，链地址法（又称链式哈希）作为解决哈希冲突的主流方案，其主要设计思路为将哈希映射结果一致的关键字以单链表结构串联，使每个哈希桶位对应一条独立链表，以此规避开放寻址法存在的寻址堆积、空间利用率低等缺陷。本文基于标准C语言实现的链式哈希完整源码，系统阐述链式哈希的基础理论原理，对源码的数据结构定义、基础工具函数、操作逻辑、动态扩容机制及内存管理方案进行逐模块、逐流程的详尽解析，同时梳理工程实现中的边界条件处理与性能优化思路，为哈希表的工程化落地与底层原理学习提供完整参考。

链式哈希基础理论

哈希表与哈希冲突

哈希表依托哈希函数，将输入关键字Key映射至预设范围内的离散哈希地址，实现关键字与存储位置的直接关联，理想状态下可达到O(1)时间复杂度的高效存取。但受哈希函数离散性能、关键字分布特征的双重影响，不同关键字经哈希运算后可能得到完全一致的哈希地址，该现象即为哈希冲突。现阶段哈希冲突的解决方案主要分为开放寻址法与链地址法两类，其中链地址法凭借空间利用率高、删除操作简便、无线性堆积问题的优势，成为工业界分布式系统与基础组件中常用的冲突解决策略。

链式哈希基本原理

链式哈希的主要设计逻辑为：将哈希表的基础存储单元定义为“哈希桶”，每个桶位对应一条单链表的头指针；所有经哈希函数映射至同一桶位的关键字，均作为链表节点插入对应链表结构；执行查找、插入、删除等操作时，先通过哈希函数定位目标哈希桶，再遍历对应链表完成目标操作。该方案可在内存允许范围内承载任意数量的冲突关键字，且删除操作仅需调整链表指针指向，无需移动其他存储节点，有效弥补了开放寻址法删除逻辑复杂、易产生寻址堆积的短板。

源码数据结构

本文所分析的链式哈希源码采用标准C语言实现，依托结构体封装哈希表整体结构、链表节点与数据元素，各数据结构分工明确、层级清晰，以下为核心结构定义及逐行解析：

// 标准C语言链式哈希源码，无冗余依赖，可直接编译运行
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

// 哈希桶容量：递增素数序列，降低哈希冲突概率，适配动态扩容
int BUCKETSIZE[10] = {13, 29, 53, 97, 193, 389, 769, 1543, 3079, 6151};
// 计算扩容序列长度，约束最大扩容次数，防止越界
#define BUCKETSIZE_COUNT (sizeof(BUCKETSIZE)/sizeof(BUCKETSIZE[0]))

// 关键字类型重定义，便于后续业务场景扩展适配
typedef int KeyType;
// 业务数据结构体，实际工程可填充对应业务字段
typedef struct {} Record;
// 哈希表存储元素：绑定关键字与附属业务数据
typedef struct {
    KeyType key;
    Record* info;
} ElemType;

// 链式哈希链表节点：数据域+指针域，串联冲突元素
typedef struct HashNode {
    ElemType data;
    struct HashNode* next;
} HashNode;

// 哈希表主体结构体：封装全局属性与操作入口
typedef struct {
    HashNode** map;        // 哈希桶数组二级指针
    size_t bucket_size;    // 当前哈希桶总容量
    size_t current_size;   // 当前有效存储节点数
    size_t bucket_index;   // 扩容序列下标，标记当前容量层级
} HashTable;

全局常量与宏定义

BUCKETSIZE数组：选取10个递增素数作为哈希桶容量序列，素数容量可大幅降低关键字取模后的哈希冲突概率，递增式设计适配哈希表动态扩容需求，避免非素数容量导致的哈希值分布不均问题；BUCKETSIZE_COUNT：通过sizeof运算符动态计算容量数组长度，实现扩容次数的精准约束，防止扩容操作超出预设容量范围，提升代码鲁棒性。

基础类型与元素结构

KeyType：将关键字类型重定义为整型，通过类型别名封装实现类型解耦，便于后续扩展为字符型、指针型等其他关键字类型，适配多场景业务需求；Record结构体：用于存储关键字对应的业务数据，本文示例中为空结构体，实际工程可根据业务需求填充字段，实现数据结构与业务逻辑的分离；ElemType结构体：封装哈希表核心存储单元，将关键字与对应业务数据指针绑定，确保关键字与附属数据的同步存储与调用。

链表节点与哈希表主体结构

HashNode结构体：链式哈希的基础链表节点单元，包含ElemType类型的数据域与指向下一节点的next指针，实现同一哈希桶内冲突节点的有序串联，是链式存储的基础单元；HashTable结构体：封装哈希表全局属性，map为二级指针，指向哈希桶数组（数组每个元素为对应链表的头指针），bucket_size表征当前哈希桶总容量，current_size统计已存储有效节点数，bucket_index标记当前容量在扩容素数序列中的下标，为动态扩容提供索引依据。

基础函数实现

基础工具函数负责哈希表初始化、节点创建、哈希运算等底层支撑工作，是链式哈希各项功能实现的基础，所有函数均加入指针合法性校验、内存分配异常处理等防御性编程逻辑，保障程序运行的稳定性与鲁棒性。

哈希表初始化函数InitHash

// 哈希表初始化函数：初始化基础属性，申请桶数组内存
void InitHash(HashTable* pt) {
    // 校验指针合法性，避免空指针操作
    assert(pt != NULL);
    // 初始化有效节点数为0
    pt->current_size = 0;
    // 初始扩容下标为0，选用最小素数容量
    pt->bucket_index = 0;
    pt->bucket_size = BUCKETSIZE[pt->bucket_index];
    // 申请桶数组内存，calloc自动初始化为NULL
    pt->map = (HashNode**)calloc(pt->bucket_size, sizeof(HashNode*));
    // 内存分配失败处理，打印错误并退出
    if (pt->map == NULL) {
        perror("calloc failed");
        exit(EXIT_FAILURE);
    }
}

该函数实现哈希表初始状态的标准化配置，主要执行逻辑为：通过assert断言校验传入哈希表指针的合法性，避免空指针操作；初始化有效节点数为0，将扩容下标置为0，选取BUCKETSIZE数组首个素数作为初始哈希桶容量；采用calloc函数动态申请哈希桶数组内存，calloc可自动将内存空间初始化为NULL，便于后续链表头指针的空值判断；若内存分配失败，通过perror打印系统级错误信息并终止程序，规避内存泄漏与野指针风险。

哈希函数HashFunc

// 哈希函数：除留余数法，关键字映射至对应哈希桶下标
int HashFunc(HashTable* pt, KeyType key) {
    // 校验哈希表指针合法性
    assert(pt != NULL);
    // 惰性初始化：未初始化或已释放时，自动初始化
    if (pt->map == NULL || pt->bucket_size == 0) {
        InitHash(pt);
    }
    // 转为无符号整型，避免负数取模导致桶位越界
    size_t k = (size_t)key;
    // 取模运算得到合法哈希桶下标
    return (int)(k % pt->bucket_size);
}

哈希函数采用除留余数法实现，为链式哈希关键字到哈希桶的关键映射逻辑：首先通过断言校验哈希表指针合法性，若哈希表未初始化或已释放内存，启动惰性初始化机制，确保函数在异常调用场景下仍可正常执行；将关键字强转为size_t无符号整型，规避负数取模导致的桶位越界问题；最终通过关键字对当前哈希桶容量取模，得到合法的目标桶位下标，完成关键字到哈希桶的精准映射。

节点创建函数CreateNode

// 创建链表节点：申请内存，初始化数据与指针域
HashNode* CreateNode(ElemType data) {
    // 动态申请节点内存
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    // 内存分配失败处理
    if(node == NULL) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    // 赋值数据域
    node->data = data;
    // 指针域置空，避免野指针
    node->next = NULL;
    return node;
}

该函数负责单链表节点的动态创建与初始化，通过malloc函数申请节点内存空间，若内存分配失败则打印错误信息并退出程序，杜绝野指针问题；将传入的存储数据赋值给节点数据域，同时将节点next指针置空，避免悬挂指针；最终返回初始化完成的节点指针，为插入操作提供基础单元，是链式哈希节点管理的基础工具函数。

增删查操作函数

操作函数是链式哈希功能实现的主要模块，涵盖数据查找、插入、删除、可视化打印与内存释放全流程，严格遵循单链表操作规范与哈希表存取逻辑，兼顾运行效率与异常处理，满足工程化使用需求。

节点查找函数FindNode

// 查找节点：根据关键字查找对应节点，存在则返回节点指针
HashNode* FindNode(HashTable* pt, KeyType key) {
    assert(pt != NULL);
    // 惰性初始化，保证异常场景可正常执行
    if (pt->map == NULL || pt->bucket_size == 0) InitHash(pt);
    // 计算目标哈希桶下标
    int index = HashFunc(pt, key);
    HashNode* node = pt->map[index];
    // 遍历对应链表，比对关键字
    while(node != NULL) {
        if(node->data.key == key) {
            // 找到匹配节点，返回指针
            return node;
        }
        node = node->next;
    }
    // 未找到对应节点，返回NULL
    return NULL;
}

查找函数实现关键字的精准定位与节点获取，主要执行流程为：校验哈希表状态并完成惰性初始化，通过哈希函数计算目标桶位下标，遍历对应链表逐一比对关键字；若匹配到目标关键字则返回对应节点指针，遍历至链表末尾仍无匹配项则返回NULL。该函数平均时间复杂度为O(1)，最坏情况下为O(n)（所有关键字冲突至同一链表），同时作为插入、删除操作的前置校验模块，用于判断关键字是否已存在，避免重复存储。

节点插入函数InsertHash

// 插入节点：去重插入，头插法挂载至对应哈希桶链表
bool InsertHash(HashTable* pt, ElemType data) {
    assert(pt != NULL);
    if (pt->map == NULL || pt->bucket_size == 0) InitHash(pt);
    // 去重校验：关键字已存在，插入失败
    if(FindNode(pt, data.key) != NULL) {
        return false;
    }
    // 定位目标哈希桶
    int index = HashFunc(pt,data.key);
    // 创建新节点
    HashNode* node = CreateNode(data);
    // 头插法：新节点指向原链表头节点
    node->next = pt->map[index];
    // 更新链表头节点
    pt->map[index] = node;
    // 有效节点数递增
    pt->current_size++;
    return true;
}

插入函数实现关键字的去重插入，采用链表头插法完成节点挂载，主要逻辑为：先通过查找函数校验关键字唯一性，若关键字已存在则返回false，避免冗余存储；通过哈希函数定位目标桶位，调用节点创建函数生成新节点；将新节点next指针指向原链表头节点，再更新哈希桶头指针为新节点，完成插入操作后递增有效节点计数。头插法无需遍历链表至尾部，大幅提升插入效率，契合哈希表高效存取的设计目标。

节点删除函数RemoveHash

// 删除节点：根据关键字删除对应节点，成功返回true，失败返回false
bool RemoveHash(HashTable* pt, KeyType key) {
    assert(pt != NULL);
    if (pt->map == NULL || pt->bucket_size == 0) InitHash(pt);
    // 定位目标哈希桶
    int index = HashFunc(pt,key);
    HashNode* node = pt->map[index];
    // 前驱指针，记录当前节点的上一个节点
    HashNode* prev = NULL;
    // 遍历链表查找目标节点
    while(node != NULL) {
        if(node->data.key == key) {
            // 目标节点为链表头节点
            if(prev == NULL) {
                pt->map[index] = node->next;
            } else {
                // 目标节点为中间/尾节点，调整前驱指针
                prev->next = node->next;
            }
            // 释放节点内存，防止内存泄漏
            free(node);
            // 有效节点数递减
            pt->current_size--;
            return true;
        }
        prev = node;
        node = node->next;
    }
    // 未找到目标节点，删除失败
    return false;
}

删除函数实现目标关键字的精准删除，是链式哈希相较于开放寻址法的重要优势场景，主要执行流程为：通过哈希函数定位目标桶位，遍历链表并通过前驱指针prev记录当前节点的前置节点；找到目标节点后，分两种场景处理：若为链表头节点，直接将桶位头指针指向后继节点；若为中间节点或尾节点，将前驱节点next指针指向后继节点；释放目标节点内存并递减有效节点计数，未找到目标关键字则返回false。该操作仅调整指针指向，无需移动其他节点，时间复杂度与查找操作保持一致。

辅助函数说明

// 打印哈希表：遍历所有桶位，可视化输出存储状态
void PrintHash(HashTable* pt) {
    // 空指针校验，直接返回
    if (pt == NULL || pt->map == NULL) return;
    for(size_t i = 0; i < pt->bucket_size; i++) {
        HashNode* node = pt->map[i];
        printf("Bucket %2zu: ", i);
        // 遍历当前桶链表，打印所有关键字
        while(node != NULL) {
            printf("Key:%d ", node->data.key);
            node = node->next;
        }
        printf("\n");
    }
}

// 释放哈希表内存：先释放链表节点，再释放桶数组
void FreeHash(HashTable* pt) {
    if (pt == NULL || pt->map == NULL) return;
    // 遍历所有哈希桶
    for(size_t i = 0; i < pt->bucket_size; i++) {
        HashNode* node = pt->map[i];
        // 释放当前桶所有节点
        while(node != NULL) {
            HashNode* temp = node;
            node = node->next;
            free(temp);
        }
    }
    // 释放桶数组内存
    free(pt->map);
    // 重置哈希表属性，避免野指针
    pt->map = NULL;
    pt->current_size = 0;
    pt->bucket_size = 0;
}

PrintHash函数实现哈希表存储状态的可视化打印，遍历所有哈希桶位并输出对应链表的关键字信息，便于程序调试与结果验证，提升代码可观测性；FreeHash函数实现哈希表全量内存的安全释放，遵循先释放链表节点、再释放哈希桶数组的顺序，逐一遍历每个桶位的链表并释放节点内存，最后释放桶数组空间并重置哈希表属性，彻底杜绝内存泄漏，符合工程化内存管理规范。

哈希表扩容机制

随着哈希表内有效节点数量持续增加，单链表长度会逐步增长，直接导致查找、插入操作的效率下降，因此哈希表需通过动态扩容机制优化性能。扩容的主要目标为增大哈希桶容量，分散链表节点，降低哈希冲突概率，将链表长度控制在合理范围内，维持哈希表的高效存取性能。

扩容函数ResizeHash

// 哈希表扩容：重新哈希所有节点，增大桶容量，降低冲突
void ResizeHash(HashTable* pt) {
    assert(pt != NULL);
    if (pt->map == NULL || pt->bucket_size == 0) InitHash(pt);
    // 扩容边界校验：已达最大容量，终止扩容
    if (pt->bucket_index + 1 >= BUCKETSIZE_COUNT) {
        return;
    }
    // 更新扩容下标，获取新容量
    pt->bucket_index++;
    size_t new_bucket_size = BUCKETSIZE[pt->bucket_index];
    // 申请新桶数组内存，初始化为NULL
    HashNode** new_map = (HashNode**)calloc(new_bucket_size, sizeof(HashNode*));
    // 内存分配失败处理
    if(new_map == NULL) {
        perror("calloc failed");
        exit(EXIT_FAILURE);
    }
    // 重新哈希：遍历旧桶所有节点，迁移至新桶
    for(size_t i = 0; i < pt->bucket_size; i++) {
        HashNode* node = pt->map[i];
        while(node != NULL) {
            // 暂存下一节点，防止断链
            HashNode* next_node = node->next;
            // 计算新桶下标
            size_t new_index = ((size_t)node->data.key) % new_bucket_size;
            // 头插法插入新桶
            node->next = new_map[new_index];
            new_map[new_index] = node;
            node = next_node;
        }
    }
    // 释放旧桶数组内存
    free(pt->map);
    // 更新哈希表属性
    pt->map = new_map;
    pt->bucket_size = new_bucket_size;
}

扩容逻辑与流程

扩容函数依托重新哈希（Rehash）机制运行，完整执行流程如下：首先校验扩容边界，若已达到预设最大容量则终止扩容，避免无限扩容；递增扩容下标，选取BUCKETSIZE数组中下一个素数作为新哈希桶容量；通过calloc申请新桶数组内存并初始化为NULL；遍历旧桶数组的所有链表，对每个节点重新计算新桶位下标，采用头插法将节点插入新桶对应位置；释放旧桶数组内存，更新哈希表的桶容量与map指针。扩容过程仅迁移节点指针，不复制实际数据，运行效率较高，素数扩容进一步降低哈希冲突概率。

扩容触发条件

// 扩容触发条件：负载因子0.75，整数运算避免浮点精度误差
// 等价判断：current_size >= ceil(bucket_size * 0.75)
if (ht.current_size * 4 >= ht.bucket_size * 3) {
    printf("\nResizing hash table...\n\n");
    // 执行扩容
    ResizeHash(&ht);
    // 打印扩容后状态
    PrintHash(&ht);
}

源码采用负载因子作为扩容触发条件，将负载因子阈值设为0.75（哈希表行业通用最优负载阈值），兼顾空间利用率与运行效率；为避免浮点运算产生的精度误差，采用整数乘法等价判断：current_size * 4 >= bucket_size * 3，无需浮点计算即可精准触发扩容，既保证哈希表空间利用率，又将链表长度控制在合理范围，维持高效存取性能。

主函数测试与结果

// 主函数：测试链式哈希基础功能与扩容机制
int main() {
    HashTable ht;
    // 初始化哈希表
    InitHash(&ht);

    // 定义测试元素
    ElemType e1 = {18, NULL};
    ElemType e2 = {14, NULL};
    ElemType e3 = {26, NULL};
    ElemType e4 = {26, NULL};

    // 执行插入操作
    InsertHash(&ht, e1);
    InsertHash(&ht, e2);
    InsertHash(&ht, e3);
    InsertHash(&ht, e4); // 重复关键字，插入失败
    // 打印初始存储状态
    PrintHash(&ht);

    // 测试删除功能
    printf("\nRemoving key 14...\n\n");
    RemoveHash(&ht, 14);
    PrintHash(&ht);
    // 释放内存
    FreeHash(&ht);

    // 测试动态扩容机制
    for (int i = 0; i < 100; i++) {
        ElemType e = {i, NULL};
        InsertHash(&ht, e);
        // 判断是否触发扩容
        if (ht.current_size * 4 >= ht.bucket_size * 3) {
            printf("\nResizing hash table...\n\n");
            ResizeHash(&ht);
            PrintHash(&ht);
        }
    }
    return 0;
}

主函数设计两组标准化测试用例，全面验证链式哈希的各项功能与扩容机制：第一组为基础功能验证，初始化哈希表后插入三组不重复数据与一组重复数据，验证去重插入逻辑的有效性；执行关键字删除操作，验证节点删除功能的准确性，打印结果可观测到重复数据未插入、目标节点成功删除。第二组为动态扩容测试，循环插入100组数据，触发多次自动扩容，可直观观测哈希表扩容、节点重新分布的全过程，验证扩容机制的稳定性与合理性。测试逻辑覆盖初始化、增删查、扩容、内存释放全流程，全面验证源码的完整性与鲁棒性。

链式哈希作为解决哈希冲突的常用技术方案，具备实现简洁、操作高效、内存利用率高的主要优势，本文解析的标准C语言源码，完整实现了链式哈希初始化、增删查改、动态扩容、内存安全释放的全功能模块，代码逻辑严谨、防御性处理完善、工程化程度高，可直接移植至实际项目与教学场景。通过对数据结构、基础函数、扩容机制、内存管理的详尽解析，可系统掌握链式哈希的底层实现原理与性能优化思路，为分布式缓存、键值存储、数据库索引等场景的哈希表设计与落地，提供坚实的理论支撑与实践参考。