Hachage d'un dictionnaire?

À des fins de mise en cache, je dois générer une clé de cache à partir des arguments GET qui sont présents dans un dict.

J'utilise actuellement sha1(repr(sorted(my_dict.items())))( sha1()c'est une méthode pratique qui utilise hashlib en interne) mais je suis curieux de savoir s'il existe un meilleur moyen.

Si votre dictionnaire n'est pas imbriqué, vous pouvez créer un frozenset avec les éléments du dict et utiliser hash():

hash(frozenset(my_dict.items()))

Cela demande beaucoup moins de calculs que de générer la chaîne JSON ou la représentation du dictionnaire.

MISE À JOUR: S'il vous plaît voir les commentaires ci-dessous, pourquoi cette approche peut ne pas produire un résultat stable.

L'utilisation sorted(d.items())n'est pas suffisante pour nous procurer une reproduction stable. Certaines des valeurs de dpeuvent également être des dictionnaires, et leurs clés sortiront toujours dans un ordre arbitraire. Tant que toutes les clés sont des chaînes, je préfère utiliser:

json.dumps(d, sort_keys=True)

Cela dit, si les hachages doivent être stables sur différentes machines ou versions de Python, je ne suis pas certain que ce soit à l'épreuve des balles. Vous souhaiterez peut-être ajouter les arguments separatorset ensure_asciipour vous protéger de toute modification des valeurs par défaut. J'apprécierais les commentaires.

EDIT : Si toutes vos clés sont des chaînes , avant de continuer à lire cette réponse, veuillez consulter la solution nettement plus simple (et plus rapide) de Jack O'Connor (qui fonctionne également pour le hachage de dictionnaires imbriqués).

Bien qu'une réponse ait été acceptée, le titre de la question est "Hashing a python dictionary", et la réponse est incomplète en ce qui concerne ce titre. (En ce qui concerne le corps de la question, la réponse est complète.)

Dictionnaires imbriqués

Si l'on recherche Stack Overflow pour savoir comment hacher un dictionnaire, on peut tomber sur cette question bien intitulée, et ne pas être satisfait si l'on tente de hacher plusieurs dictionnaires imbriqués. La réponse ci-dessus ne fonctionnera pas dans ce cas, et vous devrez implémenter une sorte de mécanisme récursif pour récupérer le hachage.

Voici un de ces mécanismes:

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: Objets et classes de hachage

La hash()fonction fonctionne très bien lorsque vous hachez des classes ou des instances. Cependant, voici un problème que j'ai trouvé avec le hachage, en ce qui concerne les objets:

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

Le hachage est le même, même après avoir modifié foo. C'est parce que l'identité de foo n'a pas changé, donc le hachage est le même. Si vous voulez que foo hache différemment en fonction de sa définition actuelle, la solution est de hacher tout ce qui change réellement. Dans ce cas, l' __dict__attribut:

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

Hélas, lorsque vous essayez de faire la même chose avec la classe elle-même:

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

La __dict__propriété class n'est pas un dictionnaire normal:

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

Voici un mécanisme similaire au précédent qui gérera les classes de manière appropriée:

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

Vous pouvez l'utiliser pour renvoyer un tuple de hachage du nombre d'éléments que vous souhaitez:

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

REMARQUE: tout le code ci-dessus suppose Python 3.x. N'a pas testé dans les versions antérieures, bien que je suppose que make_hash()cela fonctionnera dans, disons, 2.7.2. En ce qui concerne les travaux faisant des exemples, je ne sais que

func.__code__ 

doit être remplacé par

func.func_code

Voici une solution plus claire.

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

Le code ci-dessous évite d'utiliser la fonction Python hash () car elle ne fournira pas de hachages cohérents entre les redémarrages de Python (voir la fonction de hachage dans Python 3.3 renvoie des résultats différents entre les sessions ). make_hashable()convertira l'objet en tuples imbriqués et make_hash_sha256()convertira également le repr()en un hachage SHA256 encodé 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=

Mis à jour à partir de la réponse de 2013 ...

Aucune des réponses ci-dessus ne me semble fiable. La raison en est l'utilisation d'éléments (). Autant que je sache, cela sort dans un ordre dépendant de la machine.

Que diriez-vous de cela à la place?

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

Pour préserver l'ordre des clés, au lieu de hash(str(dictionary))ou hash(json.dumps(dictionary))je préférerais une solution rapide et sale:

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

Cela fonctionnera même pour les types comme DateTimeet plus qui ne sont pas sérialisables JSON.

Vous pouvez utiliser le frozendictmodule tiers pour geler votre dict et le rendre hachable.

from frozendict import frozendict
my_dict = frozendict(my_dict)

Pour gérer les objets imbriqués, vous pouvez utiliser:

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 vous souhaitez prendre en charge plus de types, utilisez 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

Vous pouvez utiliser la bibliothèque de cartes pour ce faire. Plus précisément, les cartes.

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

Pour l'installer maps, faites simplement:

pip install maps

Il gère également le dictcas imbriqué :

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

Avertissement: Je suis l'auteur de la mapsbibliothèque.

Une façon d'aborder le problème consiste à créer un tuple des éléments du dictionnaire:

hash(tuple(my_dict.items()))

Je fais ça comme ça:

hash(str(my_dict))