Helpex - Trao đổi & giúp đỡ Đăng nhập
434

Theo tài liệu Java, mã băm cho một Stringđối tượng được tính là:

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

sử dụng intsố học, nơi s[i]tôi ký tự của chuỗi thứ, nlà chiều dài của chuỗi, và ^chỉ lũy thừa.

Tại sao 31 được sử dụng như một số nhân?

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

434 hữu ích 3 bình luận 128k xem chia sẻ
10 trả lời 10
370

Theo Java hiệu quả của Joshua Bloch (một cuốn sách không thể được đề xuất đủ và tôi đã mua nhờ đề cập liên tục về stackoverflow):

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

(từ Chương 3, Mục 9: Luôn ghi đè mã băm khi bạn ghi đè bằng, trang 48)

370 hữu ích 5 bình luận chia sẻ
75

Như Goodrich và Tamassia chỉ ra, Nếu bạn lấy hơn 50.000 từ tiếng Anh (được hình thành dưới dạng liên kế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 va chạm 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 mà tôi đang đề cập ở trên. Xem phần 10.2 Bảng băm (trang 413) của Cấu trúc dữ liệu và thuật toán trong Java

75 hữu ích 3 bình luận chia sẻ
55

Trên (hầu hết) bộ xử lý cũ, nhân với 31 có thể tương đối rẻ. Trên ARM, chẳng hạn, 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ộ xử lý khác sẽ yêu cầu một lệnh dịch chuyển 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. Các bộ xử lý hiện đại có xu hướng nhân số nhanh, do đó, nó không tạo ra nhiều 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 mã 1.0 (và tốt hơn rất nhiều so với thông số 1.0!).

55 hữu ích 5 bình luận chia sẻ
28

Bằng cách nhân, bit được dịch chuyển 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 thứ tự thấp nhất, bên phải cũng được tạo ra, để trộn lẫn với phần dữ liệu tiếp theo đi vào hàm băm.

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

28 hữu ích 0 bình luận chia sẻ
24

Bạn có thể đọc lý luận ban đầu của Bloch trong phần "Nhận xét" trong http://bugs.java.com/orpdatabase/view_orms.do?orms_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í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à anh tìm thấy trong cuốn sách của K & R (nhưng ngay cả Kernighan và Ritchie cũng không thể nhớ nó đến từ đâu). Cuối cùng, anh ấy về cơ bản phải chọn một và vì vậy anh ấy đã P(31)thực hiện vì nó dường như hoạt động đủ tốt. Mặc dù P(33)không thực sự tệ hơn và nhân với 33 cũng nhanh như nhau để tính toán (chỉ cần thay đổi 5 và bổ sung), anh đã chọn 31 vì 33 không phải là số nguyên tố:

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

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

24 hữu ích 1 bình luận chia sẻ
22

Trên thực tế, 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 việc này cực kỳ nhanh.

Trong thực tế, phép nhân với số nguyên tố 73 lớn hơn thậm chí có thể được thực hiện ở cùng tốc độ bằng cách cài đặ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ã dày hơn : Hai lệnh LEA chỉ mất 6 byte so với 7 byte để di chuyển + shift + trừ cho phép nhân với 31. Một cảnh báo có thể xảy ra là các hướng dẫn 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 thêm 3 chu kỳ.

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

22 hữu ích 5 bình luận chia sẻ
18

Neil Coffey giải thích lý do tại sao 31 được sử dụng theo ủi ra sự thiên vị .

Về cơ bản, sử dụng 31 cung cấp cho bạn một phân phối xác suất bit set chẵn hơn cho hàm băm.

18 hữu ích 1 bình luận chia sẻ
7

Từ JDK-4045622 , nơi Joshua Bloch mô tả lý do tại sao String.hashCode()việc triển khai cụ thể (mới) đó được chọn

Bảng dưới đây tóm tắt hiệu suất của các hàm băm khác nhau được mô tả ở trên, cho ba bộ dữ liệu:

1) Tất cả các từ và cụm từ có mục trong Từ điển không rút gọn thứ 2 của Merriam-Webster (311,141 chuỗi, dài 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, avg dài 21 ký tự).

3) Danh sách các URL được thu thập bởi trình thu thập dữ liệu web đã chạy trong vài giờ đêm qua (28.372 chuỗi, dài 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 thành phần trong bảng băm (nghĩa là giá trị dự kiến ​​của số lượng khóa so sánh để tìm kiếm một yếu 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, rõ ràng tất cả các hàm ngoại trừ hàm Java hiện tại và hai phiên bản bị hỏng của hàm Weinberger đều cung cấp hiệu năng tuyệt vời, gần như không thể phân biệt được. 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 thực sự thay cho hàm băm.

Tôi loại trừ chức năng 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ỳ chức năng nào đơn giản hơn nhiều. Bất kỳ chức năng nào trong sáu chức năng còn lại có vẻ như là sự lựa chọn tuyệt vời, nhưng chúng ta phải chọn một chức năng. Tôi cho rằng tôi loại trừ biến thể của Vo và chức năng của Weinberger vì sự phức tạp thêm của chúng, mặc dù là nhỏ. Trong bốn cái còn lại, tôi có thể chọn P (31), vì nó rẻ nhất để tính toán trên máy RISC (vì 31 là sự khác biệt của hai sức mạnh của hai). P (33) tương tự rẻ để tính toán, nhưng hiệu suất của nó kém hơn một chút và 33 là tổng hợp, điều này khiến tôi hơi lo lắng.

Josh

7 hữu ích 0 bình luận chia sẻ
4

Tôi không chắc chắn, nhưng tôi đoán họ đã kiểm tra 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 Chuỗi có thể.

4 hữu ích 0 bình luận chia sẻ
4

Bloch không hoàn toàn đi sâu vào vấn đề này, nhưng lý do mà tôi luôn nghe / tin là đây là đại số cơ bản. Băm nhỏ làm sôi các phép toán 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ố phổ biến nếu bạn có thể giúp nó. Nói cách khác, các số nguyên tố tương đối cung cấp một phân phối đồng đều các câu trả lời.

Các số tạo nên bằng cách sử dụng hàm băm thường là:

  • 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ố lượng xô trong hashtable của bạn (khác nhau. Trong java từng là số nguyên tố, bây giờ là 2 ^ n)
  • nhân hoặc dịch chuyển với một số ma thuật trong chức năng trộn của bạn
  • Giá trị đầu vào

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

4 hữu ích 0 bình luận chia sẻ
loading
Không tìm thấy câu trả lời bạn tìm kiếm? Duyệt qua các câu hỏi được gắn thẻ java string algorithm hash , hoặc hỏi câu hỏi của bạn.

Có thể bạn quan tâm

loading