열린 주소 지정(Open Addressing)이란?
해시 테이블을 운용하다 보면 서로 다른 키가 동일한 해시 값을 가지는 충돌(Collision) 상황이 발생합니다. 열린 주소 지정은 이러한 충돌을 해결하는 대표적인 기법 중 하나입니다.
체이닝(Chaining) 방식과 달리, 열린 주소 지정은 연결 리스트 같은 별도의 자료구조에 요소를 저장하지 않습니다. 대신 충돌이 발생하면 해시 테이블 내부의 다른 빈 슬롯을 찾아 데이터를 직접 삽입합니다. 따라서 효율적인 운영을 위해서는 해시 테이블의 크기가 저장할 키의 개수보다 커야 합니다.
열린 주소 지정의 세 가지 대표 기법
열린 주소 지정에는 널리 사용되는 세 가지 방식이 있습니다.
- 선형 탐사(Linear Probing)
- 이차 탐사(Quadratic Probing)
- 이중 해싱(Double Hashing)
기본 동작 원리
다른 해싱 기법과 마찬가지로 해시 함수를 사용하여 데이터를 저장할 위치를 계산합니다. 해당 위치가 비어 있다면 그 자리에 바로 요소를 삽입하면 됩니다.
하지만 위치가 이미 차 있을 경우, 수학적 수식을 활용해 새로운 빈 슬롯을 찾게 됩니다. 선형 탐사에서는 일정 간격으로 순차적으로 이동하는 선형 방정식을 사용하고, 이차 탐사에서는 제곱 형태의 간격으로 이동하는 이차 방정식을 사용합니다. 예를 들어 선형 탐사는 충돌 시 한 칸씩 이동하며 빈 자리를 찾고, 이차 탐사는 1², 2², 3²처럼 점점 넓어지는 간격으로 탐색하여 특정 영역에 데이터가 몰리는 군집화(Clustering) 현상을 줄입니다.
이중 해싱(Double Hashing)
이중 해싱은 충돌이 발생했을 때 두 번째 해시 함수, 즉 보조 해시 함수(Secondary Hash Function)를 사용하여 새로운 위치를 결정하는 방식입니다.
충돌이 발생하지 않으면 보조 해시 함수는 전혀 사용되지 않으며, 오직 충돌 상황에서만 탐사 간격을 계산하기 위해 호출됩니다. 두 개의 서로 다른 해시 함수를 조합하기 때문에 선형·이차 탐사보다 군집화 문제를 효과적으로 완화할 수 있다는 장점이 있습니다.