Tính toán Hashcode tại sao nhân và bỏ qua các bit tràn?

Question

Câu hỏi này không phải là lý do tại sao một số nhân, đó là khá rõ ràng - về phân phối của nó.

Why use a prime number in hashCode?

Nhưng thay vì đây là chi tiết về một tài sản của nhân mà trở nên quan trọng hơn các yếu tố khác có trong một công thức tính toán hashcode.

Một phép tính đơn giản rõ ràng có thể tràn nhưng không quan trọng lắm.

a * 31 + b 

Vấn đề thực sự được thể hiện khi có nhiều mục trong công thức.

((a * 31) + b) * 31 ... 6n. 

Khi hơn 5 hoặc 6 cụm từ được bao gồm giá trị của cụm từ đầu tiên bị mất do bit của nó bị tràn bởi thời gian giá trị băm lên đến bao gồm từ 5+. Sử dụng hệ thống này chỉ có 5 thuật ngữ cuối cùng là những người đóng góp đáng kể cho giá trị cuối cùng.

31^7 > Integer.MAX_VALUE 

Vậy tại sao hầu hết các tính toán không thể cuộn các bit tràn ngược lại và xor w/các bit thấp hơn của kết quả. Tôi đánh giá cao điều này đòi hỏi một số fiddling bit và tính toán phải được thực hiện bằng cách sử dụng longs (64 bit) để 32 bit đầu có thể được XOR'd với kết quả số nguyên nhưng ít nhất không có bit sẽ bị mất.

Có bất kỳ lý do cụ thể nào khiến tràn qua bị bỏ qua không? Nó không phải là tốn kém để sử dụng một thời gian dài như mô tả trước đây.

EDIT

100000*31^7=   2751261411100000  0x9C641F717C560 
6553600000*31^7 180306667837849600000 0xC641F717C5600000 

Lưu ý rằng giá trị thứ hai là lớn hơn so với trước đó một cách chính xác 65.536 lần đó cũng có nghĩa là câu trả lời của nó là 16 bit lớn hơn. Lưu ý rằng giá trị số nguyên của 0xC641F717C5600000 là 0xC5600000 giá trị quan trọng thực tế bị mất từ ​​giá trị 16 bit.

*SAMPLE A* 
65536*4096*27512614111 

=7385361114638319616 
=0x667E12CDF0000000 
    12345678 
=0xF0000000 

*SAMPLE B* 
9*65536*4096*27512614111 

=66468250031744876544 
=0x9A6EA93D70000000 
    12345678 
=0x70000000 

Chú ý rằng các bit nhất đầu MẪU B đó là chính xác 9x MẪU Một làm cho gần như tuyệt đối không có sự khác biệt về giá trị 32 bit cuối cùng - nếu tôi thay đổi 9x đến 17 lần sau đó các bit thấp sẽ giống hệt nhau. Tuy nhiên, nếu các bit trên cùng không bị "mất" do tràn và xord với 32 bit thấp hơn thì giá trị sẽ khác nhau.

Answer 1

Có bất kỳ lý do cụ thể nào khiến tràn qua bị bỏ qua không? Nó không phải là tốn kém để sử dụng một thời gian dài như mô tả trước đây.

Nhưng hầu như chắc chắn không có lợi ích từ nó. Phương pháp này thường tạo ra một phân phối tốt các giá trị để bắt đầu.

Answer 2

Đó là lợi ích từ việc nhân với số lẻ; các số trước đó không bao giờ rơi ra khỏi đầu của số nguyên hoàn toàn. Đối với một yếu tố bị mất, 31^n sẽ cần phải là một sức mạnh của 2, và điều đó không thể xảy ra. Trong trường hợp của bạn, ví dụ: với số 31^7, bạn nhận được 0x67E12CDF cho số 32 bit; do đó, yếu tố đầu vào nhân với giá trị đó sẽ vẫn đóng góp vào kết quả, mặc dù tràn.

Answer 3

Tôi không thấy điểm trong ví dụ. Họ dường như, đối với tôi, không liên quan đến cách bạn tính toán mã băm: a * 31 + b.

Bạn có thể, có thể tìm thấy một số a và b, sẽ cung cấp cho cùng một mã băm, (nhưng khi các bit cao khác nhau). Sau đó, nó sẽ có ý nghĩa để xor bit cao trở lại vào hashcode.

Hoặc, một ví dụ khác sẽ là ((a * 31) + b)*31 + ... + z. Sau đó, tìm một số a, b, ..., z, trong đó mã băm không còn phụ thuộc vào a nữa. Vì vậy, a sẽ không phải là một đóng góp đáng kể.

Tất nhiên, nếu bạn thay đổi 31 bởi 65536, thật dễ dàng để tìm thấy những số a, ..., z. Bất kỳ giá trị nào cũng sẽ làm, tất cả a bit sẽ chỉ rơi ra, a được dịch sang trái và cắt. Nhưng, bạn có thể làm như vậy cho 31? Hoặc tương tự, bạn có thể xor các bit cao trở lại. Nhưng, tại sao? Bạn có thể tìm thấy một trường hợp mà nó giúp?

Vấn đề với 65536 là ở dạng nhị phân có dạng như sau: 10000000000000000. Vì vậy, khi bạn nhân một số của nó, trong nhị phân nó sẽ có những 16 số không một lần nữa. Đối với 31, 11111 dưới dạng nhị phân, điều đó sẽ không xảy ra.

Ồ, tôi không có nghĩa là những ví dụ đó không tồn tại, bởi vì chúng thực hiện (nó chỉ là một băm sau tất cả). Nhưng, bạn sẽ không tìm thấy nhiều ví dụ tương tự.