해시 테이블에서 충돌(collision)을 해결하는 대표적인 방법 중 하나가 바로 개방 주소법(Open Addressing)입니다. 그중에서도 가장 기본이 되는 기법이 선형 조사(Linear Probing)입니다. 이 글에서는 선형 조사법의 동작 원리와 해시 함수의 구성, 그리고 실제 예제를 통해 삽입 과정까지 자세히 살펴보겠습니다.
선형 조사란 무엇인가?
개방 주소법에서는 충돌이 발생했을 때 다른 빈 슬롯을 찾아 데이터를 저장합니다. 일반적으로 사용되는 기본 해시 함수는 다음과 같습니다.
h′(x) = x mod m
여기서 m은 해시 테이블의 크기입니다. 그러나 이 함수만으로는 충돌이 발생했을 때 어디에 저장할지 결정할 수 없습니다. 따라서 개방 주소법에서는 기본 해시 함수 h′(x)에 추가 항을 붙여 하나의 선형 방정식 형태로 확장한 실제 해시 함수 h(x)를 사용합니다.
실제 해시 함수
h(x, i) = (h′(x) + i) mod m
여기서 i는 0부터 m − 1까지의 값을 가집니다. 즉, i = 0에서 시작하여 빈 공간(free space)을 찾을 때까지 i를 1씩 증가시키며 슬롯을 순차적으로 검사합니다.
i = 0일 때는 h(x, 0) = h′(x)가 되므로, 처음에는 기본 해시 함수가 계산한 위치에 데이터를 저장하려고 시도합니다. 만약 해당 위치가 이미 차 있으면 i를 1 증가시켜 다음 슬롯을 확인하고, 이 과정을 빈 슬롯을 찾을 때까지 반복합니다.
예제: 크기 20의 해시 테이블
크기가 20(m = 20)인 해시 테이블에 다음 요소들을 선형 조사 방식으로 삽입한다고 가정해 보겠습니다.
{96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}
각 요소는 먼저 h′(x) = x mod 20을 통해 초기 위치를 계산하고, 해당 위치가 이미 사용 중이라면 한 칸씩 이동하면서 빈 슬롯을 찾게 됩니다.
삽입 과정 예시
- 96: 96 mod 20 = 16 → 인덱스 16은 비어 있으므로 그대로 저장
- 48: 48 mod 20 = 8 → 인덱스 8에 저장
- 63: 63 mod 20 = 3 → 인덱스 3에 저장
- 29: 29 mod 20 = 9 → 인덱스 9에 저장
- 87: 87 mod 20 = 7 → 인덱스 7에 저장
- 77: 77 mod 20 = 17 → 인덱스 17에 저장
- 48(두 번째): 48 mod 20 = 8 → 인덱스 8은 이미 차 있음 → i를 증가시켜 인덱스 9도 차 있음 → 최종적으로 빈 슬롯을 찾을 때까지 순차 탐색
이처럼 충돌이 발생할 때마다 한 칸씩 다음 위치를 검사하는 것이 선형 조사법의 핵심입니다.
해시 테이블
마무리
선형 조사법은 구현이 간단하고 캐시 지역성(cache locality)이 좋다는 장점이 있습니다. 하지만 여러 요소가 같은 초기 해시 값으로 몰릴 경우 빈 슬롯을 찾기 위해 연속된 슬롯을 길게 검사해야 하는 1차 군집화(primary clustering) 문제가 발생할 수 있습니다. 이를 보완하기 위해 제곱 조사(Quadratic Probing)나 이중 해싱(Double Hashing) 같은 기법들이 함께 사용됩니다.