Định nghĩa
Hàm băm hoàn hảo động được định nghĩa là một phương pháp lập trình để giải quyết các xung đột trong cấu trúc dữ liệu bảng băm.
Ứng dụng
Mặc dù tốn nhiều bộ nhớ hơn so với các đối tác bảng băm của nó, nhưng phương pháp này là lý tưởng cho các trường hợp phải thực hiện các truy vấn, chèn và xóa nhanh trên một tập hợp lớn các phần tử.
Thực hiện
Dietzfelbinger và cộng sự. giải thích từ điển động Thuật toán rằng, khi một tập hợp m mục được thêm dần vào từ điển, các truy vấn thành viên luôn sử dụng thời gian không đổi và do đó O (1) thời gian trong trường hợp xấu nhất, tổng dung lượng cần thiết là O (m) (tuyến tính), và O (1) thời gian chèn và xóa được khấu hao dự kiến (thời gian không đổi được phân bổ). bảng phụ được xây dựng lại dựa trên tổng số mục nhập mới và hàm băm được chọn ngẫu nhiên. Bởi vì hệ số tải của bảng cấp hai vẫn thấp, việc xây dựng lại không thường xuyên và chi phí phụ tùng dự kiến được phân bổ cũng như chi phí xóa dự kiến được phân bổ là O (1).
Ngoài ra, kích thước cuối cùng của bảng cấp cao nhất hoặc bất kỳ bảng phụ nào không được biết trước trong trường hợp động. Một kỹ thuật để duy trì không gian O (m) dự kiến của bảng là nhắc việc xây dựng lại đầy đủ khi đã trải qua đủ số lần chèn và xóa. Miễn là tổng số phần 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í chèn và xóa dự kiến được phân bổ vẫn là O (1) bằng cách xem xét băm lại toàn bộ.