1. 딕셔너리 자료형과 해시 테이블
파이썬의 키/값 구조로 이루어진 자료형입니다.
내부적으로 해시 테이블로 구현되어 있습니다.
리스트 자료형은 인덱스(숫자)만을 사용하여 값을 찾을 수 있지만, 딕셔너리는 해시할 수 있는 모든 객체를 키로 사용할 수 있습니다.
불변 객체는 해시할 수 있으며(hashable), 따라서 문자, 숫자, 집합까지 모두 키로 사용 가능합니다.
해시 테이블의 장점은 조회가 \(O(1)\)에 가능하다는 점입니다.
따라서 딕셔너리의 주요 연산 시간 복잡도는 \(O(1)\)에 처리가 가능하다는 장점이 있습니다.
| 연산 | 시간 복잡도 | 결과 |
| len(Dict) | \(O(1)\) | 요소의 개수 반환 |
| Dict[key] 또는 Dict.get(key) | \(O(1)\) | 키에 해당하는 값 반환 |
| Dict[key] = value | \(O(1)\) | 해당 키에 값을 삽입 |
| del Dict[key] 또는 Dict.pop(key) | \(O(1)\) | 해당 키 삭제(반환 차이) |
| Dict.clear() | \(O(1)\) | 모든 키 삭제(초기화) |
| key in Dict | \(O(1)\) | 해당 키 존재 여부 반환 |
심지어 파이썬 3.6부터는 딕셔너리의 메모리 사용량을 20% 정도 줄이는 성능 개선이 이루어졌습니다.
2. 딕셔너리와 관련된 모듈
가. defaultdict
딕셔너리 자료형에서 없는 키를 조회하면 KeyError가 발생합니다.
a = {}
a["key"]
# KeyError: 'key'KeyError를 방지하기 위해서 try, except문을 사용하거나, get 메서드를 사용할 수 있습니다.
print(a.get("key"))
# None
try:
print(a["key"])
except:
print(None)
# None하지만 defaultdict를 사용하면 편합니다.
defaultdict는 default로 사용할 타입을 지정해야하고, 키가 없을 경우 해당 타입의 기본값을 반환합니다.
from collections import defaultdict
a = defaultdict(str)
a["key"]
# ''
a = defaultdict(int)
a["key"]
# 0
a = defaultdict(list)
a["key"]
# []
a = defaultdict(dict)
a["key"]
# {}알고리즘 문제를 풀 때, 특정 값의 개수나 횟수를 구할 때 자주 사용합니다.
나. Counter
Counter 객체는 요소의 개수를 계산해 딕셔너리를 상속 받은 객체로 반환합니다.
from collections import Counter
a = [1, 1, 1, 2, 2, 3, 3, 3, 3]
Counter(a)
# Counter({3: 4, 1: 3, 2: 2})자주 사용하는 메서드는 most_common이 있고, 빈도 수가 높은 순서로 키, 값 쌍을 리스트로 반환합니다.
메서드에 숫자를 입력하면 그 숫자 개수만큼 반환해줍니다.
Counter([1, 1, 1, 2, 2, 3, 3, 3, 3]).most_common(2)
# [(3, 4), (1, 3)]그리고 Counter 객체끼리는 더하거나 빼는 산술 연산이 가능합니다.
빼서 음수가 되는 경우 해당 키가 사라집니다.
Counter([1, 1, 1, 1, 2, 2, 3, 3]) + Counter([1, 2, 2, 3, 3, 3])
# Counter({1: 5, 3: 5, 2: 4})
Counter([1, 1, 1, 1, 2, 2, 3, 3]) - Counter([1, 2, 2, 3, 3, 3])
# Counter({1: 3})다. OrderedDict
해시 테이블을 이용한 대부분의 자료형은 입력 순서가 유지되지 않습니다.
하지만 파이썬 3.7부터는 딕셔너리에 입력 순서가 유지되도록 개선되었습니다.
OrderedDict는 그 이전에 사용하던 객체로서 현재는 사실상 하위 호환성을 위해서 남아있습니다.
from collections import OrderedDict
od = OrderedDict({"a": 1, "c": 3, "b": 2})
od
# OrderedDict([('a', 1), ('c', 3), ('b', 2)])
list(od)
# ['a', 'c', 'b']
d = {"a": 1, "c": 3, "b": 2}
d
# {'a': 1, 'c': 3, 'b': 2}
list(d)
# ['a', 'c', 'b']
그러나 알고리즘 문제의 채점에 사용되는 파이썬이 하위 버전일 수도 있고, 해시 테이블이라는 자료구조가 원래 순서가 유지되지 않는 만큼 딕셔너리의 입력 순서를 너무 무의식적으로 사용하는 것은 유의해야합니다.
