LCFS 해싱이란?
이 글에서는 LCFS 해싱(Last Come First Serve Hashing)이 무엇인지 살펴보겠습니다. LCFS 해싱은 개방 주소법(open addressing) 전략 중 하나로, 기존의 충돌 해결(collision resolution) 방식을 변경한 기법입니다.
FCFS 방식과의 차이점
개방 주소법 기반 해싱 알고리즘을 분석해 보면, 두 요소가 충돌했을 때 우선순위가 높은 요소가 테이블에 먼저 삽입되고, 나중에 도착한 요소는 다른 위치를 찾아 이동해야 합니다. 즉, 개방 주소법의 해싱은 FCFS(First Come First Serve, 선착순) 방식으로 동작한다고 할 수 있습니다.
반면 LCFS(후착선출, Last Come First Serve) 방식은 정확히 반대로 동작합니다. 새로운 요소를 삽입하면 해당 요소는 위치 x0에 배치됩니다. 만약 그 자리가 이미 요소 y(yj = x0)에 의해 점유되어 있다면, y는 위치 yj+1로 옮겨지며, 이 과정에서 또 다른 요소 z를 밀어내는 등의 재배치가 연쇄적으로 일어날 수 있습니다.
기대 탐색 시간 분석
Poblete와 Munro의 연구에 따르면, 빈 테이블에 n개의 요소를 삽입한 이후의 기대 탐색 시간(expected search time)은 아래 수식으로 상한이 결정됩니다.
$$E[W]=1+\Gamma^{-1}(\alpha n)\lgroup1+\frac{ln\:ln\:\frac{1}{1+\alpha}}{ln\:\Gamma^{-1}(\alpha n)}+O(\frac{1}{ln^{2}\:\Gamma^{2}(\alpha n)})\rgroup$$
여기서 Γ는 감마 함수(Gamma function)를 의미하며, 역함수는 다음과 같이 근사됩니다.
$$\Gamma^{-1}(\alpha n)=\frac{ln\:n}{ln\:ln\:n}\lgroup1+\frac{ln\:ln\:ln\:n}{ln\:ln\:n}+O(\frac{1}{ln\:ln\:n})\rgroup$$
이러한 수학적 분석을 통해 LCFS 해싱은 특정 조건에서 FCFS 방식보다 더 나은 탐색 성능을 보일 수 있음을 확인할 수 있습니다.