[알고리즘] HashMap, TreeMap, HashSet, TreeSet

1. HashMap

해시 함수란, 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 값, 해시 코드, 해시 체크섬 혹은 해시라고 부른다. 보통 해시함수는 해시값이 다르다면 서로 다른 데이터를 가지고 있어야 하지만, 해시 값을 결정하는 함수에 따라서 서로 다른 데이터가 하나의 해시값에 저장이 되는 경우도 있다. 이런 경우를 해시 충돌이라고 한다. 해시 충돌이 빈번하게 발생하면 효율성을 떨어뜨리기 때문에 해시 충돌을 최소화하는 것이 좋다. 

 

파이썬에서는 이러한 hashmap을 간단하게 dictionary의 형태로 나타낼 수가 있다. hashmap은 (key, value)의 쌍으로 이루어져 있기 때문에 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(1)이다. 따라서 시간 효율성이 좋지만, 들어온 값의 순서를 표현하는 데에는 한계가 있다. 

 

딕셔너리를 선언하는 방식은 dict(), {} 이렇게 두가지 방식이 있고, 삽입하거나 value 값을 수정하기 위해서는 그냥 dic['a'] = 'apple'과 같은 식으로 해주면 된다. 삭제 역시도 .pop() 메소드를 이용하면 손 쉽게 할 수 있다. 

dic = dict()
dic_2 = {}

dic['a'] = 'apple'
dic.pop('a')
print(a in dic)

추가로 .keys()나 .values() .items()를 이용하면 키만 모아둔 리스트, 값만 모아둔 리스트, (키, 값)으로 이루어진 튜플을 모아둔 리스트로 각각 손쉽게 변환해줄 수 있다.

 

---

2. TreeMap

TreeMap은 균형 잡힌 이진트리 구조를 의미한다. 균형잡힌 이진트리 구조란 삽입, 삭제가 일어나는 순간에 루트 노드와 주위에 있는 노드를 적절하게 조절하여 왼쪽 자식 트리와 오른쪽 자식 트리의 높이 차가 크지 않도록 하는 트리이다. python에서는 treemap을 구현해둔 내장 함수는 없다. sortedcontainers 라이브러리에서 SortedDict라고 하는 것을 사용할 수 있지만, 외장 라이브러리이기 때문에 코딩테스트 환경에서는 대부분 사용할 수 없다. 그래도 우선 사용 방법에 대해 알아보도록 하겠다. 

$ pip install sortedcontainers

from sortedcontainers import SortedDict

sd = SortedDict()
sd['a'] = 'apple'
sd['b'] = 'banana'

sd.pop('a')

SortedDict도 사용법 자체는 python 내장의 dict와 동일하다.

다만 key값이 정렬된 상태로 항상 유지되기 때문에 이 점을 이용하면 문제를 쉽게 해결할 수 있을 때가 있다. 

 

---

3. HashSet

python의 set()은 HashSet 자료구조로 되어 있다. 이 HashSet이 해싱을 기반으로 하고 있기 때문에 삽입, 삭제, 탐색 등의 시간복잡도가 모두 O(1)이다. 하지만 들어온 값의 순서를 표현해주지는 못하고, 중복된 값은 한 번만 담기게 된다. 

 

set()의 원소로 들어올 수 있는 자료형은 immutable한 자료형, 즉 변동할 수 없는 자료형만 해당이 된다. int나 char, tuple까지도 원소로 가질 수 있지만, list나 dict 와 같은 형태는 원소가 될 수 없다. 

s = set()

s.add(1)
s.add((1, 3))
s.remove(1)

---

4. TreeSet

python에서는 균형잡힌 이진트리 형태의 treeset도 별도로 제공해주지 않고 있다. 따라서 아까 이용했던 sortedcontainers에 포함되어 있는 SortedSet을 이용할 수 있다. TreeSet도 균형잡힌 이진트리 형태이기 때문에 삽입, 삭제, 탐색 등에 걸리는 시간 복잡도는 O(log N)이다.

from sortedcontainers import SortedSet

s = SortedSet()

s.add(1)
s.add(2)
s.add(3)
s.add(4)

idx = s.bisect_left(1) # 1보다 같거나 큰 최초 숫자의 위치 idx = 0
idx = s.bisect_right(1) # 1보다 큰 최초 숫자의 위치 idx = 1
idx = s.bisect_right(5) # 5보다 큰 최초 숫자의 위치 idx = 4

SortedSet에서는 bisect_left()와 bisect_right()를 통해서 원하는 숫자보다 같거나 큰 / 큰 숫자의 최초 위치를 쉽게 파악할 수 있다. 

 

---

코딩테스트에서는 sortedcontainers 라이브러리를 이용할 수 없고, 이 자료구조를 직접 구현하는 데에는 많은 시간이 걸리기 때문에 보통 이 자료구조로만 풀리는 문제는 출제하지 않는다고 한다. (시간 효율성을 좀 더 너그럽게 주는 식이라면 다른 방법으로도 같은 문제들을 풀 수 있으니까) 그래도 자료구조에 대한 기본 개념들을 정리하기에는 괜찮은 라이브러리인 것 같다.