遍历字典返回按排序的键

Question

我有个关于Python字典如何处理数据的问题。假设我有一个简单的字典，里面的键是数字，值也是数字，如下所示：

a = { 5: 3, 20: 1, 1: 1, 5: 2, 100: 3, 11: 6,
     14: 1, 15: 2, 16: 4, 17: 2, 25: 1, 19: 1 }

我想遍历这个字典，打印出所有的键。每次我循环这个字典（如下所示），它都会按升序打印出键。

这是我想要的效果，但我在想，出于自己的好奇，为什么会这样？它是每次都自动排序成升序吗？如你所见，上面的字典中，键显然并不是按升序排列的，但下面的输出却是按升序打印的。

我只是想搞清楚这个问题，任何帮助都非常感谢。谢谢！

示例

for i in a:
    print i

输出：

1
5
11
14
15
16
17
19
20
25
100

Answer 1

文档里说：

字典最好被理解为一组无序的键值对，要求每个键都是唯一的。

跟Python的列表或元组不一样，字典里的键值对没有特定的顺序。虽然当你创建字典的时候，键值对是有顺序的，但如果你直接调用字典，你会发现它们并不是按照那个顺序存储的。如果你想要对这些键值对进行排序，可以使用内置的 sorted 方法。

Answer 2

每次我遍历字典（如下所示）时，它都会按顺序打印出键。

这其实只是碰巧。字典是一种无序的对象集合，可以通过键来访问。

字典里没有“自动排序”或者其他任何排序方式。

想一想，设置自己键的目的就是为了能通过这些键来获取对应的对象，所以键的“顺序”并不重要。关键是你知道怎么去引用每个对象，因为你自己设置了它的键。这使得获取对象的速度非常快，因为很容易找到。字典里没有重复的键，所以它内部可以以一种优化的方式存储，以便快速访问。

这和列表不同，列表是有顺序的（而且这个顺序是有保证的）。在列表中，获取对象是通过它在列表中的位置来实现的。因此，保持顺序是有意义的。

元组和列表类似，也是有顺序的。元组和列表之间的一个区别是，元组一旦创建就不能更改（你不能“扩展”或“缩小”一个元组）。如果想修改元组，你必须创建一个新的元组。所以要“扩展”一个元组，可以把两个元组合并成一个第三个不同的元组。原来的两个元组保持不变。

如果你想了解字典的技术细节以及它们是如何“在后台”工作的，可以查看这个问题，里面有很好的答案和各种信息。

Answer 3

如果你想知道为什么Python总是把键按顺序排列……其实答案是，它并不是总这样做。

如果你想了解某个特定版本的Python为什么会把你的键按顺序排列，真正的答案就在于它的源代码。

对于CPython（如果你不知道自己用的是哪个版本，可能就是这个），源代码在Objects/dictobject.c文件里。在3.4版本时，这部分代码发生了很大的变化，而在此之前的2.6和3.2版本也有过一些变化，历史上还有其他一些小的改动。所以你需要查找你关心的具体版本。对于3.4版本，源代码可以在http://hg.python.org/cpython/file/3.4/Objects/dictobject.c找到。虽然它是用C语言写的，但里面有很多很好的注释，解释了代码的功能。如果你真的想深入了解，甚至可以把它转换成Python代码，然后在pdb下运行。

有一个关键的问题，可能从代码中看不出来，除非你了解哈希表，那就是这里有两个“巧合”，而不仅仅是一个。首先，在某些版本的CPython中，当你一次性创建一个小字典时，键会按照它们的哈希值顺序排列。其次，在目前所有版本的CPython中，小整数的哈希值等于它们本身，所以——与几乎任何其他类型不同——“按哈希值顺序排列”也意味着“按值顺序排列”。

Answer 4

字典里的整数并不是总是按键的顺序排列的：

a = {2:0, 9:0}
print a.keys()  # [9, 2]

Python 的字典其实是一种叫做 哈希表 的特殊数组。在这个数组里，存储值的单元格的 索引 是通过对 键 应用一个特殊的函数（我们称之为 哈希 函数）来计算得出的。 这样，如果你想要获取某个特定 键 的 值，你可以再次计算这个 键 的 哈希 函数，这样就能得到之前相同的结果，从而找到存储 值 的索引。

哈希 函数会把 大多数 数据类型转换成一个整数：

print hash(1)             # 1
print hash('hello')       # 840651671246116861
print hash((2,3))         # 3713082714463740756

每种类型可以定义自己的 哈希 计算方式，而 int 通常 会返回它自己：

print hash(1)             # 1
print hash(20)            # 20
print hash(1000)          # 1000

如你所见，数字很快就会变得很大，我们不想为了存储字符串 hello 而创建一个有 840651671246116861 个单元的数组。 为了避免这个问题，我们可以创建一个有 n 个元素的数组，然后用 哈希 除以 n 的余数作为 索引。

例如，如果我们想在一个有 8 个元素的数组中找到 hello 的索引：

print hash('hello') % 8   # 5

所以我们的字典会知道，hello 这个键对应的 值 在索引 8 的位置。这就是字典的实现方式。

那么，为什么 {2:0, 9:0} 的键不是有序的呢？这是因为 Python 字典是用 8 个元素创建的，并且会根据需要增长（更多内容可以在 这里找到）。

让我们计算一下在一个有 n = 8 的字典中存储 key = 2 和 key = 9 的索引：

print hash(2) % 8         # 2  [hash(2) = 2 and 2 % 8 = 2]
print hash(9) % 8         # 1  [hash(9) = 9 and 9 % 8 = 1]

这意味着包含字典数据的 数组 将是：

| index | key | value |
|-------|-----|-------|
|   0   |     |       |
|   1   |  9  |   0   |
|   2   |  2  |   0   |
|   3   |     |       |
|   4   |     |       |
|   5   |     |       |
|   6   |     |       |
|   7   |     |       |

当我们遍历这个数组时，顺序将是这个表示方式中的顺序，所以 9 会在 2 之前。

你可以在 这里了解更多相关内容。