知识卡片
哈希映射先算桶再比较键
哈希表先把键映射为哈希值,再压到有限桶索引,利用这个索引缩小候选范围。不同键可能落同桶,因此最终仍需依据键的相等关系判断是否为目标。
期望快速查询依赖分布、负载和冲突处理,不是无条件最坏常数。原书最简数组表没有处理冲突,get甚至只取桶不核对键,因而仅能演示索引过程,不能当完整可靠映射。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
仅用一个数组来实现哈希表 。在哈希表中,我们将数组中的每个空位称为「桶 bucket」,每个桶可存储一个键值对。因此,查询操作就是找到key 对应的桶,并在桶中获取 value 那么,如何基于key 定位对应的桶呢?这是
参考来源
- 位置:《Hello 算法--Go版本》第06章《哈希表》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[12366,12476))
- 结论依据:实际hash%capacity和arrayHashMap get/put支持,同时指出碰撞覆盖和无键核对。
- 原始内容:仅用一个数组来实现哈希表 。在哈希表中,我们将数组中的每个空位称为「桶 bucket」,每个桶可存储一个键值对。因此,查询操作就是找到key 对应的桶,并在桶中获取 value 那么,如何基于key 定位对应的桶呢?这是