해시 오버플로란?
새로운 데이터 쌍(key, element)을 저장하려고 할 때 해당 키의 홈 버킷(home bucket)이 이미 가득 차 있으면 오버플로(overflow)가 발생합니다. 오버플로는 충돌(collision)과 직결되는 문제로, 이를 어떻게 처리하느냐에 따라 해시 테이블의 전반적인 성능이 크게 달라집니다.
오버플로 처리 방식
오버플로를 처리하는 대표적인 방법은 크게 두 가지로 나눌 수 있습니다.
1. 해시 테이블을 체계적으로 탐색
해시 테이블을 일정한 규칙에 따라 탐색하여 아직 가득 차지 않은 버킷을 찾아 데이터를 저장하는 방식입니다.
- 선형 조사(Linear Probing, 선형 개방 주소법)
- 이차 조사(Quadratic Probing)
- 무작위 조사(Random Probing)
2. 버킷에 리스트 유지
각 버킷이 자신을 홈 버킷으로 하는 모든 데이터 쌍의 목록을 함께 보관하도록 하여 오버플로 자체를 제거하는 방식입니다.
- 배열 선형 리스트(Array Linear List)
- 체인(Chain)
개방 주소법(Open Addressing)
개방 주소법은 모든 요소를 해시 테이블 내부에 직접 저장하는 방식으로, 충돌이 발생했을 때 다양한 기법을 통해 새로운 저장 위치를 찾아 충돌을 해결합니다.
선형 조사(Linear Probing)
선형 조사는 충돌이 발생하면 테이블에서 그다음 빈 슬롯(next open slot)을 찾아 데이터를 배치함으로써 충돌을 해결하는 가장 단순한 기법입니다.
선형 조사의 성능
- 최악의 경우 탐색·삽입·삭제 시간은 θ(m)이며, 여기서 m은 테이블에 저장된 데이터 쌍의 개수입니다.
- 모든 쌍이 하나의 클러스터(cluster)에 몰려 있을 때 이러한 최악의 상황이 발생합니다.
선형 조사의 문제점
- 식별자(identifier)들이 서로 뭉치는 클러스터링 현상이 발생하기 쉽습니다.
- 인접한 클러스터끼리 점점 합쳐지는 경향이 있습니다.
- 그 결과 탐색 시간이 크게 증가합니다.
이차 조사(Quadratic Probing)
선형 조사가 버킷을 (H(x)+i) % b 순서로 순차적으로 검색한다면, 이차 조사는 증분(increment)으로 i의 이차 함수를 사용합니다.
i = 1부터 (b-1)/2까지의 범위에서 다음 버킷들을 순서대로 검사합니다.
H(x), (H(x)+i²) % b, (H(x)-i²) % b
단, b는 반드시 4j+3 형태의 소수여야 하며, 여기서 j는 정수입니다. 이 조건을 만족해야 모든 버킷을 빠짐없이 검사할 수 있습니다.
무작위 조사(Random Probing)
무작위 조사는 난수를 활용하여 다음 검사 위치를 결정하는 기법입니다.
H(x) := (H'(x) + S[i]) % b
- S[i]는 크기가 b-1인 테이블입니다.
- S[i]는 [1, b-1] 범위 정수들의 무작위 순열(random permutation)로 구성됩니다.
마무리
선형 조사는 구현이 간단하지만 클러스터링 문제로 성능 저하가 발생할 수 있으며, 이차 조사와 무작위 조사는 이러한 문제를 완화하기 위해 고안된 기법입니다. 해시 테이블을 설계할 때는 데이터의 특성과 테이블 크기(b)의 조건을 함께 고려하여 적절한 충돌 해결 기법을 선택하는 것이 중요합니다.