为字典生成唯一标识符？

Question

为字典生成唯一标识符？

3

我有一个问题，我要生成一个随机字典，可能有很多种可能性（比如说，我有25000个不同的字典）。我想为每一个可能性生成一个标识符，一个ID。我的要求是：

如果两个字典的每个键都具有完全相同的值，则它们的ID相同
如果两个字典具有不同的ID，则它们的内容必须至少有一个差异。
ID在每次运行程序时保持不变（id(x)无效）
额外要求：ID在Python的不同版本（2.6、2.7、3.4、3.6）中保持不变

我的当前想法是使用哈希函数（尽管我对此知之甚少），并执行以下操作（假设有一个整数/浮点数字典）：

import hashlib
def getID(mydic):
    ID = 0
    for x in mydic.keys():
        # Hash the content
        ID = ID + int(hashlib.sha256(str(mydic[x]).encode('utf-8')).hexdigest(), 16)
        # Hash the key
        ID = ID + int(hashlib.sha256(x.encode('utf-8')).hexdigest(), 16)
    return (ID % 10**10)

据我了解，这种方法在大多数情况下应该是有效的，但根据字典的实际内容和键，不排除两个不同的字典产生相同的 ID 的可能性。例如，如果我没有对键进行哈希处理并且两个不同的条目可以是“1.0”，那么就可能会出现问题。

你有什么建议吗？希望这些建议不要依赖于运气。

编辑：我添加了更大的代码，基本上是一个随机参数优化。在 pastebin 上的代码。

- Milleuros

1

任何将大输入集映射到较小集合的哈希都会产生冲突。因此总是存在一点"运气"成分。你可以这样做：通过ID比较字典。如果ID不同，则字典不同。如果ID相同，则按值比较字典。 - Wombatz

@tyteen4a03 我有一个算法，我想在许多参数集上进行测试。我随机选择一组参数，然后运行我的算法，但我希望能够将该参数集保存到一个文件中，以免被其他参数集覆盖，这样我就可以始终知道哪些参数导致了哪些结果。你希望我在pastebin上发布更大的代码吗？ - Milleuros

问题是，为什么字典的顺序很重要？ - Milleuros

@MSeifert 是的，它们包含相同的键。至于字典顺序，我刚刚尝试了一下我的函数和你提供的两个字典，结果得到了相同的数字。这是因为我在 OP 中的函数是所有哈希键和所有哈希值的总和（可交换的）。 - Milleuros

@MSeifert 很抱歉如果这让你感觉像是我在争辩，我只是想要理解。我写了一个小脚本来打印一个样本字符串的哈希值（一些随机的键盘敲击），然后我在Python 2.7中运行了这个脚本6次，在Python 3.4中运行了25次，每次都得到相同的值。（每次运行不同的Python实例）。我不明白为什么一个字符串的哈希值会在不同的会话之间随机化，因为这会破坏哈希函数的作用（我只在5天前学习了哈希的概念）。 - Milleuros

显示剩余13条评论

2个回答

0

靠运气吧，其他人也是出于很好的原因这样做。除非您的ID比您可以编码的最长字典还要长，或者您选择不编码某些字典，否则将会有多个具有相同ID的字典。这只是一个简单的计数问题。假设您将一个字典命名为1，另一个字典命名为2，以此类推。要么您最终用完数字，要么您的ID变得更长。通常情况下，当我们想要一些代表对象的小量时，我们使用ID或哈希。如果您愿意让字典的名称与字典本身一样大，那么您正在寻找规范表示，而不是ID或哈希。

像sha256这样的东西的优点在于，我们认为很难找到两个具有相同哈希值的输入。即使理论上肯定存在多个输入给出相同的sha256，但我们相信没有人发现过两个给出相同sha256的输入。因此，您几乎可以放心地忽略可能遇到哈希碰撞的可能性。

- Sam Hartman

谢谢，我可能会接受你的答案并依靠运气。快速问题，如果我要使用“规范表示法”（我不知道这个词），我应该从哪里开始寻找？ - Milleuros

那将是一个不同的问题，但可以看一下 canonicaljson 作为一个很接近的例子。 - Sam Hartman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Laurent LAPORTE · Accepted Answer

创建一个ID，需要创建一个不可变对象。由于键是无序的，您可能需要对它们进行排序。

例如：

mydict = {'a': 1, 'c': 9, 'b': 3}

values = tuple(sorted(mydict.items()))
# -> (('a', 1), ('b', 3), ('c', 9))

然后，您可以使用自己的哈希算法，例如 sha256：

import hashlib

def hash_item(m, k, v):
    m.update(k.encode('utf-8'))
    m.update(str(k).encode('utf-8'))

m = hashlib.sha256()
for k, v in values:
    hash_item(m, k, v)
print(m.digest())
# -> b'\xa5\xb42\xee\x03\x07\xbe\x7f\xa2:\xa0\x04a\xf5N\xee4\xba\x9dE%\x1bU\x04V}7\xa8\xda3\x9d\xff'