해시 함수와 해시 테이블

오늘은 많은 파이썬 초급자들이 보았을지도 모르는 에러로 글을 시작한다.

Traceback (most recent call last):
  File "test.py", line 1, in <module>
    my_dict = {1: 'Bob', [2,3,4]: 'names'}
TypeError: unhashable type: 'list'

unhashable type이 대체 뭐야?

hash 함수

먼저 hashable의 개념을 알기 위해서는 hash 함수에 대한 개념을 알아야 한다. 해시 함수는 임의의 데이터를 정해진 범위의 값으로 매핑시키는 단방향 함수를 말한다. 위의 예시처럼 입력을 받고, 그 출력이 0에서 15로 정해져 있는 것이 해시 함수의 일종이다.

해시 함수는 사실 매우 직관적인데, 어떤 수를 10으로 나눈 나머지 역시 해시 함수라고 할 수 있다. 입력이 어떤 수든 주어지면 0에서 9로 출력이 제한되어 있기 때문이다.

hash table

해시 테이블은 이러한 해시 함수를 이용하여 변환된 key를 가지고 index (색인)으로 사용해서 그 인덱스에 value를 저장하는 형식의 자료구조를 말한다. 중요한 것은 hash table에는 자료가 저장되는 순서가 없다는 것이다.

파이썬에서 dict 자료형이 해시 테이블과 구조와 같다. dict 역시 순서가 없고, key-value 쌍으로 이루어져 있다.

hash table의 충돌

그러나 만약 같은 인덱스로 해싱되는 key가 두 개 이상 있다고 생각해보자. 이 경우 우리는 어떤 key에 인덱스를 부여해야할지, 문제가 발생하게 된다. 이것을 충돌이라고 한다.

이 문제를 해결하기 위해서 두 가지 방법이 있다.

• Open addressing: 일단 건너뛰고, 다음 인덱스에 빈 칸이 있으면 그 인덱스에 key-value쌍을 할당
• Chaining: 그냥 그 인덱스에 여러 개의 key-value쌍을 저장해두자.

hash table의 시간 복잡도

hash table이 리스트보다 유용한 경우도 있는데, 바로 이 압도적인 시간 복잡도를 활용할 수 있기 때문이다.

탐색을 하는 리스트에서는 O(n) 의 시간복잡도가 있었던 반면 hash table은 기본적으로 key-value쌍으로 이루어진 자료형이기에 key로 탐색을 해서 O(1) 로 압도적인 성능을 보여준다.

Open addressing이나 Chaining을 적용하여, load factor는 n/m (해시 테이블의 총 key-value쌍의 개수 / 해시 테이블 배열의 개수)이고, 결과적으로 O(1)의 시간복잡도가 된다.

파이썬의 hash( )

파이썬에서도 hash 함수를 쓸 수 있다.

# 문자열
print(hash("파이썬"))  # -8002119629611903017
print(hash("파이썬"))  # -8002119629611903017

# 다른 문자열
print(hash("자바"))  # -8553573703343279427

그러나 중요한 것은, 자료형이 immutable한 것만 hash 함수의 입력값으로 넣을 수 있다는 것이다. 따라서 위의 에러도 mutable한 자료형인 list를 key로 넣어서 이 hash 함수가 mutable한 자료형을 해싱할 수 없기 때문에 에러가 발생한 것이다.

파이썬에서 immutable한 자료형은 다음과 같다.

• bool
• int
• float
• str
• tuple