해시 가능, 불변

해시 가능, 불변

---

최근의 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__(). 문서에 따르면 :

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

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

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

---

로부터 파이썬 용어 :

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

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

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

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

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

---

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

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)

I actually found a use for something like this when creating a class to cast SQLAlchemy records into something mutable and more useful to me, while maintaining their hashability for use as dict keys.

---

Immutable means that object will not change in any significant manner during its lifetime. It's a vague but common idea in programming languages.

Hashability is slightly different, and refers to comparison.

hashable An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() or __cmp__() method). Hashable objects which compare equal must have the same hash value.

All user-defined classes have __hash__ method, which by default just returns the object ID. So an object that meets the criteria for hashability is not necessarily immutable.

Objects of any new class you declare can be used as a dictionary key, unless you prevent it by, for example, throwing from __hash__

We could say that all immutable objects are hashable, because if the hash changes during the object's lifetime, then it means that the object mutated.

But not quite. Consider a tuple which has a list (mutable). Some say tuple is immutable, but at the same time it is somewhat not hashable (throws).

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

Hashability and immutability refer to object instancess, not type. For example, an object of type tuple can be hashable or not.

---

In Python they're mostly interchangeable; since the hash is supposed to represent the content, so it's just as mutable as the object, and having an object change the hash value would make it unusable as a dict key.

In other languages, the hash value is more related to the objects 'identity', and not (necessarily) to the value. Thus, for a mutable object, the pointer could be used to start the hashing. Assuming, of course, that an object doesn't move in memory (as some GC do). This is the approach used in Lua, for example. This makes a mutable object usable as a table key; but creates several (unpleasant) surprises for newbies.

In the end, having an immutable sequence type (tuples) makes it nicer for 'multi-value keys'.

---

Hashable means that an variable's value can be represented (or, rather, encoded) by a constant -- string, number, etc. Now, something that is subject to change (mutable) cannot be represented by something that is not. Therefore, any variable that is mutable cannot be hashable and, by the same token, only immutable variables can be hashable.

Hope this helps ...

참고URL : https://stackoverflow.com/questions/2671376/hashable-immutable