전문가를 위한 파이썬(2판)

155

3

장

딕셔너리와 집합

3

.

9

dict

의 작동 방식이 미치는 영향

파이썬

dict

의 해시 테이블은 아주 효율적으로 구현되었지만, 이런 설계가 미치는 영향을 잘

알아야 한다.

●

키 객체는 반드시 해시 가능해야 한다. 따라서

3

.

4

.

1

절 ‘해시 가능한 객체’에서 설명했듯이

__

hash

__( )

와

__

eq

__( )

를 제대로 구현해야 한다.

●

키를 통한 항목 접근이 매우 빠르다.

dict

에는 수백만 개의 키가 있을 수 있지만, 파이썬은 키의 해시 코드

를 계산하고 해시 테이블에 대한 인덱스를 유도함으로써 키의 위치를 바로 알아낼 수 있다. 다만, 일치하는

항목을 찾아내기 위해 몇 번 더 시도해야 할 수는 있다.

●

CPython

3

.

6

dict

의 더 밀집된 메모리 배치

memory

layout

의 영향으로 키 순서가 유지된다 (

CPython

3

.

7

부터 공식 기능이 되었다 ).

●

밀집된 메모리 배치에도 불구하고

dict

의 메모리 사용량은 많을 수밖에 없다. 컨테이너 중 메모리 오버헤

드가 가장 적은 데이터 구조는 항목에 대한 포인터를 담은 배열일 것이다.

9

이에 비해 해시 테이블은 항목

마다 저장할 데이터가 더 많고, 파이썬은 해시 테이블의 효율성을 유지하려면 적어도

1

/

3

정도의 테이블을

비워 놓아야 한다.

●

메모리를 절약하려면

__

init

__( )

이외의