Python: 内置数值类型和字符串的`hash`值是标准化的吗？

Question

我在思考关于 set、frozenset 和 dict 的排序问题时，遇到了这个问题。Python 并不保证任何排序，任何排序都与某种程度上的 hash 值有关。但是，对于数字或字符串这类内置类型的值，它们的哈希值是否是标准化的呢？换句话说，如果 a、b、c、d、e、f、g 是数字值或 str，那么

hash((a,b,c,d,e,f,g))

是否会有一个确定的值呢？

Answer 1

从哈希集合的一般概念来看，你不能依赖于元素的顺序。即使你使用的实现恰好保持了顺序，但除非文档特别说明可以依赖这个顺序，否则依赖它是个坏主意。

所有放入集合中的对象的哈希值总是相同这一点，与集合的实现是否保持顺序没有关系。

对于一个简单的哈希实现，常见的做法是创建一个大小为原始大小（ORIGINAL_SIZE）的数组。当插入一个项目时，会生成它的哈希值，然后通过简单的取模运算将其映射到数组的大小范围内，然后将对象放在数组的那个位置。如果那个位置已经有一个项目（也就是说，数组的大小小于可能的项目数量），那么就会使用某种碰撞算法来处理。

当集合中的项目数量发生变化时，底层的实现可能会改变存储数据的数组大小（例如，变为原始大小的1.5倍）。当这种情况发生时，迭代时项目的顺序很可能会改变。这种情况通常只发生在插入时，但也可能在删除时发生，或者即使实现将这些操作分散到其他操作中时也会发生。

在各种编程语言中，有一些集合实现保证了顺序，还有一些保证插入项目的顺序不变，以及当你插入同一个项目两次时顺序会发生什么（例如，是否会移动到最后）。然而，除非你查看的实现特别说明它保证这一点，否则你不能依赖它。

举个具体的例子，想象一下在下一个Python版本中，发现集合的底层代码效率不高。有人决定重写它以提高速度。即使旧的实现恰好保持了顺序……如果文档没有说明它保持顺序，那么新的实现就可以不具备这个特性。

Answer 2

为了证明顺序并不是一定会保留的，可以看看DKGasser的例子。在CPython中运行时，结果是：

>>> test = ['cat', 'dog', 'mouse', 'rat', 6126, 516]
>>> temp = []
>>> for x in set(test):
        temp.append(x)  
>>> temp
[516, 'dog', 6126, 'cat', 'rat', 'mouse']

在Jython中运行时，结果是：

>>> test = ['cat', 'dog', 'mouse', 'rat', 6126, 516]
>>> temp = []
>>> for x in set(test):
        temp.append(x)  
>>> temp
[6126, 'dog', 'cat', 'rat', 516, 'mouse']

这就证明了。

这完全取决于解释器的实现，而不是语言本身所保证的。

补充说明

抱歉一直重复这个话题，但提问者似乎想要一个明确的“权威来源”的证明，说明顺序是无法保证的。我终于找到了：

http://docs.python.org/library/stdtypes.html#dict

CPython实现细节：键和值的顺序是任意的，不是随机的，且在不同的Python实现中会有所不同，这还取决于字典的插入和删除历史。

所以就是这样。希望我们可以结束这个话题了。

Answer 3

字符串和整数的哈希值是完全不统一的。也就是说，不同版本的Python可能会有不同的哈希值，比如从2.6.1到2.6.2，或者在Mac和PC上运行同一个版本时，哈希值也可能不同。

更重要的是，稳定的哈希值并不意味着你能依赖于迭代的顺序。你永远不能依赖一个集合中值的顺序。即使在同一个程序中，两个集合可能是相等的，但返回的值顺序却可能不同。这种情况可能发生在一个集合经历了很多添加和删除操作，而另一个集合没有进行这些操作时：

>>> a = set()
>>> for i in range(1000000): a.add(str(i))
...
>>> for i in range(6, 1000000): a.remove(str(i))
...
>>> b = set()
>>> for i in range(6): b.add(str(i))
...
>>> a == b
True
>>> list(a)
['1', '5', '2', '0', '3', '4']
>>> list(b)
['1', '0', '3', '2', '5', '4']