一、什么是哈希表哈希表又称为散列表是一种通过键直接映射到存储位置、实现快速存取的数据结构其核心目标是让插入、查找、删除操作的平均时间复杂度达到 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;} 
长河君 · 2026/11/4 20:01:20 · 阅读 1.2k 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;}