이 섹션에서는 LCFS 해싱이 무엇인지 볼 것입니다. 이것은 충돌 해결 전략을 변경하는 개방형 주소 지정 전략 중 하나입니다. 개방형 주소 체계에서 해싱 알고리즘을 확인하면 두 요소가 충돌하면 우선 순위가 더 높은 요소가 테이블에 삽입되고 후속 요소가 계속 이동해야 함을 알 수 있습니다. 따라서 개방형 주소 지정 방식의 해싱이 FCFS 기준임을 알 수 있습니다.
LCFS(Last Come First Serve) 방식으로. 작업은 정확히 반대 방식으로 수행됩니다. 하나의 요소를 삽입하면 x0 위치에 배치됩니다. . 장소가 이미 요소 y에 의해 점유된 경우 yj =x0 , 그런 다음 yj+1 위치에 y를 배치합니다. , 일부 요소 z 등을 대체할 수 있습니다.
Poblete와 Munro에 따르면 빈 테이블에 n개의 요소를 삽입한 후 예상되는 검색 시간은 다음 공식으로 제한될 수 있습니다.
$$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^{-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$$