Bằng chứng: tại sao việc triển khai java.lang.String.hashCode() khớp với tài liệu của nó?

Question

Các tài liệu JDK cho java.lang.String.hashCode()famously nói:

Mã băm cho một đối tượng String được tính như

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

sử dụng int số học, nơi s[i] là * i * nhân vật của chuỗi thứ, n là độ dài của chuỗi và ^ biểu thị lũy thừa.

Việc thực hiện tiêu chuẩn của biểu thức này là:

int hash = 0; 
for (int i = 0; i < length; i++) 
{ 
    hash = 31*hash + value[i]; 
} 
return hash; 

Nhìn vào này làm cho tôi cảm thấy như tôi đang ngủ qua khóa học các thuật toán của tôi. Biểu thức toán học chuyển thành mã ở trên như thế nào?

Answer 1

Tôi không chắc liệu bạn có bỏ lỡ vị trí "^ cho biết lũy thừa" (không phải xor) trong tài liệu đó hay không.

Mỗi lần qua vòng lặp, giá trị băm trước đó được nhân với 31 lần nữa trước khi được thêm vào phần tử tiếp theo là value.

Người ta có thể chứng minh những điều này đều bình đẳng bằng cảm ứng, nhưng tôi nghĩ một ví dụ có thể là hơn rõ ràng:

Nói rằng chúng tôi đang làm việc với một chuỗi 4 char.Hãy cuộn vòng lặp:

hash = 0; 
hash = 31 * hash + value[0]; 
hash = 31 * hash + value[1]; 
hash = 31 * hash + value[2]; 
hash = 31 * hash + value[3]; 

Bây giờ kết hợp các thành một tuyên bố bằng cách thay thế mỗi giá trị của băm vào tuyên bố sau:

hash = 31 * (31 * (31 * (31 * 0 + value[0]) + value[1]) + value[2]) 
    + value[3]; 

31 * 0 là 0, vì vậy đơn giản hóa:

hash = 31 * (31 * (31 * value[0] + value[1]) + value[2]) 
    + value[3]; 

Bây giờ nhân hai từ bên trong với số thứ hai 31:

hash = 31 * (31 * 31 * value[0] + 31 * value[1] + value[2]) 
    + value[3]; 

Bây giờ nhân ba thuật ngữ bên trong bằng cách đó đầu tiên 31:

hash = 31 * 31 * 31 * value[0] + 31 * 31 * value[1] + 31 * value[2] 
    + value[3]; 

và chuyển đổi sang số mũ (không thực sự Java nữa):

hash = 31^3 * value[0] + 31^2 * value[1] + 31^1 * value[2] + value[3]; 

Answer 2

bỏ vòng lặp. Sau đó, bạn nhận được:

int hash = 0; 

hash = 31*hash + value[0]; 
hash = 31*hash + value[1]; 
hash = 31*hash + value[2]; 
hash = 31*hash + value[3]; 
... 
return hash; 

Bây giờ bạn có thể làm một số thao tác toán học, cắm 0 cho giá trị băm ban đầu:

hash = 31*(31*(31*(31*0 + value[0]) + value[1]) + value[2]) + value[3])... 

Đơn giản hóa nó một số chi tiết:

hash = 31^3*value[0] + 31^2*value[1] + 31^1*value[2] + 31^0*value[3]... 

Và đó là lý về cơ bản các thuật toán ban đầu được đưa ra.

Answer 3

Hãy xem vài lần lặp đầu tiên và bạn sẽ thấy khi bắt đầu mô hình xuất hiện:

 
hash0 = 0 + s0 = s0 
hash1 = 31(hash0) + s1 = 31(s0) + s1 
hash2 = 31(hash1) + s2 = 31(31(s0) + s1) + s2 = 312(s0) + 31(s1) + s2 
... 

Answer 4

Proof bằng cảm ứng:

T1(s) = 0 if |s| == 0, else s[|s|-1] + 31*T(s[0..|s|-1]) 
T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 
P(n) = for all strings s s.t. |s| = n, T1(s) = T2(s) 

Let s be an arbitrary string, and n=|s| 
Base case: n = 0 
    0 (additive identity, T2(s)) = 0 (T1(s)) 
    P(0) 
Suppose n > 0 
    T1(s) = s[n-1] + 31*T1(s[0:n-1]) 
    T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] = s[n-1] + 31*(s[0]*31^(n-2) + s[1]*31^(n-3) + ... + s[n-2]) = s[n-1] + 31*T2(s[0:n-1]) 
    By the induction hypothesis, (P(n-1)), T1(s[0:n-1]) = T2(s[0:n-1]) so 
     s[n-1] + 31*T1(s[0..n-1]) = s[n-1] + T2(s[0:n-1]) 
    P(n) 

Tôi nghĩ rằng tôi có nó, và một bằng chứng đã được yêu cầu.

Answer 5

Không phải là nó vô dụng ở tất cả để đếm hashcode của chuỗi ra của tất cả các ký tự? Hãy tưởng tượng tên tập tin hoặc tên lớp với đường dẫn đầy đủ của chúng được đưa vào HashSet. Hoặc ai đó sử dụng HashSets của tài liệu Chuỗi thay vì Danh sách vì "HashSet always beats Lists".

tôi sẽ làm một cái gì đó như:

int off = offset; 
char val[] = value; 
int len = count; 

int step = len <= 10 ? 1 : len/10; 

for (int i = 0; i < len; i+=step) { 
    h = 31*h + val[off+i]; 
} 
hash = h 

Tại hashcode cuối cùng là gì khác hơn là một gợi ý.