그러나 삽입 연산은 좀 더 오래 걸릴 수 있습니다. A라는 원소를 삽입한다고 가정해보겠습니다. 삽입 함수는 먼저 첫 번째 해시 테이블에서 A를 삽입할 위치를 찾아 현재 비어 있는지를 검사합니다. 만약 해당 위치가 비어 있다면 그대로 A를 삽입하면 됩니다. 그러나 해당 위치에 이미 다른 원소 B가 저장되어 있다면, 해당 위치에 A를 저장하고 B를 두 번째 해시 테이블로 옮깁니다. 만약 B가 이동할 위치에 이미 다른 원소 C가 저장되어 있다면, 해당 위치에 B를 저장하고 C를 첫 번째 해시 테이블로 옮깁니다. 이러한 작업을 완전히 비어 있는 셀이 나타날 때까지 재귀적으로 반복합니다. 이러한 과정을 그림 3-9에 나타냈습니다.

▲ 그림 3-9 뻐꾸기 해싱

이러한 과정에서 만약 순환(cycle)이 발생한다면 무한 루프에 빠질 수 있습니다. 예를 들어 그림 3-9에서 C가 옮겨가야 할 위치에 다른 원소 D가 있고, D를 옮기다 보니 다시 A 위치를 방문한다고 가정하겠습니다. 이러한 경우가 순환이 발생하는 경우이며, 그림 3-10을 참고하기 바랍니다.

▲ 그림 3-10 뻐꾸기 해싱에서 발생한 순환