[PYTHON] __hash __ ()을 구현하는 정확하고 좋은 방법은 무엇입니까?

__hash __ ()을 구현하는 정확하고 좋은 방법은 무엇입니까?

__hash __ ()을 구현하는 정확하고 좋은 방법은 무엇입니까?

나는 객체를 해시 테이블 (aka 사전)에 삽입하는 데 사용되는 해시 코드를 반환하는 함수에 대해 이야기하고 있습니다.

__hash __ ()는 정수를 반환하며 해시 테이블에 객체를 "비닝"하기 위해 사용됩니다. 반환 된 정수의 값은 충돌을 최소화하기 위해 공통 데이터에 대해 균일하게 분산되어야한다고 가정합니다. 그러한 가치를 얻으려면 좋은 연습이 무엇입니까? 충돌이 문제입니까? 필자의 경우에는 int, 일부 수레 및 문자열을 포함하는 컨테이너 클래스로 작동하는 작은 클래스가 있습니다.

해결법

1. ==============================

   1.__hash __ ()을 구현하는 쉽고 정확한 방법은 키 튜플을 사용하는 것입니다. 특수화 된 해시만큼 빠르지는 않지만, 필요하다면 아마도 C로 타입을 구현해야합니다.

   __hash __ ()을 구현하는 쉽고 정확한 방법은 키 튜플을 사용하는 것입니다. 특수화 된 해시만큼 빠르지는 않지만, 필요하다면 아마도 C로 타입을 구현해야합니다.

   다음은 해시 및 동등성을 위해 키를 사용하는 예입니다.

   class A(object):
       def __key(self):
           return (self.attr_a, self.attr_b, self.attr_c)
   
       def __eq__(x, y):
           return x.__key() == y.__key()
   
       def __hash__(self):
           return hash(self.__key())
   

   또한 __hash__의 문서에는 특정 상황에서 유용 할 수있는 자세한 정보가 있습니다.

2. ==============================

   2.John Millikin은 다음과 유사한 해결책을 제안했습니다.

   John Millikin은 다음과 유사한 해결책을 제안했습니다.

   class A(object):
   
       def __init__(self, a, b, c):
           self._a = a
           self._b = b
           self._c = c
   
       def __eq__(self, othr):
           return ((self._a, self._b, self._c) ==
                   (othr._a, othr._b, othr._c))
   
       def __hash__(self):
           return hash((self._a, self._b, self._c))
   

   이 솔루션의 문제점은 해시 (A (a, b, c)) == 해시 ((a, b, c))입니다. 즉, 해시는 주요 멤버의 튜플과 충돌합니다. 어쩌면 이것은 실제로 자주 중요하지 않습니까?

   __hash__에 관한 Python 문서는 XOR과 같은 것을 사용하여 하위 구성 요소의 해시를 결합하는 것을 제안합니다.

   class B(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) ^ hash(self._b) ^ hash(self._c) ^
                   hash((self._a, self._b, self._c)))
   

   보너스 : 더 강력한 __eq__ 좋은 측정을 위해 던져졌습니다.

   업데이트 : Blckknght가 지적했듯이 a, b 및 c의 순서를 변경하면 문제가 발생할 수 있습니다. 해싱 된 값의 순서를 캡처하기 위해 ^ hash ((self._a, self._b, self._c))를 추가했습니다. 이 최종 ^ hash (...)는 결합되는 값을 재배치 할 수 없으면 제거 할 수 있습니다 (예 : 유형이 서로 다르므로 _a의 값이 _b 또는 _c 등에 할당되지 않습니다).

3. ==============================

   3.Microsoft Research의 Paul Larson은 다양한 해시 기능을 연구했습니다. 그는 내게 말했다.

   Microsoft Research의 Paul Larson은 다양한 해시 기능을 연구했습니다. 그는 내게 말했다.

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

   다양한 문자열에 놀랍도록 잘 작동했습니다. 비슷한 다항식 기법이 서로 다른 하위 필드의 해시 계산에 적합하다는 사실을 발견했습니다.

4. ==============================

   4.질문의 두 번째 부분에 답하려고 할 수 있습니다.

   질문의 두 번째 부분에 답하려고 할 수 있습니다.

   콜리 전은 아마도 해시 코드 자체가 아닌 콜렉션의 인덱스에 해시 코드를 매핑함으로써 발생합니다. 예를 들어 해시 함수가 1에서 10000 사이의 임의의 값을 반환 할 수 있지만 해시 테이블에 32 개의 항목 만 있으면 삽입시 충돌이 발생합니다.

   또한 콜렉션은 내부적으로 콜렉션에 의해 해결 될 것이라고 생각할 수 있으며 콜리 전을 해결할 수있는 많은 메소드가 있습니다. 가장 간단한 것 (그리고 최악의 경우)은 인덱스 i에 삽입 할 항목이 있으면 빈 자리를 찾아 삽입 할 때까지 1을 i에 추가합니다. 검색은 다음과 같은 방식으로 작동합니다. 이렇게하면 전체 컬렉션을 탐색해야하는 항목이있을 수 있으므로 일부 항목을 비효율적으로 검색 할 수 있습니다!

   다른 충돌 해결 방법은 항목을 삽입 할 때 해시 테이블에서 항목을 이동시켜 검색 시간을 줄입니다. 이렇게하면 삽입 시간이 늘어나지 만 삽입 한 것 이상을 읽은 것으로 간주합니다. 다른 충돌하는 항목을 시도하고 분기하여 특정 한 지점에서 항목을 클러스터링하는 방법도 있습니다.

   또한 컬렉션의 크기를 조정해야하는 경우 모든 것을 다시 숨기거나 동적 해싱 메서드를 사용해야합니다.

   간단히 말해, 해시 코드를 사용하는 대상에 따라 직접 충돌 해결 방법을 구현해야 할 수도 있습니다. 컬렉션에 저장하지 않는다면 해시 코드를 매우 큰 범위에서 생성하는 해시 함수를 사용할 수 있습니다. 그렇다면, 당신은 귀하의 메모리 문제에 따라 컨테이너가 필요 이상으로 커야합니다.

   관심이있는 경우 다음 링크를 참조하십시오.

   위키 백과에서 합치는 해싱

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

   또한 Tharp의 "File Organization And Processing"은 충돌 해결 방법을 광범위하게 다룹니다. IMO는 해싱 알고리즘에 대한 훌륭한 참고 자료입니다.

5. ==============================

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

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

   나는 비트 운영을 선호 할 것이다. 다음과 같은 C 의사 코드가 있습니다.

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

   이러한 시스템은 실수로 부동 소수점 값을 나타내는 것이 아니라 단순히 비트 값으로 가져온 경우 부동 소수점으로도 사용할 수 있습니다.

   문자열의 경우, 거의 / 전혀 알지 못합니다.

from https://stackoverflow.com/questions/2909106/whats-a-correct-and-good-way-to-implement-hash by cc-by-sa and MIT license