Tìm va chạm trong bảng băm

Question

Tôi đã xem xét cho bài kiểm tra cấu trúc dữ liệu cuối cùng của mình và tôi đã xem xét một câu hỏi trong trận chung kết năm ngoái. Đã làm việc trên nó trong ba giờ qua, tôi vẫn không thể tìm ra cách để giải quyết nó, ngoại trừ bằng thử và sai. Dưới đây là những câu hỏi:

"Giả sử rằng kích thước của bảng băm của bạn là 31, g liên tục cũng là 31, và rằng bạn sử dụng mã băm sau

int hash = 0; 
int n = s.length(); 
for (int i = 0; i < n; i++) 
    hash = g * hash + s.charAt(i); 

và rằng bạn sử dụng chain riêng biệt để giải quyết liệt kê năm tên khác nhau sẽ băm vào cùng một vị trí trong bảng. "

Tôi nghĩ rằng phải có một số thủ thuật, có thể liên quan đến toán tử modulo, để giải quyết vấn đề này, xem xét kích thước của bảng băm là 31, tương tự như hằng số g. Xin lỗi nếu tôi có vẻ như nó, nhưng tôi không yêu cầu mã hay bất cứ điều gì, chỉ cần một số suy nghĩ/gợi ý về câu hỏi. Bất kỳ bình luận được đánh giá cao. Cảm ơn

Answer 1

Theo Wikipedia article on Java's string hashing algorithm (mà cũng giống như các thuật toán bạn trình bày):

Như với bất kỳ hàm băm chung, va chạm có thể xảy ra. Đối với ví dụ , các chuỗi "FB" và "Ea" có cùng giá trị băm. Các hashCode() thực hiện chuỗi sử dụng các số nguyên tố 31 và khác biệt giữa 'a' và 'B' chỉ 31 được, vì vậy việc tính toán là 70 × 31 + 66 = 69 × 31 + 97.

Answer 2

chuỗi java có thể chứa một nhân vật không ("\0"), vì vậy tất cả những điều sau đây sẽ băm với giá trị như nhau:

"a" 
"\0a" 
"\0\0a" 
"\0\0\0a" 
"\0\0\0\0a" 

đây là bằng chứng (nhờ Eric cho ref này là băm được sử dụng):

> cat Foo.java 
class Foo { 
    public static void main(String[] args) {          
     System.out.println("a".hashCode());          
     System.out.println("\0a".hashCode());         
     System.out.println("\0a".length()); 
     System.out.println("\0a".equals("a")); 
    }                   
}   
> javac Foo.java           
> java Foo              
97 
97 
2 
false 

tôi nghi ngờ đây là câu trả lời mong đợi.

cũng vậy, nếu đây là bài kiểm tra, tôi nghi ngờ tôi có thể nhớ mã ASCII. do đó, một cách tiếp cận khác để sử dụng chuỗi kiểu trong câu trả lời khác sẽ là:

"\002\000" 
"\001\037" 

v.v ... (đây là ba bát phân - cả hai băm đến 62). nhưng có dễ dàng tạo ra năm ví dụ (tất cả cùng một băm) cho kiểu này không?