知识卡片

普通读书笔记卡 · 3620.c.1.c.3.a

均匀通用与独立性不同

理解等级:高级
  • 函数族“均匀”指单个键落入每槽概率为 1/m;
  • “通用”只要求任意两键碰撞概率≤1/m;
  • d 独立则要求任意 d 个不同键的指定槽位联合概率为 1/m^d。

三者衡量不同性质,不能由通用性反推出完整独立均匀哈希。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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