[python] 사전을 해싱?

편집 : 모든 키가 문자열 인 경우이 답변을 계속 읽기 전에 Jack O’Connor의 훨씬 간단하고 빠른 솔루션 (중첩 사전 해시에도 작동)을 참조하십시오.

답변이 수락되었지만 질문의 제목은 “python 사전 해시”이며 해당 제목과 관련하여 답변이 불완전합니다. (질문과 관련하여 답변이 완료되었습니다.)

중첩 된 사전

딕셔너리를 해시하는 방법에 대해 스택 오버플로를 검색하면 제목이 지정된이 질문에 걸려 넘어지고 중첩 된 사전을 여러 번 해시하려고하면 불만족 스러울 수 있습니다. 이 경우 위의 답변이 작동하지 않으므로 해시를 검색하기 위해 일종의 재귀 메커니즘을 구현해야합니다.

다음은 그러한 메커니즘 중 하나입니다.

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

보너스 : 해싱 객체 및 클래스

이 hash()함수는 클래스 나 인스턴스를 해시 할 때 효과적입니다. 그러나 객체와 관련하여 해시에서 발견 한 문제는 다음과 같습니다.

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

foo를 변경 한 후에도 해시는 동일합니다. 이는 foo의 ID가 변경되지 않았기 때문에 해시가 동일하기 때문입니다. 현재 정의에 따라 foo를 다르게 해시하려면 실제로 변경되는 내용을 해시하는 것이 해결책입니다. 이 경우 __dict__속성은 다음과 같습니다.

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

아아, 클래스 자체로 같은 일을하려고 할 때 :

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

클래스 __dict__속성은 일반적인 사전이 아닙니다.

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

다음은 클래스를 적절히 처리하는 이전과 비슷한 메커니즘입니다.

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

이것을 사용하여 원하는 많은 요소의 해시 튜플을 반환 할 수 있습니다.

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

참고 : 위의 모든 코드는 Python 3.x를 가정합니다. make_hash()2.7.2에서 작동 한다고 가정하지만 이전 버전에서는 테스트하지 않았습니다 . 지금까지 예제 작품을 만드는 등, 난 않는 것을 알고있다

func.__code__ 

로 교체해야합니다

func.func_code

답변

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

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=

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

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