【附C源码】C语言实现散列表散列表Hash Table作为基础数据结构之一在实际工程中应用极为广泛。无论是编译器的符号表、数据库的索引实现还是缓存系统的设计都能看到它的身影。本文将介绍一种基于链地址法的散列表实现包含动态扩容机制代码约400行适合用于学习和理解哈希结构的内部工作原理。散列表的基本原理散列表的核心思想是通过哈希函数将键映射到数组的特定位置从而实现平均O(1)时间复杂度的查找。然而由于键空间通常远大于数组容量不同的键可能映射到同一位置这种现象称为哈希冲突。处理冲突的常见策略有两种开放寻址法在数组内部寻找下一个空闲位置链地址法在每个桶位置维护一个链表冲突的元素依次存入链表本文采用链地址法其实现相对直观且删除操作更为简便。散列表结构Hash函数Key索引桶数组链表1链表2...链表n数据结构定义首先定义两个核心结构体// 键值对节点typedefstructHashNode{char*key;// 键动态字符串intvalue;// 值structHashNode*next;// 链表下一个节点}HashNode;// 散列表结构typedefstruct{HashNode**buckets;// 桶数组存储链表头指针intsize;// 当前元素数量intcapacity;// 桶数组容量}HashTable;这里有几个设计考量键使用动态字符串通过malloc分配内存确保键的生命周期独立于调用者传入的字符串桶数组存储指针HashNode**的设计使得空桶仅占用一个指针的内存空间效率较好维护size和capacity便于计算负载因子为动态扩容提供依据哈希函数的选择哈希函数的优劣直接影响散列表的性能。理想的哈希函数应当满足计算速度快输出分布均匀减少冲突本实现采用经典的DJB2算法由Daniel J. Bernstein设计staticunsignedlonghashString(constchar*str){unsignedlonghash5381;intc;while((c*str)){hash((hash5)hash)c;// hash * 33 c}returnhash;}该算法的核心在于hash * 33 c其中33的选择经过实践验证在字符串哈希场景下表现良好。初始值5381也是一个经验值有助于减少小字符串的碰撞。动态扩容机制散列表的性能与负载因子Load Factor即元素数量/桶数量密切相关。当负载因子过高时链表长度增加查找效率退化当负载因子过低时空间利用率不足。本实现设置了两个阈值扩容阈值0.75缩容阈值0.125#defineLOAD_FACTOR_THRESHOLD0.75#defineSHRINK_FACTOR_THRESHOLD0.125扩容操作需要重新计算所有元素的哈希值因为桶数量变化后取模运算的结果也会改变staticboolhashTableResize(HashTable*ht,intnewCapacity){HashNode**oldBucketsht-buckets;intoldCapacityht-capacity;// 创建新的桶数组HashNode**newBuckets(HashNode**)calloc(newCapacity,sizeof(HashNode*));if(!newBuckets)returnfalse;ht-bucketsnewBuckets;ht-capacitynewCapacity;// 重新插入所有元素for(inti0;ioldCapacity;i){HashNode*nodeoldBuckets[i];while(node){HashNode*nextnode-next;// 计算新索引并头插法插入intnewIndexgetIndex(ht,node-key);node-nextht-buckets[newIndex];ht-buckets[newIndex]node;nodenext;}}free(oldBuckets);returntrue;}扩容流程如下是否是否否是触发扩容条件创建2倍容量的新桶数组遍历旧桶数组当前桶为空?继续下一个桶遍历链表节点计算新索引头插法插入新桶链表还有节点?遍历完成?释放旧桶数组完成核心操作实现插入操作插入时需要先检查是否需要扩容然后处理两种场景键已存在则更新值键不存在则创建新节点boolhashTablePut(HashTable*ht,constchar*key,intvalue){if(!ht||!key)returnfalse;// 检查是否需要扩容if(getLoadFactor(ht)LOAD_FACTOR_THRESHOLD){if(!hashTableResize(ht,ht-capacity*2)){returnfalse;}}intindexgetIndex(ht,key);HashNode*currentht-buckets[index];// 检查是否已存在该键while(current){if(strcmp(current-key,key)0){current-valuevalue;// 更新值returntrue;}currentcurrent-next;}// 创建新节点并头插HashNode*newNodecreateNode(key,value);if(!newNode)returnfalse;newNode-nextht-buckets[index];ht-buckets[index]newNode;ht-size;returntrue;}采用头插法将新节点插入链表时间复杂度为O(1)无需遍历到链表尾部。查找与删除查找操作遍历对应桶的链表进行字符串比较boolhashTableGet(HashTable*ht,constchar*key,int*outValue){if(!ht||!key||!outValue)returnfalse;intindexgetIndex(ht,key);HashNode*currentht-buckets[index];while(current){if(strcmp(current-key,key)0){*outValuecurrent-value;returntrue;}currentcurrent-next;}returnfalse;}删除操作需要维护前驱指针以正确调整链表连接关系boolhashTableRemove(HashTable*ht,constchar*key){if(!ht||!key)returnfalse;intindexgetIndex(ht,key);HashNode*currentht-buckets[index];HashNode*prevNULL;while(current){if(strcmp(current-key,key)0){if(prev){prev-nextcurrent-next;}else{ht-buckets[index]current-next;}free(current-key);free(current);ht-size--;// 检查是否需要缩容if(ht-capacityINITIAL_CAPACITYgetLoadFactor(ht)SHRINK_FACTOR_THRESHOLD){hashTableResize(ht,ht-capacity/2);}returntrue;}prevcurrent;currentcurrent-next;}returnfalse;}删除后检查缩容条件避免内存浪费。内存管理本实现中所有动态分配的内存都有明确的释放路径节点销毁destroyNodeChain函数遍历链表依次释放键字符串和节点本身表销毁hashTableDestroy遍历所有桶调用节点销毁函数最后释放桶数组和表结构staticvoiddestroyNodeChain(HashNode*node){while(node){HashNode*tempnode;nodenode-next;free(temp-key);free(temp);}}voidhashTableDestroy(HashTable*ht){if(!ht)return;for(inti0;iht-capacity;i){destroyNodeChain(ht-buckets[i]);}free(ht-buckets);free(ht);}测试验证代码包含完整的测试用例覆盖以下场景基本插入和查询值更新删除操作扩容触发与验证键遍历冲突处理验证空值查询通过hashTablePrint函数可以直观观察散列表的内部状态包括各桶的链表分布情况便于调试和理解扩容前后的变化。总结本文介绍的散列表实现虽然代码量不大但涵盖了哈希数据结构的核心要素哈希函数设计、冲突处理、动态扩容、内存管理等。对于需要理解散列表内部机制的开发者或者需要在嵌入式等场景下使用轻量级哈希实现的场景这份代码具有一定的参考价值。完整代码已开源如有问题欢迎交流讨论。⚠️源码地址https://github.com/anjuxi/C-hash_table
【附C源码】C语言实现散列表
【附C源码】C语言实现散列表散列表Hash Table作为基础数据结构之一在实际工程中应用极为广泛。无论是编译器的符号表、数据库的索引实现还是缓存系统的设计都能看到它的身影。本文将介绍一种基于链地址法的散列表实现包含动态扩容机制代码约400行适合用于学习和理解哈希结构的内部工作原理。散列表的基本原理散列表的核心思想是通过哈希函数将键映射到数组的特定位置从而实现平均O(1)时间复杂度的查找。然而由于键空间通常远大于数组容量不同的键可能映射到同一位置这种现象称为哈希冲突。处理冲突的常见策略有两种开放寻址法在数组内部寻找下一个空闲位置链地址法在每个桶位置维护一个链表冲突的元素依次存入链表本文采用链地址法其实现相对直观且删除操作更为简便。散列表结构Hash函数Key索引桶数组链表1链表2...链表n数据结构定义首先定义两个核心结构体// 键值对节点typedefstructHashNode{char*key;// 键动态字符串intvalue;// 值structHashNode*next;// 链表下一个节点}HashNode;// 散列表结构typedefstruct{HashNode**buckets;// 桶数组存储链表头指针intsize;// 当前元素数量intcapacity;// 桶数组容量}HashTable;这里有几个设计考量键使用动态字符串通过malloc分配内存确保键的生命周期独立于调用者传入的字符串桶数组存储指针HashNode**的设计使得空桶仅占用一个指针的内存空间效率较好维护size和capacity便于计算负载因子为动态扩容提供依据哈希函数的选择哈希函数的优劣直接影响散列表的性能。理想的哈希函数应当满足计算速度快输出分布均匀减少冲突本实现采用经典的DJB2算法由Daniel J. Bernstein设计staticunsignedlonghashString(constchar*str){unsignedlonghash5381;intc;while((c*str)){hash((hash5)hash)c;// hash * 33 c}returnhash;}该算法的核心在于hash * 33 c其中33的选择经过实践验证在字符串哈希场景下表现良好。初始值5381也是一个经验值有助于减少小字符串的碰撞。动态扩容机制散列表的性能与负载因子Load Factor即元素数量/桶数量密切相关。当负载因子过高时链表长度增加查找效率退化当负载因子过低时空间利用率不足。本实现设置了两个阈值扩容阈值0.75缩容阈值0.125#defineLOAD_FACTOR_THRESHOLD0.75#defineSHRINK_FACTOR_THRESHOLD0.125扩容操作需要重新计算所有元素的哈希值因为桶数量变化后取模运算的结果也会改变staticboolhashTableResize(HashTable*ht,intnewCapacity){HashNode**oldBucketsht-buckets;intoldCapacityht-capacity;// 创建新的桶数组HashNode**newBuckets(HashNode**)calloc(newCapacity,sizeof(HashNode*));if(!newBuckets)returnfalse;ht-bucketsnewBuckets;ht-capacitynewCapacity;// 重新插入所有元素for(inti0;ioldCapacity;i){HashNode*nodeoldBuckets[i];while(node){HashNode*nextnode-next;// 计算新索引并头插法插入intnewIndexgetIndex(ht,node-key);node-nextht-buckets[newIndex];ht-buckets[newIndex]node;nodenext;}}free(oldBuckets);returntrue;}扩容流程如下是否是否否是触发扩容条件创建2倍容量的新桶数组遍历旧桶数组当前桶为空?继续下一个桶遍历链表节点计算新索引头插法插入新桶链表还有节点?遍历完成?释放旧桶数组完成核心操作实现插入操作插入时需要先检查是否需要扩容然后处理两种场景键已存在则更新值键不存在则创建新节点boolhashTablePut(HashTable*ht,constchar*key,intvalue){if(!ht||!key)returnfalse;// 检查是否需要扩容if(getLoadFactor(ht)LOAD_FACTOR_THRESHOLD){if(!hashTableResize(ht,ht-capacity*2)){returnfalse;}}intindexgetIndex(ht,key);HashNode*currentht-buckets[index];// 检查是否已存在该键while(current){if(strcmp(current-key,key)0){current-valuevalue;// 更新值returntrue;}currentcurrent-next;}// 创建新节点并头插HashNode*newNodecreateNode(key,value);if(!newNode)returnfalse;newNode-nextht-buckets[index];ht-buckets[index]newNode;ht-size;returntrue;}采用头插法将新节点插入链表时间复杂度为O(1)无需遍历到链表尾部。查找与删除查找操作遍历对应桶的链表进行字符串比较boolhashTableGet(HashTable*ht,constchar*key,int*outValue){if(!ht||!key||!outValue)returnfalse;intindexgetIndex(ht,key);HashNode*currentht-buckets[index];while(current){if(strcmp(current-key,key)0){*outValuecurrent-value;returntrue;}currentcurrent-next;}returnfalse;}删除操作需要维护前驱指针以正确调整链表连接关系boolhashTableRemove(HashTable*ht,constchar*key){if(!ht||!key)returnfalse;intindexgetIndex(ht,key);HashNode*currentht-buckets[index];HashNode*prevNULL;while(current){if(strcmp(current-key,key)0){if(prev){prev-nextcurrent-next;}else{ht-buckets[index]current-next;}free(current-key);free(current);ht-size--;// 检查是否需要缩容if(ht-capacityINITIAL_CAPACITYgetLoadFactor(ht)SHRINK_FACTOR_THRESHOLD){hashTableResize(ht,ht-capacity/2);}returntrue;}prevcurrent;currentcurrent-next;}returnfalse;}删除后检查缩容条件避免内存浪费。内存管理本实现中所有动态分配的内存都有明确的释放路径节点销毁destroyNodeChain函数遍历链表依次释放键字符串和节点本身表销毁hashTableDestroy遍历所有桶调用节点销毁函数最后释放桶数组和表结构staticvoiddestroyNodeChain(HashNode*node){while(node){HashNode*tempnode;nodenode-next;free(temp-key);free(temp);}}voidhashTableDestroy(HashTable*ht){if(!ht)return;for(inti0;iht-capacity;i){destroyNodeChain(ht-buckets[i]);}free(ht-buckets);free(ht);}测试验证代码包含完整的测试用例覆盖以下场景基本插入和查询值更新删除操作扩容触发与验证键遍历冲突处理验证空值查询通过hashTablePrint函数可以直观观察散列表的内部状态包括各桶的链表分布情况便于调试和理解扩容前后的变化。总结本文介绍的散列表实现虽然代码量不大但涵盖了哈希数据结构的核心要素哈希函数设计、冲突处理、动态扩容、内存管理等。对于需要理解散列表内部机制的开发者或者需要在嵌入式等场景下使用轻量级哈希实现的场景这份代码具有一定的参考价值。完整代码已开源如有问题欢迎交流讨论。⚠️源码地址https://github.com/anjuxi/C-hash_table
