그림 21-1은 해시테이블이 어떻게 동작하는지 그림으로 보여준다. 각 블록은 단위 작업을 나타낸 것이다. 열은 각 add에 대한 전체 작업 단위이고, 왼쪽에서 오른쪽 순서로 진행된다. 처음 2번의 add는 1단위 작업이고, 세 번째는 3단위 작업을 사용한다.
▼ 그림 21-1 해시테이블 add의 비용
재해싱에 필요한 추가 작업은 점점 커지는 타워의 순차열로 나타난다. 여기서 타워를 무너뜨려서 전체 add에 대한 크기 조정 비용을 펼쳐보면 그림에서 볼 수 있는 것처럼 n번 add 후의 전체 비용이 2n-n인 것을 볼 수 있다.
이 알고리즘의 중요한 특징은 HashTable의 크기를 변경할 때 기하학적으로 커진다는 것이다. 다시 말해서 크기를 상수로 곱한 것이다. 크기를 산술적으로 증가시키면(매번 고정된 개수를 추가하는 것) add당 평균 시간은 선형이다.
여기서 구현한 HashMap은 http://thinkpython2.com/code/Map.py에서 받을 수 있지만, 이를 사용할 이유는 없다는 사실을 기억해야 한다. 맵을 원한다면 그냥 파이썬 사전을 사용하자.