[python] 해시 가능, 불변

Program / 글쓴이

최근의 SO 질문에서 ( 목록으로 색인되는 파이썬에서 사전 만들기 참조 ) 파이썬에서 해시 가능 및 불변 객체의 의미에 대한 잘못된 개념이 있음을 깨달았습니다.

  • 실제로 해시 가능은 무엇을 의미합니까?
  • 해시 가능과 불변의 관계는 무엇입니까?
  • 해시 할 수있는 변경 가능한 객체 또는 해시 할 수없는 변경 불가능한 객체가 있습니까?

답변

해싱 은 많은 양의 데이터를 반복 가능한 방식으로 훨씬 적은 양 (일반적으로 단일 정수)으로 변환하여 일정한 시간 ( O(1)) 으로 테이블에서 조회 할 수 있도록하는 프로세스입니다 . 이는 고성능에 중요합니다. 알고리즘 및 데이터 구조.

불변성 은 객체가 생성 된 후에 특히 해당 객체의 해시 값을 변경할 수있는 어떤 방식 으로든 중요한 방식으로 변경되지 않는다는 아이디어입니다.

해시 키로 사용되는 객체는 일반적으로 불변이어야 해시 값이 변경되지 않기 때문에 두 가지 아이디어가 관련됩니다. 변경이 허용되면 해시 테이블과 같은 데이터 구조에서 해당 객체의 위치가 변경되고 효율성을위한 해싱의 전체 목적이 무효화됩니다.

아이디어를 제대로 이해하려면 C / C ++와 같은 언어로 고유 한 해시 테이블을 구현하거나 HashMap클래스 의 Java 구현을 읽어야합니다 .

답변

  • 해시 할 수있는 변경 가능한 객체 또는 해시 할 수없는 변경 불가능한 객체가 있습니까?

Python에서 튜플은 불변이지만 모든 요소가 해시 가능한 경우에만 해시 할 수 있습니다.

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'

해시 가능한 유형

  • 원자 불변 유형은 str, 바이트, 숫자 유형과 같이 모두 해시 가능합니다.
  • 고정 된 집합은 항상 해시 가능합니다 (요소는 정의에 따라 해시 가능해야 함).
  • 튜플은 모든 요소가 해시 가능한 경우에만 해시 가능합니다.
  • 사용자 정의 유형은 해시 값이 id ()이므로 기본적으로 해시 할 수 있습니다.

답변

로부터 파이썬 용어 :

객체는 수명 동안 절대 변경되지 않는 해시 값 ( __hash__()메서드 가 필요함)이있는 경우 해시 가능하고 다른 객체와 비교할 수 있습니다 ( __eq__()또는__cmp__() 메서드 . 동일하게 비교되는 해시 가능한 객체는 동일한 해시 값을 가져야합니다.

해시 가능성은 이러한 데이터 구조가 내부적으로 해시 값을 사용하기 때문에 객체를 사전 키 및 집합 멤버로 사용할 수있게합니다.

Python의 모든 불변 내장 객체는 해시 가능하지만 변경 가능한 컨테이너 (예 : 목록 또는 사전)는 없습니다. 사용자 정의 클래스의 인스턴스 인 객체는 기본적으로 해시 가능합니다. 그들은 모두 같지 않은 것을 비교하고 해시 값은 id ()입니다.

사전과 세트는 해시 테이블에서 효율적인 조회를 위해 해시를 사용해야합니다. 해시를 변경하면 데이터 구조가 엉망이되고 dict 또는 set이 실패하게되므로 해시 값은 불변이어야합니다. 해시 값을 불변으로 만드는 가장 쉬운 방법은 전체 객체를 불변으로 만드는 것이므로 두 가지가 종종 함께 언급되는 이유입니다.

내장 된 변경 가능 객체는 해시 할 수 없지만 변경 불가능한 해시 값을 사용하여 변경 가능한 객체를 만들 수 있습니다. 개체의 일부만 해당 ID를 나타내는 것이 일반적이며 나머지 개체에는 자유롭게 변경할 수있는 속성이 포함되어 있습니다. 해시 값과 비교 함수가 변경 가능한 속성이 아닌 ID를 기반으로하고 ID가 변경되지 않는 한 요구 사항을 충족 한 것입니다.

답변

기술적으로 해시 가능이란 클래스가 __hash__(). 문서에 따르면 :

__hash__()정수를 반환해야합니다. 유일한 필수 속성은 동일하게 비교되는 객체가 동일한 해시 값을 갖는 것입니다. 객체와 비교하여 역할을 수행하는 객체의 구성 요소에 대한 해시 값을 어떻게 든 함께 혼합 (예 : 배타적 또는 사용)하는 것이 좋습니다.

파이썬 내장 유형의 경우 모든 해시 가능한 유형도 불변이라고 생각합니다.

그럼에도 불구하고 정의 된 가변 객체를 갖는 것은 어렵지만 아마도 불가능하지는 않을 것 __hash__()입니다.

답변

불변과 해시 사이의 상호 작용으로 인해 불변과 해시 사이에 명시적인 관계가 없어도 암시 적입니다.

  1. 동일하게 비교되는 해시 가능한 객체는 동일한 해시 값을 가져야합니다.
  2. 객체는 수명 동안 절대 변경되지 않는 해시 값이있는 경우 해시 할 수 있습니다.

__eq__객체 클래스가 가치에 대한 동등성을 정의 하도록 재정의하지 않는 한 여기에는 문제가 없습니다 .

이 작업을 마치면 동일한 값 (예 : where __eq__) 을 나타내는 객체에 대해 항상 동일한 값을 반환하는 안정적인 해시 함수를 찾아야합니다 (예 : where )는 True를 반환하고 객체의 수명 동안 절대 변경되지 않습니다.

이것이 가능한 응용 프로그램을 찾기가 어렵습니다 . 이러한 요구 사항을 충족 하는 가능한 클래스 A 를 고려하십시오 . __hash__상수를 반환하는 명백한 퇴화 사례가 있지만 .

지금:-

>>> a = A(1)
>>> b = A(1)
>>> c = A(2)
>>> a == b
True
>>> a == c
False
>>> hash(a) == hash(b)
True
>>> a.set_value(c)
>>> a == c
True
>>> assert(hash(a) == hash(c)) # Because a == c => hash(a) == hash(c)
>>> assert(hash(a) == hash(b)) # Because hash(a) and hash(b) have compared equal 
                                 before and the result must stay static over the objects lifetime.

실제로 이것은 생성시 hash (b) == hash (c)를 의미합니다. 어쨌든 __hash__값으로 비교를 정의하는 변경 가능한 객체에 대해 () 를 유용하게 정의하는 데 어려움을 겪습니다 .

참고 : __lt__, __le__, __gt__및 __ge__당신은 여전히 가변하거나 자신의 가치를 기반으로 해쉬 객체의 순서를 정의 할 수 있도록 비교 식에는 영향을주지 않습니다.

답변

이것이 Google 인기 히트작이기 때문에 변경 가능한 객체를 해시 가능하게 만드는 간단한 방법은 다음과 같습니다.

>>> class HashableList(list):
...  instancenumber = 0  # class variable
...  def __init__(self, initial = []):
...   super(HashableList, self).__init__(initial)
...   self.hashvalue = HashableList.instancenumber
...   HashableList.instancenumber += 1
...  def __hash__(self):
...   return self.hashvalue
... 
>>> l = [1,2,3]
>>> m = HashableList(l)
>>> n = HashableList([1,2,3])
>>> m == n
True
>>> a={m:1, n:2}
>>> a[l] = 3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> m.hashvalue, n.hashvalue
(0, 1)

SQLAlchemy 레코드를 변경 가능하고 나에게 더 유용한 것으로 변환하는 클래스를 만들 때 실제로 이와 같은 용도를 찾았지만 딕셔너리 키로 사용하기위한 해시 성을 유지했습니다.

답변

불변성은 객체가 수명 동안 중요한 방식으로 변경되지 않음을 의미합니다. 프로그래밍 언어에서 모호하지만 일반적인 아이디어입니다.

해시 가능성은 약간 다르며 비교를 나타냅니다.

hashable 객체는 수명 동안 절대 변경되지 않는 해시 값 (__hash__()메서드필요)이있는 경우 해시가능하고 다른 객체 (__eq__()또는__cmp__()메서드필요)와 비교할 수 있습니다. 동일하게 비교되는 해시 가능한 객체는 동일한 해시 값을 가져야합니다.

모든 사용자 정의 클래스에는 __hash__기본적으로 개체 ID 만 반환하는 메서드가 있습니다. 따라서 해시 가능성 기준을 충족하는 객체가 반드시 변경 불가능한 것은 아닙니다.

선언 한 새 클래스의 객체는 예를 들어 다음과 같은 방법으로 방지하지 않는 한 사전 키로 사용할 수 있습니다. __hash__

모든 불변 객체는 해시 가능하다고 말할 수 있습니다. 왜냐하면 객체의 수명 동안 해시가 변경되면 객체가 변형되었음을 의미하기 때문입니다.

하지만 정답은 아닙니다. 목록 (변경 가능)이있는 튜플을 고려하십시오. 어떤 사람들은 튜플이 불변이라고 말하지만 동시에 다소 해시 할 수 없습니다.

d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws

해시 가능성과 불변성은 유형이 아닌 객체 인스턴스를 참조합니다. 예를 들어, 튜플 유형의 객체는 해시 가능하거나 그렇지 않을 수 있습니다.