7.5.1 散列表的基本概念

教材导航 · 第7章

原书定位

印刷页P323起,对应PDF第335页。下文为目视整理的知识提要;完整内容见原书对照。

H(key)H(key) 将关键字映射到表地址。不同关键字得到相同地址称冲突,这些关键字互为同义词。散列表又称哈希表,按映射和冲突规则存取记录。

设计目标是计算简单、分布均匀、降低冲突。合理负载和良好分布下可达期望 O(1)O(1) 查询,但最坏可退化到 O(n)O(n);不能把常数时间作为无条件保证。

对应练习

7.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P323,PDF第335页

原书对照,原书P324,PDF第336页