[Python] immutable한 객체는 모두 hashable한가?

① Hashing은 hash table이라는 자료구조를 이용해서 요소들을 빠르게 찾을 수 있게 하는 방법이다.

Hash table은 모든 요소들에 대해서 key를 가진다.

이 key를 통해서 요소들을 찾는데 constant time (O(1)) (= 시간 복잡도 상수 시간)을 가져

요소들의 개수와 상관 없이 원하는 값을 빠르게 찾아낼 수 있다.

 

그렇다면 hashable하다는 것의 의미는 무엇일까?

Hashable은 객체가 만들어진 이후에 hash table의 value가 바뀌지 않음을 의미한다.

 

② Mutability는 이 변수가 바뀔 수 있는지 없는지에 대한 개념이다.

파이썬의 자료형에서는

Immutable type: Tuple, int, String, Frozenset

mutable type: List, Dictionary, Set

으로 나눌 수 있다.

 

③ Hashable과 Mutability의 관계

Hash key로 사용되는 객체는 immutable해야 한다는 점에서 이 두가지 개념은 연관이 있다.

→ hash value가 바뀌면 안되기 때문에

unhashable type 오류는 mutable한 객체를 hash key로 사용하려고 할때 발생한다.

파이썬에서 set은 immutable한 객체만을 가질 수 있다.

>>> sample_set = set()
>>> sample_set.add('A')
>>> sample_set
# {'A'}
>>> sample_set.add(['B', 'C'])
# TypeError: unhashabletype: 'list'

 

하지만 두 개념이 완전히 같지 않기 때문에, immutable하지만 hashable하지 않은 객체도 있다.

예를 들어, mutable한 객체(예를 들어, 리스트)를 갖고 있는 tuple이 있다.

# Immutable and hashable
my_tuple_1 = (1,2,3)
print(type(my_tuple_1))
print(hash(my_tuple_1))
# <class 'tuple'>
# -378539185

# Immutable but not hashable
my_tuple_2 = (1,2,3, [1,2])
print(type(my_tuple_2))
print(hash(my_tuple_2))
# <class 'tuple'>
# TypeError: unhashable type: 'list'

→ tuple = immutable, 리스트를 요소로 가지고 있기 때문에 unhashable.

따라서 제목의 질문의 답은 NO이다. 

 

▶ hash table에 들어가는 객체는 immutable해야 한다.

▶ 대부분의 immutable한 객체는 hashable하지만,

▶ 그렇다고 모든 immutable한 객체가 hashable한 것은 아니다. 예) 리스트를 요소로 가진 튜플