"Hàm băm mới" trong băm cuckoo là gì?

Question

Tôi đọc về chim cu băm từ Pagh và Rodle và tôi không thể hiểu được ý nghĩa của đoạn này:.

Nó có thể xảy ra rằng quá trình này lặp, như thể hiện trong hình 1 (b). Do đó, số lần lặp được giới hạn bởi giá trị “MaxLoop” thành được chỉ định trong Phần 2.3. Nếu số lần lặp này đạt được, chúng tôi sẽ khôi phục các khóa trong bảng bằng các hàm băm mới và thử lại một lần nữa để chứa khóa không có khóa. Không cần phải cấp phát các bảng mới để phục hồi: Chúng tôi có thể chỉ cần chạy qua các bảng để xóa và thực hiện quy trình chèn thông thường trên tất cả các phím không được ở vị trí mong muốn trong bảng.

Có nghĩa là gì bởi sử dụng hàm băm mới?
Trong thuật toán chèn, bảng được thay đổi kích thước. Chúng ta phải có một "hồ bơi" của hàm băm để sử dụng bằng cách nào đó? Làm cách nào để tạo hồ bơi này?

Answer 1

Có, họ đang mong đợi hàm băm mới, giống như họ nói. May mắn thay, họ không yêu cầu một đống các thuật toán mới, chỉ có hành vi băm hơi khác nhau trên tập dữ liệu hiện tại của bạn.

Hãy xem phần 2.1 của bài báo và sau đó là Phụ lục A. Nó thảo luận về việc xây dựng ngẫu nhiên universal hash functions.

Ví dụ đơn giản, hy vọng minh họa, là giả sử bạn có một số hàm băm bình thường mà bạn thích, hoạt động trên các khối byte. Chúng tôi sẽ gọi nó là H(x). Bạn muốn sử dụng nó để tạo ra một họ các hàm băm mới, hơi khác nhau H_n(x). Vâng, nếu H(x) là tốt và yêu cầu của bạn yếu, bạn chỉ có thể xác định H_n(x) = H(concat(n,x)). Bạn không có bảo đảm chắc chắn về hành vi của H_n(x), nhưng bạn mong đợi hầu hết chúng sẽ khác nhau.