Hacher un dictionnaire ?

Question

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

Actuellement, j'utilise sha1(repr(sorted(my_dict.items()))) ( sha1() est une méthode pratique qui utilise hashlib en interne) mais je suis curieux de savoir s'il existe une meilleure méthode.

Answer 1

Utilisation de sorted(d.items()) n'est pas suffisant pour obtenir une répression stable. Certaines des valeurs dans d peuvent aussi être des dictionnaires, et leurs clés seront toujours présentées dans un ordre arbitraire. Tant que toutes les clés sont des chaînes de caractères, 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 infaillible. Vous pourriez vouloir ajouter l'option separators y ensure_ascii pour vous protéger de toute modification des valeurs par défaut. J'apprécierais les commentaires.

Answer 2

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

hash(frozenset(my_dict.items()))

Cette opération est beaucoup moins gourmande en ressources informatiques que la génération de la chaîne ou de la représentation JSON du dictionnaire.

MISE À JOUR : Veuillez consulter les commentaires ci-dessous, qui expliquent pourquoi cette approche pourrait ne pas produire un résultat stable.

Answer 3

EDITAR : Si toutes vos clés sont des chaînes de caractères Alors, avant de poursuivre la lecture de cette réponse, veuillez consulter l'article de Jack O'Connor sur le sujet. une solution plus simple (et plus rapide) (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 cherche sur Stack Overflow comment hacher un dictionnaire, on risque de tomber sur cette question bien intitulée, et de ne pas être satisfait si l'on tente de hacher des dictionnaires imbriqués plusieurs fois. 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 l'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 : Hachage d'objets et de classes

El hash() fonctionne très bien lorsque vous hachurez 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 que j'ai 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 soit haché différemment en fonction de sa définition actuelle, la solution est de hacher ce qui change réellement. Dans ce cas, le __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 tentez de faire la même chose avec la classe elle-même :

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

La classe __dict__ n'est pas un dictionnaire normal :

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

Voici un mécanisme similaire au précédent qui traitera 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 contenant autant d'éléments que vous le 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__]))

NOTE : tout le code ci-dessus suppose Python 3.x. Je n'ai pas testé les versions antérieures, bien que je suppose que make_hash() fonctionnera dans, disons, 2.7.2. Pour ce qui est de faire fonctionner les exemples, je faire sachez que

func.__code__ 

doit être remplacé par

func.func_code

Answer 4

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

Answer 5

Mise à jour de la réponse de 2013...

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

Et pourquoi pas ça à 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