为什么在 Python 中 hash(-1) == hash(-2)?

英文：https://omairmajid.com/posts/2021-07-16-why-is-hash-in-python
作者：Omair Majid
译者：豌豆花下猫&Claude-3.5-Sonnet
时间：原文发布于 2021.07.16，翻译于 2025.01.11
收录于：Python为什么系列  https://github.com/chinesehuazhou/python-whydo
当我在等待代码编译的时候，我在 Reddit 的 r/Python 上看到了这个题目：

hash(-1) == hash(-2) 是个彩蛋吗？

等等，这是真的吗？

1. $ python
2. Python 3.9.6 (default, Jun 29 2021, 00:00:00)
3. [GCC 11.1.1 20210531 (Red Hat 11.1.1-3)] on linux
4. Type "help", "copyright", "credits" or "license" for more information.
5. >>> hash(-1)
6. -2
7. >>> hash(-2)
8. -2
9. >>> hash(-1) == hash(-2)
10. True

复制代码

是的，确实如此。真让人惊讶！
让我们看看其它一些常见的哈希值：

1. >>> hash(1)
2. 1
3. >>> hash(0)
4. 0
5. >>> hash(3)
6. 3
7. >>> hash(-4)
8. -4

复制代码

看起来所有小整数的哈希值都等于它们自身，除了 -1...
现在我完全被这个题目吸引住了。我试图本身找出答案。在接下来的内容中，我将带你了解如何本身寻找这个答案。
如何开始呢？什么能给我们一个权威的答案？
让我们看看源代码！Python 的实际实当代码！
获取源代码

我假设你和我一样，对 Python 的源代码在哪里完全没有概念。
那么，我们（假设从未看过 Python 的源代码）如何获取源代码往返答最初的题目呢？
也许我们可以用 Google？搜索 "python implementation" 会带来一些风趣的结果。
我搜索的 第一个结果 提到了 "CPython 参考实现"。
Github 上 Python 组织 的第二个仓库就是 "cpython"。这看起来很靠谱。我们如何确保万无一失呢？
我们可以访问 python.org。让我们去到源码下载页面。终极我找到了 Python 3.9.6 的压缩包。解压后，README.rst 也指向了 Github 上的 CPython。
好的，这就是我们的起点。让我们获取这些代码，以便后续搜索：

1. git clone https://github.com/python/cpython --depth 1

复制代码

--depth 1 参数使 git 只获取有限的历史记录。如允许以让克隆操作快很多。如果之后需要完整的历史记录，我们可以再获取。
让我们深入研究

在研究代码时，我们需要找到一个起点。最好是轻易搜索的东西，比如一个简单的字符串，不会有太多误导性的匹配。
也许我们可以使用 hash 函数的文档？我们可以用 help(hash) 来检察文档内容：

1. >>> hash
2. <built-in function hash>
3. >>> help(hash)
4. Help on built-in function hash in module builtins:
6. hash(obj, /)
7.     Return the hash value for the given object.
9.     Two objects that compare equal must also have the same hash value, but the
10.     reverse is not necessarily true.

复制代码

现在，我们可以用它来找到 hash() 的实现：

1. $ grep -r 'Return the hash value'
2. Python/clinic/bltinmodule.c.h:"Return the hash value for the given object.\n"
3. Python/bltinmodule.c:Return the hash value for the given object.
4. Doc/library/functions.rst:   Return the hash value of the object (if it has one).  Hash values are
5. Lib/hmac.py:        """Return the hash value of this hashing object.

复制代码

hmac 大概与加密的 HMAC 实现有关，所以我们可以忽略它。functions.rst 是一个文档文件，所以也可以忽略。
Python/bltinmodule.c 看起来很风趣。如果我们检察这个文件，会找到如许一段代码：

1. /*
2. ...
3. Return the hash value for the given object.
5. Two objects that compare equal must also have the same hash value, but the
6. reverse is not necessarily true.
7. [clinic start generated code]*/
9. static PyObject *
10. builtin_hash(PyObject *module, PyObject *obj)
11. /*[clinic end generated code: output=237668e9d7688db7 input=58c48be822bf9c54]*/
12. {
13.     Py_hash_t x;
15.     x = PyObject_Hash(obj);
16.     if (x == -1)
17.         return NULL;
18.     return PyLong_FromSsize_t(x);
19. }

复制代码

搜索 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 。让我们搜索一下。

1. $ ag PyObject_Hash
2. ...
3. Objects/rangeobject.c
4. 552:    result = PyObject_Hash(t);
6. Objects/object.c
7. 777:PyObject_HashNotImplemented(PyObject *v)
8. 785:PyObject_Hash(PyObject *v)
9. 802:    return PyObject_HashNotImplemented(v);
11. Objects/classobject.c
12. 307:    y = PyObject_Hash(a->im_func);
13. 538:    y = PyObject_Hash(PyInstanceMethod_GET_FUNCTION(self));
14. ...

复制代码

固然有很多干扰，但唯一的实现似乎在 Objects/object.c 中：

1. Py_hash_t
2. PyObject_Hash(PyObject *v)
3. {
4.     PyTypeObject *tp = Py_TYPE(v);
5.     if (tp->tp_hash != NULL)
6.         return (*tp->tp_hash)(v);
7.     /* 为了保持通用做法：在 C 代码中仅从 object 继承的类型，应该无需显式调用 PyType_Ready 就能工作，
8.      * 我们在这里隐式调用 PyType_Ready，然后再次检查 tp_hash 槽
9.      */
10.     if (tp->tp_dict == NULL) {
11.         if (PyType_Ready(tp) < 0)
12.             return -1;
13.         if (tp->tp_hash != NULL)
14.             return (*tp->tp_hash)(v);
15.     }
16.     /* Otherwise, the object can't be hashed */
17.     return PyObject_HashNotImplemented(v);
18. }

复制代码

这段代码相适时人困惑。幸运的是，注释很清楚。在多次阅读后，似乎这段代码——考虑到范例的一些延迟加载（？）——先找到对象的范例（使用 Py_TYPE）。然后寻找该范例的 tp_hash 函数，并在 v 上调用该函数：(*tp->tp_hash)(v)
我们在哪里能找到 -1 的 tp_hash 呢？让我们再次搜索 tp_hash：

1. $ ag tp_hash -l
2. ...
3. Modules/_multiprocessing/semaphore.c
4. Objects/sliceobject.c
5. Objects/moduleobject.c
6. Objects/exceptions.c
7. Modules/_pickle.c
8. Objects/frameobject.c
9. Objects/setobject.c
10. Objects/rangeobject.c
11. Objects/longobject.c
12. Objects/object.c
13. Objects/methodobject.c
14. Objects/classobject.c
15. Objects/enumobject.c
16. Objects/odictobject.c
17. Objects/complexobject.c
18. ...

复制代码

这是一个很长的列表。回想一下文档中关于 PyLongObject 的分析（"这个...表示一个 Python 整数对象"），我先检察下 Objects/longobject.c ：

1. PyTypeObject PyLong_Type = {
2.     PyVarObject_HEAD_INIT(&PyType_Type, 0)
3.     "int",                                      /* tp_name */
4.     offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
5.     sizeof(digit),                              /* tp_itemsize */
6.     0,                                          /* tp_dealloc */
7.     0,                                          /* tp_vectorcall_offset */
8.     0,                                          /* tp_getattr */
9.     0,                                          /* tp_setattr */
10.     0,                                          /* tp_as_async */
11.     long_to_decimal_string,                     /* tp_repr */
12.     &long_as_number,                            /* tp_as_number */
13.     0,                                          /* tp_as_sequence */
14.     0,                                          /* tp_as_mapping */
15.     (hashfunc)long_hash,                        /* tp_hash */
16.     ...

复制代码

所以 PyLongObject 范例对象的 tp_hash 是 long_hash。让我们看看这个函数。

1. static Py_hash_t
2. long_hash(PyLongObject *v)
3. {
4.     Py_uhash_t x;
5.     Py_ssize_t i;
6.     int sign;
8.     ...
10.     if (x == (Py_uhash_t)-1)
11.         x = (Py_uhash_t)-2;
12.     return (Py_hash_t)x;
13. }

复制代码

注意我删除了大部门实现细节。但这个函数的末了正好符合我们的预期：-1 被保留用作错误信号，所以代码明确地将该返回值转换为 -2！
这就解释了为什么 hash(-1) 终极与 hash(-2) 相同。这不是一个彩蛋，只是为了避免使用 -1 作为 hash() 方法的返回值，因此采取的变通方法。
这是正确/完整的答案吗？

如前所述，我从未看过 Python 代码库。我认为本身找到了答案。但这是对的吗？我大概完全错了。
幸运的是，/u/ExoticMandibles 在 Reddit 帖子中提供了答案：

Python 的参考实现是 "CPython"，这很大概就是你正在使用的 Python。CPython 是用 C 语言编写的，与 Python 差别，C 语言没有异常处理。所以，在 C 语言中，当你设计一个函数，并且想要表示"发生了错误"时，必须通过返回值来表示这个错误。
CPython 中的 hash() 函数大概返回错误，所以它定义返回值 -1 表示"发生了错误"。但如果哈希计算正确，而对象的实际哈希值恰好是 -1，这大概会造成肴杂。所以约定是：如果哈希计算乐成，并得到值是 -1，就返回 -2。
在 CPython 中，整数（"长整型对象"）的哈希函数中有专门的代码来处理这种情况：
https://github.com/python/cpython/blob/main/Objects/longobject.c#L2967

这正是我通过阅读代码推测出的结果。
结论

我从一个看似难以回答的题目开始。但是通过几分钟的代码探索——Python 整洁的代码库使得检察它的代码比我见过的其它代码库要轻易得多——很轻易就发现和理解了答案！如果你打仗过计算机，这应该家常便饭。这里没有魔法，只有层层的抽象和代码。
如果本文有什么启示的话，那就是：检察源代码！ （文档大概会过期，注释大概不准确，但源码是永恒的。）

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。