파이썬 셋, 딕셔너리: hashtable 구조에 대하여

 

 

hashtable 구조란?

---

 

 

파이썬에서 셋이나 딕셔너리 자료형의 검색 속도가 리스트보다 빠른 건 hastable 구조 때문입니다. 그렇다면 hashtable 구조란 뭘까요?

 

hashtable은 입력된 어떤 변수를 hash 함수를 통해 고유한 index 값으로 변환하여 key:value 관계로 매핑하여 저장합니다. 따라서 검색에 활용되는 key 값은 중복이 허용되지 않는 unique 값이어야만 합니다. 

 

 

hash 함수 사용하기

 

파이썬에서 hash 함수를 사용하기 위에서는 hash 명령어를 사용합니다.

print(hash('가'))
print(hash('나'))
print(hash('다'))

 >>>>> 실행 결과
2316511072510970967
-7597973071070527842

 

위의 코드처럼 ‘가’, ‘나’, ‘다’의 각각 다른 3개의 값은 hash 함수를 통해 전혀 다른 세 개의 인덱스로  변환이 된 것을 확인할 수 있습니다. 변수 값이 unique 하므로, 변환된 인덱스 값도 unique 합니다. 

 

 

hashtable 구조가 빠른 이유

 

리스트의 경우에는 특정 값이 있는지 확인하기 위해, 순차적으로 값을 확인하지만 셋은 그럴 필요가 없습니다. 그저 한 번만 index를 입력해서 값이 있는지를 확인하면 됩니다.

 

정리하면, “셋과 딕셔너리 같은 자료형은 모든 값을 순차적으로 순회하는 경우를 제외하면 hashtable 구조 특성상 리스트보다 빠르다.”라고 할 수 있습니다.

 

 

셋의 hashable 특성과 mutable 객체?

 

셋의 원소로 리스트를 넣을 순 없지만 튜플은 넣을 수 있습니다. 이는 리스트는 mutable 객체이고 튜플은 imutable 객체이기 때문입니다.

 

mutable 객체는 값이 바뀌어도 주소값은 바뀌지 않습니다. 반면 imutable 객체는 값이 바뀌면 주소값이 바뀌어야 합니다. 따라서 mutable 객체는 값과 주소값이 unique 한 특성을 지니지만, imutable 객체는 그렇지 않죠.

 

그래서 set의 원소로 unique 한 맵핑 관계가 있는 imutable 객체만 올 수 있습니다.