知识卡片
哈希函数压缩键域
哈希函数 h 把大键域 U 映射到 m 个表槽,让表规模贴近实际存储元素数。它必须对同一键稳定给出同一槽位;若 |U|>m,鸽巢原理保证不同键可能同槽,冲突无法仅靠“看似随机”的函数彻底消除,还须配套处理策略。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 哈希函数压缩键域
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
Because |U| > m, however, there must be at least two keys that have the same hash value
参考来源
- 位置:《算法导论(第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