python - 在 Python 中检查两个 frozensets 是否相等的时间复杂度

Question

无法在网上的任何地方找到这方面的详细信息，当比较两个 frozensets 时，Python 是循环访问其中一个集中的元素还是检查 frozensets 的哈希值，因为 frozensets 是可哈希的？

Answer 1

由于引用文档对此没有任何说明，它依赖于实现，所以除了查看您正在使用的 Python 版本的源代码(在您的 CPython 发行版的 Objects/setobject.c).查看 Python 3.7.0 的源代码，答案是“可能”；-)

平等首先检查卡住集是否具有相同的大小(len())。否则，它们不可能相等，因此立即返回 False。

否则，比较哈希码如果它们已经被计算。如果它们已经被计算过，并且哈希码不相等，则立即返回 False。 Else 调用逐个元素的代码来检查一个是否是另一个的子集。

frozenset 的哈希码并不是为了它而计算的——那将是一笔可能无法偿还的费用。所以有些东西必须强制它。 frozensets 在开始时的主要用例是允许集合的集合，并且在 that 中，上下文哈希代码将被计算为将 frozenset 添加到包含集合的正常部分。 C 级集实现包含一个槽，用于在计算哈希时记录哈希，它被初始化为 -1(一个保留值，在内部表示“不知道哈希码”)。