[250416] Ideal Hash Tree(HAMT) - 02 - Hash Array Mapped Tries(HAMT) - 작성중

1. 소개
2. 핵심동작
3. HAMT 구현 장점
4. 의사코드

1 소개

지난 시간에는 AMT 의 구조에 대해 알아보았다. 이번 시간에는 HAMT 의 구조에 대해 알아보자. HAMT(Hash Array Mapped Tries)는 AMT(Array Mapped Tries)를 기반으로 한 해시 트리.

이름만 들어도 알 수 있듯이, HAMT 는 해시 테이블을 기반으로 한 트리 구조이다.

주요특징:

해시값 활용 : 키의 해시값을 트리 탐색 경로로 활용. 예) 32비트 해시 값을 5비트씩 나누어 트리의 각 레벨에서 사용(AMT 개념)
트리 구조 : 루트 노드에서 시작해 해시 값의 일부를 사용해 하위 노드로 이동하며, 단말 노드에 키-값 쌍을 저장. (AMT 개념)
충돌 해결: 동일한 해시 값이 발생하면 트리의 깊이를 늘려 추가적인 해시 비트를 사용해 충돌을 처리.

2 핵심동작

2.1 키 삽입

삽입하려는 키의 해시를 계산 (32비트 해시 값)
해시 값을 5비트 단위로 나누어 루트노드부터 트리를 탐색.
탐색 경로에 따라 노드를 찾거나 생성.
단말 노드에 도달하면 키-값 쌍을 저장.
충돌이 발생하면 새 하위 노드를 만들어 추가 해시 비트를 사용해 구분.

예시: 키 "apple"의 해시 값이 10110…이라면, 처음 5비트(10110)로 노드를 선택하고, 다음 5비트로 이동하며 저장 위치를 찾는다.

2.2 키 검색

검색하려는 키의 해시 값을 계산.
해시 값을 5비트씩 나누어 트리를 탐색.
단말 노드에 도달하면 저장된 키와 비교.
일치하면 값을 반환하고, 불일치하면 검색 실패를 반환.

예시: "apple"을 검색할 때, 동일한 해시 값 경로를 따라가 단말 노드에서 "apple"과 일치하는지 확인.

키 검색 시간 복잡도:

기본적으로 O(lgN) 이다. 키가 N개 일 때, 해시 값이 균일하게 분포한다고 가정하면, 평균적으로 lgN 비트가 단말 노드를 고유하게 식별. HAMT는 5비트씩 처리하므로, 트리의 깊이는 약 lg(N/5) 이다. 각 레벨에서 수행하는 연산(비트맵 확인, CTPOP, 포인터 이동)은 상수 시간(O(1))이므로, 전체 검색 비용은:

O(lg(N/5)) = O(lgN - lg5) = O(lgN)

검색 시간 복잡도는 키 삽입과 동일하다.

여기서 시간복잡도를 줄이는 방법은 뭘까?

아래와 같은 방법을 제시한다.

트리 깊이 최소화
루트 테이블 크기 증가 시키기
- HAMT의 루트 노드는 해시 값의 상위 t 비트(논문에서는 일반적으로 5비트, 즉 32개 슬롯)를 사용하여 첫 번째 인덱싱을 수행.
- t를 증가시키면 (예: 10비트로 1024개 슬롯), 루트 노드에서 더 많은 키를 직접 매핑할 수 있어 트리 깊이가 줄어든다.
- 논문의 HAMTC는 루트 테이블을 충분히 크게 설정하여 대부분의 키가 1~2레벨 내에서 단말 노드에 도달하도록 설계한다.
- 예: N = 10^6일 때, 루트 테이블이 1024개 슬롯이면 평균 깊이는 약 lg(10⁶) / 10 ≈ 2로, 실질적으로 상수에 가까움.
해시 함수 품질:
- 균일한 해시 함수는 키를 트리 전반에 고르게 분산시켜 충돌을 최소화.
- 충돌이 적으면 단말 노드에 도달하기까지 필요한 레벨 수가 작아지며, 평균적으로 1~2번의 비트맵 조회로 충분.
캐시 효과 활용
캐시 지역성:
- HAMT의 비트맵과 포인터 배열은 컴팩트한 구조(8바이트 노드)로 설계되어, 단일 캐시 라인에 로드됩니다(32비트) (페이지 5).
  - 32비트 아키텍처에서 비트맵(4바이트)과 포인터(4바이트)가 캐시에 로드되어 두 번째 메모리 액세스 비용이 제거됨. (한번에 조회된다. 합쳐져서.)
- 루트 노드와 상위 레벨 노드가 캐시에 상주하면, 메모리 액세스 비용이 크게 줄어듭니다.
- HAMTC는 빈번히 액세스되는 키가 상위 레벨에 위치하도록 최적화하여 캐시 히트율을 높입니다.
예상 효과:
- 페이지 5: 32비트(8바이트) 아키텍처에서 비트맵(4바이트)과 포인터(4바이트)가 캐시에 로드되어 두 번째 메모리 액세스 비용이 제거됨.
- 이는 실제 연산 시간을 상수 수준으로 유지하는 데 기여.
조기실패
실패케이스 최적화
- 비트맵에서 비트가 0이면 즉시 검색이 종료되므로, 실패(miss) 케이스는 매우 빠르게 처리됨.
- 논문은 "misses are detected early and rarely require a key comparison"이라고 강조하며, 이는 평균 검색 시간을 줄이는 핵심 요소이다.
성공케이스
- 성공(hit) 케이스에서도 키 비교는 단말 노드에서 단 한 번만 수행되므로, 추가 연산이 최소화.
- 페이지 4: "key is only compared once"는 메모리 액세스와 비교 연산의 횟수를 제한하여 상수 시간에 기여.

2.3 키 삭제

삭제하려는 키의 해시 값을 사용해 단말 노드를 찾음.
키-값 쌍을 제거.
필요하면 빈 노드를 정리해 트리 구조를 최적화.

예시: "apple"을 삭제하면 해당 단말 노드에서 데이터를 지우고, 노드가 비면 상위 노드의 비트맵을 업데이트.

3 HAMT 구현 장점

메모리 효율성: 비트맵을 사용해 실제로 데이터가 있는 노드만 저장하므로, 빈 공간을 낭비하지 않습니다.
빠른 탐색: 해시 값을 기반으로 트리를 탐색하므로, 충돌이 적을 경우 평균적으로 상수 시간에 가까운 성능을 제공합니다.
동적 확장: 고정된 크기의 버킷을 미리 할당하지 않고, 필요에 따라 트리를 확장해 메모리를 효율적으로 사용합니다.

4 의사코드

class HAMTNode:
    def __init__(self):
	self.bitmap = 0  # 비트맵으로 노드 존재 여부 표시
	self.children = []  # 하위 노드 또는 키-값 쌍 저장

def insert(hamt, key, value, hash_val, level):
    if level >= 32:  # 해시 값 모두 사용 (단말 노드)
	hamt.children.append((key, value))
	return

    bits = (hash_val >> (level * 5)) & 0x1F  # 5비트 추출
    if not (hamt.bitmap & (1 << bits)):  # 해당 위치에 노드 없음
	hamt.bitmap |= (1 << bits)
	hamt.children.append(HAMTNode())

    child_idx = bin(hamt.bitmap & ((1 << bits) - 1)).count('1')  # CTPOP으로 인덱스 계산
    insert(hamt.children[child_idx], key, value, hash_val, level + 1)

# 사용 예시
root = HAMTNode()
insert(root, "apple", 5, hash("apple"), 0)