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

Question

无法在网上的任何地方找到这方面的详细信息，当比较两个 frozensets 时，Python 会遍历其中一个集中的元素，还是检查 frozensets 的散列值，因为 frozensets 是可散列的？

Answer 1

hash(x) == hash(y) 并不意味着 x == y:

>>> help(hash)
hash(...)
    hash(object) -> integer

    Return a hash value for the object.  Two objects with the same value have
    the same hash value.  The reverse is not necessarily true, but likely.

所以要比较两个 frozenset 值是否相等，您仍然需要检查两个集合的大小是否相同，然后检查一个集合中的每个元素是否也在另一个集合中。

我把它留作 reader 的练习，我有很多空闲时间来寻找两个具有相同哈希值的不同 frozenset。

Answer 2

由于参考文档对此没有任何说明，它依赖于实现，所以除了查看您正在使用的 Python 版本的源代码之外没有答案（在您的CPython 分布的 Objects/setobject.c)。查看 Python 3.7.0 的源代码，答案是 "maybe" ;-)

平等首先检查冻结集是否具有相同的大小（len()）。如果不相等，则不能相等，所以立即返回False。

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

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

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

Time-complexity of checking if two frozensets are equal in Python

python

frozenset