问题 Python,dict的校验和


我正在考虑创建一个dict的校验和来知道它是否被修改过 目前我有这个:

>>> import hashlib
>>> import pickle
>>> d = {'k': 'v', 'k2': 'v2'}
>>> z = pickle.dumps(d)
>>> hashlib.md5(z).hexdigest()
'8521955ed8c63c554744058c9888dc30'

也许存在更好的解决方案?

注意:我想创建一个独特的dict id来创建一个好的Etag。

编辑: 我可以在dict中获得抽象数据。


11873
2017-08-03 08:41


起源

你的dict包含什么?如果它只是字符串(比如说),你可以只散列排序的字符串表示: hash(repr(sorted(my_dict.items())))。 - Katriel
什么是抽象数据? dict-hash算法的稳定性和工作性很大程度上取决于它所拥有的数据。例如,如果你有一个dicts的词典怎么办? - Katriel
这些数据类型: code.google.com/appengine/docs/python/datastore/... - sahid


答案:


像这样的东西:

reduce(lambda x,y : x^y, [hash(item) for item in d.items()])

获取dict中每个(key,value)元组的哈希值并将它们全部异或。

@katrielalex 如果dict包含不可用的项目,您可以这样做:

hash(str(d))

或者甚至更好

hash(repr(d))

9
2017-08-03 08:52



这很优雅。 - Colin Valliant
如果dict包含不可用的项目怎么办? - Katriel
你做不到 str(d) 没有错误否定,因为项目在字符串表示中出现的顺序是未定义的。 - Katriel
如果没有这样做,就无法从dict中获取定义顺序的项目 sorted(d.iteritems()) - agf
@agf:你绝对是对的!但第一个解决方案( reduce() thing)将哈希与XOR结合起来,这会丢弃元素的顺序。 - Bart


我不知道是否 pickle 保证每次都以相同的方式序列化哈希。

如果你只有字典,我会去打电话的组合 keys()sorted(),根据排序的键/值对构建一个字符串,并计算其上的校验和


1
2017-08-03 08:49



"".join("%s,%s"%(x,y) for x, y in sorted(foo.iteritems())) (其中foo是dict)可以作为你可以散列的签名。 - Noufal Ibrahim
如果我在我的词典中有抽象数据呢?那不是问题吗? - sahid
我认为你必须做一个递归函数,它将序列化每个子结构的排序数据 - Tudor Constantin
如果dict包含dicts怎么办?然后对它们进行字符串格式化不会产生可靠的唯一结果。 - Katriel
这就是为什么我说需要递归函数 - 主要函数中包含的每个dict应该被视为主要函数 - 它的键被排序和序列化基于 - Tudor Constantin


如你所说,你想根据字典内容生成一个Etag, OrderedDict 保留字典顺序可能是更好的候选人。只需通过键,值对进行迭代,然后构造您的Etag字符串。


0
2017-08-03 09:14





我想你可能没有意识到一些细微之处。第一个问题是项目在dict中出现的顺序不是由实现定义的。这意味着只需要求 str 一个字典不起作用,因为你可以

str(d1) == "{'a':1, 'b':2}"
str(d2) == "{'b':2, 'a':1}"

这些将散列到不同的值。如果你在dict中只有hashable项目,你可以哈希它们然后加入它们的哈希值 @Bart 做或简单

hash(tuple(sorted(hash(x) for x in d.items())))

请注意 sorted,因为你必须确保散列元组以相同的顺序出现,而不管项目在dict中出现的顺序。如果你在dict中有dicts,你可以解决这个问题,但这会很复杂。

但是如果你允许的话,很容易打破这样的任何实现 随意 字典中的数据,因为你可以简单地写一个破碎的对象 __hash__ 实施和使用。你不能使用 id,因为那时你可能有相同的项目比较不同。

这个故事的寓意是Python中不支持哈希词典。


0
2017-08-03 10:30





在Python 3中,哈希函数用随机数初始化,对于每个python会话都是不同的。如果这对于预期的应用是不可接受的,请使用例如zlib.adler32为dict构建校验和:

import zlib

d={'key1':'value1','key2':'value2'}
checksum=0
for item in d.items():
    c1 = 1
    for t in item:
        c1 = zlib.adler32(bytes(repr(t),'utf-8'), c1)
    checksum=checksum ^ c1

print(checksum)

0
2018-02-09 22:49