408真题解析-2010-41-数据结构-散列表一 真题2010-题号2010-41.10分将关键字序列7, 8, 30, 11, 18, 9, 14散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组散列函数为H ( k e y ) ( k e y × 3 ) m o d 7 H(key)(key×3)mod 7H(key)(key×3)mod7处理冲突采用线性探测再散列法要求装填因子为0.7。1请画出所构造的散列表2分别计算等概率情况下查找成功和查找不成功的平均查找长度。二 题目要素解析核心考点散列表构造、线性探测法处理冲突、装填因子计算、平均查找长度 ASL。考查知识点装填因子公式$ \alpha \frac{\text{表中填入元素个数}}{\text{散列表长度}} $散列函数计算线性探测法$ H_i (H(key) i) \mod m, \quad i 0, 1, 2, \ldots $查找成功 ASL所有关键字查找次数之和 / 关键字个数查找不成功 ASL所有散列地址探测到空位置次数之和 / 散列函数取值数题型特征给定序列、哈希函数、冲突处理、装填因子 → 建表 算 ASL。易错点先算表长 m再算哈希地址线性探测时从 i0 开始计数比较 1 次算 1 次查找不成功分母是散列函数模值 m不是元素个数大纲 / 教材对应数据结构 – 查找 – 散列表哈希表三 哔哔详解✅步骤1确定散列表长度关键字数量 $ n 7 $装填因子 $ \alpha 0.7 \frac{n}{m} \rightarrow m \frac{7}{0.7} 10 $散列表下标范围$ 0 \sim 9 $共10个单元✅步骤2逐个插入关键字线性探测关键点散列函数结果 $ h_0 (key \times 3) \mod 7 $ 是初始探测位置但实际探测在长度为10的表中进行即若 $ h_0 $ 冲突则探测 $ (h_0 1) \mod 10 $, $ (h_0 2) \mod 10 $, …关键字$ h_0 (key×3) \mod 7 $探测过程模10最终位置查找成功比较次数7(7×3) mod 7 21 mod 7 00空→ 插入018(8×3) mod 7 24 mod 7 33空→ 插入3130(30×3) mod 7 90 mod 7 690÷712*784, 余66空→ 插入6111(11×3) mod 7 33 mod 7 533-2855空→ 插入5118(18×3) mod 7 54 mod 7 554-4955占→ 6占→ 7空73探5,6,79(9×3) mod 7 27 mod 7 627-2166占→ 7占→ 8空83探6,7,814(14×3) mod 7 42 mod 7 00占→ 1空→ 插入12探0,1 易错警示散列函数结果 $ h_0 $ 是 0 - 6但探测空间是0 - 9表长10线性探测公式 $ (h_0 i) \mod 10 $不是 $ \mod 7 $✅ 步骤3绘制散列表地址0123456789关键字71481130189✅ 步骤4计算平均查找长度ASL(1) 查找成功 ASL- 每个关键字查找成功的比较次数 插入时的探测次数见上表 - $ \text{ASL}_{\text{成功}} \frac{1211331}{7} \frac{12}{7} \approx 1.714 $(2) 查找不成功 ASL- 关键原则对散列函数所有可能输出值0~6计算探测次数因 $ h_0 \in {0,1,2,3,4,5,6} $ - 对每个 $ h_0 \in {0,1,2,3,4,5,6} $模拟查找失败过程直到遇到空单元探测序列模10失败位置比较次数00(7)→1(14)→2(空)2311(14)→2(空)2222(空)2133(8)→4(空)4244(空)4155(11)→6(30)→7(18)→8(9)→9(空)9566(30)→7(18)→8(9)→9(空)94说明$ h_0 0 $探0(有)→1(有)→2(空) → 比较3次$ h_0 5 $探5(有)→6(有)→7(有)→8(有)→9(空) → 比较5次仅考虑 $ h_0 0 $ 到 $ 6 $因散列函数输出范围是0~6$ \text{ASL}_{\text{不成功}} \frac{3212154}{7} \frac{18}{7} \approx 2.571 $四 参考答案1散列表地址0123456789关键字714—8—1130189—2查找成功 ASL $ \dfrac{12}{7} $查找不成功 ASL $ \dfrac{18}{7} $五 强相关知识点5.1 本题重要知识点概念说明408高频陷阱装填因子$ \alpha \frac{n}{m} $ → 求表长 m误用 $ m7 $ 混淆模数与表长线性探测范围在 表长 m 的空间 中探测非散列函数模数探测时错误使用 mod 7ASL不成功对 散列函数所有输出值 计算本题0~6错误对地址0~9全部计算探测终止条件查找失败遇到空单元即停止继续探测到表尾5.2 线性探测再散列法一、基本概念 定义线性探测再散列法Linear Probing是开放定址法Open Addressing中最简单的一种冲突处理策略当发生哈希冲突时顺序检查散列表中下一个相邻位置模表长直到找到空单元或匹配关键字。 探测序列公式H i ( H ( k e y ) i ) m o d m , i 0 , 1 , 2 , … , m − 1 H_i (H(key) i) \mod m, \quad i 0, 1, 2, \ldots, m-1Hi(H(key)i)modm,i0,1,2,…,m−1$ H(key) $初始哈希地址由给定哈希函数计算$ i $探测次数从0开始 - $ m $散列表长度注意模的是表长 $ m $不是哈希函数的模数 插入/查找流程计算初始地址 $ h_0 H(key) $若 $ T[h_0] $ 为空 → 插入 / 查找失败 3.若 $ T[h_0] $ 被占但关键字 ≠ key → 探测 $ h_1 (h_0 1) \mod m $重复步骤 2-3直到找到空位插入或匹配项成功或遍历全表失败二、性质与特征性质说明408考查意义聚集现象Primary Clustering冲突导致连续占用块使后续冲突更易发生形成“雪球效应”解释ASL增大的根本原因空间局部性好连续内存访问缓存命中率高对比链地址法的指针跳转装填因子敏感α 0.7 时性能急剧下降408要求 α ≤ 0.7计算表长的关键约束删除需特殊标记不能直接置空会截断探测链需用“删除标记”理解开放定址法删除复杂性探测路径唯一分析查找失败探测次数的基础三、与其他探测法对比408核心辨析特性线性探测二次探测双散列链地址法冲突处理开放定址开放定址开放定址链式结构探测公式$ (Hi) \mod m $$ (H \pm i^2) \mod m $$ (H_1 i \cdot H_2) \mod m $头插/尾插链表聚集问题一次聚集严重二次聚集较轻无聚集无聚集空间开销无额外指针无额外指针无额外指针需指针域≈50%开销ASL成功$ \approx \frac{1}{2}(1\frac{1}{1-\alpha}) $优于线性最优$ 1\frac{\alpha}{2} $ASL不成功$ \approx \frac{1}{2}(1\frac{1}{(1-\alpha)^2}) $优于线性最优$ 1\alpha $408考查频率⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐关键区别总结开放定址 vs 链地址开放定址所有元素存表内表长 ≥ 元素数$ \alpha \leq 0.7 $链地址元素可超表长表长 桶数$ \alpha $ 可 1线性 vs 二次探测线性$ i 1, 2, 3, \ldots $ → 严格顺序二次$ i 1^2, -1^2, 2^2, -2^2, \ldots $ → 跳跃探测需 $ m $ 为质数且 $ \alpha \leq 0.5 $ASL计算差异开放定址$ \text{ASL}{\text{不成功}} $ 远大于 $ \text{ASL}{\text{成功}} $因需探完整个簇链地址$ \text{ASL}{\text{不成功}} \approx \text{ASL}{\text{成功}} $仅多1次指针判断六 扩展知识点七 核心考点考点1散列表构造★★★★★关键陷阱混淆 哈希函数模数 与 表长 $ m $例$ H(key) key \mod 7 $但表长 $ m 10 $ → 探测用 $ \mod 10 $忽略 装填因子求表长$ m \lceil n / \alpha \rceil $真题锚点2010-41、2019-42 考点2ASL计算★★★★★ASL类型计算规则易错点查找成功$ \frac{\sum \text{每个关键字的探测次数}}{n} $探测次数 插入时比较次数查找不成功$ \frac{\sum_{h0}^{r-1} \text{从 } h \text{ 开始探测到空的次数}}{r} $ $ r $ 哈希函数值域大小仅对哈希函数输出值计算如 $ H(key)key\mod7 $ → $ r7 $ ✅口诀“成功看插入不成功看函数值函数模几就除几表长只管探测域” 考点3聚集现象分析★★★问题形式“为什么线性探测在高装填因子下效率低”标准答案“因一次聚集Primary Clustering导致冲突元素形成连续簇增加后续探测长度”八 408考研大纲和教材对应章节项目内容408考纲“散列表散列函数、冲突处理线性探测、ASL计算”严蔚敏《数据结构》第9章 9.3节“散列表”P257-265ASL计算例题九 考点跟踪年份题号考查内容CSDN 参考链接VX参考链接2010第41题散列表 线性探测408真题解析-2010-41-数据结构-散列表说明本文内容基于公开资料整理参考了包括但不限于《数据结构》严蔚敏、《计算机操作系统》汤小丹、《计算机网络》谢希仁、《计算机组成原理》唐朔飞等国内高校经典教材以及其他国际权威著作。同时借鉴了王道、天勤、启航等机构出版的计算机专业考研辅导系列丛书中的知识体系框架与典型题型分析思路。文中所有观点、例题解析及文字表述均为作者结合自身理解进行的归纳与重述未直接复制任何出版物原文。内容仅用于学习交流若有引用不当或疏漏之处敬请指正。