数据结构---哈希表

一、哈希表的核心思想用函数算位置1.1 为什么需要哈希表我们先看不同数据结构的查找效率数组 / 线性表查找时间复杂度O(n)需要遍历链表查找时间复杂度O(n)需要遍历树二叉搜索树查找时间复杂度O(logN)需要逐层比较。而哈希表的目标是给定一个关键字直接算出它在数组中的位置一步到位找到数据效率接近O(1)。1.2 哈希函数关键字 → 存储位置哈希函数的作用是把任意长度的输入关键字变换成固定长度的输出数组下标这个输出就是数据的存储位置。最常用的哈希函数是取余法哈希地址 关键字 % 数组长度示例关键字集合18, 23, 45, 62, 71, 85数组长度为 1018 % 10 8→ 存在数组下标 8 的位置23 % 10 3→ 存在数组下标 3 的位置45 % 10 5→ 存在数组下标 5 的位置62 % 10 2→ 存在数组下标 2 的位置71 % 10 1→ 存在数组下标 1 的位置85 % 10 5→ 存在数组下标 5 的位置。可以看到45和85都映射到了下标 5这就产生了哈希冲突。二、哈希冲突不可避免的问题2.1 什么是哈希冲突当两个不同的关键字通过同一个哈希函数计算出相同的哈希地址时就发生了哈希冲突也叫碰撞。本质原因哈希函数的输入空间关键字集合远大于输出空间数组下标集合根据鸽巢原理冲突不可避免我们只能想办法「处理冲突」。2.2 处理哈希冲突的两种经典方法方法 1开放地址法核心思想如果当前位置被占了就向后找下一个空位置存放数据比如线性探测、二次探测。优点实现简单只需要数组缺点容易产生「堆积」冲突数据挤在一起查找效率下降。方法 2链地址法拉链法最常用核心思想数组的每个位置不是存数据而是存一个链表的头指针所有冲突的节点都挂在同一个链表上。优点不会产生堆积删除操作方便缺点需要额外的链表指针开销。本文重点讲解链地址法这也是工业界最常用的冲突处理方式。三、链地址法哈希表结构与实现3.1 链地址法的结构哈希表由两部分组成哈希数组每个元素是一个链表的头指针链表节点存储数据和指向下一个节点的指针。结构示意图下标0 1 2 3 4 5 6 7 8 9 | | | | | | | | | | ∅ 71 → ∅ 23 → ∅ 45 → 85 → ∅ ∅ 18 → ∅ ∅下标 1 的链表71下标 3 的链表23下标 5 的链表45 → 85冲突数据挂在同一条链表上下标 8 的链表18。3.2 C 语言结构定义#include stdio.h #include stdlib.h #include string.h // 数据类型别名可根据需求修改为int、char*等 typedef int data_t; // 链表节点结构 typedef struct node { data_t data; // 数据域 struct node *next; // 指针域指向下一个冲突节点 } node_t; // 哈希表大小可根据需求调整通常取质数 #define HASH_SIZE 10 // 哈希表数组每个元素是链表头指针 node_t *hash_table[HASH_SIZE] {NULL};3.3 哈希函数实现取余法// 哈希函数取余法 int hash_func(data_t data) { return data % HASH_SIZE; }3.4 插入数据链地址法// 哈希表插入数据 int hash_insert(data_t data) { // step1: 计算哈希地址数组下标 int index hash_func(data); // step2: 创建新节点并赋值 node_t *p_new (node_t *)malloc(sizeof(node_t)); if (p_new NULL) { printf(内存分配失败\n); return -1; } p_new-data data; p_new-next NULL; // step3: 头插法插入链表新节点放在链表头部 p_new-next hash_table[index]; // 新节点指向原链表头 hash_table[index] p_new; // 哈希表数组指向新节点 return 0; }核心逻辑新节点总是插在链表头部这样插入操作是 O (1) 时间复杂度。3.5 查找数据先算位置再遍历链表// 哈希表查找数据找到返回节点地址未找到返回NULL node_t *hash_find(data_t data) { // step1: 计算哈希地址 int index hash_func(data); // step2: 遍历对应链表 node_t *p hash_table[index]; while (p ! NULL) { if (p-data data) { return p; // 找到目标节点 } p p-next; } return NULL; // 未找到 }3.6 遍历哈希表打印所有数据// 遍历哈希表 void hash_show() { for (int i 0; i HASH_SIZE; i) { printf(下标 %d, i); node_t *p hash_table[i]; if (p NULL) { printf(∅\n); continue; } // 遍历链表 while (p ! NULL) { printf(%d → , p-data); p p-next; } printf(∅\n); } }3.7 销毁哈希表释放所有内存// 销毁哈希表 void hash_destroy() { for (int i 0; i HASH_SIZE; i) { node_t *p hash_table[i]; while (p ! NULL) { node_t *temp p; p p-next; free(temp); // 释放节点 } hash_table[i] NULL; // 置空指针 } }3.8 完整测试代码int main() { // 插入测试数据 data_t arr[] {18, 23, 45, 62, 71, 85, 94, 34}; int len sizeof(arr) / sizeof(arr[0]); for (int i 0; i len; i) { hash_insert(arr[i]); } // 遍历哈希表 printf(哈希表内容\n); hash_show(); // 查找测试 node_t *p hash_find(85); if (p ! NULL) { printf(\n找到数据%d\n, p-data); } else { printf(\n未找到数据\n); } // 销毁哈希表 hash_destroy(); return 0; }运行结果哈希表内容 下标 0∅ 下标 171 → ∅ 下标 262 → ∅ 下标 323 → ∅ 下标 434 → 94 → ∅ 下标 585 → 45 → ∅ 下标 6∅ 下标 7∅ 下标 818 → ∅ 下标 9∅ 找到数据85四、哈希表的核心指标负载因子4.1 什么是负载因子负载因子Load Factor是衡量哈希表「拥挤程度」的指标负载因子 哈希表中元素个数 / 哈希表数组长度4.2 负载因子的意义负载因子越小冲突概率越低查找效率越高但空间浪费越多负载因子越大冲突概率越高查找效率越低但空间利用率越高。工业界通常将负载因子控制在 0.7~0.8 之间超过这个阈值就需要扩容重新哈希。五、哈希表 vs 其他数据结构数据结构查找时间复杂度插入 / 删除时间复杂度空间复杂度适用场景数组 / 线性表O(n)O(n)O(n)数据量小、频繁遍历链表O(n)O (1)已知位置O(n)频繁插入 / 删除二叉搜索树O(logN)O(logN)O(n)数据有序、范围查询哈希表O (1)平均O (1)平均O(n)高频查找、键值对存储六、总结与学习建议6.1 核心知识点回顾哈希表核心通过哈希函数将关键字映射到数组位置实现 O (1) 平均查找效率哈希冲突不可避免最常用的处理方法是链地址法数组 链表链地址法每个数组位置是链表头冲突节点挂在链表上核心操作插入头插法、查找算位置 遍历链表、遍历、销毁负载因子控制哈希表拥挤程度超过阈值需要扩容。