确定性键序列化

Question

我正在写一个可以把数据保存到磁盘的映射类。目前我只允许使用 str 类型的键，但我希望能用更多类型的键：希望能支持所有可哈希的类型（也就是和内置的 dict 一样的要求），不过更实际一点，我希望能接受字符串、Unicode、整数，以及这些类型的元组。

为此，我想设计一个确定性的序列化方案。

选项 1 - 使用 Pickle 序列化键

我最初的想法是使用 pickle（或 cPickle）模块来序列化键，但我发现 pickle 和 cPickle 的输出结果不一致：

>>> import pickle
>>> import cPickle
>>> def dumps(x):
...     print repr(pickle.dumps(x))
...     print repr(cPickle.dumps(x))
... 
>>> dumps(1)
'I1\n.'
'I1\n.'
>>> dumps('hello')
"S'hello'\np0\n."
"S'hello'\np1\n."
>>> dumps((1, 2, 'hello'))
"(I1\nI2\nS'hello'\np0\ntp1\n."
"(I1\nI2\nS'hello'\np1\ntp2\n."

有没有什么 pickle 的实现或协议组合，对于某些类型是确定性的（例如，是否只能使用 cPickle 的协议 0）？

选项 2 - 使用 repr 和 ast.literal_eval

另一个选项是使用 repr 来输出，使用 ast.literal_eval 来加载。我写了一个函数来判断给定的键是否能通过这个过程（它对允许的类型比较保守）：

def is_reprable_key(key):
    return type(key) in (int, str, unicode) or (type(key) == tuple and all(
        is_reprable_key(x) for x in key))

这个方法的问题在于 repr 本身对于我允许的类型是否是确定性的。我认为这可能无法跨越 2/3 版本的障碍，因为字符串和 Unicode 字面量发生了变化。对于整数来说，在 32 位和 64 位平台之间跳转时，2**32 - 1 < x < 2**64 也会有问题。还有其他条件吗（也就是说，在同一个解释器中，字符串在不同条件下的序列化是否会不同）？ 编辑：我只是想了解这个方法失效的条件，并不一定要克服它们。

选项 3: 自定义 repr

另一个可能有点过于复杂的选项是写一个自己的 repr，把我知道（或怀疑可能会）出问题的内容扁平化。我在这里写了一个例子： http://gist.github.com/423945

（如果这些方法都失败了，我可以存储键的哈希值，以及键和值的 pickle，然后在哈希匹配的行中查找能解压出预期键的项，但这样会让其他事情变得复杂，我不太想这样做。 编辑： 结果发现 内置的 hash 在不同平台上也是不确定的。算了。）

有什么见解吗？

Answer 1

说“任何可以作为内置字典的键的值”是不现实的：这些值包括一些类的实例，这些类没有定义__hash__或比较方法，系统会隐式地使用它们的id来进行哈希和比较。而且，即使是同一个程序的不同运行，这些id也不会相同（除非这些运行在所有方面都是完全相同的，这很难做到——比如输入完全相同、开始时间完全相同、环境完全相同等等）。

对于字符串、Unicode、整数，以及所有这些类型的元组（包括嵌套元组），marshal模块可能会有帮助（但仅限于同一个Python版本：不同版本之间的序列化代码可能会变化）。例如：

>>> marshal.dumps(23)
'i\x17\x00\x00\x00'
>>> marshal.dumps('23')
't\x02\x00\x00\x0023'
>>> marshal.dumps(u'23')
'u\x02\x00\x00\x0023'
>>> marshal.dumps((23,))
'(\x01\x00\x00\x00i\x17\x00\x00\x00'

这是Python 2；Python 3会类似（除了所有这些字节字符串的表示前面会有一个b，这只是个表面问题，当然u'23'会变成无效语法，而'23'会变成Unicode字符串）。你可以看到大致的思路：前面的字节表示类型，比如u表示Unicode字符串，i表示整数，(表示元组；然后对于容器，会有一个小端整数表示项目的数量，后面跟着这些项目本身，整数会被序列化成小端格式。marshal的设计是为了在不同平台之间可移植（针对特定版本；而不是跨版本），因为它被用作编译字节码文件（.pyc或.pyo）的底层序列化方式。

Answer 2

重要提示：如果你要序列化的对象里面包含字典或集合类型，使用 repr() 的结果是不确定的，也就是说，键的顺序可能会乱。

举个例子，print repr({'a':1, 'b':2}) 可能会显示为 {'a':1, 'b':2}，也可能会显示为 {'b':2, 'a':1}，这取决于 Python 是怎么处理字典里的键的。

Answer 3

在阅读了很多关于CPython 2.6.5的源代码后，我得出的结论是，基本类型的repr确实是确定性的。老实说，这个结果我早就预料到了。

我认为，repr方法在很多情况下会遇到和marshal方法一样的问题，比如在32位机器上，超过2的32次方的long永远不能被当作int使用，而且不同版本或解释器之间的结果也不一定保持一致等等。

目前，我的解决办法是使用repr方法，并编写一个全面的测试套件，以确保在我使用的不同平台上，repr返回的值是相同的。

从长远来看，定制的repr函数可以消除所有平台和实现之间的差异，但对于当前的项目来说，这样做有点过于复杂。不过，我将来可能会考虑这样做。