딕셔너리는 해시 테이블이다
파이썬의 딕셔너리(dict)는 내부적으로 해시 테이블(hash table) 구조로 구현되어 있습니다. 트리 탐색과 같은 방식은 전혀 사용하지 않으며, 키(key)를 조회하는 작업은 딕셔너리의 크기와 거의 무관하게 분할상환 상수 시간(amortized constant time)에 처리됩니다.
해시 조회의 동작 과정
특정 키로 값을 조회할 때 파이썬은 다음과 같은 단계를 거칩니다.
1. 먼저 해당 키에 대한 해시 값을 계산합니다.
2. 계산된 해시 값에 연결된 저장 위치(버킷)를 찾아갑니다.
3. 만약 그 위치에서 다른 키와의 충돌(collision)이 발생했다면, 충돌 해결 알고리즘을 실행하여 실제 원하는 값을 찾아냅니다.
덕분에 요소가 수백만 개에 달하더라도 조회 성능이 크게 저하되지 않습니다.
속도를 위한 공간 트레이드오프
이처럼 빠른 조회 속도를 얻는 대신, 해시 테이블은 충돌을 줄이기 위해 희소(sparse)한 구조로 유지됩니다. 그 결과 딕셔너리는 리스트나 튜플 같은 밀집된 자료구조에 비해 더 많은 메모리 공간을 차지하는 단점이 있습니다. 즉, 파이썬 딕셔너리는 메모리를 좀 더 사용하는 대신 조회 속도를 극대화한 자료구조라고 할 수 있습니다.