브렌트 방법(Brent's Method)이란? 오픈 어드레싱 해시 테이블 탐색 최적화 기법

브렌트 방법(Brent's Method) 개요

이 글에서는 오픈 어드레싱(open addressing) 해싱과 관련된 브렌트 방법(Brent's Method)에 대해 알아봅니다. 브렌트 방법은 일종의 휴리스틱(heuristic) 기법으로, 해시 테이블에서 성공적인 탐색(successful search)에 걸리는 평균 시간을 최소화하는 것을 목표로 합니다.

이 방법은 원래 더블 해싱(double hashing) 기법에 적용하기 위해 고안되었지만, 선형 조사(linear probing)나 이차 조사(quadratic probing)처럼 다른 오픈 어드레싱 기법에도 동일하게 활용할 수 있습니다.

요소의 '나이(age)'란 무엇인가?

브렌트 방법을 이해하려면 먼저 '나이'라는 개념을 알아야 합니다. 오픈 어드레싱 해시 테이블에 저장된 요소 x의 나이(age)란, x가 실제로 저장된 위치 A[x_i]에 도달하기까지의 최소값 i를 의미합니다. 즉, 해시 함수가 처음 가리킨 위치에서부터 실제 저장 위치까지 얼마나 멀리 이동했는지를 나타내는 지표입니다.

브렌트 방법의 삽입 과정

브렌트 방법은 테이블에 있는 모든 요소의 총 나이(total age)를 최소화하려고 시도합니다. 새로운 요소 x를 삽입할 때는 다음과 같은 단계를 거칩니다.

먼저, A[x_i]가 비어 있는 가장 작은 i 값을 찾습니다. 이 위치는 표준 오픈 어드레싱 방식이라면 x를 삽입했을 자리입니다. 다음으로, A[x_i-2]에 저장되어 있는 어떤 요소 y를 살펴봅니다. 이 요소는 y_j = x_i-2를 만족하는 어떤 j ≥ 0 값 때문에 해당 자리에 저장되어 있던 것입니다. 이때 배열 위치 A[y_j+1]이 비어 있다면, y를 A[y_j+1]로 옮기고, 원래 y가 있던 자리 A[x_i-2]에 x를 저장합니다.

일반 오픈 어드레싱과의 비교

일반적인 오픈 어드레싱 방식과 비교했을 때, 위 과정은 전체 요소의 총 나이를 1만큼 줄여줍니다. 보다 일반적으로 브렌트 방법은 2 ≤ k ≤ i 범위의 각 k에 대해 배열 항목 A[x_i-k]를 검사하고, 그곳에 저장된 요소 y를 A[y_j+1], A[y_j+2], ..., A[y_j+k-1] 중 하나로 이동할 수 있는지 확인하여 x를 위한 자리를 마련합니다.

브렌트 방법의 특징과 활용

브렌트 방법은 삽입 시점에 추가적인 검사와 이동 연산이 필요하다는 비용이 있지만, 그 대신 이미 삽입된 요소들이 더 얕은 위치(더 작은 나이)에 배치됩니다. 그 결과 이후에 수행되는 탐색 속도가 눈에 띄게 빨라집니다. 따라서 데이터 삽입보다 조회가 훨씬 빈번하게 발생하는 응용 환경에서 브렌트 방법은 특히 효과적인 선택이 됩니다.