정의
동적 완벽 해싱(dynamic perfect hashing)은 해시 테이블 자료구조에서 발생하는 충돌(collision)을 해결하기 위한 프로그래밍 기법입니다. 이 방식은 어떤 경우에도 충돌 없이 상수 시간 내에 데이터에 접근할 수 있도록 보장하는 것이 특징입니다.
활용 분야
동적 완벽 해싱은 다른 해시 테이블 방식에 비해 더 많은 메모리를 소비하지만, 대규모 요소 집합을 대상으로 빠른 조회(query), 삽입(insertion), 삭제(deletion) 연산을 반복적으로 수행해야 하는 상황에서 특히 유용합니다. 따라서 성능이 메모리 사용량보다 중요한 애플리케이션에 적합한 선택지가 됩니다.
구현 방식
Dietzfelbinger 등은 동적 사전(dynamic dictionary) 알고리즘을 제시했습니다. 이 알고리즘에서는 m개의 항목이 사전에 점진적으로 추가되더라도 멤버십 질의(membership query)는 항상 상수 시간, 즉 최악의 경우에도 O(1) 시간에 수행됩니다. 필요한 총 저장 공간은 O(m)으로 선형이며, 삽입과 삭제 역시 평균적으로 상수 시간인 O(1)의 기대 상각 시간(expected amortized time) 안에 처리됩니다.
동적 환경에서 새로운 키가 해시 테이블에 삽입될 때, 해당 키가 매핑되는 2차 하위 테이블(subtable)의 엔트리가 이미 차 있다면 충돌이 발생합니다. 이 경우 해당 하위 테이블은 갱신된 전체 엔트리 수와 무작위로 선택된 새로운 해시 함수를 기반으로 재구축(rebuild)됩니다. 2차 레벨 테이블의 적재율(load factor)을 낮게 유지하기 때문에 재구축 작업은 자주 일어나지 않으며, 그 결과 삽입과 삭제의 상각 기대 비용(amortized expected cost)은 O(1) 수준으로 유지됩니다.
또한 동적 환경에서는 최상위(top-level) 테이블이나 각 하위 테이블의 최종 크기를 사전에 알 수 없습니다. 테이블의 기대 저장 공간을 O(m) 수준으로 유지하는 한 가지 기법은, 충분히 많은 수의 삽입과 삭제가 누적되었을 때 전체 재구축(full rebuild)을 수행하는 것입니다. 마지막 재구축 시점의 요소 수보다 누적된 삽입·삭제 횟수가 더 많아지기 전까지는, 전체 리해싱(full rehashing)을 고려하더라도 삽입과 삭제의 상각 기대 비용은 여전히 O(1)로 유지됩니다.