Chức năng băm hoàn hảo và băm hoàn hảo động - giải thích xin vui lòng?

Question

Vì vậy, tôi đang đọc về các bảng băm, hàm băm, v.v. Tôi rất thích đọc trên wikipedia về cách "băm hoàn hảo động" liên quan đến việc sử dụng bảng băm thứ hai làm cấu trúc dữ liệu để lưu trữ nhiều giá trị trong một nhóm cụ thể.

Tuy nhiên, khi tôi bị lạc, hãy chọn hàm băm chung để thực hiện băm cho bảng băm thứ hai đó. Bất cứ ai có thể giải thích làm thế nào chức năng băm phổ quát này được xác định từ các giá trị được lưu trữ trong xô? Tôi mơ hồ theo lý luận và logic trong trang "hàm băm phổ quát" của wikipedia, nhưng tôi đang đấu tranh để có bất kỳ trực giác nào trên đó. Đặc biệt, làm thế nào để các chức năng này đảm bảo không có xung đột? Hoặc ít nhất, nếu chúng được xử lý và một cái mới được tạo ra nếu một xung đột được phát hiện, làm thế nào để chúng ta biết điều này có thể được thực hiện trong một khoảng thời gian thực tế nếu ở tất cả?

Giải thích sách về Ladybird?

Answer 1

Phương tiện băm hoàn hảo có nghĩa là truy cập đọc mất thời gian không đổi ngay cả trong trường hợp xấu nhất.

Để chèn khóa không có đảm bảo trường hợp xấu nhất, giới hạn thời gian chỉ đúng với mức trung bình (hoặc có thể được khấu hao).

Để chèn nhanh đủ mức, bảng băm thứ hai được chọn rất lớn cho số phím (k), đủ lớn để va chạm trở nên không đủ. Đây không phải là vấn đề với w.r.t. kích thước vì hàm băm cấp đầu tiên phân phối các khóa đồng đều sao cho các bảng băm cấp độ trung bình vẫn còn nhỏ.

Hàm băm cho bảng cấp hai được chọn ngẫu nhiên từ một tập hợp các hàm băm được tham số hóa.

Answer 2

Làm thế nào để xem một số bài giảng của MIT? :)
MIT’s Introduction to Algorithms, Lectures 7 and 8: Hashing