정의
동적 완전 해싱은 해시 테이블 데이터 구조에서 충돌을 해결하기 위한 프로그래밍 방법으로 정의됩니다.
응용 프로그램
해시 테이블에 비해 메모리 집약적이지만 이 방법은 많은 요소 집합에서 빠른 쿼리, 삽입 및 삭제를 수행해야 하는 상황에 이상적입니다.
구현
Dietzfelbinger et al. 동적 사전 알고리즘을 설명하십시오. m개의 항목 집합이 사전에 증분적으로 추가될 때 구성원 쿼리는 항상 일정한 시간을 소비하므로 O(1) 최악의 경우 시간이 필요하며 필요한 총 스토리지는 O(m)(선형), 그리고 O(1) 예상 상각 삽입 및 삭제 시간(상각 상각 시간) 하위 테이블은 새로운 총 항목 수와 무작위로 선택된 해시 함수를 기반으로 다시 작성됩니다. 두 번째 수준 테이블의 부하율이 낮게 유지되기 때문에 재구축이 자주 발생하지 않으며 상각 예상 삽입 비용과 상각 예상 삭제 비용이 O(1)입니다.
또한 최상위 테이블 또는 하위 테이블의 궁극적인 크기는 동적 경우에 대한 사전 지식이 없습니다. 테이블의 예상 O(m) 공간을 유지하는 한 가지 기술은 충분한 수의 삽입 및 삭제가 발생했을 때 전체 재구축을 프롬프트하는 것입니다. 삽입 또는 삭제의 총 수가 마지막 구성 시점의 요소 수를 초과하는 한 전체 재해싱을 고려하면 삽입 및 삭제의 상각 예상 예상 비용은 O(1)로 유지됩니다.