设置 "in" 运算符：使用相等性还是标识性？

Question

class A(object):
    def __cmp__(self):
        print '__cmp__'
        return object.__cmp__(self)

    def __eq__(self, rhs):
        print '__eq__'
        return True
a1 = A()
a2 = A()
print a1 in set([a1])
print a1 in set([a2])

为什么第一行输出True，而第二行输出False？而且两者都没有进入运算符eq？

我正在使用Python 2.6。

- Gennadiy Rozental

---

在进行相等性比较之前，集合可能会使用哈希码。请尝试实现__hash__方法。 - millimoose

你尝试过注释掉__cmp__函数后运行这段代码吗？ - inspectorG4dget

x.__contains__(y) <==> y in x - wim

只是为了确保您知道...集合对于in运算符的工作并不是必需的。如果您只需要进行简单的测试，a1 in [a1]就可以了。 - KobeJohn

有趣的是，如果你移除了set，只有第二个（a1 in [a2]）会调用__eq__。我猜in操作符首先检查身份是否相同，这是一种优化吗？ - KobeJohn

Answer 1

set的__contains__方法按以下顺序进行检查：

 'Match' if hash(a) == hash(b) and (a is b or a==b) else 'No Match'

相关的C源代码位于Objects/setobject.c::set_lookkey()和Objects/object.c::PyObject_RichCompareBool()中。

- Raymond Hettinger

---

列表 __contains__ 看起来表现相同。 - Moberg

Answer 2

你需要定义 __hash__ 方法。例如：

class A(object):
    def __hash__(self):
        print '__hash__'
        return 42

    def __cmp__(self, other):
        print '__cmp__'
        return object.__cmp__(self, other)

    def __eq__(self, rhs):
        print '__eq__'
        return True

a1 = A()
a2 = A()
print a1 in set([a1])
print a1 in set([a2])

会按预期工作。

通常情况下，每当您实现 __cmp__ 时，都应该实现一个 __hash__，使得对于所有的 x == y 的情况，x.__hash__() == y.__hash__()。

- David Wolever

---

我的代码中实际上没有__cmp__，只有__eq__（如果我删除__cmp__它仍然会产生False）。我只是在寻找解释。那么你的意思是每次我实现__eq__时也需要__hash__吗？ - Gennadiy Rozental

好的，明白了。集合是由哈希表支持的，因此进行集合成员测试（x in my_set）时，首先调用 x.__hash__() 方法，检查任何值是否与 my_set 中的哈希值匹配，然后只有在找到匹配项时才调用 __eq__ 方法。 - David Wolever

是的，__hash__ 的实现应该涉及到对象和 __eq__ 实现中相同的属性。（只需将它们全部放入元组中，然后对该元组进行 hash()） - millimoose

你的 __cmp__ 函数似乎缺少了 other 参数。 - Ian A. Mason

Answer 3

集合和字典通过使用哈希作为全等检查的快速近似来提高其速度。如果您想重新定义相等性，则通常需要重新定义哈希算法以使其一致。默认哈希函数使用对象的身份，这在作为全等的快速近似方面相当无用，但至少允许您将任意类实例用作字典键，并检索存储在其中的值，如果您传递完全相同的对象作为键，则可以检索存储在其中的值。但这意味着，如果您重新定义相等性并且不重新定义哈希函数，则对象将进入字典/集合中，而不会抱怨不可哈希，但仍然不能按照您期望的方式工作。有关详细信息，请参见官方 Python 文档关于 __hash__。

- Ben

---

+1 是为了解释根本原因（默认哈希使用 id）。这使得解决方案变得更加容易。 - KobeJohn

Answer 4

一个旁敲侧击的答案，但是你的问题和我的测试让我很好奇。如果你忽略了设置运算符（即你的__hash__问题的源头），结果发现你的问题仍然很有意思。

通过在这个SO问题上得到的帮助，我能够将in运算符追踪到其根源。在底部附近，我找到了PyObject_RichCompareBool函数，它确实在测试相等性之前测试身份（请参见“快速结果”注释）。

所以，除非我误解了事情的工作方式，你问题的技术答案是首先测试身份，然后再通过相等性测试本身来检测是否相等。只是为了重申，这不是导致你看到的行为的源头，而只是你问题的技术答案。

如果我误解了来源，请有人纠正我。

int
PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
{
    PyObject *res;
    int ok;

    /* Quick result when objects are the same.
       Guarantees that identity implies equality. */
    if (v == w) {
        if (op == Py_EQ)
            return 1;
        else if (op == Py_NE)
            return 0;
    }

    res = PyObject_RichCompare(v, w, op);
    if (res == NULL)
        return -1;
    if (PyBool_Check(res))
        ok = (res == Py_True);
    else
        ok = PyObject_IsTrue(res);
    Py_DECREF(res);
    return ok;
}

- KobeJohn

Answer 5

集合似乎使用哈希码，然后是身份标识，在比较相等性之前。以下代码：

class A(object):
    def __eq__(self, rhs):
        print '__eq__'
        return True
    def __hash__(self):
        print '__hash__'
        return 1

a1 = A()
a2 = A()

print 'set1'
set1 = set([a1])

print 'set2'
set2 = set([a2])

print 'a1 in set1'
print a1 in set1

print 'a1 in set2'
print a1 in set2

输出:

set1
__hash__
set2
__hash__
a1 in set1
__hash__
True
a1 in set2
__hash__
__eq__
True

发生的情况似乎是：

1. 当一个元素被插入到哈希表中时，计算其哈希码。（与现有元素进行比较。）
2. 计算您要使用 in 运算符检查的对象的哈希码。
3. 首先通过检查哈希码相同的集合元素，确定它们是否与您正在查找的对象相同，或者它们在逻辑上是否等于它。

- millimoose