知识卡片

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

集合有独立散列表实现

理解等级:中级

CPython的set与dict共享散列表设计思想,但set并不是在运行时持有一个“值为空”的普通dict对象,而有自己的表结构与查找优化。平均成员判断和增删成本受散列分布影响,最坏仍可能线性。原书把概念类比当成具体对象结构过于简化,不据此估算精确内存开销。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《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)。但