知识卡片
同桶容器保留全部候选
链式地址在桶中保存一个候选集合,查询先定位桶,再逐项比较键;更新已有键就改值,没有才增加;删除只移除匹配项。这样同桶键可以共存。
候选越长查找越慢,最坏所有键同桶时退化线性。原书Go代码用切片而不是节点链表实现桶内集合;返回空字符串也不能区分缺失和合法空值,应把存在性合同单独表达。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
将所有发生冲突的键值对都存储在同一链表中。图6‑5 展示了一个链式地址哈希表的 例子。 图6‑5 链式地址哈希表 基于链式地址实现的哈希表的操作方法发生了以下变化。 ‧ 查询元素:输入key ,经过哈希函数得到桶索引,即
参考来源
- 位置:《Hello 算法--Go版本》第06章《哈希表》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[15648,15758))
- 结论依据:实际chaining说明及[][]pair代码支持同桶候选,限定切片实现与空返回歧义。
- 原始内容:将所有发生冲突的键值对都存储在同一链表中。图6‑5 展示了一个链式地址哈希表的 例子。 图6‑5 链式地址哈希表 基于链式地址实现的哈希表的操作方法发生了以下变化。 ‧ 查询元素:输入key ,经过哈希函数得到桶索引,即