知识卡片
独立均匀哈希是理想模型
1. 先看数据放在哪里
哈希表像一排带编号的储物格。“键”是用来查数据的标识,例如用户编号;“槽”是数据的存储位置;“哈希函数”根据键算出槽的编号。
假设有 4 个槽,编号为 0、1、2、3。下面是一组演示结果:
这里用 A、B、C 分别代表三个人的用户编号。
| 操作与键 | 槽号 | 结果 |
|---|---|---|
| 存张三(A) | 2 | 数据放到槽 2 |
| 存李四(B) | 0 | 数据放到槽 0 |
| 查张三(A) | 2 | 仍到槽 2 查找 |
| 存王五(C) | 2 | 与 A 碰撞,需另行处理 |
先记住:同一个键的位置要固定;不同键的位置可以重复。 表中的结果只演示操作,不足以证明哈希函数独立、均匀。
2. “均匀”和“独立”分别是什么意思
为了分析性能,书中假设一种理想的分配方式:为每个不同的键随机选一个槽,而且各键的选择彼此独立。每个键的位置一旦选定,以后就不再改变。
以下概率描述的是位置确定之前的理想模型,并非反复查询同一个键得到的统计结果。
| 我们知道的条件 | B 去槽 0 | B 去槽 1 | B 去槽 2 | B 去槽 3 |
|---|---|---|---|---|
| 不知道 A 的位置 | 25% | 25% | 25% | 25% |
| 已知 A 在槽 2 | 25% | 25% | 25% | 25% |
- 均匀:看同一行。 每个槽的概率都相同,没有偏爱的槽。
- 独立:比较两行。 知道 A 的位置后,B 的概率仍然不变。表格演示两个键;完整模型要求所有不同键的选择都彼此独立。
- 固定:位置确定后不重选。 同一个键再次查询时,不会重新随机分配位置。
3. 碰撞概率为什么是 1/m
若 A 已经选中槽 2,B 恰好也选中槽 2 的概率是 25%,也就是 1⁄4。A 无论选中哪个槽,道理都一样。
把槽的数量从 4 换成 m,两个指定的不同键碰撞的概率就是 1/m。独立并不意味着没有碰撞,均匀也不意味着每个槽恰好放一个键。
结构图:
4. 为什么同一个键的位置必须固定
下面只展示定位过程;如果槽里有多个键,还需要进一步辨认目标键。
flowchart TD
A["存入张三:键 A"] --> B["哈希函数算出槽号 2"]
B --> C["到槽 2 存放数据"]
C --> D["之后查张三:仍用键 A"]
D --> E["同一函数仍算出槽号 2"]
E --> F["到槽 2 查找 A 的数据"]
5. 这个模型有什么用
书中用它分析哈希表的平均性能。实际哈希函数需要设法近似这些性质,因此使用性能结论时,要检查它依赖的假设是否成立。
一句话记忆:不同键各自等概率选位置,同一个键选定后位置固定;这是分析用的理想模型。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
An “ideal” hashing function h would have, for each possible input k in the domain U, an output h(k) that is an element randomly and independently chosen uniformly from the range {0, 1,
参考来源
- 位置:《算法导论(第4版)》第 11 章《散列表》11.2 节(源文件:`_epub-src/OEBPS/chapter011.xhtml`,“Independent uniform hashing”小节)。
- 结论依据:原文先定义键到槽的映射和碰撞,再定义独立、均匀且对同一键输出固定的理想函数,并说明该模型用于性能分析,实际需要寻找近似方案。正文的 4 槽操作表、概率表和流程图均为依据原书定义补充的教学示例,并非书中案例或实测数据;操作表不用于证明随机性,概率表说明理想模型的假设,流程图说明确定映射如何支持再次查找;1/m 是由均匀性和独立性推出的两个指定不同键的碰撞概率。
- 原始内容:An “ideal” hashing function h would have, for each possible input k in the domain U, an output h(k) that is an element randomly and independently chosen uniformly from the range {0, 1, …, m − 1}. Once a value h(k) is randomly chosen, each subsequent call to h with the same input k yields the same output h(k). […] Independent uniform hashing is an ideal theoretical abstraction, but it is not something that can reasonably be implemented in practice.