知识卡片

普通读书笔记卡 · 1958.c.12.a.1.bn · 生成模型:未记录

散列冲突需要继续定位

理解等级:中级

不同键可能给出相同散列值,字典不能因此认定是同一个键,还需在冲突处理后比较相等。原书CPython字典用开放定址与探测寻找位置,探测不是向外部链表追加节点。冲突越多通常比较和探测越多,故优秀平均性能依赖合理分布;具体探测细节属于实现,不能强加给所有Python解释器。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《Python编程精进(第1辑)(套装共3册)(异步图书)》Python高级编程(第2版) · 第2章 语法最佳实践——类级别以下,spine011单元005;来源项目book-sources,extracted/Python编程精进(第1辑)(套装共3册)(异步图书)/_epub-src/OEBPS/text00010.html。 - 结论依据:原文用开放定址和探测解释冲突位置,支持相同hash后仍需定位与比较键,不是把所有冲突键视作相等。未在本机运行示例或改变环境。 - 原始内容:所有Python实现都必须解决散列冲突。CPython用 开放定址法 (open addressing)来解决这一冲突(https://en.wikipedia.org/wiki/Open_addressing)。不过,发生冲突的概率对性