각 HashMap에는 BetterMap이 들어 있다. _ _init_ _은 처음에 LinearMap 단 2개로 시작하고, 항목 개수를 관리할 num을 초기화한다.

get은 단순히 BetterMap을 가져오기만 한다. 진짜 일은 add에서 일어난다. add는 항목의 개수와 BetterMap의 크기를 확인한다. 즉, 이 둘이 같다면 LinearMap당 항목의 평균 개수는 1이므로 크기를 조정한다.

resize는 새로운 BetterMap을 만든다. 이전 BetterMap보다 두 배 더 크게 만들고, 이전 맵의 항목을 새로운 맵으로 “재해시”한다.

LinearMap의 수를 변경하면 find_map의 나머지 연산자의 분모가 변경되기 때문에 재해싱은 반드시 해야 한다. 즉, 같은 LinearMap에 해시하는 데 사용된 일부 객체가 분할될 것이다(이것이 우리가 원했던 것이지 않은가?)

재해싱은 선형이므로 크기 변경도 선형이다. 나는 add가 상수 시간일 것이라고 약속했으므로 이는 나빠 보인다. 그러나 크기 변경을 매번 하는 것이 아니라는 것을 기억하자. 즉, add는 일반적으로 상수 시간이고, 때에 따라 선형이 될 뿐이다. add을 n번 수행하는 전체 작업 시간은 n에 비례하지만, 각 add의 평균 시간은 상수 시간이다!