파이썬의 딕셔너리(dict)는 내부적으로 해시 테이블(hash table) 구조로 구현되어 있습니다. 일부 자료구조처럼 트리를 순회하며 값을 찾는 방식이 아니라, 키(key)를 해시 함수에 통과시켜 저장 위치를 바로 계산하는 방식을 사용합니다.
딕셔너리 검색 과정
딕셔너리에서 키를 조회하는 과정은 다음과 같습니다.
1. 키의 해시값을 계산합니다.
2. 해시값에 대응하는 메모리 위치(버킷)를 찾아갑니다.
3. 해당 위치에 다른 키가 이미 저장되어 있어 충돌(collision)이 발생하면, 충돌 해결 알고리즘을 통해 실제 값이 저장된 위치를 찾아냅니다.
거의 일정한 조회 속도
이러한 구조 덕분에 딕셔너리에서 키를 찾는 연산은 요소가 몇 개든 거의 일정한 시간, 즉 분할 상환 상수 시간(amortized O(1))에 수행됩니다. 데이터 크기가 커져도 조회 속도가 눈에 띄게 느려지지 않는 것이 딕셔너리의 가장 큰 장점입니다.
공간을 더 차지하는 이유
다만 빠른 속도에는 대가가 따릅니다. 해시 충돌을 줄이고 효율적인 조회를 유지하기 위해 딕셔너리는 실제 저장된 항목 수보다 넉넉한 공간을 미리 확보합니다. 그래서 딕셔너리는 메모리 측면에서 희소(sparse)한 구조를 가지며, 리스트와 같은 밀집된 자료구조보다 더 많은 공간을 차지하게 됩니다.
정리하면, 파이썬 딕셔너리는 '속도를 위해 공간을 희생'하는 설계입니다. 빈번한 키 조회가 필요한 경우 딕셔너리가 최적의 선택인 이유가 바로 여기에 있습니다.