知识卡片

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

哈希函数压缩键域

理解等级:中级

哈希函数 h 把大键域 U 映射到 m 个表槽,让表规模贴近实际存储元素数。它必须对同一键稳定给出同一槽位;若 |U|>m,鸽巢原理保证不同键可能同槽,冲突无法仅靠“看似随机”的函数彻底消除,还须配套处理策略。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 11 章 11.2 节(`OEBPS/chapter011.xhtml`,文本字符 [5000, 8500);图 11.2/Art_P379)。 - 结论依据:原文给出 h:U→{0,…,m−1}、空间动机、确定性要求与不可避免的冲突。 - 原始内容:Because | U | > m , however, there must be at least two keys that have the same hash value