python - 为什么 -1 和 -2 在 CPython 中都散列为 -2？

Question

Possible Duplicate:
When is a python object's hash computed and why is the hash of -1 different?

如果是 Python，为什么 -1 和 -2 都哈希到相同的数字？

既然如此，Python 是如何区分这两个数字的呢？

>>> -1 is -2
False
>>> hash(-1) is hash(-2)
True
>>> hash(-1)
-2
>>> hash(-2)
-2

Answer 1

-1 是 CPython 的 C 级别的保留值，可防止散列函数产生 -1 的散列值。正如 DSM 所指出的，在 IronPython 和 PyPy 中情况并非如此，其中 hash(-1) != hash(-2)。

见 this Quora answer :

If you write a type in a C extension module and provide a tp_hash method, you have to avoid -1 — if you return -1, Python will assume you meant to throw an error.

If you write a class in pure Python and provide a __hash__ method, there's no such requirement, thankfully. But that's because the C code that invokes your __hash__ method does that for you — if your __hash__ returns -1, then hash() applied to your object will actually return -2.

这实际上只是重新包装了来自 effbot 的信息:

The hash value -1 is reserved (it’s used to flag errors in the C implementation). If the hash algorithm generates this value, we simply use -2 instead.

您也可以在源代码中看到这一点。例如对于 Python 3 的 int 对象，它位于 the hash implementation 的末尾:

if (x == (Py_uhash_t)-1)
    x = (Py_uhash_t)-2;
return (Py_hash_t)x;

---

Since they do, how does Python tell these two numbers apart?

由于所有散列函数都将大输入空间映射到较小输入空间，因此无论散列函数有多好，总是会发生冲突。例如，考虑散列字符串。如果哈希码是 32 位整数，则您有 2^32(略多于 40 亿)个哈希码。如果您考虑所有长度为 6 的 ASCII 字符串，您的输入空间中有 (2^7)^6(略低于 4.4 万亿)不同的项目。仅此一套，无论您多么出色，都可以保证有很多很多碰撞。向其中添加 Unicode 字符和无限长度的字符串!

因此，哈希码仅提示在对象的位置，随后进行相等性测试以测试候选键。要在哈希表集中实现成员资格测试，哈希码会为您提供“桶”编号，以便在其中搜索值。但是，所有具有相同哈希码的集合项都在存储桶中。为此，您还需要一个相等性测试来区分存储桶中的所有候选者。

CPython documentation on hashable objects 中暗示了这种哈希码和相等对偶性。 .在其他语言/框架中，有一个准则/规则，如果您提供自定义哈希码函数，您还必须提供自定义相等测试(在与哈希码函数相同的字段上执行)。

---

确实，今天的 Python 版本正好解决了这个问题，它提供了一个安全补丁来解决当这个(相同的哈希值，但大规模)被用作拒绝服务攻击时的效率问题 - http://mail.python.org/pipermail/python-list/2012-April/1290792.html