키에서 저장 위치로
이름을 키로 삼아 전화번호를 저장한다면 키의 해시값을 이용해 확인할 위치를 좁힐 수 있다. 모든 항목을 처음부터 읽는 대신 위치 계산을 활용하는 방식이다. 계산된 위치에 다른 키가 들어 있을 가능성도 확인해야 한다.
충돌은 서로 다른 키 사이에서도 생긴다
저장 공간의 위치 수는 제한되어 있으므로 다른 키가 같은 위치로 연결될 수 있다. 같은 위치에 여러 항목을 연결하거나 다른 빈 위치를 찾아 저장하는 방식 등이 사용된다. 해시값이 같다는 사실만으로 원래 키도 같다고 판단해서는 안 된다.
항상 같은 시간은 아니다
적절한 해시 함수와 공간 관리 아래에서는 조회 등의 연산이 평균적으로 상수 시간에 가까울 수 있다. 충돌이 많이 몰리거나 저장 공간이 빽빽해지면 비용이 커질 수 있다. 하나의 성능 수치를 모든 입력과 구현에 무조건 적용할 수는 없다.
저장 공간을 바꿀 때
항목이 늘어나면 더 큰 공간을 마련하고 위치를 다시 계산하는 구현이 있다. 이 작업에는 여러 항목을 옮기는 비용이 들 수 있다. 개별 조회의 비용과 공간 확장 과정의 비용을 구분해 성능을 살펴야 한다.