知识卡片
均匀通用与独立性不同
- 函数族“均匀”指单个键落入每槽概率为 1/m;
- “通用”只要求任意两键碰撞概率≤1/m;
- d 独立则要求任意 d 个不同键的指定槽位联合概率为 1/m^d。
三者衡量不同性质,不能由通用性反推出完整独立均匀哈希。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
The family H is d-independent if for any distinct keys k1, k2,
参考来源
- 位置:《算法导论(第4版)》第 11 章 11.3.3 节(`OEBPS/chapter011.xhtml`,文本字符 [31500, 34500))。
- 结论依据:原文分别列出三个函数族性质,并在前节给出通用但并非独立均匀的恒等映射例子。
- 原始内容:The family H is d-independent if for any distinct keys k 1 , k 2 , …, k d in U