c语言哈希表-云帆数科

一、什么是哈希表哈希表又称为散列表是一种通过键直接映射到存储位置、实现快速存取的数据结构其核心目标是让插入、查找、删除操作的平均时间复杂度达到 O(1)。它由数组和哈希函数组成通过哈希函数将键转换为数组索引从而跳过逐元素比较直接定位数据。二、为什么要用哈希表极致的查找速度O(1)哈希表通过哈希函数把查找变成了直接定位。无论你的表里有多少条数据它都能像数组一样瞬间找到目标。增删改查全面高效不仅查找快它的插入、删除操作同样不需要像链表那样遍历平均时间复杂度都是 O(1) 。空间效率高在判断“元素是否存在”、“两集合求交集”或者“去重统计”时如果用传统的双层循环时间复杂度是 O(n^2)数据过万就会卡顿而用哈希表可以将这类操作的性能提升百倍甚至千倍。三、哈希表的构造方法除留余数法核心思想将关键字除以一个整数取其余数作为散列地址。优点节约空间都能通过取余数的方式把数据集中映射到一段连续的空间里避免了内存浪费。计算高效核心操作就是简单的数学“取模”运算在计算机底层实现起来非常简单计算速度极快。缺点会产生哈希冲突因为是把大量数据压缩到有限的格子里不同的关键字极有可能算出相同的余数从而映射到同一个下标位置引发冲突。对除数的选择非常敏感如果除数选得不好比如选了偶数或10的幂会导致地址分布不均匀发生大量冲突。解决思路除数尽量选质数数学证明表明选取一个小于或等于表长的最大质数作为除数能最大程度打散数据减少冲突。构造的代码如下#includestdio.h#defineTABLE_SIZE10#defineEMPTY-1intmain(){inthashTable[TABLE_SIZE];// 申请一块内存空间定义了一个数组for(inti0;iTABLE_SIZE;i){// 把所有格子初始化为空hashTable[i]EMPTY;}intkey25;// 假设要存入的数字是 25intindexkey%TABLE_SIZE;// 算出下标25 % 10 5hashTable[index]key;// 把 25 放到下标为 5 的格子里printf(构造完成数据 25 被放在了第 %d 个格子里。\n,index);return0;}直接定址法核心思想取关键字的某个线性函数值作为散列地址例如 H(key) key 或者 H(key) a * key b 其中 a 和 b 为常数。优点绝对不会发生冲突因为每个关键字都是一对一映射所以绝不会有两个人被分到同一个柜子的情况。计算简单不需要像除留余数法那样去算余数也不需要考虑什么质数直接就能定位。查找速度极快因为不需要处理冲突只要知道关键字一步就能拿到数据效率极高。缺点空间浪费严重如果关键字的范围很大且非常分散比如用身份证号做关键字就必须开辟一个极其庞大数组。适用场景非常局限它只适合关键字范围比较小、且非常集中的场景比如统计 0~99 岁的人口年龄或者 26 个英文字母的出现频率。构造的代码如下#includestdio.h#defineTABLE_SIZE100// 定义一个“空”的标记用来表示这个格子还没存数据#defineEMPTY-1intmain(){inthashTable[TABLE_SIZE];for(inti0;iTABLE_SIZE;i){hashTable[i]EMPTY;}// 假设我们要存入的数据关键字是 25 和 88intkey125;hashTable[key1]1;// 1 可以代表这个数据出现了1次intkey288;hashTable[key2]1;if(hashTable[25]!EMPTY){//验证一下printf(成功下标 25 的格子里有数据%d\n,hashTable[25]);}return0;}数字分析法核心思想分析关键字的数字分布规律选取分布均匀、重复可能性小的若干位作为哈希地址。平方取中法核心思想将关键字平方后取中间几位作为地址。折叠法核心思想将关键字分割成位数相同的几部分最后一部分位数可以不同然后将这几部分叠加求和作为地址。随机数法核心思想取关键字的随机函数值作为地址。当散列表中关键字长度不等时该方法比较合适。四、哈希冲突两个完全不同的关键字经过哈希函数计算后算出了相同的下标叫哈希冲突。解决方法链地址法(拉链法)在同一个位置上用链表串起来。核心代码// 假设 hashTable 是一个指针数组每个元素指向一个链表头voidinsert_chaining(intkey){intindexhashFunction(key);// 算出初始位置// 申请一个新节点Node*newNode(Node*)malloc(sizeof(Node));newNode-datakey// 头插法newNode-nexthashTable[index];hashTable[index]newNode;}开放地址法(线性探测)发生冲突时从当前位置开始依次往后探测直到找到第一个空位为止。核心代码voidinsert_linear(intkey){intindexhashFunction(key);// 算出初始位置intstartindex;// 记录起点防止无限死循环// 只要当前位置不为空就一直往后找while(hashTable[index]!EMPTY){index(index1)%TABLE_SIZE;// 往后挪一步% 是为了绕回表头// 如果转了一圈回到起点说明表满了if(indexstart)return;}// 3. 找到空位就填进去hashTable[index]key;}

企业数字化 ERP 产品动态

相关推荐

从 Claude Code 到 ABAP Server，彻底看懂 ADT Language Server 与 MCP 的三层架构

这张图只有三个大方框，但真正装进去的东西非常多。它画的并不是一个简单的 AI → MCP → SAP 调用链，而是 SAP 为了把已经存在十多年的 ADT 技术资产，重新包装成一套可以被 GitHub Copilot、Claude Code、Codex、OpenCode 这类 Agent 使用的开发基础设施。尤其到了 2026 … · 2026/11/4 20:00:19

裁员潮下，后端程序员简历写 AI 项目，3 个加分技巧 + 避坑点

前言最近不少后端朋友在准备简历，都会加一个 AI 相关项目，希望在求职内卷里拉开差距。但我看过几十份简历，发现一个普遍问题：简历一句话：基于大模型 API，开发智能问答系统。这种描述，面试官 10… · 2026/11/4 19:59:18

如何做到切surfaceview之后不卡画面

切换surface之后释放老解码器，创建新解码器参数 name 是解码器名称，例如某个设备厂商的硬件解码器。返回 false：条件允许时，直接通过 setOutputSurface() 把现有解码器切到新画面窗口，继续复用它。返回 true&#xff… · 2026/11/4 19:59:18

Folia 手机 PWA：从部署到独立应用安装的完整链路

Folia 手机 PWA：从部署到独立应用安装的完整链路【免费下载链接】folia-major 专注于绚丽的歌词动画效果的本地音乐/navidrome/第三方多平台在线音乐播放器项目地址: https://gitcode.com/GitHub_Trending/fo/folia-major 在地铁里点一下主屏幕上的 Folia … · 2026/11/4 22:14:40

拖拽提交完成变基:GitUp,一款实用的 Mac Git 客户端

拖拽提交完成变基:GitUp,一款实用的 Mac Git 客户端【免费下载链接】GitUp The Git interface youve been missing all your life has finally arrived. 项目地址: https://gitcode.com/gh_mirrors/gi/GitUp 你盯着终端里那串 git rebase -i HEAD~3 愣了五秒——按哪个… · 2026/11/4 22:14:40

shadPS4 到底能不能在 PC 上玩《血源诅咒》？先做 3 项自查

shadPS4 到底能不能在 PC 上玩《血源诅咒》？先做 3 项自查【免费下载链接】shadPS4 PlayStation 4 emulator for Windows, Linux, macOS and FreeBSD written in C 项目地址: https://gitcode.com/GitHub_Trending/sh/shadPS4 shadPS4 是一个 C 编写的 Play… · 2026/11/4 22:14:40

SFML 入门指南：跨平台 C++ 多媒体库的 10 分钟上手手册

SFML 入门指南：跨平台 C 多媒体库的 10 分钟上手手册【免费下载链接】SFML Simple and Fast Multimedia Library 项目地址: https://gitcode.com/gh_mirrors/sf/SFML SFML 是一款免费、跨平台的 C 多媒体库，一次编写即可运行在 Windows、Linux、… · 2026/11/4 22:13:39

如何快速上手 LinkSwift：网盘直链解析完整使用指南

如何快速上手 LinkSwift：网盘直链解析完整使用指南【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 ，支持百度网盘 / 阿里云盘 / 中国移动云盘 / 天翼云盘… · 2026/11/4 22:12:34

Boss Show Time 使用指南：3 步装好插件，在 4 大招聘平台查看岗位发布时间

Boss Show Time 使用指南：3 步装好插件，在 4 大招聘平台查看岗位发布时间【免费下载链接】boss-show-time 展示boss直聘岗位的发布时间项目地址: https://gitcode.com/GitHub_Trending/bo/boss-show-time 刷新搜索页半小时，列表顶部… · 2026/11/4 22:12:34

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49