高级算法 (Spring 2026)/作业2
- 每道题目的解答都要有完整的解题过程，中英文不限。
- 我们推荐大家使用LaTeX, markdown等对作业进行排版。
- 没有条件的同学可以用纸笔完成作业之后拍照。
- 本门课的所有作业中如果出现了课程中（包括课件中和作业题目中）的算法或者概念或者符号，则禁止使用自己发明的说法或者符号，必须与课程内容保持一致。
- 将 power of two choices 扩展到 power of [math]\displaystyle{ d }[/math] choices。此时 maximum load 是多少？尝试分析和证明你的结论。
- 考虑两种构造哈希表的基本模式：拉链法和基于桶的哈希表。
- 分别使用朴素的真随机哈希函数和power of two choices构造基于拉链法的哈希表。假设我们插入 n keys，哈希表有 n slots，那么每次查询的时候的时间开销的期望和方差大约是多少？时间开销以高概率不会超过多少？
- 基于桶的哈希表按照如下方式运行：假设哈希表有 m slots，这个时候我们可以把哈希表分成 [math]\displaystyle{ m/c }[/math] 个桶，每个桶容量为 [math]\displaystyle{ c }[/math]。每次插入的时候选择一个桶，再到桶内选择一个空的 slots 放入。查询时则遍历桶内所有的 slots，删除则是简单移除对应的 key。
分别使用朴素的真随机哈希函数和power of two choices构造基于桶的哈希表。当你的负载率达到大约多少的时候，一次插入的失败概率会高于 [math]\displaystyle{ 1/m^{10} }[/math]?