知识卡片

普通读书笔记卡 · 5654.d.1.a.3.a.2

同桶容器保留全部候选

理解等级:中级

链式地址在桶中保存一个候选集合,查询先定位桶,再逐项比较键;更新已有键就改值,没有才增加;删除只移除匹配项。这样同桶键可以共存。

候选越长查找越慢,最坏所有键同桶时退化线性。原书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 ,经过哈希函数得到桶索引,即