해싱

정의

해시 테이블(hash table)은 키(key) (필요한 경우 연관된 value)를 저장, 삭제, 열람 할 때 평균 O(1) 만큼 시간이 걸리는 것을 목표로 한다. 이를 위해, key는 hash 함수를 통해 변환되어 hash code (int)로 array (=hash table)에 저장된다. key가 hash 함수를 통과하여 array에 매핑된 결과는 가급적 균일하게 분포하도록 hash 함수를 설계하는 것이 필요하다. (주의깊은 해싱함수의 설계에도 불구하고) 두 key가 array의 같은 위치에 매핑되는 것을 충돌(collision)이라고 부른다. 이를 처리하기 위해 각 위치에 연결리스트(linked list)를 두거나 open addressing, linear probing 등의 방법을 활용한다. 결론적으로, 해싱함수와 hash code가 저장될 array (hash table)가 해싱 자료구조에 필요한 구성요소이다. 파이썬에서는 hash() 라는 built-in 함수가 제공되므로 간단한 설계를 해야 할 때는 이것을 활용할 수 있을 것이다.

해싱함수 동작 예 (출처: https://en.wikipedia.org/wiki/Hash_function)

Key의 자격

어떤 key의 hash code 값이 hash table에 저장되고 나면, '함수'의 정의에 따라, 같은 key를 다시 입력할 경우 늘 이전에 만들었던 것과 같은 hash code를 생성하므로 언제나 hash table의 해당 위치에서 값을 가져올 수 있어야 한다. 하지만, 만일 현존하는 key값이 변경될 경우에는 나중에는 그 hash code가 존재함에도 이를 가져올 수 없다. 그러므로 key에는 이런 현상을 방지하기 위해 immutable object를 사용하는 것이 필요하다.

예를 들어, hash 대상 object로서 a = [1,2,3] 가 해싱함수에 들어갔다고 해보자. 이 객체는 변형이 가능(mutable) 하기 때문에 hash(a) 한 후에 a[1] = 5 라고 바꾸고 다시 hash(a) 를 하면 전혀 다른 곳으로 매핑이 되게 된다. 그곳에는 다른 자료가 존재하는 것이다. 그러므로 파이썬에서는 이를 방지하기 위해 mutable object를 해싱하려고 하면 오류가 발생한다. 만일 list를 해싱하고 싶다면 이를 hash(frozenset(a)) 처럼 해야한다.

ADT와 자료구조

추상자료형(ADT, abstract data type)은 우리가 구현하고 싶은 기능을 모아놓은 자료구조의 내용이라고 할 수 있다. 위에서 설명한 것과 같은 기능을 map ADT라고 한다. 이를 실제로 구현하는 것이 Hash table 자료구조이다. 그리고 이는 파이썬에서 dict 자료형(클래스)으로 마련되어 있어서 사용자가 바로 활용할 수 있다. hash table 구조가 구현된 다른 자료형으로는 set, frozenset, collections.defaultdict, collections.Counter 등이 있다. 소개한 자료형 중 set은 key만 저장한다. 나머지는 key-value pairs를 저장한다.

dict의 경우는 저장되지 않은 key를 접근하려고 시도하면 KeyError 예외가 발생하나 defaultdict는 객체를 만들때 설정했던 기본값(default)을 돌려준다. defaultdict의 활용법은 graph 등의 실제 문제와 결부하여 다루도록 하겠다.

먼저 set의 사용법을 살펴보자.

s = set()
s.add('Jason')
s.add('Muzi')
s.remove('Muzi')
x = 'Jason'
x in s   # True
t = set()
t.add('Jason')
t.add('Nini')
s <= t  # True
t - s   # {'Nini'}

아래는 dict의 사용법이다.

>>> d = {'Jason': 30, 'Muzi': 43, 'Ryan': 56}
>>> for k, v in d.items():
...     print(k, v)
... 
Jason 30
Muzi 43
Ryan 56

>>> for k in d.keys():
...     print(k)
... 
Jason
Muzi
Ryan

# default for iteration on key-value pair gives key
>>> for i in d:
...     print(i)
... 
Jason
Muzi
Ryan

>>> for v in d.values():
...     print(v)
... 
30
43
56

다음에는 해싱의 대표적 사례로서 LRU Cache를 다뤄보도록 하겠다.