해시 배열 트리

컴퓨터 과학에서 해시 배열 트리(, HAT)는 1996년 에드워드 시타르스키(Edward Sitarski)가 발표한 동적 배열 자료 구조이다. 데이터를 하나의 연속된 메모리 영역에 유지하는 단순한 동적 배열과 달리, 해시 배열 트리는 데이터를 저장하기 위해 별도의 메모리 조각(또는 "리프")들의 배열을 유지한다. 이 구조의 주요 목적은 자동 배열 크기 조정 작업으로 인한 요소 복사량을 줄이고 메모리 사용 패턴을 개선하는 것이다.

기하학적 확장에 기반한 단순한 동적 배열은 배열의 요소 수가 n일 때 선형(Ω(n)) 공간을 낭비하지만, 해시 배열 트리는 단지 O() 순서의 저장 공간만을 낭비한다. 알고리즘을 최적화하면 낭비되는 공간이 늘어나는 대신 데이터 복사를 완전히 없앨 수 있다.

단순한 동적 배열보다는 약간 느리지만, 상수 시간(O(1))에 임의 접근을 수행할 수 있다. 해시 배열 트리의 끝에 일련의 객체를 추가할 때 이 알고리즘은 O(1)의 분할 상환 성능을 가진다. 이름과 달리 해시 함수를 사용하지는 않는다.

섬네일|219px|16개의 요소를 가진 가득 찬 해시 배열 트리

 정의 
시타르스키가 정의한 바에 따르면, 해시 배열 트리는 2의 거듭제곱 개수의 리프 배열을 포함하는 최상위 디렉터리를 갖는다. 모든 리프 배열은 최상위 디렉터리와 크기가 같다. 이 구조는 외견상 배열 기반의 충돌 체인을 가진 해시 테이블과 닮았으며, 이것이 해시 배열 트리라는 이름의 기초가 되었다. 가득 찬 해시 배열 트리는 m이 최상위 디렉터리의 크기일 때 m2개의 요소를 담을 수 있다. 2의 거듭제곱을 사용하면 몫과 나머지의 산술 연산 대신 비트 연산을 통해 더 빠른 물리 주소 지정이 가능하며, 확장 시 가끔 발생하는 전체 배열 복사 상황에서도 추가 작업의 O(1) 분할 상환 성능을 보장한다.

 확장 및 크기 축소 
일반적인 동적 배열의 기하학적 확장 방식에서는 배열 전체를 현재 크기의 두 배인 하나의 연속된 메모리 덩어리로 재할당하며, 모든 데이터는 새 위치로 이동한다. 이는 확장된 배열이 새 용량의 절반까지 채워짐에 따라 O(n)의 공간이 낭비되는 대신 O(1) 분할 상환 연산을 보장한다.

해시 배열 트리가 가득 차면, 추가적인 삽입 연산을 수용하기 위해 디렉터리와 리프를 이전 크기의 두 배로 재구조화해야 한다. 이때 기존 구조에 저장된 데이터는 새 위치로 이동된다. 그 후 하나의 새 리프만 할당되어 최상위 배열에 추가되며, 따라서 최상위 배열은 새 용량의 4분의 1만 채워지게 된다. 나머지 여분의 리프들은 아직 할당되지 않고 필요할 때만 할당되므로, 오직 O()의 저장 공간만 낭비하게 된다.

크기를 줄이기 위한 여러 대안이 있다. 해시 배열 트리가 8분의 1만 채워졌을 때, 이를 절반 크기의 더 작은 해시 배열 트리로 재구조화할 수 있다. 또 다른 옵션은 리프의 크기를 조정하지 않고 사용하지 않는 리프 배열만 해제하는 것이다. 추가적인 최적화에는 기하학적 확장을 통해 필요에 따라 디렉터리 배열을 키우면서 크기 조정 없이 새 리프를 추가하는 방법이 포함된다. 이는 낭비되는 공간을 작은 상수를 가진 O(n)으로 만드는 대신 데이터 복사의 필요성을 완전히 제거하며, 설정된 임계값 오버헤드에 도달했을 때만 재구조화를 수행한다.

 관련 자료 구조 

브로드닉(Brodnik) 등은 해시 배열 트리와 유사한 공간 낭비 프로필을 가진 동적 배열 알고리즘을 제시했다. 브로드닉의 구현은 이전에 할당된 리프 배열을 유지하며, 해시 배열 트리에 비해 더 복잡한 주소 계산 함수를 사용한다.

 같이 보기 
 동적 배열
 언롤드 연결 리스트
 B 트리

 각주 

분류:배열