Tại sao hashCode của Java() trong String sử dụng 31 làm hệ số?

Question

Trong Java, hash code 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^thứ nhân vật của chuỗi, n là chiều dài của chuỗi, và ^ biểu thị lũy thừa.

Tại sao 31 được sử dụng làm hệ số?

Tôi hiểu rằng hệ số phải là số nguyên tố tương đối lớn. Vậy tại sao không 29, hay 37, hay thậm chí 97?

Answer 1

Theo Joshua Bloch Effective Java (một cuốn sách mà không thể được đề nghị đủ, và mà tôi đã mua nhờ liên tục đề cập về stackoverflow):

Giá trị 31 được chọn vì nó là một số nguyên tố lẻ. Nếu nó đã được ngay cả và nhân tràn, thông tin sẽ bị mất, như nhân bằng 2 là tương đương với chuyển dịch. Lợi thế của việc sử dụng một số nguyên tố ít rõ ràng hơn, nhưng nó là truyền thống. Một thuộc tính tốt đẹp của 31 là phép nhân có thể được thay thế bằng phép dịch và phép trừ để có hiệu năng tốt hơn: 31 * i == (i << 5) - i. Các máy ảo hiện đại tự động thực hiện loại tối ưu hóa này.

(từ chương 3, khoản 9: Luôn luôn ghi đè hashcode khi bạn ghi đè lên bằng, trang 48)

Answer 2

Tôi không chắc chắn, nhưng tôi đoán họ đã thử nghiệm một số mẫu số nguyên tố và thấy rằng 31 đã phân phối tốt nhất trên một số mẫu Strings có thể.

Answer 3

Trên (chủ yếu) bộ xử lý cũ, nhân với 31 có thể tương đối rẻ. Trên một ARM, ví dụ, nó chỉ là một hướng dẫn:

RSB  r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5) 

Hầu hết các bộ vi xử lý khác sẽ yêu cầu hướng dẫn thay đổi và trừ riêng biệt. Tuy nhiên, nếu số nhân của bạn chậm thì đây vẫn là một chiến thắng. Bộ vi xử lý hiện đại có xu hướng có nhân nhanh vì vậy nó không tạo ra nhiều sự khác biệt, miễn là 32 đi đúng hướng.

Nó không phải là một thuật toán băm tuyệt vời, nhưng nó đủ tốt và tốt hơn so với mã 1.0 (và rất tốt hơn so với 1.0 spec!).

Answer 4

Như Goodrich and Tamassia điểm ra, Nếu bạn đi qua 50.000 từ tiếng Anh (được hình thành như sự hợp nhất của danh sách từ được cung cấp trong hai biến thể của Unix), sử dụng các hằng số 31, 33, 37, 39 và 41 sẽ tạo ra ít hơn 7 xung đột trong mỗi trường hợp. Biết được điều này, sẽ không có gì ngạc nhiên khi nhiều triển khai Java chọn một trong các hằng số này.

Thật trùng hợp, tôi đang đọc phần "mã băm đa thức" khi tôi thấy câu hỏi này.

EDIT: đây là liên kết đến cuốn sách PDF ~ 10mb tôi đang đề cập ở trên. Xem phần 10.2 Bảng băm (trang 413) của Data Structures and Algorithms in Java

Answer 5

Bằng cách nhân, bit được dịch sang trái. Điều này sử dụng nhiều không gian có sẵn của mã băm, giảm va chạm.

Bằng cách không sử dụng sức mạnh của hai, các bit dưới cùng bên phải, cũng được điền, để được trộn lẫn với phần dữ liệu tiếp theo đi vào băm.

Biểu thức n * 31 tương đương với (n << 5) - n.

Answer 6

Bloch không hoàn toàn đi vào điều này, nhưng lý do tôi đã luôn luôn nghe/tin rằng đây là đại số cơ bản. Phát ban sôi xuống hoạt động nhân và mô đun, có nghĩa là bạn không bao giờ muốn sử dụng các số có các yếu tố chung nếu bạn có thể trợ giúp nó. Nói cách khác, các số nguyên tố tương đối cung cấp phân phối câu trả lời đồng đều.

Những con số tạo nên sử dụng một băm thường:

• mô đun của loại dữ liệu bạn đặt nó vào (2^32 hoặc 2^64)
• mô đun của số xô tại của bạn Hashtable (thay đổi. trong java từng là đắc địa, hiện giờ là 2^n)
• nhân hoặc thay đổi bởi một con số kỳ diệu trong chức năng trộn của bạn
• giá trị đầu vào

Bạn thực sự chỉ nhận được để kiểm soát một vài trong số các giá trị này, do đó, một chút chăm sóc thêm là do.

Answer 7

Thực ra, 37 sẽ hoạt động khá tốt! z: = 37 * x có thể được tính là y := x + 8 * x; z := x + 4 * y. Cả hai bước tương ứng với một hướng dẫn LEA x86, vì vậy điều này cực kỳ nhanh.

Thực tế, phép nhân với số nguyên lớn hơn có thể được thực hiện ở cùng tốc độ bằng cách đặt y := x + 8 * x; z := x + 8 * y.

Sử dụng 73 hoặc 37 (thay vì 31) có thể tốt hơn, vì nó dẫn đến mã đặc biệt: Hai hướng dẫn LEA chỉ mất 6 byte so với 7 byte để di chuyển + shift + trừ cho phép nhân 31 Một điều có thể xảy ra là các lệnh LEA 3-đối số được sử dụng ở đây trở nên chậm hơn trên kiến ​​trúc cầu Sandy của Intel, với độ trễ tăng lên 3 chu kỳ.

Hơn nữa, 73 là số yêu thích của Sheldon Cooper.

Answer 8

Neil Coffey explains lý do tại sao 31 được sử dụng dưới Ủi sai lệch.

Về cơ bản, sử dụng 31 cung cấp cho bạn khả năng phân phối xác suất bit thiết lập thậm chí nhiều hơn cho hàm băm.

Answer 9

Bạn có thể đọc lý do ban đầu của Bloch trong "Nhận xét" trong http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622. Ông đã nghiên cứu hiệu suất của các hàm băm khác nhau liên quan đến kết quả "kích thước chuỗi trung bình" trong bảng băm. P(31) là một trong những chức năng phổ biến trong thời gian đó mà ông tìm thấy trong cuốn sách của K & R (nhưng ngay cả Kernighan và Ritchie không thể nhớ nó xuất phát từ đâu). Cuối cùng, ông về cơ bản đã phải chọn một và vì vậy ông đã P(31) vì nó dường như thực hiện đủ tốt.Mặc dù P(33) là không thực sự tồi tệ hơn và nhân 33 cũng không kém phần nhanh để tính toán (chỉ cần một sự thay đổi bởi 5 và một sự bổ sung), ông đã lựa chọn 31 từ năm 33 không phải là một số nguyên tố:

Trong số còn lại bốn, Tôi có lẽ sẽ chọn P (31), vì nó là rẻ nhất để tính toán trên một máy RISC (vì 31 là sự khác biệt của hai cường độ của hai). P (33) là tương tự với giá rẻ để tính toán, nhưng hiệu suất của nó là nhẹ hơn, và 33 là hỗn hợp, khiến tôi hơi lo lắng.

Vì vậy, lý do không hợp lý vì nhiều câu trả lời ở đây dường như ngụ ý. Nhưng tất cả chúng ta đều tốt trong việc đưa ra những lý do hợp lý sau khi quyết định ruột (và thậm chí cả Bloch có thể dễ bị như vậy).

Answer 10

Từ JDK-4045622, nơi Joshua Bloch mô tả những lý do tại sao điều đó đặc biệt (mới) String.hashCode() thực hiện được chọn

Bảng dưới đây tóm tắt các hoạt động của các hash khác nhau chức năng mô tả ở trên, đối với ba bộ dữ liệu:

1) Tất cả các từ và cụm từ có các mục nhập trong sốTừ điển thứ hai không được lược tả của Merriam-Webster (311,141 chuỗi, độ dài trung bình 10 ký tự).

2) Tất cả các chuỗi trong/bin/,/usr/bin/,/usr/lib/,/usr/UCB/ và/usr/openwin/bin/* (66.304 chuỗi, độ dài trung bình 21 ký tự).

3) Danh sách URL được thu thập bởi trình thu thập dữ liệu web chạy trong một số giờ đêm qua (28,372 chuỗi, chiều dài trung bình 49 ký tự).

Chỉ số hiệu suất được hiển thị trong bảng là "kích thước chuỗi trung bình" trên tất cả các phần tử trong bảng băm (tức là giá trị mong đợi của số so sánh chính để tìm kiếm phần tử).

      Webster's Code Strings URLs 
          --------- ------------ ---- 
Current Java Fn.   1.2509  1.2738   13.2560 
P(37) [Java]   1.2508  1.2481   1.2454 
P(65599) [Aho et al]  1.2490  1.2510   1.2450 
P(31) [K+R]   1.2500  1.2488   1.2425 
P(33) [Torek]   1.2500  1.2500   1.2453 
Vo's Fn     1.2487  1.2471   1.2462 
WAIS Fn     1.2497  1.2519   1.2452 
Weinberger's Fn(MatPak) 6.5169  7.2142   30.6864 
Weinberger's Fn(24)  1.3222  1.2791   1.9732 
Weinberger's Fn(28)  1.2530  1.2506   1.2439 

Nhìn vào bảng này, thì rõ ràng rằng tất cả các chức năng trừ chức năng Java hiện tại và hai phiên bản vỡ của chức năng phục vụ Weinberger của tuyệt vời, hiệu suất gần như không thể phân biệt. I phỏng đoán mạnh mẽ rằng hiệu suất này về cơ bản là "lý tưởng lý thuyết" , đó là những gì bạn sẽ nhận được nếu bạn sử dụng một trình tạo số ngẫu nhiên đúng thay cho hàm băm.

Tôi muốn loại bỏ hàm WAIS vì đặc điểm kỹ thuật của nó chứa các trang có số ngẫu nhiên và hiệu suất của nó không tốt hơn bất kỳ hàm nào đơn giản hơn nhiều so với bất kỳ hàm nào trong số . Bất kỳ hàm nào trong số sáu hàm còn lại có vẻ như là các lựa chọn tuyệt vời, nhưng chúng ta phải chọn một. Tôi cho rằng tôi sẽ loại trừ biến thể của Vo và chức năng của Weinberger vì chúng phức tạp hơn phức tạp, mặc dù nhỏ. Trong bốn chiếc còn lại, tôi có thể chọn P (31), vì nó rẻ nhất để tính toán trên một máy RISC (vì 31 là sự khác biệt của hai cường độ của hai). P (33) là tương tự rẻ để tính toán, nhưng hiệu suất của nó là nhẹ tồi tệ hơn, và 33 là composite, mà làm cho tôi một chút lo lắng.

Josh