确定性密钥序列化

Question

我正在编写一个持久保存到磁盘的映射类。我目前只允许 str 键，但如果我可以使用更多类型，那就太好了：希望达到任何可散列的类型（即与内置 dict)，但更合理的是我会接受 string、unicode、int 和这些类型的元组。

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

选项 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 本身对于我所定义的类型是否具有确定性已允许这里。我相信由于 str/unicode 文字的变化，这将无法在 2/3 版本障碍中幸存。这对于 2**32 - 1 2**32 - 1 的整数也不起作用。 x < 2**64 在 32 和 64 位平台之间跳转。是否还有其他条件（即字符串在同一解释器中的不同条件下序列化是否不同）？ 编辑：我只是想了解这种情况发生的情况，而不一定要克服它们。

选项 3：自定义 repr

另一个可能有点过分的选项是编写我自己的 repr，它可以消除我知道（或怀疑可能存在）问题的 repr 内容。我刚刚在这里写了一个例子： http://gist.github.com/423945

（如果这一切失败得很惨，然后我可以存储键的哈希值以及键和值的pickle，然后迭代具有匹配哈希值的行，寻找一个能够unpickles到预期键的哈希值，但这确实使其他一些事情变得复杂我宁愿不这样做编辑： 事实证明 内置哈希在跨平台上也不是确定性的。）

有什么见解吗？

Answer 1

重要提示：如果字典或集合类型嵌入到您尝试序列化的对象中，则 repr() 不是确定性的。密钥可以按任何顺序打印。

例如 print repr({'a':1, 'b':2}) 可能会打印为 {'a':1, 'b':2}或 {'b':2, 'a':1}，具体取决于 Python 决定如何管理字典中的键。

Answer 2

在阅读了基本类型的 repr 实现的大部分源代码（CPython 2.6.5）后，我得出结论（有合理的信心）这些类型的 repr 实际上是确定性的。但坦率地说，这是预料之中的。

我相信 repr 方法很容易受到 marshal 方法崩溃的几乎所有相同情况的影响（longs > 2 **32 永远不可能是 32 位机器上的 int，不能保证在版本或解释器等之间不会改变）。

我暂时的解决方案是使用 repr 方法并编写一个全面的测试套件，以确保 repr 在我使用的各种平台上返回相同的值。

从长远来看，自定义 repr 函数将消除所有平台/实现差异，但对于手头的项目来说肯定是大材小用。不过，我将来可能会这样做。

Answer 3

“任何对于内置字典可接受的键的值”都是不可行的：此类值包括未定义 __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 4

您在段落中提到了一些要求，我认为您可能希望对这些要求更清楚一些。到目前为止，我了解到：

• 您正在构建一个基本上是字典的 SQLite 后端。
• 您希望允许键的类型超过基本字符串类型（哪些类型）。
• 你希望它能够在 Python 2 中幸存 -> Python 3 障碍。
• 您希望支持 2**32 以上的大整数作为键。
• 能够存储无限值（因为您不希望发生哈希冲突）。

那么，您是否正在尝试构建一个通用的“这可以解决所有问题”的解决方案，或者只是尝试解决当前项目中继续存在的紧迫问题？您应该多花一点时间来提出一套明确的要求。

对我来说，使用哈希似乎是最好的解决方案，但后来你抱怨说，你将有多行具有相同的哈希，这意味着你将存储足够的值，甚至不用担心哈希。