Haszować słownik?

Do celów buforowania potrzebuję wygenerować klucz pamięci podręcznej z argumentów GET, które są obecne w dict.

Obecnie używam sha1(repr(sorted(my_dict.items())))( sha1()jest to wygodna metoda wykorzystująca wewnętrznie hashlib ), ale jestem ciekawy, czy istnieje lepszy sposób.

Jeśli twój słownik nie jest zagnieżdżony, możesz utworzyć zestaw zamrażający z elementami dyktu i użyć hash():

hash(frozenset(my_dict.items()))

Jest to znacznie mniej intensywne obliczeniowo niż generowanie ciągu JSON lub reprezentacja słownika.

AKTUALIZACJA: Zapoznaj się z komentarzami poniżej, dlaczego takie podejście może nie dać stabilnych wyników.

Użycie sorted(d.items())nie wystarczy, aby uzyskać stabilny repr. Niektóre wartości dmogą być również słownikami, a ich klucze nadal będą pojawiać się w dowolnej kolejności. Jeśli wszystkie klawisze są strunami, wolę używać:

json.dumps(d, sort_keys=True)

To powiedziawszy, jeśli skróty muszą być stabilne na różnych komputerach lub wersjach Pythona, nie jestem pewien, czy jest to kuloodporne. Możesz chcieć dodać argumenty separatorsi, ensure_asciiaby uchronić się przed wszelkimi zmianami wartości domyślnych. Byłbym wdzięczny za komentarze.

EDYCJA : Jeśli wszystkie twoje klucze są ciągami , to przed kontynuowaniem czytania tej odpowiedzi zapoznaj się ze znacznie prostszym (i szybszym) rozwiązaniem Jacka O'Connora (które działa również w przypadku haszowania zagnieżdżonych słowników).

Chociaż odpowiedź została zaakceptowana, tytuł pytania brzmi „Haszowanie słownika Pythona”, a odpowiedź jest niekompletna w odniesieniu do tego tytułu. (Jeśli chodzi o treść pytania, odpowiedź jest kompletna).

Zagnieżdżone słowniki

Jeśli ktoś szuka przepełnienia stosu, aby dowiedzieć się, jak haszować słownik, można natknąć się na to trafnie zatytułowane pytanie i pozostawić niezadowolony, jeśli ktoś próbuje haszować mnożenie zagnieżdżonych słowników. Powyższa odpowiedź nie zadziała w tym przypadku i będziesz musiał zaimplementować jakiś mechanizm rekurencyjny, aby pobrać hash.

Oto jeden taki mechanizm:

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: haszowanie obiektów i klas

hash()Funkcja działa świetnie, gdy hash klas lub instancji. Jednak tutaj jest jeden problem, który znalazłem z hashem, jeśli chodzi o obiekty:

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

Hasz jest taki sam, nawet po zmianie foo. Dzieje się tak, ponieważ tożsamość foo się nie zmieniła, więc hash jest taki sam. Jeśli chcesz, aby foo różnie haszowało w zależności od jego aktualnej definicji, rozwiązaniem jest haszowanie tego, co faktycznie się zmienia. W tym przypadku __dict__atrybut:

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

Niestety, kiedy próbujesz zrobić to samo z samą klasą:

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

Właściwość class __dict__nie jest zwykłym słownikiem:

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

Oto podobny mechanizm jak poprzednio, który będzie odpowiednio obsługiwał klasy:

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

Możesz użyć tego, aby zwrócić krotkę mieszającą dowolną liczbę elementów:

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

UWAGA: cały powyższy kod zakłada Python 3.x. Nie testowałem we wcześniejszych wersjach, choć zakładam, że make_hash()będzie działać powiedzmy w 2.7.2. Jeśli chodzi o to, by przykłady działały, to wiem

func.__code__ 

należy zastąpić

func.func_code

Oto jaśniejsze rozwiązanie.

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

Poniższy kod unika używania funkcji hash () w języku Python, ponieważ nie zapewnia ona skrótów spójnych podczas ponownych uruchomień Pythona (patrz funkcja skrótu w Pythonie 3.3 zwraca różne wyniki między sesjami ). make_hashable()skonwertuje obiekt na zagnieżdżone krotki, a make_hash_sha256()także skonwertuje na repr()skrót SHA256 zakodowany algorytmem 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=

Zaktualizowano odpowiedź z 2013 roku ...

Żadna z powyższych odpowiedzi nie wydaje mi się wiarygodna. Powodem jest użycie items (). O ile wiem, pojawia się to w kolejności zależnej od maszyny.

A może zamiast tego?

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

Aby zachować kolejność kluczy, zamiast hash(str(dictionary))lub hash(json.dumps(dictionary))wolałbym szybkie i brudne rozwiązanie:

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

Będzie działać nawet w przypadku typów takich jak DateTimei innych, które nie są serializowane w formacie JSON.

Możesz użyć frozendictmodułu innej firmy , aby zamrozić swój dykt i uczynić go hashowalnym.

from frozendict import frozendict
my_dict = frozendict(my_dict)

Do obsługi obiektów zagnieżdżonych możesz użyć:

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

Jeśli chcesz obsługiwać więcej typów, użyj 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

W tym celu możesz skorzystać z biblioteki map . W szczególności mapy. FrozenMap

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

Aby zainstalować maps, po prostu wykonaj:

pip install maps

Obsługuje również zagnieżdżony dictprzypadek:

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

Zastrzeżenie: jestem autorem mapsbiblioteki.

Jednym ze sposobów rozwiązania problemu jest utworzenie krotki elementów słownika:

hash(tuple(my_dict.items()))

Robię to tak:

hash(str(my_dict))