이 섹션에서는 개방 주소 해싱과 관련된 Brent의 방법이 무엇인지 볼 것입니다. 이 방법은 휴리스틱입니다. 이것은 해시 테이블에서 성공적인 검색을 위한 평균 시간을 최소화하려고 시도합니다.
이 방법은 원래 이중 해싱 기술에 적용되었지만 선형 및 2차 프로빙과 같은 모든 개방형 주소 지정 기술에 사용할 수 있습니다. 요소 x의 나이는 공개 주소 지정 해시 테이블에 저장되며, x가 A[xi에 배치되도록 최소값 i입니다. ]
Brent의 방법은 모든 요소의 총 수명을 최소화하려고 합니다. 요소 x를 삽입하면 몇 가지 단계를 따릅니다. - A[xi가 되도록 i의 가장 작은 값을 찾습니다. ]가 비어 있는 경우 표준 개방 주소 지정이 x를 삽입하는 위치입니다. 이제 A[xi-2에 저장된 하나의 요소 y를 고려하십시오. ]. 이 요소는 yj =xi-2이기 때문에 거기에 저장됩니다. , j ≥ 0의 일부 값에 대해 배열 위치 A[yj+1 ]가 비어 있으면 y를 위치 A[yj+1로 이동합니다. ] 및 위치 A[xi-2에 x를 저장합니다. ].
일반 개방형 주소 지정에 비해 총 수명이 1 감소합니다. 일반적으로 Brent의 방법은 2 ≤ k ≤ i 각각에 대해 검사합니다. 배열 항목 A[xi-k ] 확인하려면 요소 y가 저장되어 있으면 A[yj+1 중 하나로 이동할 수 있습니다. ], A[yj+2 ], . . ., A[yj+k-1 ], x를 위한 공간을 확보합니다.