__hash__()를 구현하는 올바르고 좋은 방법은 무엇입니까?

__hash__()를 구현하는 올바르고 좋은 방법은 무엇입니까?

구현 알 수 있을까요?__hash__()

해시 코드를 반환하는 함수를 말하는 것입니다.이 함수는 객체를 해시 테이블 사전으로 삽입하기 위해 사용됩니다.

~로__hash__()정수를 반환하고 객체를 해시 테이블로 "bining"하기 위해 사용됩니다. 반환되는 정수의 값은 (충돌을 최소화하기 위해) 공통 데이터에 대해 균일하게 분포되어야 한다고 가정합니다.이러한 가치를 얻기 위한 좋은 방법은 무엇일까요?돌이이 문제? ???저 같은 경우에는 컨테이너 클래스 역할을 하는 작은 클래스가 있는데, 몇 개의 인트와 플로트, 그리고 끈을 가지고 있습니다.

」를 하게 실장하는 __hash__()키 태플을 사용하는 것입니다.전용 해시만큼 빠르지는 않지만 필요한 경우 C에서 유형을 구현해야 합니다.

해시 및 등식에 키를 사용하는 예를 다음에 나타냅니다.

class A:
    def __key(self):
        return (self.attr_a, self.attr_b, self.attr_c)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        if isinstance(other, A):
            return self.__key() == other.__key()
        return NotImplemented

또, 의 메뉴얼에는, 특정의 상황에서 도움이 되는 상세한 정보가 기재되어 있습니다.

John Milikin은 다음과 같은 솔루션을 제안했습니다.

class A(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        return (isinstance(othr, type(self))
                and (self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))

    def __hash__(self):
        return hash((self._a, self._b, self._c))

은 '이렇게 하다'라는 것입니다.hash(A(a, b, c)) == hash((a, b, c))아마 이것은 실제에서는 그다지 중요하지 않은 것일까요?

업데이트: Python 문서에서는 위의 예시와 같이 태플을 사용할 것을 권장합니다.문서에는 다음과 같이 기술되어 있습니다.

유일하게 필요한 속성은 동등하게 비교되는 개체의 해시 값이 같다는 것입니다.

그 반대는 사실이 아닙니다.일치하지 않는 객체는 동일한 해시 값을 가질 수 있습니다.이러한 해시 충돌로 인해 오브젝트가 동등하게 비교되지 않는 한 dict 키 또는 set 요소로 사용되는 경우 오브젝트가 다른 오브젝트를 대체하지 않습니다.

구식/불량 솔루션

의 Python 문서에서는 XOR과 같은 기능을 사용하여 하위 구성요소의 해시를 결합할 것을 제안하고 있습니다.이것에 의해, 다음의 정보가 제공됩니다.

class B(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        if isinstance(othr, type(self)):
            return ((self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))
        return NotImplemented

    def __hash__(self):
        return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

업데이트: Blcknight가 지적한 바와 같이 a, b, c의 순서를 변경하면 문제가 발생할 수 있습니다.는 가 i i가추 i i i i i 。^ hash((self._a, self._b, self._c))해시되는 값의 순서를 캡처합니다. 마지막 ★★★★★★★★★★★★★★★.^ hash(...)하고 있는 할 수 를 들어 는할 수 ._a ._b ★★★★★★★★★★★★★★★★★」_c등 ) 。

마이크로소프트 리서치의 Paul Larson은 다양한 해시 함수를 연구했습니다.그는 나에게 그걸 말했다.

for c in some_string:
    hash = 101 * hash  +  ord(c)

다양한 현악기에도 놀라울 정도로 잘 작동했습니다.유사한 다항식 기법이 서로 다른 서브필드의 해시를 계산하는 데 효과적이라는 것을 알게 되었습니다.

해시(및 list, dict, tuple)를 구현하는 좋은 방법은 를 사용하여 반복 가능하게 함으로써 오브젝트에 예측 가능한 항목 순서를 설정하는 것입니다.그래서 위에서 예를 수정하는 것입니다.

class A(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __iter__(self):
        yield "a", self._a
        yield "b", self._b
        yield "c", self._c

    def __hash__(self):
        return hash(tuple(self))

    def __eq__(self, other):
        return (isinstance(other, type(self))
                and tuple(self) == tuple(other))

에 (여기에)__eq__해시에는 필수가 아니지만 구현은 간단합니다).

이제 몇 가지 가변 구성원을 추가하여 작동 방식을 확인합니다.

a = 2; b = 2.2; c = 'cat'
hash(A(a, b, c))  # -5279839567404192660
dict(A(a, b, c))  # {'a': 2, 'b': 2.2, 'c': 'cat'}
list(A(a, b, c))  # [('a', 2), ('b', 2.2), ('c', 'cat')]
tuple(A(a, b, c)) # (('a', 2), ('b', 2.2), ('c', 'cat'))

오브젝트 모델에 비호환 멤버를 넣으려고 할 때만 모든 것이 무너집니다.

hash(A(a, b, [1]))  # TypeError: unhashable type: 'list'

질문의 두 번째 부분은 제가 대답할 수 있습니다.

충돌은 해시 코드 자체가 아니라 해시 코드를 컬렉션의 인덱스에 매핑하기 때문에 발생할 수 있습니다.예를 들어 해시 함수는 1 ~10000의 랜덤 값을 반환할 수 있지만 해시 테이블에 32개의 엔트리만 있는 경우 삽입 시 충돌이 발생합니다.

또, 콜리젼은 내부적으로 콜리젼을 해결한다고 생각하고, 콜리젼을 해결하는 방법도 많이 있다고 생각합니다.가장 간단한(및 최악의) 방법은 인덱스 i에 삽입할 엔트리를 지정하면 빈 지점을 찾은 후 삽입할 때까지 i에 1을 더하는 것입니다.취득도 같은 방법으로 동작합니다.따라서 전체 컬렉션을 탐색해야 하는 항목이 있을 수 있으므로 일부 항목에 대한 검색 효율성이 떨어집니다.

다른 충돌 해결 방법은 항목을 삽입하여 사물을 펼치면 해시 테이블 내의 엔트리를 이동함으로써 검색 시간을 단축합니다.이렇게 하면 삽입 시간이 길어지지만 삽입 시간보다 더 많이 읽게 됩니다.또한 다른 충돌 엔트리를 시도하고 분기하여 엔트리가 특정 스폿에 클러스터되도록 하는 메서드도 있습니다.

또한 컬렉션 크기를 조정해야 할 경우 모든 항목을 다시 캐시하거나 동적 해시 방법을 사용해야 합니다.

즉, 어떤 해시 코드를 사용하고 있는지에 따라 독자적인 충돌 해결 방법을 구현해야 할 수 있습니다.컬렉션에 저장하지 않는 경우 매우 큰 범위의 해시 코드만 생성하는 해시 함수를 사용할 수 있습니다.이 경우, 메모리 문제에 따라 필요한 것보다 큰 용기(물론 큰 용기일수록 좋습니다)를 확인할 수 있습니다.

자세한 내용은 다음 링크를 참조하십시오.

위키피디아에 대한 통합 해시

Wikipedia에는 다양한 충돌 해결 방법이 요약되어 있습니다.

또한 Tharp의 "파일 구성 및 처리"는 충돌 해결 방법을 광범위하게 다룹니다.IMO는 해시 알고리즘의 훌륭한 레퍼런스입니다.

구현 시기와 방법에 대한 매우 적절한 설명__hash__함수는 programmiz 웹사이트에 있습니다.

스크린샷으로 개요 설명 : (2019-12-13)

이 방법의 개인적인 실장에 대해서는, 상기의 사이트에서 millerdev의 회답과 일치하는 예를 제공하고 있다.

class Person:
def __init__(self, age, name):
    self.age = age
    self.name = name

def __eq__(self, other):
    return self.age == other.age and self.name == other.name

def __hash__(self):
    print('The hash is:')
    return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))

반환하는 해시 값의 크기에 따라 다릅니다.4개의 32비트 int의 해시를 기반으로 32비트 int를 반환해야 할 경우 충돌이 발생한다는 것은 간단한 논리입니다.

비트 조작을 선호합니다.예를 들어 다음과 같은 C 유사 코드:

int a;
int b;
int c;
int d;
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);

이러한 시스템은 부동소수점 값을 나타내는 것이 아니라 단순히 비트 값으로 받아들인다면 플로트에도 사용할 수 있습니다.

현악기 같은 건 잘 모르겠어요.

언급URL : https://stackoverflow.com/questions/2909106/whats-a-correct-and-good-way-to-implement-hash