이차함수 탐색

선형 탐색의 가장 큰 문제점은 군집화입니다. 충돌이 발생하면 군집을 차례대로 검사해야 하기 때문입니다. 이를 해결하기 위해 선형 방정식이 아닌 이차 방정식을 사용하여 탐색을 수행할 수 있습니다. 이러한 방식의 탐색을 이차함수 탐색(quadratic probing)이라고 합니다.

예를 들어 데이터 x를 hash(x) 위치에 삽입하려고 합니다. 만약 이 위치가 이미 사용 중이라면 hash(x + 1²)으로 이동하고, 그다음은 hash(x + 2²)으로 이동합니다. 이처럼 이동 폭을 이차함수 형태로 증가시키면 데이터 군집이 나타날 확률은 상대적으로 줄어듭니다.

선형 탐색 및 이차함수 탐색은 모두 원소 위치가 기존에 삽입되어 있는 다른 원소들에 의해 영향을 받습니다. 이때 기존에 저장되어 있던 원소는 새로 삽입하는 원소와 서로 다른 해시 값을 가질 수도 있습니다. 즉, 특정 해시 값을 갖는 키가 오직 하나만 존재한다 하더라도 충돌이 발생할 수 있습니다. 예를 들어 선형 탐색에서 해시 값이 4인 키가 두 개 있는 경우, 하나는 4 위치에 삽입하고 다른 하나는 5 위치에 삽입합니다. 이후 해시 값이 5인 키를 새로 삽입해야 한다면 이는 6 위치에 삽입해야 합니다. 이 키는 다른 원소와 중복된 해시 값을 갖지 않았지만 저장되는 위치에는 영향을 받았습니다.