Về các hàm băm chống va chạm, trong Katz's Introduction to Modern Cryptography,
6.1 Định nghĩa
Các hàm băm chỉ đơn giản là các hàm lấy đầu vào có độ dài nhất định và
nén chúng thành các đầu ra ngắn, có độ dài cố định.Việc sử dụng cổ điển của (không
cryptographic) hàm băm nằm trong cấu trúc dữ liệu, nơi chúng có thể được sử dụng để
xây dựng các bảng băm cho phép thời gian tra cứu O(1) khi lưu trữ một tập hợp các phần tử.
Cụ thể, nếu phạm vi của hàm băm H có kích thước N thì phần tử x
được lưu trữ trong hàng H(x) của một bảng có kích thước N. Để truy xuất x, chỉ cần tính H(x) và thăm dò hàng đó của bảng để tìm các phần tử được lưu trữ ở đó. Một hàm băm tốt cho mục đích này là một hàm tạo ra ít va chạm, trong đó
một xung đột là một cặp phần tử riêng biệt x và x0
mà H(x) = H(x0);
trong trường hợp này chúng ta cũng nói rằng x và x0
va chạm. (Khi xảy ra va chạm, hai
các phần tử cuối cùng được lưu trữ trong cùng một ô, làm tăng thời gian tra cứu.)
Các hàm băm chống va chạm có tinh thần tương tự nhau; một lần nữa, mục tiêu là
để tránh va chạm. Tuy nhiên, có những khác biệt cơ bản. Cho một,
mong muốn giảm thiểu va chạm trong việc thiết lập cấu trúc dữ liệu trở thành một
yêu cầu để tránh xung đột trong cài đặt mật mã. Hơn nữa, trong
ngữ cảnh của cấu trúc dữ liệu, chúng tôi giả sử rằng tập hợp các phần tử được băm
được chọn độc lập với H và không có ý định gây ra va chạm. Trong
bối cảnh của mật mã, ngược lại, chúng ta phải đối mặt với một kẻ thù
có thể chọn các phần tử với mục tiêu rõ ràng là gây ra va chạm. Điều này có nghĩa là
rằng các hàm băm chống va chạm khó thiết kế hơn nhiều.
Về khái niệm băm hoàn hảo, trong Giới thiệu về thuật toán của CLRS:
11.5 Băm hoàn hảo
Chúng tôi gọi một kỹ thuật băm là băm hoàn hảo nếu truy cập bộ nhớ O(1) được yêu cầu để thực hiện tìm kiếm trong trường hợp xấu nhất.
Để tạo sơ đồ băm hoàn hảo, chúng tôi sử dụng hai cấp độ băm, với băm chung ở mỗi cấp độ.
Cấp độ đầu tiên về cơ bản giống như đối với băm với chuỗi: chúng tôi băm n khóa vào m vị trí bằng cách sử dụng hàm băm h được chọn cẩn thận từ một họ
các hàm băm phổ quát.
Tuy nhiên, thay vì tạo một danh sách liên kết các khóa được băm vào vị trí j , chúng tôi sử dụng một bảng băm thứ cấp nhỏ S j với hàm băm liên quan h j . Băng cach chọn
các hàm băm h j cẩn thận, chúng tôi có thể đảm bảo rằng không có va chạm ở cấp trung học.
và trong https://en.wikipedia.org/wiki/Perfect_hash_function
Trong khoa học máy tính, một hàm băm hoàn hảo h cho một tập hợp S là một hàm băm ánh xạ các phần tử riêng biệt trong S thành một tập hợp gồm m số nguyên, không va chạm. Về mặt toán học, nó là một hàm nội tiếp.
Có đúng là trong cuốn sách của Katz, hàm băm chống va chạm có nghĩa chính xác là hàm băm không va chạm không? (Tôi nghĩ vậy.)
Hàm băm hoàn hảo trong Wikipedia có giống với hàm băm chống va chạm trong cuốn sách của Katz không? (Tôi nghĩ vậy.)
Hàm băm hoàn hảo trong cuốn sách của CLRS có giống như hàm băm chống va chạm trong cuốn sách của Katz không? (CLRS định nghĩa hàm băm hoàn hảo về độ phức tạp của truy cập bộ nhớ là O(1) và thực hiện hàm băm hoàn hảo dưới dạng hàm băm chống va chạm, vì vậy tôi nghĩ rằng hàm băm chống va chạm cũng là hàm băm hoàn hảo chức năng, nhưng tôi không chắc liệu hàm băm hoàn hảo có nhất thiết phải chống va chạm hay không.)
Hàm băm hoàn hảo trong cuốn sách của CLRS có giống với hàm băm hoàn hảo trong Wikipedia không?
Cảm ơn.
