LinearMap.get의 실행 시간은 항목의 개수에 비례하므로 BetterMap이 LinearMap보다 약 100배 더 빠르다고 기대할 수 있다. 증가 기준은 여전히 선형이지만, 최고차항이 더 작다. 이것도 멋지지만, 해시테이블만큼 성능이 좋지는 않다.

여기서 마지막으로 해시테이블을 빠르게 만들 결정적인 아이디어를 살펴보자. LinearMap들의 최대 길이를 유지할 수 있다면 LinearMap.get은 상수 시간이다. 이렇게 하려면 항목의 개수를 관리하고, LinearMap당 항목의 개수가 임계값을 초과하면 더 많은 LinearMap을 추가해서 해시테이블 크기를 조정하면 된다.

다음은 해시테이블을 구현한 것이다.

class HashMap:

def _ _init_ _(self):

self.maps = BetterMap(2)

self.num = 0

def get(self, k):

return self.maps.get(k)

def add(self, k, v):

if self.num == len(self.maps.maps):

self.resize()

self.maps.add(k, v)

self.num += 1

def resize(self):

new_maps = BetterMap(self.num * 2)

for m in self.maps.maps:

for k, v in m.items:

new_maps.add(k, v)

self.maps = new_maps