이번 글에서는 개방 주소법(Open Addressing) 방식에서 해시 충돌을 해결하는 대표적인 기법인 2차 탐사(Quadratic Probing)에 대해 자세히 알아보겠습니다.
2차 탐사의 기본 원리
2차 탐사는 일반적인 해시 함수 h′(x) : U → {0, 1, ..., m – 1}을 기반으로 동작합니다. 개방 주소법에서 실제로 사용되는 해시 함수 h(x)는 이 일반 해시 함수에 2차식 형태의 항을 덧붙여 만든 하나의 이차 방정식입니다.
먼저 일반 해시 함수는 다음과 같이 정의됩니다.
h′(x) = x mod m
그리고 실제 해시 함수는 여기에 탐사 횟수 i의 제곱을 더한 형태입니다.
h(x, i) = (h′(x) + i²) mod m
필요에 따라 상수를 활용하여 다른 형태의 2차 방정식을 사용할 수도 있습니다. 예를 들어 h(x, i) = (h′(x) + c₁i + c₂i²) mod m처럼 상수 c₁, c₂를 조절하면 탐사 순서를 다양하게 변경할 수 있습니다.
여기서 i의 값은 0, 1, ..., m – 1 범위를 가집니다. i = 0부터 시작하여 빈 슬롯(empty slot)을 찾을 때까지 i를 하나씩 증가시킵니다. 처음 i = 0일 때는 h(x, i)가 원래의 해시 함수 h′(x)와 동일하다는 점에 유의하세요.
동작 과정 요약
2차 탐사의 동작 순서를 정리하면 다음과 같습니다.
1. 먼저 i = 0으로 두고 h(x, 0) = h′(x) 위치에 데이터를 삽입을 시도합니다.
2. 해당 슬롯이 비어 있으면 그대로 저장하고, 이미 차 있다면 i를 1 증가시킵니다.
3. h(x, i) = (h′(x) + i²) mod m으로 새로운 위치를 계산합니다.
4. 빈 슬롯을 찾을 때까지 2~3단계를 반복합니다.
이러한 방식은 선형 탐사(Linear Probing)에서 발생하는 1차 군집화(primary clustering) 문제를 완화하는 데 효과적입니다. 충돌이 발생해도 제곱 간격만큼 떨어진 위치를 확인하기 때문에 데이터가 한 곳에 몰리는 현상이 줄어듭니다.
예제
크기가 20(m = 20)인 해시 테이블이 있다고 가정하고, 다음 요소들을 2차 탐사 방식으로 삽입해 보겠습니다.
{96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}
각 요소를 h′(x) = x mod 20으로 계산하면 초기 위치가 결정되며, 충돌이 발생하면 (h′(x) + i²) mod 20 공식으로 다음 위치를 찾습니다. 예를 들어 48은 48 mod 20 = 8이므로 인덱스 8에 삽입되지만, 같은 값 48이 다시 들어오면 충돌이 발생하여 (8 + 1²) mod 20 = 9, 그래도 충돌하면 (8 + 2²) mod 20 = 12 순으로 위치를 탐색합니다.
모든 요소를 삽입한 후의 최종 해시 테이블 상태는 아래와 같습니다.
마무리
2차 탐사는 구현이 간단하면서도 선형 탐사보다 군집화 문제를 줄일 수 있는 실용적인 충돌 해결 기법입니다. 다만 동일한 초기 해시 값을 가지는 키들이 같은 탐사 순서를 따르는 2차 군집화(secondary clustering) 현상이 남아 있으며, 테이블 크기 m이 적절히 선택되지 않으면 모든 슬롯을 탐색하지 못할 수도 있다는 점을 기억해야 합니다. 일반적으로 m을 소수(prime number)로 설정하면 이러한 문제를 완화할 수 있습니다.