이 섹션에서는 Robin-Hood 해싱 방식이 무엇인지 살펴보겠습니다. 이 해싱은 개방형 주소 지정 기술 중 하나입니다. 이것은 더 공정한 충돌 해결 전략을 사용하여 요소의 검색 시간을 균등화하려고 시도합니다. 삽입을 시도하는 동안 위치 xi에 요소 x를 삽입하려는 경우 요소 y가 이미 yj에 배치되어 있습니다. =xi , 그러면 두 요소 중 더 작은 요소가 계속 이동해야 합니다. 따라서 i ≤ j이면 xi+1 위치에 x를 삽입하려고 합니다. , xi+2 등등. 그렇지 않으면 xi 위치에 x를 저장합니다. , 위치 yj+1에 y를 삽입하려고 합니다. , yj+2 등등.
Devroye et al.에 따르면 Robin-Hood 삽입 알고리즘을 사용하여 크기가 𝑚 =Α𝑛인 초기 빈 테이블에 n개의 삽입을 수행한 후 최악의 검색 시간의 예상 값은 -
$$E[W]=\Theta(log\:log\:n)$$
그리고 그 경계는 빡빡합니다. 따라서 이 알고리즘은 이중 로그 최악의 경우 검색 시간을 갖는 개방형 주소 지정의 한 형태입니다.