知识卡片
集合有独立散列表实现
CPython的set与dict共享散列表设计思想,但set并不是在运行时持有一个“值为空”的普通dict对象,而有自己的表结构与查找优化。平均成员判断和增删成本受散列分布影响,最坏仍可能线性。原书把概念类比当成具体对象结构过于简化,不据此估算精确内存开销。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第2章 语法最佳实践——类级别以下 2.1.2 集合类型 · 查看原书依据
集合被实现为带有空值的字典
参考来源
- 位置:《Python编程精进(第1辑)(套装共3册)(异步图书)》Python高级编程(第2版) · 第2章 语法最佳实践——类级别以下,spine011单元005;来源项目book-sources,extracted/Python编程精进(第1辑)(套装共3册)(异步图书)/_epub-src/OEBPS/text00010.html。
- 结论依据:原文“空值字典”用于说明散列思想,本卡将类比与实际set结构分开,不据概念相似推定运行时拥有普通dict或精确内存相同。补充核验入口:https://raw.githubusercontent.com/python/cpython/v3.5.10/Objects/setobject.c。未在本机运行示例或改变环境。
- 原始内容:thon中的集合与字典非常相似。事实上,集合被实现为带有空值的字典,只有键才是实际的集合元素。此外,集合还利用这种没有值的映射做了其他优化。 由于这一点,可以快速向集合添加元素、删除元素或检查元素是否存在,平均时间复杂度均为O(1)。但