超适合初学者——哈希表的C语言简单实现

Ne0inhk

— 12 min read

文章目录

哈希表

1.为什么需要哈希表?

从一个实际问题开始，比如在10万条学生记录中，如何通过学号快速找到某个学生的信息？

  • 如果用数组，需要遍历，O(n)时间复杂度，太慢
  • 如果用链表，同样需要遍历
  • 如果学号直接作为数组下标呢？但如果学号是字符串（如”S20240001“）或者范围很大（如0-10亿），直接作为下标会浪费巨大内存

这时，我们需要一种结构，既能像数组一样通过“下标”快速访问，又能灵活处理各种类型的键并节省空间。这就是哈希表

2. 哈希表的核心思想

  • 核心概念： 将任意长度的键（Key）通过一个哈希函数 映射到一个固定范围的数组下标。
  • 工作流程：
    1. 存储（Put）：键(Key) -> 哈希函数 -> 数组索引(Index) -> 在索引处存储值(Value)
    2. 查找（Get）：键(Key) -> 哈希函数 -> 数组索引(Index) -> 从索引处读取值(Value)
  • 哈希表的要素：
要素作用（解释）
键（key）节点编号
值（value)节点信息
索引（index）数组的下标，用以快速定位和检索数据
哈希桶保存索引的数组（链表），数组成员为每一个索引值相同的多个元素
哈希函数将一个较大的输入空间映射到一个较小的输出空间，即将节点编号映射到索引上，采用求余法

3. 哈希冲突

  • 什么是哈希冲突？

两个不同的键，经过哈希函数计算后，得到了相同的数组索引，这就是哈希冲突

  • 解决方案：
    1. 链地址法：
      • 思想：数组的每一个元素不是一个值，而是一个链表（或其他结构）的头指针。所有映射到同一索引的键值对都放在这个链表里
      • 优缺点:
        • 优点：简单有效，易于实现
        • 缺点：需要额外的指针存储空间
    2. 开放地址法：
      • 思想：当发生冲突时，按照某种探测序列在哈希表中寻找下一个空闲位置
      • 探测方法:
        • 线性探测：index = (hash(key) + i) % table_size
        • 二次探测：index = (hash(key) + i²) % table_size
        • 双重散列：index = (hash1(key) + i * hash2(key)) % table_size
      • 优缺点：
        • 优点：所以数据都存储在数组中
        • 缺点：删除操作复杂

4. C语言实现简单哈希表

4.1 定义

#include<stdio.h>#include<stdlib.h>#include<math.h>//定义哈希表节点typedefstructHashNode{int key;//键int value;//值structHashNode* next;//下一节点}HashNode;//定义哈希表typedefstruct{ HashNode** table;//存储哈希表中各个桶的头指针(指针的指针）int size;//哈希表大小int count;//元素个数}HashTable;

4.2 创建哈希表

//创建哈希表 HashTable*createHashTable(int size){if(size <=0){printf("哈希表大小必须大于0\n");returnNULL;} HashTable* hashTable =(HashTable*)malloc(sizeof(HashTable));if(hashTable ==NULL){printf("内存分配失败\n");returnNULL;} hashTable->size = size; hashTable->count =0;//初始化元素数量 hashTable->table =(HashNode**)malloc(sizeof(HashNode*)* size);if(hashTable->table ==NULL){printf("内存分配失败\n");free(hashTable);returnNULL;}//初始化所有桶为空for(int i =0; i < size; i++){ hashTable->table[i]=NULL;}printf("创建哈希表成功，大小为：%d\n",size);return hashTable;}

代码说明：

  • 函数声明，返回HashTable指针，参数size为哈希表大小，即哈希桶的个数
  • 分配HashTable结构体的内存空间，初始化哈希表：
    • size：设置哈希表的大小（哈希桶的数量）
    • count：当前哈希表内的元素数量初始化为0
  • 再为哈希桶分配内存（每个桶都是一个HashNode*的指针）：遍历所有桶，将每个桶都初始化为NULL
  • 最后，返回创建好的哈希表指针

4.3 哈希函数

//哈希函数inthashFunction(HashTable* hashTable,int key){returnabs(key)% hashTable->size;}

代码说明：

  • 计算并返回哈希值
    • 取key的绝对值，避免负数导致计算出的哈希值为负数（数组索引不能为负数）
    • 取模：将key映射到[0,hashTable->size - 1]的范围内，确保哈希值在哈希表的有效索引范围内

4.4 插入哈希表

//插入哈希表intinsertHash(HashTable* hashTable,int key,int value){if(hashTable ==NULL){printf("哈希表为空，无法插入\n");return0;//插入失败}int hashIndex =hashFunction(hashTable, key);//检查键是否已经存在 HashNode* curNode = hashTable->table[hashIndex];while(curNode !=NULL){if(curNode->key == key){ curNode->value = value;printf("更新键：%d\n", key);return2;//更新操作} curNode = curNode->next;}//创建新节点 HashNode* newNode =(HashNode*)malloc(sizeof(HashNode));if(newNode ==NULL){printf("内存分配失败\n");return0;} newNode->key = key; newNode->value = value;//插入到链表头部 newNode->next = hashTable->table[hashIndex]; hashTable->table[hashIndex]= newNode; hashTable->count++;return1;//插入成功}

代码说明：

  • 首先，检查哈希表指针是否为空，若为空，则插入失败，返回0
  • 接着，计算哈希索引：
    • 调用前面的哈希函数HashFunction，根据key计算应该存储在哪个桶里
    • 检查键是否存在：
      • 获取对应桶的链表头指针
      • 遍历链表
      • 若找到相同的key：更新value值，返回2，表示更新；若未找到，则说明key不存在，需要插入新节点
  • 创建新节点，设置新节点的键值对，再将其插入链表头部（头插法）
  • 最后增加哈希表的元素个数，返回1，表示插入成功

4.5 查找哈希表

//查找哈希表intsearchHash(HashTable* hashTable,int key,int* value){if(hashTable ==NULL|| value ==NULL){return0;}int hashIndex =hashFunction(hashTable, key); HashNode* curNode = hashTable->table[hashIndex];while(curNode !=NULL){if(curNode->key == key){*value = curNode->value;return1;//找到} curNode = curNode->next;}return0;//没找到}

代码说明：

  • 该函数中的参数分别为：哈希表指针HashTable* hashTable、要查找的目标键int key、输出参数，用来存储找到的值int* value
  • 检查哈希表指针和输出参数指针是否为空
  • 接着，计算哈希索引：
    • 调用hashFunction函数
    • 计算key对应的桶索引
    • 获取对应桶的链表头指针，直接访问哈希表的桶数组
  • 遍历链表，找到匹配的key，将值赋给输出参数*value

4.6 删除哈希表

//删除哈希表intDeleteHash(HashTable* hashTable,int key){if(hashTable ==NULL){printf("哈希表为空，无法删除\n");return0;//删除失败}int hashIndex =hashFunction(hashTable, key); HashNode* curNode = hashTable->table[hashIndex]; HashNode* prevNode =NULL;while(curNode !=NULL){if(curNode->key == key){if(prevNode ==NULL){//删除头节点 hashTable->table[hashIndex]= curNode->next;}else{//删除中间或尾部节点 prevNode->next = curNode->next;}free(curNode); hashTable->count--;printf("删除成功\n");return1;//删除成功} prevNode = curNode; curNode = curNode->next;}printf("删除失败\n");return0;//未找到键，删除失败}

代码说明：

  • 检查哈希表指针是否为空
  • 计算哈希索引：
    • 调用hashFunction函数
    • 计算key对应的桶索引
  • 遍历链表查找目标键：
    • curNode：当前节点指针，初始化为链表头；prevNode：前驱节点指针，初始化为NULL
    • 循环直到链表末尾
    • 检查当前节点的key是否匹配目标key
  • 找到后，进行删除操作：
    • 删除头节点（prevNode == NULL）
      • 将桶的头指针指向当前节点的下一个节点
      • 直接跳过要删除的节点
    • 删除中间或尾部节点
      • 将前驱节点的next指针指向当前节点的下一个节点
      • 跳过要删除的节点
    • 删除：
      • free(curNode)：释放被删除节点的内存
      • hashTable->count--：减少哈希表元素个数

4.7 释放哈希表

//释放哈希表voidfreeHash(HashTable* hashTable){if(hashTable ==NULL){return;}for(int i =0; i < hashTable->size; i++){ HashNode* curNode = hashTable->table[i];while(curNode !=NULL){ HashNode* temp = curNode; curNode = curNode->next;free(temp);}}free(hashTable->table);free(hashTable);}

代码说明：

  • 检查哈希表指针是否为空
  • 遍历所有桶----->遍历当前桶的链表----->释放所有节点
  • 释放桶数组内存
  • 释放哈希表结构体内存

4.8 完整测试

#include<stdio.h>#include<stdlib.h>#include<math.h>//定义哈希表节点typedefstructHashNode{int key;//键int value;//值structHashNode* next;//下一节点}HashNode;//定义哈希表typedefstruct{ HashNode** table;//存储哈希表中各个桶的头指针(指针的指针）int size;//哈希表大小int count;//元素个数}HashTable;//创建哈希表 HashTable*createHashTable(int size){if(size <=0){printf("哈希表大小必须大于0\n");returnNULL;} HashTable* hashTable =(HashTable*)malloc(sizeof(HashTable));if(hashTable ==NULL){printf("内存分配失败\n");returnNULL;} hashTable->size = size; hashTable->count =0;//初始化元素数量 hashTable->table =(HashNode**)malloc(sizeof(HashNode*)* size);if(hashTable->table ==NULL){printf("内存分配失败\n");free(hashTable);returnNULL;}//初始化所有桶为空for(int i =0; i < size; i++){ hashTable->table[i]=NULL;}printf("创建哈希表成功，大小为：%d\n",size);return hashTable;}//哈希函数inthashFunction(HashTable* hashTable,int key){returnabs(key)% hashTable->size;}//插入哈希表intinsertHash(HashTable* hashTable,int key,int value){if(hashTable ==NULL){printf("哈希表为空，无法插入\n");return0;//插入失败}int hashIndex =hashFunction(hashTable, key);//检查键是否已经存在 HashNode* curNode = hashTable->table[hashIndex];while(curNode !=NULL){if(curNode->key == key){ curNode->value = value;printf("更新键：%d\n", key);return2;//更新操作} curNode = curNode->next;}//创建新节点 HashNode* newNode =(HashNode*)malloc(sizeof(HashNode));if(newNode ==NULL){printf("内存分配失败\n");return0;} newNode->key = key; newNode->value = value;//插入到链表头部 newNode->next = hashTable->table[hashIndex]; hashTable->table[hashIndex]= newNode; hashTable->count++;printf("插入成功: 键=%d, 值=%d\n", key, value);return1;//插入成功}//查找哈希表intsearchHash(HashTable* hashTable,int key,int* value){if(hashTable ==NULL|| value ==NULL){return0;}int hashIndex =hashFunction(hashTable, key); HashNode* curNode = hashTable->table[hashIndex];while(curNode !=NULL){if(curNode->key == key){*value = curNode->value;return1;//找到} curNode = curNode->next;}return0;//没找到}//删除哈希表中的节点intDeleteHash(HashTable* hashTable,int key){if(hashTable ==NULL){printf("哈希表为空，无法删除\n");return0;//删除失败}int hashIndex =hashFunction(hashTable, key); HashNode* curNode = hashTable->table[hashIndex]; HashNode* prevNode =NULL;while(curNode !=NULL){if(curNode->key == key){if(prevNode ==NULL){//删除头节点 hashTable->table[hashIndex]= curNode->next;}else{//删除中间或尾部节点 prevNode->next = curNode->next;}free(curNode); hashTable->count--;printf("删除键 %d 成功\n", key);return1;//删除成功} prevNode = curNode; curNode = curNode->next;}printf("删除失败，未找到键: %d\n", key);return0;//未找到键，删除失败}// 打印哈希表内容voidprintHashTable(HashTable* hashTable){if(hashTable ==NULL){printf("哈希表为空\n");return;}printf("\n=== 哈希表状态 ===\n");printf("大小: %d, 元素个数: %d\n", hashTable->size, hashTable->count);for(int i =0; i < hashTable->size; i++){if(hashTable->table[i]!=NULL){printf("桶[%d]: ", i); HashNode* curNode = hashTable->table[i];while(curNode !=NULL){printf("(%d:%d)", curNode->key, curNode->value);if(curNode->next !=NULL){printf(" -> ");} curNode = curNode->next;}printf("\n");}}printf("=================\n");}//释放哈希表voidfreeHash(HashTable* hashTable){if(hashTable ==NULL){return;}for(int i =0; i < hashTable->size; i++){ HashNode* curNode = hashTable->table[i];while(curNode !=NULL){ HashNode* temp = curNode; curNode = curNode->next;free(temp);}}free(hashTable->table);free(hashTable);printf("哈希表已释放\n");}//测试函数intmain(){printf("===== 哈希表测试程序 =====\n");//创建哈希表 HashTable* ht =createHashTable(5);if(ht ==NULL){return1;}//测试插入printf("\n1. 测试插入操作:\n");insertHash(ht,1,100);insertHash(ht,6,200);// 冲突：1和6在同一桶（1%5=1, 6%5=1）insertHash(ht,11,300);// 继续冲突（11%5=1）insertHash(ht,2,400);insertHash(ht,3,500);//打印当前状态printHashTable(ht);//测试更新printf("\n2. 测试更新操作:\n");insertHash(ht,1,150);// 更新键1的值printHashTable(ht);//测试查找printf("\n3. 测试查找操作:\n");int value;if(searchHash(ht,6,&value)){printf("找到键 6, 值为: %d\n", value);}else{printf("未找到键 6\n");}if(searchHash(ht,99,&value)){printf("找到键 99, 值为: %d\n", value);}else{printf("未找到键 99\n");}//测试删除printf("\n4. 测试删除操作:\n");DeleteHash(ht,6);DeleteHash(ht,99);// 删除不存在的键printHashTable(ht);//测试负键值printf("\n5. 测试负键值:\n");insertHash(ht,-4,600);// abs(-4)%5 = 4insertHash(ht,-9,700);// abs(-9)%5 = 4（冲突）printHashTable(ht);//清理freeHash(ht);return0;}

结果：

===== 哈希表测试程序 ===== 创建哈希表成功，大小为：5 1. 测试插入操作: 插入成功: 键=1, 值=100 插入成功: 键=6, 值=200 插入成功: 键=11, 值=300 插入成功: 键=2, 值=400 插入成功: 键=3, 值=500 === 哈希表状态 === 大小: 5, 元素个数: 5 桶[1]: (11:300) -> (6:200) -> (1:100) 桶[2]: (2:400) 桶[3]: (3:500) ================= 2. 测试更新操作: 更新键：1 === 哈希表状态 === 大小: 5, 元素个数: 5 桶[1]: (11:300) -> (6:200) -> (1:150) 桶[2]: (2:400) 桶[3]: (3:500) ================= 3. 测试查找操作: 找到键 6, 值为: 200 未找到键 99 4. 测试删除操作: 删除键 6 成功 删除失败，未找到键: 99 === 哈希表状态 === 大小: 5, 元素个数: 4 桶[1]: (11:300) -> (1:150) 桶[2]: (2:400) 桶[3]: (3:500) ================= 5. 测试负键值: 插入成功: 键=-4, 值=600 插入成功: 键=-9, 值=700 === 哈希表状态 === 大小: 5, 元素个数: 6 桶[1]: (11:300) -> (1:150) 桶[2]: (2:400) 桶[3]: (3:500) 桶[4]: (-9:700) -> (-4:600) ================= 哈希表已释放

Read more

用 Python 构建跨平台前端界面：深入解读 Flet 库

一、Flet 是什么？ 在过去的很长一段时间里，构建用户界面（UI）往往是 Python 开发者的“短板”。虽然我们有 Tkinter、PyQt、wxPython 等 GUI 工具，但它们或过于陈旧、或依赖庞大的桌面框架，难以适应现代前端的体验。而 Web 前端则需要掌握 HTML/CSS/JavaScript，学习成本高、调试复杂。 于是，Flet 出现了。 Flet 是一个使用 Python 构建现代 Web、桌面和移动应用的框架，它的目标是让开发者只使用 Python 就可以完成跨平台 UI 应用的开发。 简而言之：像写命令行脚本一样用 Python 写 Web 前端界面，跨平台自动适配。 1.

By Ne0inhk
【2025保姆级】Open-WebUI五大功能区首曝！第一篇：管理员面板深度拆解，手把手讲解&配置AI管理中枢

【2025保姆级】Open-WebUI五大功能区首曝！第一篇：管理员面板深度拆解，手把手讲解&配置AI管理中枢

【2025保姆级】Open-WebUI五大功能区首曝！第一篇：管理员面板深度拆解，手把手讲解&配置AI管理中枢 * 一、引言 * 二、用户 * 2.1 概述 * 2.2 权限组 * 三、竞技场评估 * 四、函数 * 五、设置 * 5.1 通用 * 5.1.1 身份验证 * 5.1.2 功能 * 5.2 外部连接 * 5.2.1 OpenAI API * 5.2.2 Ollama API * 5.2.3

By Ne0inhk

Clawdbot整合Qwen3-32B保姆级教程：Web网关18789端口调试全记录

Clawdbot整合Qwen3-32B保姆级教程：Web网关18789端口调试全记录 1. 为什么需要这个整合方案 你是不是也遇到过这样的问题：想用本地部署的大模型做聊天机器人，但发现直接调用Ollama的API在Web前端里跨域报错？或者Clawdbot配置完后一直连不上模型，控制台疯狂刷404？又或者好不容易跑起来了，发个消息却卡在“正在思考”半天没反应？ 这正是我们搭建这套环境时踩过的坑。Clawdbot本身不直接对接Ollama，它需要一个中间层来处理协议转换、请求转发和端口映射。而18789这个端口，就是整个链路里最关键的“通关密码”——它不是随便选的，而是Clawdbot默认监听的Web网关入口。 整套方案的核心逻辑其实很朴素： * 你在浏览器里访问 http://localhost:18789，看到的是Clawdbot的聊天界面 * Clawdbot收到你的消息后，不自己去算答案，而是把请求转给内部代理 * 代理再把请求发到 http://localhost:8080（Ollama API地址） * Ollama调用本地的Qwen3-32B模型生成回复

By Ne0inhk

前端设计模式详解

前端设计模式全面解析 一、设计模式概述 1.1 什么是设计模式 设计模式是针对特定上下文的常见问题的可重用解决方案。在前端开发中，它们帮助我们构建可维护、可扩展、可重用的代码。 1.2 设计模式分类 * 创建型模式：处理对象创建机制 * 结构型模式：处理对象组合方式 * 行为型模式：处理对象间的通信和责任分配 二、创建型模式 2.1 工厂模式（Factory Pattern） 将对象创建逻辑封装起来。 // 简单工厂classButtonFactory{createButton(type){switch(type){case'primary':returnnewPrimaryButton();case'secondary':returnnewSecondaryButton();default:thrownewError('Unknown button type'

By Ne0inhk