Hashing um dicionário?

Para fins de armazenamento em cache, eu preciso gerar uma chave de cache a partir dos argumentos GET que estão presentes em um dict.

Atualmente estou usando sha1(repr(sorted(my_dict.items())))( sha1()é um método de conveniência que usa hashlib internamente), mas estou curioso para saber se existe uma maneira melhor.

Se o seu dicionário não estiver aninhado, você poderá criar um frozenset com os itens do dict e usar hash():

hash(frozenset(my_dict.items()))

Isso é muito menos computacionalmente intenso do que gerar a sequência JSON ou representação do dicionário.

ATUALIZAÇÃO: Por favor, veja os comentários abaixo, por que essa abordagem pode não produzir um resultado estável.

Usar sorted(d.items())não é suficiente para obter um repr estável. Alguns dos valores também dpodem ser dicionários, e suas chaves ainda serão exibidas em uma ordem arbitrária. Contanto que todas as chaves sejam strings, eu prefiro usar:

json.dumps(d, sort_keys=True)

Dito isto, se os hashes precisarem ser estáveis ​​em diferentes máquinas ou versões do Python, não tenho certeza de que isso seja à prova de balas. Você pode adicionar os argumentos separatorse ensure_asciipara se proteger de quaisquer alterações nos padrões lá. Eu apreciaria comentários.

EDIT : Se todas as suas chaves são strings , então antes de continuar a ler esta resposta, consulte significativamente de Jack O'Connor solução mais simples (e mais rápido) (que também trabalha para hash dicionários aninhados).

Embora uma resposta tenha sido aceita, o título da pergunta é "Hashing um dicionário python" e a resposta está incompleta em relação a esse título. (No que diz respeito ao corpo da pergunta, a resposta está completa.)

Dicionários aninhados

Se alguém pesquisar Stack Overflow para saber como fazer hash em um dicionário, poderá se deparar com essa pergunta com título adequado e ficar insatisfeito se estiver tentando hash multiplicar dicionários aninhados. A resposta acima não funcionará neste caso, e você precisará implementar algum tipo de mecanismo recursivo para recuperar o hash.

Aqui está um desses mecanismos:

import copy

def make_hash(o):

  """
  Makes a hash from a dictionary, list, tuple or set to any level, that contains
  only other hashable types (including any lists, tuples, sets, and
  dictionaries).
  """

  if isinstance(o, (set, tuple, list)):

    return tuple([make_hash(e) for e in o])    

  elif not isinstance(o, dict):

    return hash(o)

  new_o = copy.deepcopy(o)
  for k, v in new_o.items():
    new_o[k] = make_hash(v)

  return hash(tuple(frozenset(sorted(new_o.items()))))

Bônus: Hashing de objetos e classes

A hash()função funciona muito bem quando você hash classes ou instâncias. No entanto, aqui está um problema que encontrei com o hash, no que diz respeito aos objetos:

class Foo(object): pass
foo = Foo()
print (hash(foo)) # 1209812346789
foo.a = 1
print (hash(foo)) # 1209812346789

O hash é o mesmo, mesmo depois que eu mudei de foo. Isso ocorre porque a identidade de foo não mudou, então o hash é o mesmo. Se você deseja que o hash seja diferente de acordo com sua definição atual, a solução é fazer o hash do que está realmente mudando. Nesse caso, o __dict__atributo:

class Foo(object): pass
foo = Foo()
print (make_hash(foo.__dict__)) # 1209812346789
foo.a = 1
print (make_hash(foo.__dict__)) # -78956430974785

Infelizmente, quando você tenta fazer o mesmo com a própria classe:

print (make_hash(Foo.__dict__)) # TypeError: unhashable type: 'dict_proxy'

A __dict__propriedade da classe não é um dicionário normal:

print (type(Foo.__dict__)) # type <'dict_proxy'>

Aqui está um mecanismo semelhante ao anterior, que manipulará as classes adequadamente:

import copy

DictProxyType = type(object.__dict__)

def make_hash(o):

  """
  Makes a hash from a dictionary, list, tuple or set to any level, that 
  contains only other hashable types (including any lists, tuples, sets, and
  dictionaries). In the case where other kinds of objects (like classes) need 
  to be hashed, pass in a collection of object attributes that are pertinent. 
  For example, a class can be hashed in this fashion:

    make_hash([cls.__dict__, cls.__name__])

  A function can be hashed like so:

    make_hash([fn.__dict__, fn.__code__])
  """

  if type(o) == DictProxyType:
    o2 = {}
    for k, v in o.items():
      if not k.startswith("__"):
        o2[k] = v
    o = o2  

  if isinstance(o, (set, tuple, list)):

    return tuple([make_hash(e) for e in o])    

  elif not isinstance(o, dict):

    return hash(o)

  new_o = copy.deepcopy(o)
  for k, v in new_o.items():
    new_o[k] = make_hash(v)

  return hash(tuple(frozenset(sorted(new_o.items()))))

Você pode usar isso para retornar uma tupla de hash de quantos elementos você desejar:

# -7666086133114527897
print (make_hash(func.__code__))

# (-7666086133114527897, 3527539)
print (make_hash([func.__code__, func.__dict__]))

# (-7666086133114527897, 3527539, -509551383349783210)
print (make_hash([func.__code__, func.__dict__, func.__name__]))

NOTA: todo o código acima assume o Python 3.x. Não testou em versões anteriores, embora eu assuma make_hash()que funcionará, digamos, 2.7.2. Tanto quanto fazer a exemplos de trabalho, eu não sei que

func.__code__ 

deve ser substituído por

func.func_code

Aqui está uma solução mais clara.

def freeze(o):
  if isinstance(o,dict):
    return frozenset({ k:freeze(v) for k,v in o.items()}.items())

  if isinstance(o,list):
    return tuple([freeze(v) for v in o])

  return o


def make_hash(o):
    """
    makes a hash out of anything that contains only list,dict and hashable types including string and numeric types
    """
    return hash(freeze(o))  

O código abaixo evita o uso da função hash () do Python porque não fornecerá hashes consistentes nas reinicializações do Python (consulte a função hash no Python 3.3 retorna resultados diferentes entre as sessões ). make_hashable()converterá o objeto em tuplas aninhadas e make_hash_sha256()também converterá repr()em um hash SHA256 codificado em base64.

import hashlib
import base64

def make_hash_sha256(o):
    hasher = hashlib.sha256()
    hasher.update(repr(make_hashable(o)).encode())
    return base64.b64encode(hasher.digest()).decode()

def make_hashable(o):
    if isinstance(o, (tuple, list)):
        return tuple((make_hashable(e) for e in o))

    if isinstance(o, dict):
        return tuple(sorted((k,make_hashable(v)) for k,v in o.items()))

    if isinstance(o, (set, frozenset)):
        return tuple(sorted(make_hashable(e) for e in o))

    return o

o = dict(x=1,b=2,c=[3,4,5],d={6,7})
print(make_hashable(o))
# (('b', 2), ('c', (3, 4, 5)), ('d', (6, 7)), ('x', 1))

print(make_hash_sha256(o))
# fyt/gK6D24H9Ugexw+g3lbqnKZ0JAcgtNW+rXIDeU2Y=

Atualizado a partir da resposta de 2013 ...

Nenhuma das respostas acima me parece confiável. O motivo é o uso de itens (). Tanto quanto eu sei, isso sai em uma ordem dependente da máquina.

Que tal isso?

import hashlib

def dict_hash(the_dict, *ignore):
    if ignore:  # Sometimes you don't care about some items
        interesting = the_dict.copy()
        for item in ignore:
            if item in interesting:
                interesting.pop(item)
        the_dict = interesting
    result = hashlib.sha1(
        '%s' % sorted(the_dict.items())
    ).hexdigest()
    return result

Para preservar a ordem das chaves, em vez de hash(str(dictionary))ou hash(json.dumps(dictionary))prefiro uma solução rápida e suja:

from pprint import pformat
h = hash(pformat(dictionary))

Funcionará mesmo para tipos como DateTimee mais que não são JSON serializáveis.

Você pode usar o frozendictmódulo de terceiros para congelar seu ditado e torná-lo lavável.

from frozendict import frozendict
my_dict = frozendict(my_dict)

Para manipular objetos aninhados, você pode usar:

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__))

Se você deseja dar suporte a mais tipos, use 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

Você pode usar a biblioteca de mapas para fazer isso. Especificamente, maps.FrozenMap

import maps
fm = maps.FrozenMap(my_dict)
hash(fm)

Para instalar maps, basta fazer:

pip install maps

Ele também lida com o dictcaso aninhado :

import maps
fm = maps.FrozenMap.recurse(my_dict)
hash(fm)

Disclaimer: Eu sou o autor da mapsbiblioteca.

Uma maneira de abordar o problema é fazer uma tupla dos itens do dicionário:

hash(tuple(my_dict.items()))

Eu faço assim:

hash(str(my_dict))