Ein Wörterbuch hashing?

Die Verwendung von sorted(d.items()) reicht nicht aus, um einen stabilen Repräsentanten zu erhalten. Einige der Werte in d könnten auch Wörterbücher sein, und ihre Schlüssel werden immer noch in beliebiger Reihenfolge ausgegeben. Solange alle Schlüssel Strings sind, verwende ich am liebsten:

json.dumps(d, sort_keys=True)

Wenn die Hashes auf verschiedenen Maschinen oder Python-Versionen stabil sein müssen, bin ich nicht sicher, dass dies kugelsicher ist. Möglicherweise möchten Sie die Argumente separators und ensure_ascii hinzufügen, um sich vor Änderungen der Standardeinstellungen zu schützen. Ich würde mich über Kommentare freuen.

EDIT: Wenn alle Ihre Schlüssel Zeichenfolgen sind, dann lesen Sie bitte diese Antwort, bevor Sie fortfahren siehe Jack O'Connors bedeutend einfachere (und schnellere) Lösung (was auch für das Hashing verschachtelter Wörterbücher funktioniert).

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 nach dem Hash-Verfahren für ein Wörterbuch sucht, stößt man möglicherweise auf diese Frage mit dem passenden Titel und bleibt unbefriedigt, wenn man versucht, mehrere 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: Hashing von Objekten und Klassen

Die Funktion hash () funktioniert hervorragend, wenn Sie Hash-Klassen oder -Instanzen verwenden. 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, der Hash ist also der gleiche. Wenn Sie möchten, dass foo je nach aktueller Definition anders hasht, besteht die Lösung darin, das zu hashen, was sich tatsächlich ändert. In diesem Fall ist das Attribut __dict__:

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, das Gleiche mit der Klasse selbst zu tun:

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

Die Eigenschaft class __dict__ 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 ausgehe, dass make_hash () 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))  

Aktualisiert von 2013 antworten ...

Keine der obigen Antworten scheint mir zuverlässig zu sein. Der Grund ist die Verwendung von Items (). Soweit ich weiß, erscheint dies in einer maschinenabhängigen Reihenfolge.

Wie wäre es stattdessen?

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 zu erhalten, 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 DateTime und mehr, die nicht in JSON serialisierbar sind.

Der folgende Code vermeidet die Verwendung der Python-Funktion hash (), da er keine Hashes bereitstellt, die über Neustarts von Python hinweg konsistent sind (siehe hash-Funktion in Python 3.3 gibt unterschiedliche Ergebnisse zwischen den Sitzungen zurück). make_hashable() konvertiert das Objekt in verschachtelte Tupel und make_hash_sha256() konvertiert auch 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=

Sie können dazu die Bibliothek maps verwenden. Speziell maps.FrozenMap

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

Um maps zu installieren, mach einfach:

pip install maps

Es behandelt auch den verschachtelten dict-Fall:

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

Haftungsausschluss: Ich bin der Autor der Bibliothek maps.

Der generelle Ansatz ist gut, aber Sie sollten die Hashmethode in Betracht ziehen.

SHA wurde für kryptographische Stärke entwickelt (auch Geschwindigkeit, aber Stärke ist wichtiger). Möglicherweise möchten Sie dies berücksichtigen. Daher ist die Verwendung der eingebauten hash-Funktion wahrscheinlich eine gute Idee, es sei denn, Sicherheit ist hier ein Schlüssel.

Sie können das Drittanbieter-Modul frozendict verwenden, um Ihr Diktier einzufrieren und als Hash-Funktion zu verwenden.

from frozendict import frozendict
my_dict = frozendict(my_dict)

Für die Handhabung verschachtelter Objekte können Sie Folgendes verwenden:

import collections.abc

def make_hashable(x):
    if isinstance(x, collections.abc.Sequence):
        return Tuple(freeze(xi) for xi in x)
    Elif isinstance(x, collections.abc.Set):
        return frozenset(freeze(xi) for xi in x)
    Elif isinstance(x, collections.abc.Mapping):
        return frozendict({k: freeze(v) for k, v in x.items()})
    else:
        return x