Python 딕셔너리

파이썬의 딕셔너리는 키/값 구조로 이루어진 딕셔너리를 말한다.

3.7+ 부터는 입력 순서가 유지되며, 내부적으로 해시 테이블로 구현되어 있다.

 

언어	해시 테이블
파이썬	dict()
C++	std:unordered_map
자바	HashMap

 

해싱

파이썬의 딕셔너리는 해시할 수만 있다면 숫자 뿐만 아니라, 문자, 집합까지 불변 객체를 모두 키로 사용할 수 있다. 이 과정을 해싱이라고 하며, 해시 테이블을 이용해 자료를 저장한다. 무엇보다 해시 테이블은 다양한 타입을 키로 지원하면서도 입력과 조회 모두 O(1)에 가능하다. 분할 상환 분석(Amortized Analysis)에 따른 시간 복잡도는 O(1)이다. 이외에 해시 테이블의 주요 연산과 시간 복잡도는 아래와 같다.

연산	시간 복잡도	설명
len(a)	O(1)	요소의 개수를 리턴한다.
a[key]	O(1)	키를 조회하여 값을 리턴한다.
a[key] = value	O(1)	키/값을 삽입한다.
key in a	O(1)	딕셔너리에 키가 존재하는지 확인한다.

딕셔너리는 대부분의 연산이 O(1)에 처리 가능한 매우 우수한 자료형이다. 3.6 이하에서는 딕셔너리에서 순서가 유지되지 않아서 collections.OrderedDict()라는 별도 자료형을 제공했다. 하지만 3.7 이상부터는 내부적으로 인덱스를 이용해 입력 순서를 유지하도록 개선됐다. 3.6 이하의 버전을 사용하는 경우에는 아래와 같은 추가 모듈들이 유용하게 사용된다.

 

• collections.OrderedDict(): 항상 입력 순서가 유지되는 객체
• collections.defaultdict(): 조회시 항상 디폴트 값을 생성해 키 오류를 방지하는 객체
• collections.Counter(): 요소의 값을 키로 하고, 개수를 값 형태로 만들어 카운팅 하는 객체