Haszować słownik?

156

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.

ThiefMaster
źródło
4
może to nie działać z zagnieżdżonymi dyktami. najkrótszym rozwiązaniem jest użycie zamiast tego json.dumps (my_dict, sort_keys = True), który będzie się powtarzał w wartościach dict.
Andrey Fedorov
2
FYI re: dumps, stackoverflow.com/a/12739361/1082367 mówi: „Nie ma gwarancji , że dane wyjściowe z pikle będą kanoniczne z podobnych powodów, aby dyktować i ustawiać kolejność, która jest niedeterministyczna. Nie używaj pikle, pprint lub repr do mieszania ”.
Matthew Cornell,
posortuj klucze dyktowania, a nie elementy, wysłałbym również klucze do funkcji skrótu.
nyuwec
2
Ciekawa historia o haszowaniu zmiennych struktur danych (takich jak słowniki): zaproponowano python.org/dev/peps/pep-0351, aby umożliwić dowolne zamrażanie obiektów, ale odrzucono. Aby zapoznać się z uzasadnieniem, zobacz ten wątek w python-dev: mail.python.org/pipermail/python-dev/2006-Feb February
FluxLemur
Jeśli Twoje dane mają format json i chcesz semantycznie niezmienną mieszanie, wyewidencjonuj github.com/schollii/sandals/blob/master/json_sem_hash.py . Działa na strukturach zagnieżdżonych (oczywiście od json) i nie zależy od elementów wewnętrznych dykta, takich jak zachowany porządek (który ewoluował przez całe życie Pythona) i da ten sam hash, jeśli dwie struktury danych są semantycznie takie same ( like {'a': 1, 'b':2}jest semantycznie taki sam jak {'b':2, 'a':1}). Nie użyłem go jeszcze do niczego zbyt skomplikowanego, więc YMMV, ale mile widziane opinie.
Oliver

Odpowiedzi:

110

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.

Imran
źródło
9
To nie zadziałało w przypadku zagnieżdżonego słownika. Nie próbowałem rozwiązania poniżej (zbyt skomplikowane). Rozwiązanie OP działa doskonale. Zamieniłem sha1 na hash, aby zapisać import.
spatel
9
@Ceaser To nie zadziała, ponieważ krotka oznacza zamawianie, ale elementy dyktowania są nieuporządkowane. Frozenset jest lepszy.
Antymon
28
Uważaj na wbudowany hash, jeśli coś musi być spójne na różnych komputerach. Implementacje Pythona na platformach chmurowych, takich jak Heroku i GAE, zwrócą różne wartości dla hash () w różnych instancjach, co czyni go bezużytecznym dla wszystkiego, co musi być współdzielone między dwoma lub więcej „maszynami” (dynos w przypadku heroku)
Ben Roberts
6
Może być interesujące, że hash()funkcja nie zapewnia stabilnych wyników. Oznacza to, że przy tych samych danych wejściowych zwraca różne wyniki z różnymi instancjami tego samego interpretera języka Python. Dla mnie wygląda na to, że za każdym razem, gdy uruchamiany jest interpreter, generowana jest jakaś wartość ziarna.
Hermann Schachner
7
spodziewany. ziarno jest wprowadzane ze względów bezpieczeństwa, o ile pamiętam, aby dodać jakiś rodzaj randomizacji pamięci. Nie możesz więc oczekiwać, że hash będzie taki sam między dwoma procesami Pythona
Nikokrock
137

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.

Jack O'Connor
źródło
6
To po prostu paranoja, ale JSON pozwala większości znaków pojawiać się w łańcuchach bez żadnego dosłownego znaku ucieczki, więc koder może dokonać wyboru, czy uciec przed znakami, czy po prostu je przepuścić. Ryzyko polega zatem na tym, że różne wersje (lub przyszłe wersje) kodera mogą domyślnie dokonywać różnych opcji ucieczki, a następnie program będzie obliczał różne wartości skrótu dla tego samego słownika w różnych środowiskach. ensure_asciiArgumentem by chronić przed tym całkowicie hipotetycznego problemu.
Jack O'Connor,
4
Przetestowałem wydajność tego z innym zestawem danych, jest znacznie szybszy niż make_hash. gist.github.com/charlax/b8731de51d2ea86c6eb9
charlax
3
@charlax Ujson nie gwarantuje kolejności par dyktowania, więc nie jest to bezpieczne
Arthurprs
11
To rozwiązanie działa tylko wtedy, gdy wszystkie klucze są ciągami, np. Json.dumps ({'a': {(0, 5): 5, 1: 3}}) nie powiedzie się.
kadee
5
@LorenzoBelli, możesz temu zaradzić, dodając default=strdo dumpspolecenia. Wygląda na to, że dobrze działa.
mlissner
63

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
jomido
źródło
isinstance pobiera sekwencję dla drugiego argumentu, więc isinstance (o, (zbiór, krotka, lista)) będzie działać.
Xealot
Dziękujemy za uczynienie mnie zrealizować frozenset mógł konsekwentnie parametry mieszania kwerendy :)
Xealot
1
Elementy muszą zostać posortowane, aby utworzyć ten sam hash, jeśli kolejność pozycji dyktowania jest inna, ale wartości kluczy nie są -> return hash (tuple (frozenset (sort (new_o.items ())))
Bas Koopmans
Miły! Dodałem również wywołanie do hashlist wokół i krotek. W przeciwnym razie pobiera moje listy liczb całkowitych, które są wartościami w moim słowniku i zwraca listy skrótów, co nie jest tym, czego chcę.
osa
Frozenset to kolekcja UNORDERED, więc nie ma nic do zyskania poprzez sortowanie jego danych wejściowych. Z drugiej strony listy i krotki są kolekcjami ZAMAWIANYMI („sekwencjami”), więc kolejność elementów w nich powinna mieć wpływ na wartość skrótu. Nie powinieneś ich sortować!
RobM
14

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))  
smartnut007
źródło
Jeśli zmienisz if isinstance(o,list):na, if isinstance(obj, (set, tuple, list)):ta funkcja może działać na dowolnym obiekcie.
Peter Schorn
10

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=
Claudio Fahey
źródło
1
make_hash_sha256(((0,1),(2,3)))==make_hash_sha256({0:1,2:3})==make_hash_sha256({2:3,0:1})!=make_hash_sha256(((2,3),(0,1))). To nie jest rozwiązanie, którego szukam, ale jest to fajny półprodukt. Myślę o dodaniu type(o).__name__na początku każdej z krotek, aby wymusić różnicowanie.
Poik
Jeśli chcesz również posortować listę:tuple(sorted((make_hashable(e) for e in o)))
Suraj
make_hash_sha256 () - fajnie!
jtlz2
1
@Suraj Nie powinieneś chcieć sortować listy przed haszowaniem, ponieważ listy, które mają zawartość w różnej kolejności, zdecydowanie nie są tym samym. Jeśli kolejność elementów nie ma znaczenia, problem polega na tym, że używasz niewłaściwej struktury danych. Zamiast listy powinieneś używać zestawu.
scottclowe
@scottclowe To bardzo prawda. Dzięki za dodanie tego punktu. Istnieją 2 scenariusze, w których nadal potrzebujesz listy (bez konkretnych potrzeb w zakresie zamawiania) - 1. Lista powtarzających się elementów. 2. Kiedy musisz bezpośrednio używać JSON. Ponieważ JSON nie obsługuje reprezentacji „zestawu”.
Suraj
5

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
Steve Yeago
źródło
Jak myślisz, dlaczego to ważne, że dict.itemsnie zwraca przewidywalnie uporządkowanej listy? frozensetdba o to
glarrain
2
Zestaw z definicji jest nieuporządkowany. Dlatego kolejność, w jakiej dodawane są obiekty, nie ma znaczenia. Musisz zdać sobie sprawę, że wbudowana funkcja hashnie dba o to, jak drukowana jest zawartość zamrożonego zestawu, czy coś w tym rodzaju. Przetestuj to na kilku komputerach i wersjach Pythona, a zobaczysz.
glarrain
Dlaczego używasz dodatkowego wywołania hash () w value = hash ('% s ::% s'% (value, type (value))) ??
RuiDo,
4

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.

shirk3y
źródło
3
Kto gwarantuje, że pformat lub json zawsze używają tej samej kolejności?
ThiefMaster
1
@ThiefMaster, "Zmieniono w wersji 2.5: słowniki są sortowane według klucza przed obliczeniem wyświetlania; przed 2.5 słownik był sortowany tylko wtedy, gdy jego wyświetlanie wymagało więcej niż jednej linii, chociaż nie było to udokumentowane." ( Docs.python. org / 2 / library / pprint.html )
Arel
2
To nie wydaje mi się ważne. Autorzy rozumieją, że moduły pprint i format pformat służą do wyświetlania, a nie do serializacji. Z tego powodu nie powinieneś czuć się bezpiecznie, zakładając, że pformat zawsze zwróci wynik, który zadziała.
David Sanders,
3

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
Eric
źródło
To nie działa, na przykład, dla dictz DataFrameobiektów.
James Hirschorn,
@JamesHirschorn: Zaktualizowano, aby głośno zawodzić
Eric
Lepszy! Dodałem następującą elifklauzulę, aby działała z DataFrames: elif isinstance(x, pd.DataFrame): return make_hashable(hash_pandas_object(x).tolist())
Zmienię
1
DOBRZE. Widzę, że prosiłem o coś więcej niż „hashable”, co gwarantuje tylko, że obiekty, które są równe, będą miały ten sam hash. Pracuję nad wersją, która będzie dawała tę samą wartość między uruchomieniami i niezależną od wersji Pythona itp.
James Hirschorn
1
hashrandomizacja jest celową funkcją bezpieczeństwa włączoną domyślnie w Pythonie 3.7.
Eric
1

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.

Pedro Cattori
źródło
Biblioteka nie sortuje listy w dyktandzie. A zatem może to dać inny haszysz. Powinna istnieć również opcja sortowania listy. Frozenset powinien pomóc, ale zastanawiam się, jak poradziłbyś sobie ze sprawą z zagnieżdżonym dyktem zawierającym listę dykt. Ponieważ dyktowanie są niezasłonięte.
Suraj
1
@Suraj: to ma uchwyt zagnieżdżony poprzez strukturę .recurse. Zobacz maps.readthedocs.io/en/latest/api.html#maps.FrozenMap.recurse . Porządkowanie w listach ma znaczenie semantyczne, jeśli chcesz niezależności kolejności, możesz przekonwertować listy na zestawy przed wywołaniem .recurse. Można również skorzystać z list_fnparametru .recurseużyć innego hashable strukturę danych niż tuple(.eg frozenset)
Pedro Cattori
0

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

hash(tuple(my_dict.items()))
Anonimowy
źródło
-8

Robię to tak:

hash(str(my_dict))
garbanzio
źródło
1
Czy ktoś może wyjaśnić, co jest takiego złego w tej metodzie?
mhristache
7
Słowniki @maximi nie są stabilne pod względem porządku hash(str({'a': 1, 'b': 2})) != hash(str({'b': 2, 'a': 1}))(chociaż może działać w przypadku niektórych słowników, nie gwarantuje się, że będzie działać we wszystkich).
Vlad Frolov