知识卡片
散列冲突需要继续定位
不同键可能给出相同散列值,字典不能因此认定是同一个键,还需在冲突处理后比较相等。原书CPython字典用开放定址与探测寻找位置,探测不是向外部链表追加节点。冲突越多通常比较和探测越多,故优秀平均性能依赖合理分布;具体探测细节属于实现,不能强加给所有Python解释器。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第2章 语法最佳实践——类级别以下 2.1.2 集合类型 · 查看原书依据
CPython用开放定址法
参考来源
- 位置:《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)。不过,发生冲突的概率对性