Hashing un diccionario?

Para propósitos de almacenamiento en caché, necesito generar una clave de caché a partir de argumentos GET que están presentes en un dict.

Actualmente estoy usando sha1(repr(sorted(my_dict.items())))( sha1()es un método de conveniencia que usa hashlib internamente) pero tengo curiosidad por saber si hay una mejor manera.

Si su diccionario no está anidado, puede hacer un congelamiento con los elementos del dict y usar hash():

hash(frozenset(my_dict.items()))

Esto es mucho menos computacionalmente intenso que generar la cadena JSON o la representación del diccionario.

ACTUALIZACIÓN: consulte los comentarios a continuación, por qué este enfoque podría no producir un resultado estable.

Usar sorted(d.items())no es suficiente para obtener una repr estable. Algunos de los valores en dpodrían ser diccionarios también, y sus claves seguirán saliendo en un orden arbitrario. Mientras todas las teclas sean cadenas, prefiero usar:

json.dumps(d, sort_keys=True)

Dicho esto, si los hashes necesitan ser estables en diferentes máquinas o versiones de Python, no estoy seguro de que esto sea a prueba de balas. Es posible que desee agregar los argumentos separatorsy ensure_asciipara protegerse de cualquier cambio en los valores predeterminados allí. Agradecería los comentarios.

EDITAR : Si todas sus claves son cadenas , entonces antes de continuar leyendo esta respuesta, consulte la solución significativamente más simple (y más rápida) de Jack O'Connor (que también funciona para los diccionarios anidados hash).

Aunque se ha aceptado una respuesta, el título de la pregunta es "Hashing a python dictionary", y la respuesta es incompleta con respecto a ese título. (Con respecto al cuerpo de la pregunta, la respuesta está completa).

Diccionarios anidados

Si uno busca en Stack Overflow cómo hash un diccionario, uno puede tropezar con esta pregunta acertadamente titulada, y dejar insatisfecho si está intentando hash multiplicar diccionarios anidados. La respuesta anterior no funcionará en este caso, y tendrá que implementar algún tipo de mecanismo recursivo para recuperar el hash.

Aquí hay uno de esos 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()))))

Bonus: objetos y clases hash

La hash()función funciona muy bien cuando hash clases o instancias. Sin embargo, aquí hay un problema que encontré con hash, en lo que respecta a los objetos:

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

El hash es el mismo, incluso después de haber modificado foo. Esto se debe a que la identidad de foo no ha cambiado, por lo que el hash es el mismo. Si desea que el hash haga hash de manera diferente dependiendo de su definición actual, la solución es eliminar lo que realmente está cambiando. En este caso, el __dict__atributo:

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

Por desgracia, cuando intentas hacer lo mismo con la clase misma:

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

La __dict__propiedad de clase no es un diccionario normal:

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

Aquí hay un mecanismo similar al anterior que manejará las clases adecuadamente:

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

Puede usar esto para devolver una tupla hash de la cantidad de elementos que desee:

# -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 el código anterior supone Python 3.x. No probé en versiones anteriores, aunque supongo make_hash()que funcionará en, digamos, 2.7.2. En lo que a hacer el trabajo de ejemplos, que no sé que

func.__code__ 

debe ser reemplazado con

func.func_code

Aquí hay una solución más 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))  

El siguiente código evita el uso de la función hash () de Python porque no proporcionará hashes que sean consistentes en los reinicios de Python (ver la función hash en Python 3.3 devuelve resultados diferentes entre sesiones ). make_hashable()convertirá el objeto en tuplas anidadas y make_hash_sha256()también lo convertirá repr()en un hash SHA256 codificado en 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=

Actualizado desde 2013 respuesta ...

Ninguna de las respuestas anteriores me parece confiable. La razón es el uso de elementos (). Hasta donde yo sé, esto sale en un orden dependiente de la máquina.

¿Qué tal esto en su lugar?

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 el orden de las claves, en lugar de hash(str(dictionary))o hash(json.dumps(dictionary))preferiría una solución rápida y sucia:

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

Funcionará incluso para tipos como DateTimey más que no son serializables JSON.

Podrías usar el frozendictmódulo de terceros para congelar tu dict y hacerlo hashaable.

from frozendict import frozendict
my_dict = frozendict(my_dict)

Para manejar objetos anidados, puede ir con:

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

Si desea admitir más 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

Puede usar la biblioteca de mapas para hacer esto. Específicamente, mapas . Mapa congelado

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

Para instalar maps, solo haz:

pip install maps

También maneja el dictcaso anidado :

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

Descargo de responsabilidad: soy el autor de la mapsbiblioteca.

Una forma de abordar el problema es hacer una tupla de los elementos del diccionario:

hash(tuple(my_dict.items()))

Lo hago así:

hash(str(my_dict))