Định nghĩa
Băm hoàn hảo động (Dynamic perfect hashing) được định nghĩa là phương pháp lập trình để giải quyết va chạm (collisions) trong cấu trúc dữ liệu bảng băm (hash table).
Ứng dụng
Mặc dù tốn bộ nhớ hơn các đối ứng bảng băm, phương pháp này lý tưởng cho tình huống cần truy vấn nhanh (fast queries), chèn và xóa trên tập hợp lớn phần tử.
Cài đặt
Dietzfelbinger et al. mô tả thuật toán từ điển động (dynamic dictionary Algorithm) mà khi tập m mục được thêm dần vào từ điển, truy vấn thành viên luôn tốn thời gian hằng số do đó O(1) trường hợp xấu nhất, tổng bộ nhớ cần O(m) (tuyến tính), và chèn/xóa kỳ vọng khấu hao O(1) (amortized constant time). Trong trường hợp động, khi khóa được chèn vào bảng băm, nếu mục trong bảng con tương ứng bị chiếm, va chạm xảy ra và bảng con được xây dựng lại dựa trên tổng số mục mới và hàm băm ngẫu nhiên. Vì tải yếu tố (load factor) của bảng cấp hai được giữ thấp, việc xây dựng lại không thường xuyên, và chi phí kỳ vọng khấu hao của chèn cũng như xóa là O(1).
Thêm vào đó, kích thước cuối cùng của bảng cấp cao nhất hoặc bất kỳ bảng con nào không có kiến thức trước trong trường hợp động. Một kỹ thuật duy trì O(m) không gian kỳ vọng của bảng là kích hoạt xây dựng lại hoàn toàn (full rebuilding) khi đủ số chèn và xóa đã xảy ra. Miễn là tổng số chèn hoặc xóa vượt quá số phần tử tại thời điểm xây dựng cuối cùng, chi phí kỳ vọng khấu hao của chèn và xóa vẫn O(1) bằng cách xem xét rehashing toàn bộ.