21.4 해시테이블

해시테이블이 어떻게 동작하며, 성능은 왜 그렇게 좋은지 설명하기 위해 간단한 map을 구현하고, 이를 점진적으로 개선해서 해시테이블을 만드는 것부터 시작하겠다.

파이썬을 사용해 이들 구현을 보여주겠지만, 실제로 파이썬에서 이런 코드를 작성하는 일은 없을 것이다. 바로 사전을 써라! 따라서 이 장의 나머지는 사전이 없기 때문에 키와 값을 연결하는 자료 구조를 구현하고 싶다고 상상해야 한다.

add(k, v)

키 k와 값 v를 연결하는 새로운 항목을 추가한다. 파이썬 사전 d라면 이 연산을 d[k] = v라고 작성했을 것이다.

get(k)

탐색해서 키 k에 대응하는 값을 반환한다. 파이썬 사전 d라면 이 연산은 d[k] 또는 d.get(k)라고 작성했을 것이다.