được ký bằng băm hoàn hảo gần như hoàn hảo

Question

Tôi có một loại số nguyên, nói long, có giá trị nằm giữa Long.MIN_VALUE = 0x80...0 (-2^63) và Long.MAX_VALUE = 0x7f...f (2^63 - 1). Tôi muốn băm nó với sự va chạm ~ 50% với một số nguyên dương cùng loại (tức là giữa 1 và Long.MAX_VALUE) một cách sạch sẽ và hiệu quả.

nỗ lực đầu tiên của tôi là một cái gì đó như:

• Math.abs(x) + 1
• (x & Long.MAX_VALUE) + 1

nhưng những người và tương tự như phương pháp luôn luôn có vấn đề với các giá trị nhất định, ví dụ: khi x là 0/Long.MIN_VALUE/Long.MAX_VALUE. Tất nhiên, giải pháp ngây thơ là sử dụng 2 nếu câu lệnh, nhưng tôi đang tìm kiếm một cái gì đó sạch hơn/ngắn hơn/nhanh hơn. Bất kỳ ý tưởng?

Lưu ý: Giả sử rằng tôi đang làm việc trong Java, nơi không có chuyển đổi tiềm ẩn thành ngữ nghĩa boolean và thay đổi được xác định.

Answer 1

Chỉ để chắc chắn, bạn có một thời gian dài và muốn băm nó vào một int?

Bạn có thể làm ...

(int) x     // This results in a meaningless number, but it works 
(int) (x & 0xffffffffl) // This will give you just the low order bits 
(int) (x >> 32)   // This will give you just the high order bits 
((Long) x).hashcode() // This is the high and low order bits XORed together 

Nếu bạn muốn giữ lại một chặng đường dài bạn có thể làm ...

x & 0x7fffffffffffffffl // This will just ignore the sign, Long.MIN_VALUE -> 0 
x & Long.MAX_VALUE  // Should be the same I think 

Nếu nhận được một 0 là không tốt ...

x & 0x7ffffffffffffffel + 1 // This has a 75% collision rate. 

Chỉ cần suy nghĩ to ...

((x & Long.MAX_VALUE) << 1) + 1 // I think this is also 75% 

Tôi nghĩ rằng bạn sẽ cần phải thể là ok với 75% hoặc nhận được một chút xấu xí:

(x > 0) ? x : (x < 0) ? x & Long.MAX_VALUE : 7 

Answer 2

Giả sử bạn muốn sụp đổ tất cả các giá trị vào không gian tích cực, tại sao không chỉ số không dấu bit?

Bạn có thể thực hiện việc này bằng cách sử dụng một bit bit duy nhất bằng cách tận dụng thực tế là MAX_VALUE chỉ là bit dấu 0, theo sau là

int positive = value & Integer.MAX_VALUE; 

Hoặc cho chờ đợi:

long positive = value & Long.MAX_VALUE; 

Nếu bạn muốn có một "tốt hơn" băm với chất lượng giả ngẫu nhiên, có thể bạn muốn PSS giá trị thông qua một hàm băm đầu tiên. Băm nhanh yêu thích của tôi là gia đình XORshift của George Marsaglia. Chúng có thuộc tính tốt đẹp mà chúng ánh xạ toàn bộ không gian int/long hoàn toàn vào chính nó, vì vậy bạn sẽ vẫn nhận được chính xác 50% va chạm sau khi zeroing bit dấu.

Dưới đây là một việc thực hiện XORshift nhanh chóng trong Java:

public static final long xorShift64(long a) { 
    a ^= (a << 21); 
    a ^= (a >>> 35); 
    a ^= (a << 4); 
    return a; 
} 

public static final int xorShift32(int a) { 
    a ^= (a << 13); 
    a ^= (a >>> 17); 
    a ^= (a << 5); 
    return a; 
} 

Answer 3

Phương pháp đơn giản nhất là zero bit dấu và sau đó bản đồ số không đến một số giá trị khác:

Long y = x & Long.MAX_VALUE; 
return (y == 0)? 42: y; 

này rất đơn giản, chỉ sử dụng một nếu/ternary điều hành, và cho tỷ lệ va chạm ~ 50% trung bình. Có một bất lợi: nó ánh xạ 4 giá trị khác nhau (0, 42, MIN_VALUE, MIN_VALUE + 42) đến một giá trị (42). Vì vậy, đối với giá trị này, chúng tôi có 75% va chạm, trong khi đối với các giá trị khác - chính xác là 50%.

Nó có thể thích hợp hơn để phân phối va chạm đồng đều hơn:

return (x == 0)? 42: (x == Long.MIN_VALUE) ? 142: x & Long.MAX_VALUE; 

Mã này cung cấp cho 67% va chạm với 2 giá trị và 50% đối với các giá trị khác. Bạn không thể phân phối xung đột đồng đều hơn, nhưng có thể chọn 2 giá trị va chạm lớn nhất này. Nhược điểm là mã này sử dụng hai toán tử ifs/ternary.

Có thể tránh 75% va chạm trên giá trị duy nhất trong khi chỉ sử dụng một nếu/nhà điều hành ternary:

Long y = x & Long.MAX_VALUE; 
return (y == 0)? 42 - (x >> 7): y; 

Mã này cung cấp cho 67% va chạm với 2 giá trị và 50% va chạm cho các giá trị khác. Có ít tự do lựa chọn những giá trị va chạm lớn nhất: 0 bản đồ đến 42 (và bạn có thể chọn hầu như bất kỳ giá trị nào thay thế); MIN_VALUE bản đồ đến 42 - (MIN_VALUE >> 7) (và bạn có thể dịch chuyển MIN_VALUE theo bất kỳ giá trị nào từ 1 đến 63, chỉ đảm bảo rằng A - (MIN_VALUE >> B) không tràn).

---

Có thể để có được kết quả tương tự (67% va chạm với 2 giá trị và 50% va chạm cho các giá trị khác) mà không khai thác có điều kiện (nhưng với mã phức tạp hơn):

Long y = x - 1 - ((x >> 63) << 1); 
Long z = y + 1 + (y >> 63); 
return z & Long.MAX_VALUE; 

Điều này cho phép 67% va chạm cho các giá trị '1' và 'MAX_VALUE'. Nếu thuận tiện hơn để có được hầu hết các va chạm đối với một số giá trị khác, chỉ cần áp dụng thuật toán này cho x + A, trong đó 'A' là bất kỳ số nào.

Một biến thể cải tiến của giải pháp này:

Long y = x + 1 + ((x >> 63) << 1); 
Long z = y - (y >> 63); 
return z & Long.MAX_VALUE; 

Answer 4

Từ giao diện thông tin lý thuyết, bạn có 2^64 giá trị để ánh xạ vào 2^63-1 giá trị.

Như vậy, lập bản đồ là tầm thường với các nhà điều hành mô đun, vì nó luôn luôn có một kết quả không âm:

y = 1 + x % 0x7fffffffffffffff; // the constant is 2^63-1 

Điều này có thể khá đắt tiền, vì vậy những gì khác là có thể?

Toán đơn giản 2^64 = 2 * (2^63 - 1) + 2 cho biết chúng ta sẽ có hai ánh xạ giá trị nguồn cho một giá trị đích ngoại trừ trong hai trường hợp đặc biệt, trong đó ba trường hợp sẽ chuyển sang một giá trị. Hãy coi đây là hai giá trị 64 bit đặc biệt, gọi chúng là x1 và x2, mỗi giá trị đó chia sẻ mục tiêu với hai giá trị nguồn khác. Trong biểu thức mod ở trên, điều này xảy ra bằng cách "gói". Giá trị mục tiêu y=2^31-2 và y=2^31-3 có ba ánh xạ. Tất cả những người khác có hai.Vì chúng ta phải sử dụng một cái gì đó phức tạp hơn so với mod, hãy tìm cách để ánh xạ các giá trị đặc biệt ở bất kỳ nơi nào chúng ta muốn với chi phí thấp. 7] đến y ở [1..7], thay vì không gian 64 bit.

Một khóa học dễ dàng là có các giá trị x trong [1..7] bản đồ cho chính chúng, sau đó sự cố giảm để ánh xạ x trong [-8..0] đến y trong [1..7]. Lưu ý có 9 giá trị nguồn ở đây và chỉ có 7 mục tiêu như được thảo luận ở trên.

Có nhiều chiến lược rõ ràng. Tại thời điểm này, bạn có thể thấy gazzilion. Tôi sẽ mô tả chỉ một điều đặc biệt đơn giản.

Hãy để y = 1 - x cho tất cả các giá trị ngoại trừ trường hợp đặc biệt x1 == -8 và x2 == -7. Các chức năng toàn bộ băm do đó trở thành

y = x <= -7 ? S(x) : x <= 0 ? 1 - x : x; 

Đây S(x) là một chức năng đơn giản mà nói nơi x1 và x2 được ánh xạ. Chọn S dựa trên những gì bạn biết về dữ liệu. Ví dụ: nếu bạn cho rằng giá trị mục tiêu cao không có khả năng, hãy ánh xạ chúng thành 6 và 7 với S(x) = -1 - x.

Việc lập bản đồ cuối cùng là:

-8: 7 -7: 6 -6: 7 -5: 6 -4: 5 -3: 4 -2: 3 -1: 2 
0: 1  1: 1  2: 2  3: 3  4: 4  5: 5  6: 6  7: 7 

Lấy logic này lên đến khoảng 64-bit, bạn phải

y = (x <= Long.MIN_VALUE + 1) ? -1 - x : x <= 0 ? 1 - x : x; 

Nhiều loại khác điều chỉnh có thể xảy ra trong khuôn khổ này.

Answer 5

tôi sẽ lựa chọn đơn giản nhất, nhưng không hoàn toàn thời gian phiên bản lãng phí:

public static long postiveHash(final long hash) { 
    final long result = hash & Long.MAX_VALUE; 
    return (result != 0) ? result : (hash == 0 ? 1 : 2); 
} 

thi này trả tiền một hoạt động có điều kiện cho tất cả nhưng hai đầu vào càng tốt: 0 và MIN_VALUE. Hai giá trị này được gán ánh xạ giá trị khác nhau với điều kiện thứ hai. Tôi nghi ngờ bạn sẽ có một sự kết hợp tốt hơn (mã) đơn giản và phức tạp (tính toán).

Tất nhiên, nếu bạn có thể sống với bản phân phối tồi tệ hơn, nó được đơn giản hơn nhiều. Bằng cách hạn chế không gian để 1/4 thay vì tới 1/2 -1 bạn có thể nhận được:

public static long badDistribution(final long hash) { 
    return (hash & -4) + 1; 
} 

Answer 6

Nếu giá trị là tích cực, nó có thể có thể được sử dụng trực tiếp, nếu không, đảo ngược tất cả các bit:

x >= 0 ? hash = x : hash = x^Long.MIN_VALUE 

Tuy nhiên, bạn nên tranh giành giá trị này hơn một chút nếu các giá trị của x có tương quan (có nghĩa là: đối tượng tương tự sản xuất giá trị tương tự cho x), có lẽ với

hash = a * (hash + b) % (Long.MAX_VALUE) + 1 

cho một số hằng số dương a và b, trong đó a phải khá lớn và b ngăn không cho rằng 0 luôn được ánh xạ tới 1. Điều này cũng ánh xạ toàn bộ nội dung tới [1, Long.MAX_VALUE] thay vì [0, Long.MAX_VALUE].Bằng cách thay đổi các giá trị cho a và b, bạn cũng có thể triển khai các hàm băm phức tạp hơn như cooko hashing, cần hai hàm băm khác nhau.

Giải pháp như vậy chắc chắn nên được ưu tiên thay vì giải pháp mang lại "phân bố va chạm lạ" cho cùng một giá trị mỗi lần sử dụng.

Answer 7

Bạn có thể làm điều đó mà không cần bất kỳ điều kiện và trong một biểu thức duy nhất bằng cách sử dụng toán tử chuyển đổi unsigned:

public static int makePositive(int x) { 
    return (x >>> 1) + (~x >>> 31); 
} 

Answer 8

Điều này có vẻ đơn giản nhất của tất cả:

(x % Long.MAX_VALUE) + 1 

Tôi sẽ quan tâm đến tốc độ so sánh tất cả các phương pháp được đưa ra.

Answer 9

Chỉ VÀ giá trị đầu vào của bạn bằng Long.MAX_VALUE và OR với 1. Không cần gì khác.

Ex:

long hash = (input & Long.MAX_VALUE) | 1;