42

可能重复：
何时计算 python 对象的哈希值，为什么 -1 的哈希值不同？

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

既然他们这样做了，Python 是如何区分这两个数字的呢？

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

1 回答 1

47

-1是 CPython 的 C 级别的保留值，它防止哈希函数能够产生-1. 正如 DSM 所指出的，IronPython 和 PyPy 中的情况并非如此hash(-1) != hash(-2)。

请参阅此 Quora 答案：

如果你在 C 扩展模块中编写一个类型并提供一个tp_hash 方法，你必须避免-1——如果你 return -1，Python 会假设你打算抛出一个错误。

如果你用纯 Python 编写一个类并提供一个__hash__方法，那么谢天谢地，没有这样的要求。但那是因为调用您的__hash__方法的 C 代码会为您执行此操作 - 如果您的 __hash__返回-1，则hash()应用于您的对象将实际返回-2。

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

哈希值-1是保留的（它用于标记 C 实现中的错误）。如果哈希算法生成这个值，我们就简单地使用-2。

您也可以在源代码中看到这一点。例如对于 Python 3 的int对象，这是在哈希实现的末尾：

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

既然他们这样做了，Python 是如何区分这两个数字的呢？

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

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

这种散列码和相等对偶性在CPython 的可散列对象文档中有所暗示。在其他语言/框架中，有一个准则/规则，如果您提供自定义哈希码函数，您还必须提供自定义相等测试（在与哈希码函数相同的字段上执行）。

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

于 2012-04-12T19:34:23.837 回答