add는 items 리스트에 키-값 튜플을 추가하며, 이는 상수 시간이 걸린다.

get은 리스트에서 검색하기 위해 for 루프를 사용한다. 대상 키를 발견하면 그에 해당하는 값을 반환하고, 그렇지 않으면 KeyError를 일으킨다. 따라서 get은 선형이다.

다른 방법으로는 키를 정렬된 상태로 리스트를 유지하는 것이다. 그러면 get은 이분 검색을 사용할 수 있고, 이분 검색은 O(log n)이다. 그러나 리스트의 중간에 새 항목을 삽입하는 것이 선형이므로 이것도 최선의 선택은 아닐 수 있다. add와 get을 로그 시간으로 구현하는 다른 자료 구조가 있지만, 상수 시간만큼 좋은 것은 아니므로 여기서는 이 상태로 계속해서 진행해보자.

LinearMap을 개선하는 한 가지 방법은 키-값 쌍의 리스트를 더 작은 리스트로 나누는 것이다. 다음은 100개의 LinearMap의 리스트로 구현한 BetterMap이다. 잠깐 살펴보겠지만, get의 증가 기준은 여전히 선형이지만, BetterMap은 해시테이블을 향한 경로에 한 단계 더 나아간 것이다.