프로그램 실행 결과를 보면 해시 테이블 내부에서 데이터가 어떻게 관리되고 있는지를 파악할 수 있습니다. 원소 삽입 시 기존의 원소가 어떻게 이동하는지도 자세히 보여줍니다. 마지막에 14를 입력할 때 순환이 발생한다는 것도 확인할 수 있습니다. 이 경우 일곱 번 이상의 내부 이동이 발생한 것입니다. 바로 위 print() 함수 출력 결과를 보면 이미 양쪽 테이블의 대부분이 채워져 있는 것을 확인할 수 있습니다. 즉, 전체 14개 셀 중에서 10개가 채워져 있는 상태이므로 원소 이동 가능성이 높은 상태입니다.

위 구현에서 삭제 연산은 lookup() 함수 호출과 벡터에서 특정 원소를 -1로 설정하는 형태로 구현되어 있으므로 시간 복잡도는 O(1)입니다. 원소 삽입에서만 어느 정도 시간을 필요로 할 뿐입니다. 그러므로 연습 문제 15의 구현 코드는 원소 삽입보다 룩업 연산이 훨씬 많은 응용 프로그램에 적합합니다.

뻐꾸기 해싱을 사용한 삽입, 검색, 삭제 연산의 예를 그림 3-11부터 그림 3-15까지 도식적으로 나타냈습니다.

▲ 그림 3-11 뻐꾸기 해싱을 사용하는 해시 테이블에 원소 삽입하기