链接法散列性能分析
• 【证明核心步骤】
○ 【证明目标锁定】：查找所需要的平均次数
○ 分类套路，查找成功，查找失败
○ 穷举，对所有查找成功的可能进行穷举，利用指示器变量工具对穷举结果进行数学描述
• 【证明套路】
○ 通过指示器变量对非随机算法进行概率分析，必须要强调的是，任何牵扯到算法概率分析的相关证明都可以使用指示器变量，不要以为仅仅是随机性算法才会使用指示器变量
• 【证明成功的背后本质原因】
○ 简单均匀散列假设充当重要作用，该假设简化了指示器变量期望值的计算
○ 链式散列表查找性能之所以快，是因为他屏蔽了大量的虚假操作。简单均匀散列假设保证了被屏蔽的虚假操作数量在可控范围之内。