为什么CPython Dicts不会受到散列值影响？阴性和阴性两种

Question

Hash tables are supposed be high-performance mappings,and because Python dicts are implemented with hash tables，它们也具有很高的性能。但是在查看负整数的散列值时，我遇到了一个奇怪的结果。

>>> for i in range(7): 
...  print hash(i-4) 
...  
-4 
-3 
-2 
-2 
0 
1 
2 

但是这显然对类型的字典没有影响：

>>> d = dict() 
>>> d[-1] = 'foo' 
>>> d[-2] = 'bar' 
>>> d 
{-2: 'bar', -1: 'foo'} 

为什么会这样，为什么当我使用他们不是类型的字典受到影响？

Answer 1

x具有与y不同的散列值的事实意味着x != y。但相反是不正确的！因此，当x的散列值等于y时，它们仍然显式检查是否相等。

时hash(x) == hash(y)和x != y被称为碰撞中的散列函数的情况下，是东西是可能发生不时的情形。你想尽可能避免它，但总的来说这是不可避免的。你可以阅读更多关于哈希函数和碰撞here。

Answer 2

如果您问为什么字符串不受重复散列值的影响，那是因为散列值不需要唯一，散列表才能工作。

Python实现整数哈希值解析为整数的简单哈希。由于-1在内部用于表示失败产生散列值，所以值-1被默默地替换为-2，这同样适用。

Answer 3

-1是C代码中的错误代码，并且没有散列函数可以返回它，以免它发出C代码错误。 C没有例外，所以Python开发者必须保留一个返回值来指示错误。

字典不使用只是散列;它也测试平等。请注意，散列表是小与可能的散列值的数量进行比较，即使散列值是而不是相等，它们仍然可以结束映射到相同的插槽。如果散列值映射到相同的槽并且密钥不相等，则散列会受到干扰并找到新的槽。因为-1 != -2，Python仍然保持两个键不同。

请参阅Overriding Python's Hashing Function in Dictionary和Why is the order in dictionaries and sets arbitrary?了解有关Python字典如何使用散列的更多详细信息。

Answer 4

当散列值不同时散列表执行得更好，但它们可以处理相同的散列值。这些被称为哈希碰撞，并且处理哈希碰撞的方法是哈希表优化和调整的重要方式之一。

hash(-1) == -2因为-1是用于在C实现中发信号错误的特殊值。哈希码不能取这个值;如果您尝试定义一个给出-1的散列的类，Python将检测它并使用-2代替。