Ein Wörterbuch zerschlagen?

Für Caching-Zwecke muss ich einen Cache-Schlüssel aus GET-Argumenten generieren, die in einem Diktat vorhanden sind.

Derzeit verwende ich sha1(repr(sorted(my_dict.items())))( sha1()ist eine bequeme Methode, die Hashhlib intern verwendet), aber ich bin gespannt, ob es einen besseren Weg gibt.

Wenn Ihr Wörterbuch nicht verschachtelt ist, können Sie ein Frozenset mit den Elementen des Diktats erstellen und Folgendes verwenden hash():

hash(frozenset(my_dict.items()))

Dies ist viel weniger rechenintensiv als das Generieren der JSON-Zeichenfolge oder der Darstellung des Wörterbuchs.

UPDATE: Bitte beachten Sie die folgenden Kommentare, warum dieser Ansatz möglicherweise kein stabiles Ergebnis liefert.

Die Verwendung sorted(d.items())reicht nicht aus, um uns einen stabilen Repräsentanten zu verschaffen. Einige der Werte in dkönnten auch Wörterbücher sein, und ihre Schlüssel werden weiterhin in einer beliebigen Reihenfolge ausgegeben. Solange alle Schlüssel Zeichenfolgen sind, bevorzuge ich:

json.dumps(d, sort_keys=True)

Das heißt, wenn die Hashes auf verschiedenen Computern oder Python-Versionen stabil sein müssen, bin ich mir nicht sicher, ob dies kugelsicher ist. Möglicherweise möchten Sie die Argumente separatorsund hinzufügen ensure_ascii, um sich vor Änderungen an den dortigen Standardeinstellungen zu schützen. Ich würde mich über Kommentare freuen.

BEARBEITEN : Wenn alle Ihre Schlüssel Zeichenfolgen sind , lesen Sie bitte Jack O'Connors wesentlich einfachere (und schnellere) Lösung (die auch für das Hashing verschachtelter Wörterbücher funktioniert ) , bevor Sie diese Antwort weiter lesen .

Obwohl eine Antwort akzeptiert wurde, lautet der Titel der Frage "Hashing a Python Dictionary", und die Antwort ist in Bezug auf diesen Titel unvollständig. (In Bezug auf den Hauptteil der Frage ist die Antwort vollständig.)

Verschachtelte Wörterbücher

Wenn man im Stapelüberlauf nach dem Hash eines Wörterbuchs sucht, kann man auf diese treffend betitelte Frage stoßen und unbefriedigt bleiben, wenn man versucht, verschachtelte Wörterbücher zu hashen. Die obige Antwort funktioniert in diesem Fall nicht und Sie müssen einen rekursiven Mechanismus implementieren, um den Hash abzurufen.

Hier ist ein solcher Mechanismus:

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: Objekte und Klassen zerschlagen

Die hash()Funktion funktioniert hervorragend, wenn Sie Klassen oder Instanzen hashen. Hier ist jedoch ein Problem, das ich mit Hash in Bezug auf Objekte gefunden habe:

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

Der Hash ist der gleiche, auch nachdem ich foo geändert habe. Dies liegt daran, dass sich die Identität von foo nicht geändert hat, sodass der Hash derselbe ist. Wenn Sie möchten, dass foo je nach aktueller Definition unterschiedlich hasht, besteht die Lösung darin, alles zu hashen, was sich tatsächlich ändert. In diesem Fall ist das __dict__Attribut:

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

Leider, wenn Sie versuchen, dasselbe mit der Klasse selbst zu tun:

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

Die class __dict__-Eigenschaft ist kein normales Wörterbuch:

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

Hier ist ein ähnlicher Mechanismus wie zuvor, der Klassen angemessen behandelt:

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

Sie können dies verwenden, um ein Hash-Tupel mit beliebig vielen Elementen zurückzugeben:

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

HINWEIS: Der gesamte obige Code setzt Python 3.x voraus. In früheren Versionen nicht getestet, obwohl ich davon make_hash()ausgehe, dass dies beispielsweise in 2.7.2 funktioniert. Soweit die Beispiele funktionieren, weiß ich das

func.__code__ 

sollte durch ersetzt werden

func.func_code

Hier ist eine klarere Lösung.

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

Der folgende Code vermeidet die Verwendung der Python-Funktion hash (), da keine Hashes bereitgestellt werden, die bei Neustarts von Python konsistent sind (siehe Hash-Funktion in Python 3.3 gibt unterschiedliche Ergebnisse zwischen Sitzungen zurück ). make_hashable()konvertiert das Objekt in verschachtelte Tupel und make_hash_sha256()konvertiert den repr()in einen base64-codierten SHA256-Hash.

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=

Aktualisiert von 2013 Antwort ...

Keine der oben genannten Antworten scheint mir zuverlässig zu sein. Der Grund ist die Verwendung von items (). Soweit ich weiß, erfolgt dies in maschinenabhängiger Reihenfolge.

Wie wäre es stattdessen damit?

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

Um die Schlüsselreihenfolge beizubehalten, würde ich anstelle von hash(str(dictionary))oder hash(json.dumps(dictionary))eine schnelle und schmutzige Lösung bevorzugen:

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

Es funktioniert auch für Typen wie DateTimeund mehr, die nicht JSON-serialisierbar sind.

Sie können das frozendictModul eines Drittanbieters verwenden , um Ihr Diktat einzufrieren und es hashbar zu machen.

from frozendict import frozendict
my_dict = frozendict(my_dict)

Für den Umgang mit verschachtelten Objekten können Sie Folgendes verwenden:

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

Wenn Sie weitere Typen unterstützen möchten, verwenden Sie 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

Sie können dazu die Kartenbibliothek verwenden. Insbesondere maps.FrozenMap

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

Zum Installieren mapseinfach:

pip install maps

Es behandelt auch den verschachtelten dictFall:

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

Haftungsausschluss: Ich bin der Autor der mapsBibliothek.

Eine Möglichkeit, sich dem Problem zu nähern, besteht darin, ein Tupel aus den Elementen des Wörterbuchs zu erstellen:

hash(tuple(my_dict.items()))

So mach ich es:

hash(str(my_dict))