로빈후드 해싱(Robin Hood Hashing) 개요
로빈후드 해싱(Robin Hood Hashing)은 개방 주소법(Open Addressing)에 속하는 해싱 기법 중 하나입니다. 이름에서 알 수 있듯이 '부자에게서 빼앗아 가난한 자에게 주는' 로빈후드의 정신처럼, 기존 방식보다 더 공정한 충돌 해결(fair collision resolution) 전략을 사용하여 요소 탐색 시간의 편차를 줄이고 균형을 맞추려고 시도합니다.
삽입 과정의 동작 원리
로빈후드 해싱의 핵심 아이디어는 삽입 과정에서 확인할 수 있습니다. 요소 x를 위치 xi에 삽입하려고 할 때, 이미 다른 요소 y가 해당 위치(yj = xi)를 차지하고 있다면, 두 요소 중 원래 해시 위치에서 더 멀리 떨어져 있는, 즉 더 늦게 들어온 요소가 자리를 양보해야 합니다.
구체적인 동작은 다음과 같습니다.
- 만약 i ≤ j라면, 즉 새로 삽입하려는 요소 x가 기존 요소 y보다 원래 해시 위치에 가깝거나 같다면, x를 다음 위치인 xi+1, xi+2, ... 순서로 이동하며 빈 슬롯을 찾아 삽입을 시도합니다.
- 반대로 i > j라면, 요소 x를 현재 위치 xi에 저장하고, 밀려난 기존 요소 y를 yj+1, yj+2, ... 순서로 재삽입을 시도합니다.
이러한 방식으로 탐색 거리가 긴 요소가 짧은 요소에게 자리를 내주게 되므로, 테이블 전체의 탐색 시간 분포가 고르게 유지됩니다.
최악의 경우 탐색 시간 분석
Devroye 등의 연구에 따르면, 크기가 m = αn(α는 적재율)인 초기에 비어 있는 테이블에 로빈후드 삽입 알고리즘을 사용하여 n번의 삽입을 수행했을 때, 최악의 경우 탐색 시간의 기대값은 다음과 같습니다.
$$E[W]=\Theta(log\:log\:n)$$
여기서 중요한 점은 이 상한(bound)이 타이트(tight)하다는 것입니다. 즉, 실제 성능이 이 점근적 표기와 실질적으로 일치한다는 의미입니다.
결론
로빈후드 해싱은 개방 주소법의 한 형태로, 이중 로그(doubly logarithmic) 수준의 최악의 경우 탐색 시간을 보장합니다. 일반적인 선형 탐사(linear probing)와 비교했을 때 최악의 경우 성능이 크게 개선되므로, 탐색 시간의 안정성이 중요한 응용 분야에서 유용하게 활용될 수 있는 해싱 기법입니다.