将字典进行哈希处理?

233

为了缓存目的,我需要从一个包含在字典中的GET参数生成一个缓存键。

目前,我正在使用sha1(repr(sorted(my_dict.items())))sha1()是一个使用hashlib内部的便捷方法),但我很好��是否有更好的方法。


7
这可能不能处理嵌套字典。最简短的解决方案是使用json.dumps(my_dict, sort_keys=True)替代,它会递归到字典值中。 - Andrey Fedorov
3
关于转储,请参考 http://stackoverflow.com/a/12739361/1082367,该网站指出:“pickle 的输出不能保证规范化,原因与 dict 和 set 的顺序不确定性相似。不要使用 pickle、pprint 或 repr 进行哈希处理。” - Matthew Cornell
2
有关哈希可变数据结构(如字典)的有趣背景故事:https://www.python.org/dev/peps/pep-0351/曾提出允许任意冻结对象,但被拒绝。有关理由,请参见python-dev中的此线程:https://mail.python.org/pipermail/python-dev/2006-February/060793.html - FluxLemur
1
如果你的数据是json格式,并且你想要语义不变的哈希,请查看https://github.com/schollii/sandals/blob/master/json_sem_hash.py。它适用于嵌套结构(当然,因为json),并且不依赖于像保留顺序这样的字典内部(在python的生命周期中已经发生了演变),如果两个数据结构在语义上相同,则会给出相同的哈希值(例如`{'a': 1, 'b':2}在语义上与{'b':2, 'a':1}`相同)。我还没有在任何太复杂的东西上使用过它,所以效果可能有所不同,但欢迎反馈。 - Oliver
1
@shelper 你忘记了 repr() 函数(在 Python 3 中可能还需要加上 .encode())。 - ThiefMaster
显示剩余2条评论
17个回答

3
你可以使用第三方 frozendict模块 来冻结你的字典并使其可哈希化。
from frozendict import frozendict
my_dict = frozendict(my_dict)

处理嵌套对象,您可以选择:

import collections.abc

def make_hashable(x):
    if isinstance(x, collections.abc.Hashable):
        return x
    elif isinstance(x, collections.abc.Sequence):
        return tuple(make_hashable(xi) for xi in x)
    elif isinstance(x, collections.abc.Set):
        return frozenset(make_hashable(xi) for xi in x)
    elif isinstance(x, collections.abc.Mapping):
        return frozendict({k: make_hashable(v) for k, v in x.items()})
    else:
        raise TypeError("Don't know how to make {} objects hashable".format(type(x).__name__))

如果您想支持更多类型,请使用functools.singledispatch(Python 3.7):
@functools.singledispatch
def make_hashable(x):
    raise TypeError("Don't know how to make {} objects hashable".format(type(x).__name__))

@make_hashable.register
def _(x: collections.abc.Hashable):
    return x

@make_hashable.register
def _(x: collections.abc.Sequence):
    return tuple(make_hashable(xi) for xi in x)

@make_hashable.register
def _(x: collections.abc.Set):
    return frozenset(make_hashable(xi) for xi in x)

@make_hashable.register
def _(x: collections.abc.Mapping):
    return frozendict({k: make_hashable(v) for k, v in x.items()})

# add your own types here

请注意,DataFrameHashable的一个实例,因为它具有__hash__函数,即使该函数返回错误消息。 - James Hirschorn
我回滚了你的更改,并提供了一个更具可扩展性的替代方案。 - Eric
不幸的是,我发现这种方法失败了。例如,<frozendict {'a': 2, 'b': 1}> 每次运行 Python 脚本时返回不同的哈希值。 - James Hirschorn
1
好的。我明白了,我需要的不仅仅是“可哈希”,它只保证相等的对象具有相同的哈希值。我正在开发一个版本,它将在运行之间给出相同的值,并且与Python版本无关等。 - James Hirschorn
1
哈希随机化是Python 3.7中默认启用的一项有意的安全功能。 - Eric
显示剩余3条评论

3
你可以使用地图库来完成这个任务。具体地说,使用地图.FrozenMap
import maps
fm = maps.FrozenMap(my_dict)
hash(fm)

安装maps只需执行以下操作:
pip install maps

它也处理嵌套的dict情况:
import maps
fm = maps.FrozenMap.recurse(my_dict)
hash(fm)

免责声明:我是maps库的作者。

该库不会对字典内部的列表进行排序,因此可能会产生不同的哈希值。应该有一个选项来对列表进行排序。frozenset 应该有所帮助,但我想知道如何处理包含字典列表的嵌套字典的情况,因为字典是不可哈希的。 - Suraj
1
@Suraj:它通过.recurse处理嵌套结构。请参见https://maps.readthedocs.io/en/latest/api.html#maps.FrozenMap.recurse。列表中的排序在语义上是有意义的,如果您想要无序性,则可以在调用`.recurse`之前将列表转换为集合。您还可以利用`.recurse`的`list_fn`参数来使用不同于`tuple`(例如`frozenset`)的可哈希数据结构。 - Pedro Cattori

0
一种解决问题的方法是将字典的项制作成元组:
hash(tuple(my_dict.items()))

0

对于嵌套结构,在顶层字典中具有字符串键时,您可以使用pickle(protocol = 5)并对字节对象进行哈希处理。如果需要安全性,可以使用安全序列化器。


0

这不是一个通用的解决方案(即仅在您的字典未嵌套时才能轻松工作),但由于没有人建议过,我认为分享它可能会有用。

可以使用(第三方)immutables包,并像这样创建一个不可变的字典“快照”:

from immutables import Map

map = dict(a=1, b=2)
immap = Map(map)
hash(immap)

这似乎比原始字典的字符串化更快。

我从这篇不错的文章中了解到了这一点。


你不需要第三方包来创建一个不可变字典 - bfontaine

-1
扩展Shay的回答。 我不得不为很多字典做这个操作,而yaml.dump或json.dump花费了很多时间。如果你没有嵌套的数据类型,这将是一种更快的处理方式。
  def dict_hash(dictionary: Dict[str, Any]) -> str:
      """MD5 hash of a dictionary."""
      dhash = hashlib.md5()
      ##sortedString = yaml.dump(dictionary, sort_keys=True)
      sortedString = str(collections.OrderedDict({k:dictionary[k] for k in sorted(dictionary)}))
      encoded = sortedString.encode()
      dhash.update(encoded)
      return dhash.hexdigest()

-6
我是这样做的:
hash(str(my_dict))

1
有人能解释一下这个方法有什么问题吗? - mhristache
9
字典在排序方面是不稳定的,因此hash(str({'a': 1, 'b': 2})) != hash(str({'b': 2, 'a': 1}))(尽管对于某些字典可能有效,但不能保证适用于所有字典)。 - Vlad Frolov
对于我的使用情况,这已经足够了。 - imbr

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接