Python의 Hashable (Dictionary의 key가 되는 기준은 무엇일까?)

Dictionary의 key는 Immutable 객체만 가능?

  Python에서 dictionary(dict)는 강력한 기능을 가지고 있다. dict의 정수, 문자열, 심지어 tuple도 key로 들어갈 수 있다.

d = dict()
d[1] = 1
d["hi"] = 2
d[(1,2,3)] = 3

"파이썬 알고리즘 인터뷰"라는 책을 읽으면서 다음과 같은 문구가 있었다[1].

특히 파이썬의 딕셔너리는 해시할 수만 있다면 숫자뿐만 아니라, 문자, 집합까지 불변 객체를 모두 키로 사용할 수 있다.

나는 이 때 이 문장의 전체를 보지 못하고, 보고싶은 단어만 보았다. 이 문구의 의미가 "dict의 key는 불변 객체만 가능하다"라고 이해했다. 그래서 궁금했다. Immutable 객체만 key가 될 수 있는 이유가 있을까? 그렇게 dictionary를 찾아봤는데, 또 보고싶은 단어만 보았다. 아래는 Python docs에서 가져온 dictionary의 정의 중 일부다[2].

Immutable type은 dict의 key가 될 수 있다. Immutable 객체만 key가 될 수 있다랑 같은 말은 아니지만, 얼추 비슷해보인다. 내가 잘못 이해한 부분에 대해서는 결론에서 이야기해보겠다... 일단 이런 동기로 검색을 시작했다.

 

Mutable 객체도 가능?

  dict은 내부적으로 hash table로 구현되어 있고, key로 객체가 들어간다는 것은 hash function에 input으로 사용하기 위해 해당 객체에 관련된 다른 값이 사용될 확률이 높다. hash key와 Immutable 객체가 연관성이 있을까?

  검색을 시작하자마자 재밌는걸 발견했다. Mutable 객체도 key로 사용된다는 Stack Overflow 글이다. 참고로 2010년도 글이다.

https://stackoverflow.com/questions/4418741/im-able-to-use-a-mutable-object-as-a-dictionary-key-in-python-is-this-not-disa

I'm able to use a mutable object as a dictionary key in python. Is this not disallowed?

해당 글 내용을 보면, class(A)를 선언하여 dict의 key로 사용한다. 그리고 인스턴스(i)를 생성하여 dict의 key로 사용하고, 해당 인스턴스의 값(x)을 바꾸었다. 바꾸고 나서도 key로써의 역할을 수행한다. 오잉? Immutable 객체만 key가 될 수 있는 것 아닌가?

  답변에는 이러한 문구가 있다.

Any object with a __hash__ method can be a dictionary key

__hash__ 메소드를 포함하는 객체는 dictionary의 key가 될 수 있다. 즉, dictionary의 key로 사용되는 핵심 중에 하나는 hash()이다. 그리고 밑에 다른 댓글에는 아래 문구가 등장한다.

An object can be a key in a dictionary if it is hashable

dict의 key가 될 수 있는 또다른 단서는 hashable이었다. Immutable 객체만 key가 될 수 있다는 의문으로 시작하여 hashable에 도달하게 되었다.

 

Hashable?

  Hashable은 Python docs에 정의되어있다. Python docs에서 정의하는 hashable을 그대로 번역해보았다.

https://docs.python.org/3/glossary.html#term-hashable

Glossary — Python 3.9.6 documentation

  Object가 hashable하다는 것은 hash 값을 갖는다는 의미이며, 이 hash 값은 lifetime동안 절대 변하지 않고(__hash__() 메소드 필요), 다른 object들과 비교가 가능하다(__eq__() 메소드 필요). 비교했을 때 같은 object는 같은 hash 값을 갖는다.
  Hashability는 object를 dictionary의 key, set의 요소가 될 수 있게 해주는데, 이는 이 자료구조들이 내부적으로 hash value를 사용하기 때문이다.
  대부분의 Python Immutable built-in object가 hashable이다. list, dictionary와 같은 mutable container들은 hashable이 아니며, tuple, frozenset과 같은 immutable container들이 hashable한 요소들을 가질 경우만 hashable이다. 기본적으로 유저가 정의한 class의 인스턴스들도 hashable이다. 이들은 모두 비교했을 때 같지 않으며(자기 자신 제외), 이들의 hash 값은 이들의 id()로 도출된다.

번역한 내용을 정리하면 아래와 같다.

• Hashable = hash 값을 가짐
• Hashabe의 조건
  1. __hash__() : lifetime동안 hash값이 절대 변하지 않음
  2. __eq__() : 다른 객체들과 비교 가능
• Immutable 객체도 Hashable 요소들을 가질 경우만 hashable
• Hashable 객체는 id()를 통해 hash 값을 도출
  - 유저가 정의한 class의 인스턴스들은 id가 서로 다르기 때문에 hashable

이를 통해, __hash__ 뿐만 아니라 __eq__도 hashable과 연관이 있다는 것을 알 수 있다.

 

__eq__와 hashable의 관계?

  그러나 "다른 객체와 비교가 가능하다" 만으로는 hashable을 정의하기 모호하다. 다시 위 StackOverflow로 돌아가면, 아래와 같은 문구가 있다.

For classes you write, this method(__hash__) defaults to returning a value based off id(self), and if equality is not determined by identity for those classes, you may be suprised by using them as keys

여기서의 요점은 아래와 같다.

• 유저가 정의한 class의 default __hash__의 key는 인스턴스의 id이다.
• 만약 인스턴스들의 equality가 id에서 바뀐다면, dict의 key로 동작하지 않는다.

__eq__는 결국 두 객체의 값을 비교하여 equality를 판단하는 함수이다. 위 내용에 따르면, 유저가 정의한 class는 default로 __hash__의 key로 인스턴스의 id를 사용했고, __eq__를 따로 정의하지 않았기 때문에 key로 사용이 가능한 것이다. 그러나 __eq__를 정의하는 순간, key로 사용이 불가능하다. 무언가 더 필요하다. __hash__에 __eq__가 관여하는 것인지 확인하고 싶어, __hash__를 docs에서 찾아보았다.

https://docs.python.org/ko/3.6/reference/datamodel.html#object.__hash__

3. 데이터 모델 — Python 3.6.14 문서

여기에는 많은 "만약에"가 있다. 이들을 분리해서 정리해보았다.

• 같다고 비교되는 객체들이 같은 hash 값을 가져야한다는 성질만 요구됨

def __hash__(self):
    return hash((self.name, self.nick, self.color))

• 객체 비교에 사용되는 요소들의 tuple로 hash 값을 취하여야 함
• __eq__를 정의하지 않으면 -> __hash__도 정의하지 말아야 함
• __eq__를 정의하고 __hash__를 정의하지 않으면 -> hashable이 아님
• Mutable 객체를 정의하고 __eq__를 정의하면 -> __hash__를 정의하지 말아야 함
  (hash 값이 불변임을 요구하기 때문)
• 유저 정의 클래스의 default
  • __eq__ : 자기 자신을 제외하고 모두 같지 않음
  • __hash__ : 적절한 값 (id기반)
  • x == y일 때, x is y와 hash(x) == hash(y)가 동시에 성립
• __eq__를 재정의, __hash__를 정의하지 않으면 -> __hash__는 None
  (따라서 hashable이 아님)

 

결론

  여기서 hashable을 정리할 수 있을 것 같다.

1. Hashable 객체가 되기 위해서는 __eq__와 __hash__가 모두 정의되어야한다.
2. __hash__는 해당 객체의 hash 값을 반환한다.
3. __hash__는 hash key로, 객체를 비교(__eq__)할 때 사용하는 값을 사용해야한다(권장이라고는 함).
4. 두 객체에 대해 __eq__를 통해 같다고 판단되면, 두 객체의 hash값은 같아야 한다.

  즉, hashable하다는 것은 이 객체에 대해 __eq__의 결과가 True일 때, __hash__의 결과도 같음을 만족해야한다. Immutable 객체의 경우, 특정 값을 지닌 객체는 단 하나다. 즉, 값이 같으면 id도 같다. list의 경우 id가 다른 두 객체의 비교에서, 두 값이 같다라는 판단이 가능하다. 이는 객체를 구분하는 매커니즘의 명확해야함을 의미하는 듯 하다. 그래야 내가 요구하는 key값이 무엇인지, 이 유별한 key에 해당하는 hash bucket이 어디인지가 확실하게 판별되기 때문이다.

 

참고

[1] https://www.onlybook.co.kr/entry/algorithm-interview

파이썬 알고리즘 인터뷰

[2] https://docs.python.org/3/tutorial/datastructures.html#dictionaries

5. Data Structures — Python 3.9.6 documentation