Python 中为什么 hash(-1) == hash(-2)？
推荐超级课程：
@TOC
前几天在浏览 Reddit 时，我在 r/Python 上看到了这样一个问题：
hash(-1) == hash(-2) 是彩蛋吗？ 等等，这是真的吗？
$ python
Python 3.9.6 (default, Jun 29 2021, 00:00:00)
[GCC 11.1.1 20210531 (Red Hat 11.1.1-3)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash(-1)
-2
>>> hash(-2)
-2
>>> hash(-1) == hash(-2)
True
是的，确实如此。这太令人惊讶了！ 让我们检查一些其他常见的哈希值：
>>> hash(1)
1
>>> hash(0)
0
>>> hash(3)
3
>>> hash(-4)
-4
除了 -1 之外，所有的小数字似乎都哈希到它们自己……
现在我完全被吸引住了。我试图自己找到答案。在本文的其余部分，我将向您展示如何找到这个答案。
让我们从哪里开始？
我们可以从哪里开始呢？什么是权威的答案？让我们使用Python 的实际源代码！
获取源代码！
那么我们如何才能获得源代码来回答原始问题呢？搜索“python implementation”会出现一些有趣的结果。 对于我来说，第一个结果 https://wiki.python.org/moin/PythonImplementations 指出了“CPython 引用实现”。 https://github.com/python 将“cpython”作为第 2 个存储库。
我们如何才能更加确定呢？
我们可以检查 python.org。让我们去源代码下载。我最终到达了 https://www.python.org/ftp/python/3.9.6/Python-3.9.6.tgz
。解压后，README.rst 也指向 https://github.com/python/cpython
好的，我们将从这里开始。让我们获取这个代码，这样我们就可以稍后搜索它：
git clone https://github.com/python/cpython --depth 1
--depth 1 参数使 git 获取有限的历史记录。这使得克隆操作更快。如果我们需要完整的历史记录，我们可以稍后获取它。
让我们浏览一下
我们需要在开始挖掘代码时找到一个起点。一些容易搜索的东西。一些简单没有太多误导匹配的字符串。
也许我们可以使用 hash 函数的文档？我们可以使用 help(hash) 查看文档文本：
>>> hash
<built-in function hash>
>>> help(hash)
Help on built-in function hash in module builtins:
hash(obj, /)
Return the hash value for the given object.
Two objects that compare equal must also have the same hash value, but the
reverse is not necessarily true.
现在，我们可以用它来查找 hash() 的实现：
$ grep -r 'Return the hash value'
Python/clinic/bltinmodule.c.h:"Return the hash value for the given object.\n"
Python/bltinmodule.c:Return the hash value for the given object.
Doc/library/functions.rst: Return the hash value of the object (if it has one). Hash values are
Lib/hmac.py: """Return the hash value of this hashing object.
hmac 可能与加密 HMAC 实现相关。所以我们可以忽略它。functions.rst 是一个文档文件。所以，让我们也忽略它。
Python/bltinmodule.c 看起来很有趣。如果我们查看一下，我们会找到这段代码：
/*
...
Return the hash value for the given object.
Two objects that compare equal must also have the same hash value, but the
reverse is not necessarily true.
[clinic start generated code]*/
static PyObject *
builtin_hash(PyObject *module, PyObject *obj)
/*[clinic end generated code: output=237668e9d7688db7 input=58c48be822bf9c54]*/
{
Py_hash_t x;
x = PyObject_Hash(obj);
if (x == -1)
return NULL;
return PyLong_FromSsize_t(x);
}
搜索 PyLong 带我 这里
。看起来 PyLongObject 是 Python 整数的本地表示（这将在稍后也很有用）。在浏览了 PyLongObject 文档然后重新阅读此代码之后，它看起来像：
- 我们调用
PyObject_Hash来查找对象的哈希值 - 如果计算的哈希值是 -1，那么这是一个错误。
- 它看起来我们使用 -1 来表示错误，所以没有哈希函数会为真实对象计算 -1
- 我们将
Py_ssize_t转换为PyLongObject（文档将其称为：“这是PyObject的一个子类型，表示 Python 整数对象”）。 啊哈！这解释了为什么hash(0)是0，hash(1)是1，hash(-2)是-2，但hash(-1)不是-1。这是因为-1在内部用于表示错误。 但为什么hash(-1)是-2呢？是什么将它设置为这个值？ 让我们看看是否可以找出原因。 我们可以从寻找PyObject_Hash开始。让我们搜索它。
$ ag PyObject_Hash
...
Objects/rangeobject.c
552: result = PyObject_Hash(t);
Objects/object.c
777:PyObject_HashNotImplemented(PyObject *v)
785:PyObject_Hash(PyObject *v)
802: return PyObject_HashNotImplemented(v);
Objects/classobject.c
307: y = PyObject_Hash(a->im_func);
538: y = PyObject_Hash(PyInstanceMethod_GET_FUNCTION(self));
...
唯一的实现似乎在 Objects/object.c 中：
Py_hash_t
PyObject_Hash(PyObject *v)
{
PyTypeObject *tp = Py_TYPE(v);
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
/* To keep to the general practice that inheriting
* solely from object in C code should work without
* an explicit call to PyType_Ready, we implicitly call
* PyType_Ready here and then check the tp_hash slot again
*/
if (tp->tp_dict == NULL) {
if (PyType_Ready(tp) < 0)
return -1;
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
}
/* Otherwise, the object can't be hashed */
return PyObject_HashNotImplemented(v);
}
这是一段相当令人困惑的代码
注释很有启发性。阅读几次后，它似乎像代码 - 考虑到一些类型的懒惰加载 (?) - 找到对象的类型（使用 Py_TYPE）。然后查找该类型的函数 tp_hash 并在 v 上调用该函数：(*tp->tp_hash)(v)
我们在哪里可以找到 -1 的 tp_hash？让我们再搜索 tp_hash：
$ ag tp_hash -l
...
Modules/_multiprocessing/semaphore.c
Objects/sliceobject.c
Objects/moduleobject.c
Objects/exceptions.c
Modules/_pickle.c
Objects/frameobject.c
Objects/setobject.c
Objects/rangeobject.c
Objects/longobject.c
Objects/object.c
Objects/methodobject.c
Objects/classobject.c
Objects/enumobject.c
Objects/odictobject.c
Objects/complexobject.c
...
这是一个巨大的列表。回想一下文档对 PyLongObject 的说法（“这……表示 Python 整数对象”），我开始查看 Objects/longobject.c：
PyTypeObject PyLong_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int", /* tp_name */
offsetof(PyLongObject, ob_digit), /* tp_basicsize */
sizeof(digit), /* tp_itemsize */
0, /* tp_dealloc */
0, /* tp_vectorcall_offset */
0, /* tp_getattr */
0, /* tp_setattr */
0, /* tp_as_async */
long_to_decimal_string, /* tp_repr */
&long_as_number, /* tp_as_number */
0, /* tp_as_sequence */
0, /* tp_as_mapping */
(hashfunc)long_hash, /* tp_hash */
...
所以 tp_hash 是 long_hash 的 PyLongObject 类型的对象。让我们看看那个。
static Py_hash_t
long_hash(PyLongObject *v)
{
Py_uhash_t x;
Py_ssize
Py_ssize_t i;
int sign;
...
if (x == (Py_uhash_t)-1)
x = (Py_uhash_t)-2;
return (Py_hash_t)x;
}
请注意，我已经删除了大量的实现细节。但此函数的结尾与我们期望的完全一致：-1 被保留为错误信号，因此代码将此返回值显式转换为 -2！
这就解释了为什么 hash(-1) 最终会与 hash(-2) 相同。这不是一个彩蛋，只是解决 -1 不能作为 hash() 方法的可能结果的问题。
这是正确/完整的答案吗？
如前所述，我从未查看过 Python 代码库。我认为我找到了答案。但它是正确的吗？我可能完全错了。
Python 的参考实现是“CPython”，这几乎肯定是你正在使用的 Python。CPython 是用 C 语言编写的，与 Python 不同，C 没有异常。所以，当你设计一个函数时，如果你想让你的函数能够指示“发生了错误”，它必须将其错误作为返回值返回。
CPython 中的
hash()函数可以返回错误，因此它定义了一个返回代码-1来表示“发生了错误”。但如果哈希工作正常，并且对象的实际哈希值是-1，这可能会很混乱。所以约定是：如果哈希工作正常，并且你得到了-1，则返回-2。在 CPython 中有一个针对整数（“长对象”）的哈希函数的特殊代码，它确实是这样做的： https://github.com/python/cpython/blob/main/Objects/longobject.c#L2967 这正好是我通过阅读代码猜测的。
结论
我开始了一个我认为可能很难回答的问题。但几分钟的代码挖掘 - 查看Python 代码库使得查看它比我看到的其他一些代码库更容易 - 答案很容易发现和理解！这不应该让您感到惊讶，如果您一直在计算机领域工作。没有魔法，只有一层又一层的抽象和代码。 Just show me the fu**ing code!