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

Question

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

Answer 1

由于参考文档对此没有任何说明，它依赖于实现，因此除了查看您正在使用的 Python 版本的源代码（在您的 CPython 发行版中）之外，没有任何答案Objects/setobject.c。查看 Python 3.7.0 的源代码，答案是“也许”；-)

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

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

冻结集的哈希码不仅仅是为了它而计算的——这将是一笔可能无法得到回报的费用。所以必须有东西强迫它。freezesets 一开始的主要用例是允许集合的集合，在这种情况下，哈希码将作为将frozenset 添加到包含集合的正常部分来计算。C-level set 实现包含一个槽来记录哈希是否以及何时计算，它被初始化为 -1（一个保留值，表示内部“没有已知的哈希码”）。

Answer 2

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值是否相等，您仍然需要检查两个集合是否具有相同的大小，然后检查一个中的每个元素是否也在另一个中。

我把它作为练习留给有大量空闲时间的读者来寻找frozenset具有相同哈希值的两个不同的 s。