Memukul kamus?

Untuk tujuan caching saya perlu membuat kunci cache dari argumen GET yang ada dalam dikt.

Saat ini saya menggunakan sha1(repr(sorted(my_dict.items())))( sha1()adalah metode kenyamanan yang menggunakan hashlib secara internal) tapi saya ingin tahu apakah ada cara yang lebih baik.

Jika kamus Anda tidak bersarang, Anda bisa membuat frozenset dengan item dict dan menggunakan hash():

hash(frozenset(my_dict.items()))

Ini jauh lebih sedikit komputasi daripada menghasilkan string JSON atau representasi kamus.

UPDATE: Silakan lihat komentar di bawah ini, mengapa pendekatan ini mungkin tidak menghasilkan hasil yang stabil.

Menggunakan sorted(d.items())tidak cukup untuk membuat kita repr stabil. Beberapa nilai dalam dbisa berupa kamus juga, dan kunci-kuncinya masih akan keluar dalam urutan yang sewenang-wenang. Selama semua kunci adalah string, saya lebih suka menggunakan:

json.dumps(d, sort_keys=True)

Yang mengatakan, jika hash harus stabil di berbagai mesin atau versi Python, saya tidak yakin ini anti peluru. Anda mungkin ingin menambahkan separatorsdan ensure_asciiargumen untuk melindungi diri dari perubahan apa pun ke default di sana. Saya menghargai komentar.

EDIT : Jika semua kunci Anda adalah string , maka sebelum melanjutkan untuk membaca jawaban ini, silakan lihat solusi Jack O'Connor yang secara signifikan lebih sederhana (dan lebih cepat) (yang juga berfungsi untuk membuat kamus bersarang bersarang).

Meskipun jawaban telah diterima, judul pertanyaannya adalah "Hashing a python dictionary", dan jawabannya tidak lengkap sehubungan dengan judul itu. (Sehubungan dengan tubuh pertanyaan, jawabannya sudah lengkap.)

Kamus bersarang

Jika seseorang mencari Stack Overflow untuk bagaimana mem-hash kamus, orang mungkin akan tersandung pada pertanyaan yang berjudul tepat ini, dan membiarkannya tidak puas jika seseorang mencoba untuk meng hash kamus berlipat ganda yang bersarang. Jawaban di atas tidak akan berfungsi dalam kasus ini, dan Anda harus menerapkan semacam mekanisme rekursif untuk mengambil hash.

Berikut ini salah satu mekanismenya:

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: Objek dan Kelas Hashing

The hash()fungsi bekerja besar ketika Anda hash kelas atau contoh. Namun, berikut adalah satu masalah yang saya temukan dengan hash, mengenai objek:

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

Hash sama, bahkan setelah saya mengubah foo. Ini karena identitas foo tidak berubah, jadi hashnya sama. Jika Anda ingin hash berbeda tergantung pada definisi saat ini, solusinya adalah dengan memotong apa pun yang sebenarnya berubah. Dalam hal ini, __dict__atributnya:

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

Sayangnya, ketika Anda mencoba melakukan hal yang sama dengan kelas itu sendiri:

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

__dict__Properti kelas bukan kamus normal:

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

Berikut adalah mekanisme yang sama seperti sebelumnya yang akan menangani kelas dengan tepat:

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

Anda dapat menggunakan ini untuk mengembalikan hash tuple dari banyak elemen yang Anda inginkan:

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

CATATAN: semua kode di atas mengasumsikan Python 3.x. Tidak menguji di versi sebelumnya, meskipun saya berasumsi make_hash()akan bekerja, katakanlah, 2.7.2. Sejauh membuat contoh kerja, saya tidak tahu bahwa

func.__code__ 

harus diganti dengan

func.func_code

Ini solusi yang lebih jelas.

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

Kode di bawah ini menghindari penggunaan fungsi hash () Python karena tidak akan memberikan hash yang konsisten di me-restart Python (lihat fungsi hash di Python 3.3 mengembalikan hasil yang berbeda antara sesi ). make_hashable()akan mengkonversi objek ke tuple bersarang dan make_hash_sha256()juga akan mengkonversi repr()ke hash SHA256 yang disandikan 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=

Diperbarui dari 2013 balasan ...

Tidak ada jawaban di atas yang tampaknya dapat diandalkan bagi saya. Alasannya adalah penggunaan item (). Sejauh yang saya tahu, ini keluar dalam urutan yang tergantung pada mesin.

Bagaimana dengan ini?

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

Untuk mempertahankan pesanan utama, alih-alih hash(str(dictionary))atau hash(json.dumps(dictionary))saya lebih suka solusi cepat dan kotor:

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

Ini akan bekerja bahkan untuk tipe suka DateTimedan banyak lagi yang bukan JSON serializable.

Anda bisa menggunakan frozendictmodul pihak ketiga untuk membekukan dict Anda dan membuatnya menjadi hashable.

from frozendict import frozendict
my_dict = frozendict(my_dict)

Untuk menangani objek bersarang, Anda bisa menggunakan:

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

Jika Anda ingin mendukung lebih banyak jenis, gunakan 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

Anda dapat menggunakan perpustakaan peta untuk melakukan ini. Khususnya, maps.FrozenMap

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

Untuk menginstal maps, lakukan saja:

pip install maps

Ini menangani dictkasus bersarang juga:

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

Penafian: Saya adalah penulis mapsperpustakaan.

Salah satu cara untuk mendekati masalah adalah dengan membuat tuple dari item kamus:

hash(tuple(my_dict.items()))

Saya melakukannya seperti ini:

hash(str(my_dict))