尧图网站建设 
文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载导读本文基于开源仓库 gh_mirrors/cl/CLRS 中的 11.1.md对《算法导论》Introduction to Algorithms第 11 章散列表Hash Tables第 1 节直接寻址表Direct-Address Tables的四道课后习题进行逐题精解。读完本文你将掌握直接寻址表的最坏情况分析、位向量bit vector表示法、含卫星数据与重复键时的链表实现以及大数组延迟初始化这一经典面试级技巧如何用 O(1) 时间初始化一个巨大的直接寻址表。文中所有结论均以仓库文档为依据并联动 11.211.5 节的散列技术作为延伸。一、背景什么是直接寻址表直接寻址表是散列思想最朴素的形态。当全域universeU 中的键都是 0 到 m-1 之间的整数时我们可以直接用一个长度为 m 的数组 T 作为字典键 k 的元素存放在T[k]中不需要任何散列函数因为键本身即可作为数组下标。若T[k] NIL表示字典中没有键 k 的元素查找SEARCH、插入INSERT、删除DELETE三个字典操作都只需 O(1) 时间。它的致命缺点是空间效率当全域很大而实际存储的键很少时分配一个大小为 |U| 的数组完全不现实。这也正是后续章节引入散列函数11.3.md的根本动机——把大域中的键压缩映射到较小的表上。11.1 节的四道习题正是围绕直接寻址表的O(1) 时间、O(m) 空间这一基本性质展开的边界情形讨论。二、习题 11.1-1查找集合中的最大元素原题设动态集合 S 用长度为 m 的直接寻址表 T 表示描述一个找出 S 中最大元素的过程并给出最坏情况性能。解答对应文档 11.1.md 的 Answer遍历整个表即依次检查T[0], T[1], ..., T[m-1]跳过 NIL 槽位并维护当前最大值。最坏情况下集合中的最大键恰好在表的末端或表接近全满需要扫描全部 m 个槽位时间复杂度为O(m)。补充分析直接寻址表不保证键按值有序存储键 k 一定在T[k]因此无法利用二分等有序结构加速最大值只能靠线性扫描获得若需要频繁求最大值应考虑改用最大堆等有序结构可参考本仓库 C06-Heapsort 章节这是直接寻址只擅长按键定位、不擅长范围查询的重要认知本解法同样适用于 11.2 节之后的链接法散列表无论冲突如何解决求最大元素都需遍历所有槽位及其链表。三、习题 11.1-2用位向量表示无卫星数据的动态集合原题位向量bit vector是比特0 和 1构成的数组长度为 m 的位向量比长度为 m 的指针数组占用空间小得多。描述如何用位向量表示无卫星数据、元素各不相同的动态集合并让字典操作在 O(1) 时间内完成。解答对应文档 Answer位向量 B[0..m-1] 直接以某位是否为 1表示该键是否在集合中B[k] 1表示键 k 在集合中B[k] 0表示键 k 不在集合中。由于题目限定元素各不相同且无卫星数据集合成员关系只需一个二进制状态即可完整描述查找、插入、删除分别对应读位、置 1、清 0全部为 O(1) 时间。补充分析相比指针数组每个槽位需一个指针32/64 位位向量每个键只需 1 bit空间压缩了数十倍删除操作需要先把对应位从 1 改为 0先确认该位为 1否则删除不存在元素应报错位向量的衍生用途哈希表延迟初始化见习题 11.1-4中位向量可作为判断大数组槽位是否有效的辅助标志本仓库 C32-String-Matching 等章节中亦常见位运算加速思想。四、习题 11.1-3重复键 卫星数据下的直接寻址实现原题建议一种直接寻址表实现其中存储元素的键不必互不相同且元素可携带卫星数据satellite data。三种字典操作 INSERT、DELETE、SEARCH 都须在 O(1) 时间内完成。注意DELETE 的参数是待删除对象的指针而非键。解答对应文档 Answer把每个键 k 映射到一个双向链表doubly linked listT[k]指向该链表同键元素组成的链。INSERT在T[k]指向的链表头部插入新元素含卫星数据O(1)DELETE题目明确传入的是元素指针因此无需再按键查找直接利用双向链表节点自带的 prev 指针在 O(1) 内完成摘除若用单向链表摘除尾节点仍需要 O(链长) 时间——这正是必须用双向链表的关键原因SEARCH遍历T[k]处的链表找到键为 k 的元素。最坏情况 O(链长)但由于同一键的元素都挂在同一条链上每个键的查找只局限于自己的链表。补充分析该方案本质上是每个槽位一条同键链表与 11.2 节链接法chaining的每个槽位一条跨键链表结构相反前者按键分桶后者按散列值分桶二者都可用双向链表实现 O(1) 删除卫星数据如学生记录中的姓名、成绩等是实际数据库字典的常见需求该题说明直接寻址表同样能承载一值多元素 附带数据的完整形态关于链接法在有序链表等变体下的性能分析可进一步阅读 11.2.md 的习题 11.2-3教授假设将每个链表保持有序对四种操作的影响。五、习题 11.1-4巨大数组的 O(1) 延迟初始化核心难点原题我们希望用直接寻址在一个巨大的数组上实现字典。初始时数组项可能包含垃圾值garbage而完整初始化整个数组因规模过大不可行。请设计一种方案每个存储对象占用 O(1) 空间SEARCH、INSERT、DELETE 均 O(1)数据结构的初始化也只需 O(1) 时间。提示用一个额外栈栈的大小等于字典中实际存储的键的个数用于判断大数组的某个槽位是否有效。解答对应文档 Answer经整理为可执行流程根据提示需要一个额外栈该栈存储指向大数组中元素的指针同时大数组的元素是对应栈下标top 的值两者互相指认形成双向验证。设大数组为T[0..m-1]额外栈为S[0..n-1]n 为实际存储的键数栈顶指针为top。关键不变量为对每个已使用的槽位T[k]T[k]存放的是它对应的栈下标i且S[i]指向T[k]即S[T[k]] T[k]对每个未使用的槽位其值可能是任意垃圾数据但垃圾值必然不满足上述双向验证。INSERT(T, k)将T[k]的地址T[k]压入栈 SS[top] T[k]将大数组槽位写为对应栈顶下标T[k] toptop 1。此时S[T[k]] T[k]恒成立槽位正式合法化。SEARCH(T, k)读v T[k]直接寻址O(1)校验 v 是否为一个合法栈下标要求0 ≤ v top且S[v]恰好指向T[k]即S[v] T[k]校验通过 → 键 k 在字典中返回元素否则 → 该槽位从未被写入垃圾值恰好满足前半个条件也无妨因为后半条件必然失败返回 NIL。DELETE(T, k)按 SEARCH 的校验确认T[k]有效记其栈下标i T[k]删除后栈中S[i]处产生空洞。将栈顶元素S[top-1]及其对应大数组槽位j S[top-1] 的数组下标移到空洞处S[i] S[top-1]同时把大数组中该槽位的值更新为iT[ j ] i保持双向验证不变量top - 1空洞被补齐T[k]恢复为垃圾态。复杂度INSERT/SEARCH/DELETE 均只做常数次数组与栈操作全部 O(1)初始化只需把top置 0大数组本身无需清零故初始化也是 O(1)。补充分析该方案是《算法导论》中极具代表性的惰性初始化 双向指认技巧常出现在面试与系统设计中例如需要为超大地址空间维护稀疏字典、避免启动时 O(m) 清零开销的场景关键洞察在于垃圾值不可靠但**栈中存在指向该槽的指针**这一条件可靠。栈的大小恰好等于实际存储的键数随插入/删除动态伸缩这正是提示中栈的大小为字典中实际存储键的个数的意义可以推断若将习题 11.1-2 的位向量与本题结合位向量可作为独立于垃圾值的有效位标志二者在工程上是同一思路的两种变体。六、延伸阅读从直接寻址到完整散列表体系直接寻址表是第 11 章的起点本仓库的 C11-Hash-Tables 目录围绕散列表给出了完整的习题解答脉络11.2.md链接法chaining解决冲突含简单均匀散列下期望冲突数分析习题 11.2-1、h(k) k mod 9插入演示习题 11.2-2配图见 repo/s1/1.png、有序链表的性能影响11.2-3、槽内空闲链表free list分配11.2-4以及最坏情况 Θ(n) 的证明11.2-511.3.md散列函数设计含字符串散列的 Horner 法11.3-2、除法散列与基数性质11.3-3、乘法散列计算示例11.3-4、ϵ-universal 散列族的下界证明11.3-5以及多项式散列族的 ((n−1)/p)-universal 论证11.3-6文中给出了完整的归纳法证明11.4.md开放寻址open addressing含线性探测、二次探测、双重散列三种策略对同一组键的完整插入对照表11.4-1、HASH-DELETE / HASH-INSERT 伪代码11.4-2其中 INSERT 需兼容 DELETED 特殊值、双重散列遍历范围与最大公约数的关系11.4-3、均匀散列下成功/不成功查找的期望探查次数上界计算11.4-4加载因子 3/4 与 7/8及两者相等时 α≈0.717 的求解11.4-511.5.md完美散列perfect hashing的铺垫习题 11.5-1 用数学归纳法证明 n 个键插入大小为 m 的表时无冲突概率 p(n,m) ≤ e^(−n(n−1)/2m)并论证 n 超过 √m 后无冲突概率迅速趋零problem.md章节综合问题包括开放寻址的最长探查上界longest-probe bound借助 5.4 节球与盒子结论证明 E[X] O(lgn)与链接法的槽容量上界slot-size bound目标是证明 E[M] ≤ O(lgn/lg lgn)。值得注意的是README.md 明确标注该目录部分习题为 UNSOLVED未解答涉及 11.3.5、11.3.6 与 11.5.1其中 11.3.5 与 11.3.6 的解答实际已收录于 11.3.md。读者可将 11.1 节的直接寻址作为基线对照后续各节体会从 O(m) 空间的直接寻址到 O(n) 空间的散列表再到概率意义上的常数时间——这正是散列表设计的完整演进路径。小结通过 11.1 节四道习题我们可以提炼出直接寻址表的三个核心结论定位 O(1) 但求最值 O(m)直接寻址只保证按键的常数时间访问不提供有序性空间可按需压缩无卫星数据且键唯一时位向量是空间最优表示垃圾值不可信结构可验证面对巨型数组无法初始化时用栈 双向指认的不变量替代清零依然可以做到插入、查找、删除与初始化全部 O(1)。掌握这些边界情形再进入链接法、散列函数与开放寻址的后续习题整个散列表章节的知识框架就能自然贯通。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐Maestro深度链接教程如何用一条 maestro:// 链接直达任意智能体与功能Maestro深度链接教程如何用一条 maestro:// 链接直达任意智能体与功能 Maestro 是开源的 Agent 编排指挥中心它内置了一个强大的桌面应用AI AgentAgent 编排交互助手人工智能Gutenberg Tag Cloud 标签云块深度解析从动态渲染到样式定制的完整指南Gutenberg Tag Cloud 标签云块深度解析从动态渲染到样式定制的完整指南 标签云Tag Cloud是 WordPress 侧边栏中最经典的组文档教程示例工程CLRS 第 17.4 节习题精解势能法证明动态表 2/3 收缩策略下 TABLE-DELETE 的常数摊还代价CLRS 第 17.4 节习题精解势能法证明动态表 2/3 收缩策略下 TABLE DELETE 的常数摊还代价 本篇文章围绕开源仓库 C17 Amortiz文档教程示例工程上一篇Return YouTube Dislike 工作原理与计数推算机制深度解析数据来源、缓存策略与用户投票外推算法下一篇Skill Seekers 文档架构指南docs 目录组织、分类规范与维护流程全解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 CLRS 第 11 章 11.1 节精读：直接寻址表（Direct-Address Table）习题全解
文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载导读本文基于开源仓库 gh_mirrors/cl/CLRS 中的 11.1.md对《算法导论》Introduction to Algorithms第 11 章散列表Hash Tables第 1 节直接寻址表Direct-Address Tables的四道课后习题进行逐题精解。读完本文你将掌握直接寻址表的最坏情况分析、位向量bit vector表示法、含卫星数据与重复键时的链表实现以及大数组延迟初始化这一经典面试级技巧如何用 O(1) 时间初始化一个巨大的直接寻址表。文中所有结论均以仓库文档为依据并联动 11.211.5 节的散列技术作为延伸。一、背景什么是直接寻址表直接寻址表是散列思想最朴素的形态。当全域universeU 中的键都是 0 到 m-1 之间的整数时我们可以直接用一个长度为 m 的数组 T 作为字典键 k 的元素存放在T[k]中不需要任何散列函数因为键本身即可作为数组下标。若T[k] NIL表示字典中没有键 k 的元素查找SEARCH、插入INSERT、删除DELETE三个字典操作都只需 O(1) 时间。它的致命缺点是空间效率当全域很大而实际存储的键很少时分配一个大小为 |U| 的数组完全不现实。这也正是后续章节引入散列函数11.3.md的根本动机——把大域中的键压缩映射到较小的表上。11.1 节的四道习题正是围绕直接寻址表的O(1) 时间、O(m) 空间这一基本性质展开的边界情形讨论。二、习题 11.1-1查找集合中的最大元素原题设动态集合 S 用长度为 m 的直接寻址表 T 表示描述一个找出 S 中最大元素的过程并给出最坏情况性能。解答对应文档 11.1.md 的 Answer遍历整个表即依次检查T[0], T[1], ..., T[m-1]跳过 NIL 槽位并维护当前最大值。最坏情况下集合中的最大键恰好在表的末端或表接近全满需要扫描全部 m 个槽位时间复杂度为O(m)。补充分析直接寻址表不保证键按值有序存储键 k 一定在T[k]因此无法利用二分等有序结构加速最大值只能靠线性扫描获得若需要频繁求最大值应考虑改用最大堆等有序结构可参考本仓库 C06-Heapsort 章节这是直接寻址只擅长按键定位、不擅长范围查询的重要认知本解法同样适用于 11.2 节之后的链接法散列表无论冲突如何解决求最大元素都需遍历所有槽位及其链表。三、习题 11.1-2用位向量表示无卫星数据的动态集合原题位向量bit vector是比特0 和 1构成的数组长度为 m 的位向量比长度为 m 的指针数组占用空间小得多。描述如何用位向量表示无卫星数据、元素各不相同的动态集合并让字典操作在 O(1) 时间内完成。解答对应文档 Answer位向量 B[0..m-1] 直接以某位是否为 1表示该键是否在集合中B[k] 1表示键 k 在集合中B[k] 0表示键 k 不在集合中。由于题目限定元素各不相同且无卫星数据集合成员关系只需一个二进制状态即可完整描述查找、插入、删除分别对应读位、置 1、清 0全部为 O(1) 时间。补充分析相比指针数组每个槽位需一个指针32/64 位位向量每个键只需 1 bit空间压缩了数十倍删除操作需要先把对应位从 1 改为 0先确认该位为 1否则删除不存在元素应报错位向量的衍生用途哈希表延迟初始化见习题 11.1-4中位向量可作为判断大数组槽位是否有效的辅助标志本仓库 C32-String-Matching 等章节中亦常见位运算加速思想。四、习题 11.1-3重复键 卫星数据下的直接寻址实现原题建议一种直接寻址表实现其中存储元素的键不必互不相同且元素可携带卫星数据satellite data。三种字典操作 INSERT、DELETE、SEARCH 都须在 O(1) 时间内完成。注意DELETE 的参数是待删除对象的指针而非键。解答对应文档 Answer把每个键 k 映射到一个双向链表doubly linked listT[k]指向该链表同键元素组成的链。INSERT在T[k]指向的链表头部插入新元素含卫星数据O(1)DELETE题目明确传入的是元素指针因此无需再按键查找直接利用双向链表节点自带的 prev 指针在 O(1) 内完成摘除若用单向链表摘除尾节点仍需要 O(链长) 时间——这正是必须用双向链表的关键原因SEARCH遍历T[k]处的链表找到键为 k 的元素。最坏情况 O(链长)但由于同一键的元素都挂在同一条链上每个键的查找只局限于自己的链表。补充分析该方案本质上是每个槽位一条同键链表与 11.2 节链接法chaining的每个槽位一条跨键链表结构相反前者按键分桶后者按散列值分桶二者都可用双向链表实现 O(1) 删除卫星数据如学生记录中的姓名、成绩等是实际数据库字典的常见需求该题说明直接寻址表同样能承载一值多元素 附带数据的完整形态关于链接法在有序链表等变体下的性能分析可进一步阅读 11.2.md 的习题 11.2-3教授假设将每个链表保持有序对四种操作的影响。五、习题 11.1-4巨大数组的 O(1) 延迟初始化核心难点原题我们希望用直接寻址在一个巨大的数组上实现字典。初始时数组项可能包含垃圾值garbage而完整初始化整个数组因规模过大不可行。请设计一种方案每个存储对象占用 O(1) 空间SEARCH、INSERT、DELETE 均 O(1)数据结构的初始化也只需 O(1) 时间。提示用一个额外栈栈的大小等于字典中实际存储的键的个数用于判断大数组的某个槽位是否有效。解答对应文档 Answer经整理为可执行流程根据提示需要一个额外栈该栈存储指向大数组中元素的指针同时大数组的元素是对应栈下标top 的值两者互相指认形成双向验证。设大数组为T[0..m-1]额外栈为S[0..n-1]n 为实际存储的键数栈顶指针为top。关键不变量为对每个已使用的槽位T[k]T[k]存放的是它对应的栈下标i且S[i]指向T[k]即S[T[k]] T[k]对每个未使用的槽位其值可能是任意垃圾数据但垃圾值必然不满足上述双向验证。INSERT(T, k)将T[k]的地址T[k]压入栈 SS[top] T[k]将大数组槽位写为对应栈顶下标T[k] toptop 1。此时S[T[k]] T[k]恒成立槽位正式合法化。SEARCH(T, k)读v T[k]直接寻址O(1)校验 v 是否为一个合法栈下标要求0 ≤ v top且S[v]恰好指向T[k]即S[v] T[k]校验通过 → 键 k 在字典中返回元素否则 → 该槽位从未被写入垃圾值恰好满足前半个条件也无妨因为后半条件必然失败返回 NIL。DELETE(T, k)按 SEARCH 的校验确认T[k]有效记其栈下标i T[k]删除后栈中S[i]处产生空洞。将栈顶元素S[top-1]及其对应大数组槽位j S[top-1] 的数组下标移到空洞处S[i] S[top-1]同时把大数组中该槽位的值更新为iT[ j ] i保持双向验证不变量top - 1空洞被补齐T[k]恢复为垃圾态。复杂度INSERT/SEARCH/DELETE 均只做常数次数组与栈操作全部 O(1)初始化只需把top置 0大数组本身无需清零故初始化也是 O(1)。补充分析该方案是《算法导论》中极具代表性的惰性初始化 双向指认技巧常出现在面试与系统设计中例如需要为超大地址空间维护稀疏字典、避免启动时 O(m) 清零开销的场景关键洞察在于垃圾值不可靠但**栈中存在指向该槽的指针**这一条件可靠。栈的大小恰好等于实际存储的键数随插入/删除动态伸缩这正是提示中栈的大小为字典中实际存储键的个数的意义可以推断若将习题 11.1-2 的位向量与本题结合位向量可作为独立于垃圾值的有效位标志二者在工程上是同一思路的两种变体。六、延伸阅读从直接寻址到完整散列表体系直接寻址表是第 11 章的起点本仓库的 C11-Hash-Tables 目录围绕散列表给出了完整的习题解答脉络11.2.md链接法chaining解决冲突含简单均匀散列下期望冲突数分析习题 11.2-1、h(k) k mod 9插入演示习题 11.2-2配图见 repo/s1/1.png、有序链表的性能影响11.2-3、槽内空闲链表free list分配11.2-4以及最坏情况 Θ(n) 的证明11.2-511.3.md散列函数设计含字符串散列的 Horner 法11.3-2、除法散列与基数性质11.3-3、乘法散列计算示例11.3-4、ϵ-universal 散列族的下界证明11.3-5以及多项式散列族的 ((n−1)/p)-universal 论证11.3-6文中给出了完整的归纳法证明11.4.md开放寻址open addressing含线性探测、二次探测、双重散列三种策略对同一组键的完整插入对照表11.4-1、HASH-DELETE / HASH-INSERT 伪代码11.4-2其中 INSERT 需兼容 DELETED 特殊值、双重散列遍历范围与最大公约数的关系11.4-3、均匀散列下成功/不成功查找的期望探查次数上界计算11.4-4加载因子 3/4 与 7/8及两者相等时 α≈0.717 的求解11.4-511.5.md完美散列perfect hashing的铺垫习题 11.5-1 用数学归纳法证明 n 个键插入大小为 m 的表时无冲突概率 p(n,m) ≤ e^(−n(n−1)/2m)并论证 n 超过 √m 后无冲突概率迅速趋零problem.md章节综合问题包括开放寻址的最长探查上界longest-probe bound借助 5.4 节球与盒子结论证明 E[X] O(lgn)与链接法的槽容量上界slot-size bound目标是证明 E[M] ≤ O(lgn/lg lgn)。值得注意的是README.md 明确标注该目录部分习题为 UNSOLVED未解答涉及 11.3.5、11.3.6 与 11.5.1其中 11.3.5 与 11.3.6 的解答实际已收录于 11.3.md。读者可将 11.1 节的直接寻址作为基线对照后续各节体会从 O(m) 空间的直接寻址到 O(n) 空间的散列表再到概率意义上的常数时间——这正是散列表设计的完整演进路径。小结通过 11.1 节四道习题我们可以提炼出直接寻址表的三个核心结论定位 O(1) 但求最值 O(m)直接寻址只保证按键的常数时间访问不提供有序性空间可按需压缩无卫星数据且键唯一时位向量是空间最优表示垃圾值不可信结构可验证面对巨型数组无法初始化时用栈 双向指认的不变量替代清零依然可以做到插入、查找、删除与初始化全部 O(1)。掌握这些边界情形再进入链接法、散列函数与开放寻址的后续习题整个散列表章节的知识框架就能自然贯通。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐Maestro深度链接教程如何用一条 maestro:// 链接直达任意智能体与功能Maestro深度链接教程如何用一条 maestro:// 链接直达任意智能体与功能 Maestro 是开源的 Agent 编排指挥中心它内置了一个强大的桌面应用AI AgentAgent 编排交互助手人工智能Gutenberg Tag Cloud 标签云块深度解析从动态渲染到样式定制的完整指南Gutenberg Tag Cloud 标签云块深度解析从动态渲染到样式定制的完整指南 标签云Tag Cloud是 WordPress 侧边栏中最经典的组文档教程示例工程CLRS 第 17.4 节习题精解势能法证明动态表 2/3 收缩策略下 TABLE-DELETE 的常数摊还代价CLRS 第 17.4 节习题精解势能法证明动态表 2/3 收缩策略下 TABLE DELETE 的常数摊还代价 本篇文章围绕开源仓库 C17 Amortiz文档教程示例工程上一篇Return YouTube Dislike 工作原理与计数推算机制深度解析数据来源、缓存策略与用户投票外推算法下一篇Skill Seekers 文档架构指南docs 目录组织、分类规范与维护流程全解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考