[Python][자료구조] HashMap과 TreeMap, HashSet과 TreeSet

HashMap(dictionary)

 

HaspMap은 해싱을 기반으로 하는 자료구조이고 파이썬에서는 dictionary라는 HashMap이 존재한다.

 

HashMap은 key-value 쌍으로 값을 저장하는 자료구조이고 해싱을 기반으로 하기 때문에

 

탐색, 삽입, 삭제의 시간복잡도가 O(1)이다.

 

사용법

1. 선언

map = dict()

2. 삽입

map[key] = value

3. 탐색

 

키 탐색

if key in map: #key가 map에 존재한다면 true

값 탐색

if value in map.values(): #value가 map에 존재하면 true

4. 삭제

d.pop(key) # key에 해당하는 값 삭제하고 그 값 반환

map["a"] += 1과 같이 정수형 value를 저장한 다음 연산을 할 수도 있다.

 

그런데 이 방법은 미리 딕셔너리에 "a"라는 key에 해당하는 정수형 value가 저장되어있지 않으면 에러가 발생한다.

 

그래서 연산을 하기 전에 해당 키 값이 있는지 확인하고 있다면 연산을 하고 없다면 특정 값을 저장하도록 한다.

 

그런데 defaultdict를 사용하면 키 값 존재 여부를 확인할 필요가 없도록 default 값을 설정할 수 있다.

 

해당 키 값이 없으면 default로 설정해둔 값이 자동으로 저장된다.

 

defaultdict는 선언 부분만 다르고 나머지는 dictionary와 동일하다.

 

선언

from collections import defaultdict
map=defaultdict(lambda : 0) # lambda : default 로 초기값을 정할 수 있다.

map에 아무것도 존재하지 않을 때 map["a"] += 1을 하면 자동으로 ( "a" - 0 )쌍을 만들어서 저장하고 여기에 1을 더한다.

 

TreeMap(SortedDict)

HashMap의 경우 key-value 쌍으로 저장할 수 있지만 순서대로 저장하지는 않는다.

 

이에 비해 TreeMap은 key-value 쌍으로 저장하고 key 값을 기준으로 자동으로 정렬을 해준다.

 

TreeMap은 탐색, 삽입, 삭제의 시간복잡도가 O(log N)이다.

사용법

1. 선언

from sortedcontainers import SortedDict
map=SortedDict()

선언을 제외한 나머지는 dictionary와 동일하다.

 

HashSet(set)

HaspSet은 해싱을 기반으로 하는 자료구조이고 파이썬에서는 set이라는 HashSet이 존재한다.

 

HashSet은 값을 저장하는 자료구조이고 해싱을 기반으로 하기 때문에

 

탐색, 삽입, 삭제의 시간복잡도가 O(1)이다.

HashSet은 중복을 허용하지 않는다.

 

사용법

1. 선언

s=set()

2. 삽입

s.add(6)

3. 탐색

if value in s: #존재하면 true

4. 삭제

s.remove(value)

TreeSet(SortedSet)

HashSet의 경우 중복되지 않는 값을 저장할 수 있지만 순서대로 저장하지는 않는다.

 

이에 비해 TreeSet은 중복되지 않는 값을 저장하고 값을 기준으로 자동으로 정렬을 해준다.

 

TreeSet은 탐색, 삽입, 삭제의 시간복잡도가 O(log N)이다.

 

1. 선언

from sortedcontainers import SortedSet
s=SortedSet()

나머지는 HashSet과 동일하다.