企业官网建设流程全解析

一、什么是哈希表

• 哈希表又称为散列表，是一种通过键直接映射到存储位置、实现快速存取的数据结构，其核心目标是让插入、查找、删除操作的平均时间复杂度达到 O(1)。它由数组和哈希函数组成，通过哈希函数将键转换为数组索引，从而跳过逐元素比较，直接定位数据。
  

二、为什么要用哈希表

• 极致的查找速度（O(1)）：
  哈希表通过哈希函数，把查找变成了直接定位。无论你的表里有多少条数据，它都能像数组一样瞬间找到目标 。

• 增删改查全面高效：
  不仅查找快，它的插入、删除操作同样不需要像链表那样遍历，平均时间复杂度都是 O(1) 。

• 空间效率高：
  在判断“元素是否存在”、“两集合求交集”或者“去重统计”时，如果用传统的双层循环，时间复杂度是 O(n^2)，数据过万就会卡顿；而用哈希表，可以将这类操作的性能提升百倍甚至千倍 。

三、哈希表的构造方法

1. 除留余数法

• 核心思想：将关键字除以一个整数，取其余数作为散列地址。
• 优点：
  节约空间：都能通过取余数的方式，把数据集中映射到一段连续的空间里，避免了内存浪费 。
  计算高效：核心操作就是简单的数学“取模”运算，在计算机底层实现起来非常简单，计算速度极快 。
• 缺点：
  会产生哈希冲突：因为是把大量数据压缩到有限的格子里，不同的关键字极有可能算出相同的余数，从而映射到同一个下标位置，引发冲突 。
  对除数的选择非常敏感：如果除数选得不好（比如选了偶数或10的幂），会导致地址分布不均匀，发生大量冲突 。
  解决思路：除数尽量选质数，数学证明表明，选取一个小于或等于表长的最大质数作为除数，能最大程度打散数据，减少冲突。

构造的代码如下：

#include<stdio.h>#defineTABLE_SIZE10#defineEMPTY-1intmain(){inthashTable[TABLE_SIZE];// 申请一块内存空间，定义了一个数组for(inti=0;i<TABLE_SIZE;i++){// 把所有格子初始化为空hashTable[i]=EMPTY;}intkey=25;// 假设要存入的数字是 25intindex=key%TABLE_SIZE;// 算出下标：25 % 10 = 5hashTable[index]=key;// 把 25 放到下标为 5 的格子里printf("构造完成，数据 25 被放在了第 %d 个格子里。\n",index);return0;}

2. 直接定址法

• 核心思想：取关键字的某个线性函数值作为散列地址，例如 H(key) = key 或者 H(key) = a * key + b （其中 a 和 b 为常数）。
• 优点：
  绝对不会发生冲突：因为每个关键字都是一对一映射，所以绝不会有两个人被分到同一个柜子的情况。
  计算简单：不需要像除留余数法那样去算余数，也不需要考虑什么质数，直接就能定位。
  查找速度极快：因为不需要处理冲突，只要知道关键字，一步就能拿到数据，效率极高。
• 缺点：
  空间浪费严重：如果关键字的范围很大且非常分散（比如用身份证号做关键字），就必须开辟一个极其庞大数组。
  适用场景非常局限：它只适合关键字范围比较小、且非常集中的场景（比如统计 0~99 岁的人口年龄，或者 26 个英文字母的出现频率）。

构造的代码如下：

#include<stdio.h>#defineTABLE_SIZE100// 定义一个“空”的标记，用来表示这个格子还没存数据#defineEMPTY-1intmain(){inthashTable[TABLE_SIZE];for(inti=0;i<TABLE_SIZE;i++){hashTable[i]=EMPTY;}// 假设我们要存入的数据（关键字）是 25 和 88intkey1=25;hashTable[key1]=1;// 1 可以代表这个数据出现了1次intkey2=88;hashTable[key2]=1;if(hashTable[25]!=EMPTY){//验证一下printf("成功！下标 25 的格子里有数据：%d\n",hashTable[25]);}return0;}

3. 数字分析法
   核心思想：分析关键字的数字分布规律，选取分布均匀、重复可能性小的若干位作为哈希地址。
4. 平方取中法
   核心思想：将关键字平方后，取中间几位作为地址 。
5. 折叠法
   核心思想：将关键字分割成位数相同的几部分（最后一部分位数可以不同），然后将这几部分叠加求和作为地址 。
6. 随机数法
   核心思想：取关键字的随机函数值作为地址。当散列表中关键字长度不等时，该方法比较合适 。

四、哈希冲突

• 两个完全不同的关键字，经过哈希函数计算后，算出了相同的下标，叫哈希冲突 。
  
  解决方法：

1. 链地址法(拉链法)：
   在同一个位置上用链表串起来。
   核心代码：

// 假设 hashTable 是一个指针数组，每个元素指向一个链表头voidinsert_chaining(intkey){intindex=hashFunction(key);// 算出初始位置// 申请一个新节点Node*newNode=(Node*)malloc(sizeof(Node));newNode->data=key；// 头插法newNode->next=hashTable[index];hashTable[index]=newNode;}

2. 开放地址法(线性探测)：
   发生冲突时，从当前位置开始依次往后探测，直到找到第一个空位为止。
   核心代码：

voidinsert_linear(intkey){intindex=hashFunction(key);// 算出初始位置intstart=index;// 记录起点，防止无限死循环// 只要当前位置不为空，就一直往后找while(hashTable[index]!=EMPTY){index=(index+1)%TABLE_SIZE;// 往后挪一步，% 是为了绕回表头// 如果转了一圈回到起点，说明表满了if(index==start)return;}// 3. 找到空位就填进去hashTable[index]=key;}