[python] Python 해시 가능 사전

@Unknown의 답변과 @AlexMartelli의 답변은 완벽하게 작동하지만 다음 제약 조건에서만 작동합니다.

1. 사전의 값은 해시 가능해야합니다. 예를 들어 hash(hashabledict({'a':[1,2]}))올릴 것이다 TypeError.
2. 키는 비교 연산을 지원해야합니다. 예를 들어 hash(hashabledict({'a':'a', 1:1}))올릴 것이다 TypeError.
3. 키에 대한 비교 연산자는 전체 순서를 부과합니다. 예를 들어 사전에있는 두 키가 frozenset((1,2,3))및 frozenset((4,5,6))인 경우 두 방향에서 같지 않은 값을 비교합니다. 따라서 이러한 키를 사용하여 사전 항목을 정렬하면 임의의 순서가 발생할 수 있으므로 동일한 객체가 동일한 해시 값을 가져야한다는 규칙을 위반하게됩니다.

@ObenSonne의 훨씬 더 빠른 답변은 제약 조건 2와 3을 해제하지만 여전히 제약 조건 1에 의해 구속됩니다 (값은 해시 가능해야 함).

@RaymondHettinger의 더 빠르면서도 대답 .values()은 해시 계산에 포함되지 않기 때문에 세 가지 제약 조건을 모두 해제합니다 . 그러나 다음과 같은 경우에만 성능이 좋습니다.

4. 해시해야하는 대부분의 (같지 않은) 사전은 동일하지 않습니다 .keys().

이 조건이 충족되지 않으면 해시 함수는 여전히 유효하지만 너무 많은 충돌이 발생할 수 있습니다. 예를 들어 모든 사전이 웹 사이트 템플릿에서 생성되는 극단적 인 경우 (필드 이름은 키로, 사용자 입력은 값으로) 키는 항상 동일하며 해시 함수는 모든 입력에 대해 동일한 값을 반환합니다. . 결과적으로 이러한 해시 함수에 의존하는 해시 테이블은 항목을 검색 할 때 목록만큼 느려집니다 ( O(N)대신 O(1)).

위에 나열된 4 개의 제약 조건을 모두 위반하더라도 다음 솔루션이 합리적으로 잘 작동 할 것이라고 생각합니다. 딕셔너리뿐만 아니라 모든 컨테이너가 중첩 된 변경 가능한 컨테이너가 있더라도 해시 할 수 있다는 추가적인 이점이 있습니다.

나는 지금까지 이것을 가볍게 테스트했기 때문에 이것에 대한 피드백을 많이 주시면 감사하겠습니다.

# python 3.4
import collections
import operator
import sys
import itertools
import reprlib

# a wrapper to make an object hashable, while preserving equality
class AutoHash:
    # for each known container type, we can optionally provide a tuple
    # specifying: type, transform, aggregator
    # even immutable types need to be included, since their items
    # may make them unhashable

    # transformation may be used to enforce the desired iteration
    # the result of a transformation must be an iterable
    # default: no change; for dictionaries, we use .items() to see values

    # usually transformation choice only affects efficiency, not correctness

    # aggregator is the function that combines all items into one object
    # default: frozenset; for ordered containers, we can use tuple

    # aggregator choice affects both efficiency and correctness
    # e.g., using a tuple aggregator for a set is incorrect,
    # since identical sets may end up with different hash values
    # frozenset is safe since at worst it just causes more collisions
    # unfortunately, no collections.ABC class is available that helps
    # distinguish ordered from unordered containers
    # so we need to just list them out manually as needed

    type_info = collections.namedtuple(
        'type_info',
        'type transformation aggregator')

    ident = lambda x: x
    # order matters; first match is used to handle a datatype
    known_types = (
        # dict also handles defaultdict
        type_info(dict, lambda d: d.items(), frozenset),
        # no need to include set and frozenset, since they are fine with defaults
        type_info(collections.OrderedDict, ident, tuple),
        type_info(list, ident, tuple),
        type_info(tuple, ident, tuple),
        type_info(collections.deque, ident, tuple),
        type_info(collections.Iterable, ident, frozenset) # other iterables
    )

    # hash_func can be set to replace the built-in hash function
    # cache can be turned on; if it is, cycles will be detected,
    # otherwise cycles in a data structure will cause failure
    def __init__(self, data, hash_func=hash, cache=False, verbose=False):
        self._data=data
        self.hash_func=hash_func
        self.verbose=verbose
        self.cache=cache
        # cache objects' hashes for performance and to deal with cycles
        if self.cache:
            self.seen={}

    def hash_ex(self, o):
        # note: isinstance(o, Hashable) won't check inner types
        try:
            if self.verbose:
                print(type(o),
                    reprlib.repr(o),
                    self.hash_func(o),
                    file=sys.stderr)
            return self.hash_func(o)
        except TypeError:
            pass

        # we let built-in hash decide if the hash value is worth caching
        # so we don't cache the built-in hash results
        if self.cache and id(o) in self.seen:
            return self.seen[id(o)][0] # found in cache

        # check if o can be handled by decomposing it into components
        for typ, transformation, aggregator in AutoHash.known_types:
            if isinstance(o, typ):
                # another option is:
                # result = reduce(operator.xor, map(_hash_ex, handler(o)))
                # but collisions are more likely with xor than with frozenset
                # e.g. hash_ex([1,2,3,4])==0 with xor

                try:
                    # try to frozenset the actual components, it's faster
                    h = self.hash_func(aggregator(transformation(o)))
                except TypeError:
                    # components not hashable with built-in;
                    # apply our extended hash function to them
                    h = self.hash_func(aggregator(map(self.hash_ex, transformation(o))))
                if self.cache:
                    # storing the object too, otherwise memory location will be reused
                    self.seen[id(o)] = (h, o)
                if self.verbose:
                    print(type(o), reprlib.repr(o), h, file=sys.stderr)
                return h

        raise TypeError('Object {} of type {} not hashable'.format(repr(o), type(o)))

    def __hash__(self):
        return self.hash_ex(self._data)

    def __eq__(self, other):
        # short circuit to save time
        if self is other:
            return True

        # 1) type(self) a proper subclass of type(other) => self.__eq__ will be called first
        # 2) any other situation => lhs.__eq__ will be called first

        # case 1. one side is a subclass of the other, and AutoHash.__eq__ is not overridden in either
        # => the subclass instance's __eq__ is called first, and we should compare self._data and other._data
        # case 2. neither side is a subclass of the other; self is lhs
        # => we can't compare to another type; we should let the other side decide what to do, return NotImplemented
        # case 3. neither side is a subclass of the other; self is rhs
        # => we can't compare to another type, and the other side already tried and failed;
        # we should return False, but NotImplemented will have the same effect
        # any other case: we won't reach the __eq__ code in this class, no need to worry about it

        if isinstance(self, type(other)): # identifies case 1
            return self._data == other._data
        else: # identifies cases 2 and 3
            return NotImplemented

d1 = {'a':[1,2], 2:{3:4}}
print(hash(AutoHash(d1, cache=True, verbose=True)))

d = AutoHash(dict(a=1, b=2, c=3, d=[4,5,6,7], e='a string of chars'),cache=True, verbose=True)
print(hash(d))