[Python] Hash Map과 dictionary

🎱 Hash Map

해시맵(Hash Map)은 key-value의 쌍 형태로 데이터를 저장하며, 해싱을 기반으로 데이터들을 관리해주는 자료구조이다.

해시맵에서는 삽입, 삭제, 탐색, 포함 여부 확인 등 모든 함수의 시간복잡도가 전부 O(1)이라는 큰 특징이 있다.
대신 데이터간 순서가 없다는 점은 주의해야한다.

Python에는 편리하게도 이를 기반으로 구현된 클래스가 있다.
바로 dict다!

🎱 dictionary

d1 = dict()
d2 = {}
d3 = {'k1': 1, 'k2': 2, 'k3': 3}
d4 = {key: 0 for key in ['k1', 'k2', 'k3']}

d3['k1'] # key가 k1인 value 반환
d3.pop('k1') # key가 k1인 데이터 추출 및 반환
'k2' in d3 # d3의 key 중에 k2가 있다면 True, 없다면 False
d3.keys() # d3의 key들만 추출
d3.values() # d3의 value들만 추출

dict를 선언하는 방법은 여러가지가 있다.
빈 딕셔너리를 생성할때는 d1, d2 같은 방식이 많이 쓰이고,
초기화 할 경우 d3 과 같이 쓰기도 하며
반복문을 통해 초기화하고 싶다면 d4 와 같이 리스트 컴프리헨션을 통한 선언 또한 가능하다.

여기서 주의할 점은 key로 가능한 타입은 immutable 뿐이라는 점이다! 즉, list나 set같은 nutable 객체는 key로 사용할 수 없다.

🎱 언제 사용할까?

dict는 워낙 일반적으로 자주 쓰이는 자료구조라서 언제 쓰인다! 라고 말하기도 애매하다. 하지만 알고리즘 문제를 푼다면 아래와 같이 특수한 인덱스를 써야할 경우 특히 유용하다.

1. 큰 간격/큰 숫자를 index로 사용해야할 경우
2. 문자열을 index로 사용해야할 경우