더북(TheBook)

그림 21-1은 해시테이블이 어떻게 동작하는지 그림으로 보여준다. 각 블록은 단위 작업을 나타낸 것이다. 열은 각 add에 대한 전체 작업 단위이고, 왼쪽에서 오른쪽 순서로 진행된다. 처음 2번의 add1단위 작업이고, 세 번째는 3단위 작업을 사용한다.

▼ 그림 21-1 해시테이블 add의 비용

1146756.png 

재해싱에 필요한 추가 작업은 점점 커지는 타워의 순차열로 나타난다. 여기서 타워를 무너뜨려서 전체 add에 대한 크기 조정 비용을 펼쳐보면 그림에서 볼 수 있는 것처럼 nadd 후의 전체 비용이 2n-n인 것을 볼 수 있다.

이 알고리즘의 중요한 특징은 HashTable의 크기를 변경할 때 기하학적으로 커진다는 것이다. 다시 말해서 크기를 상수로 곱한 것이다. 크기를 산술적으로 증가시키면(매번 고정된 개수를 추가하는 것) add당 평균 시간은 선형이다.

여기서 구현한 HashMaphttp://thinkpython2.com/code/Map.py에서 받을 수 있지만, 이를 사용할 이유는 없다는 사실을 기억해야 한다. 맵을 원한다면 그냥 파이썬 사전을 사용하자.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.