Trong khi mẫu được nêu trong câu trả lời của Jon Skeet hoạt động tốt nói chung là họ hàm băm, lựa chọn các hằng số là quan trọng và hạt giống 17 và hệ số 31 như được ghi trong câu trả lời không hoạt động tốt chút nào trường hợp sử dụng phổ biến. Trong hầu hết các trường hợp sử dụng, giá trị được băm gần bằng không hơn int.MaxValue và số lượng mục được băm cùng nhau là vài chục hoặc ít hơn.
Để băm nhỏ một số nguyên tuple {x, y} trong đó -1000 <= x <= 1000 và -1000 <= y <= 1000, nó có tỷ lệ va chạm quá mức gần 98,5%. Ví dụ: {1, 0} -> {0, 31}, {1, 1} -> {0, 32}, v.v. Nếu chúng tôi mở rộng phạm vi phủ sóng cũng bao gồm các phần tử ở nơi 3 <= n <= 25, điều đó sẽ không tồi tệ hơn với tỷ lệ va chạm khoảng 38%. Nhưng chúng ta có thể làm tốt hơn nhiều.
public static int CustomHash(int seed, int factor, params int[] vals)
{
int hash = seed;
foreach (int i in vals)
{
hash = (hash * factor) + i;
}
return hash;
}
Tôi đã viết một Monte Carlo vòng lặp tìm kiếm lấy mẫu thử nghiệm các phương pháp trên với các giá trị khác nhau cho hạt giống và yếu tố trên khác nhau ngẫu nhiên n-tuples các số nguyên ngẫu nhiên i. Phạm vi được phép là 2 <= n <= 25 (trong đó n là ngẫu nhiên nhưng thiên về phía cuối thấp hơn của dải ô) và -1000 <= i <= 1000. Ít nhất 12 triệu thử nghiệm va chạm duy nhất được thực hiện cho mỗi cặp hạt và yếu tố.
Sau khoảng 7 giờ chạy, cặp tốt nhất được tìm thấy (trong đó hạt giống và hệ số được giới hạn ở 4 chữ số trở xuống) là: seed = 1009, factor = 9176, với tỷ lệ va chạm là 0,1131%. Trong các khu vực 5 và 6 chữ số, thậm chí còn có các tùy chọn tốt hơn. Nhưng tôi đã chọn biểu diễn 4 chữ số hàng đầu cho ngắn gọn và nó hoạt động khá tốt trong tất cả các trường hợp băm phổ biến int và char. Nó cũng có vẻ làm việc tốt với số nguyên lớn hơn nhiều.
Cần lưu ý rằng "là thủ tướng" dường như không phải là điều kiện tiên quyết chung cho hiệu suất tốt như là một hạt giống và/hoặc yếu tố mặc dù nó có khả năng giúp. 1009 lưu ý ở trên thực tế là nguyên tố, nhưng 9176 thì không. Tôi đã thử nghiệm một cách rõ ràng các biến thể về điều này, nơi tôi đã thay đổi factor thành nhiều số nguyên tố gần 9176 (trong khi rời khỏi seed = 1009) và tất cả chúng đều hoạt động kém hơn giải pháp trên.
Cuối cùng, tôi cũng so sánh với nhóm chức năng giới thiệu chung của ReSharper là hash = (hash * factor)^i; và số CustomHash() ban đầu như đã nêu ở trên có hiệu suất cao hơn rất nhiều. Kiểu dáng ReSharper XOR dường như có tỷ lệ va chạm trong khoảng 20-30% cho các giả định trường hợp sử dụng phổ biến và không nên được sử dụng theo ý kiến của tôi.
Vâng, đó là mối quan tâm của tôi về XORing, trong loại dữ liệu tôi ghép nối, nó không thể ghép nối các mục quá bình đẳng nhưng không thể không? – RobV
Trông giống như băm của Dan Bernstein (hoặc Chris Torek), chỉ với các hằng số khác nhau. Không ai biết tại sao nó hoạt động tốt. – ephemient
@RobV: Tôi không muốn phải suy nghĩ nếu tôi không phải làm vậy. Tôi sử dụng băm này ngay cả khi tôi * có thể * lấy đi với XOR, chỉ để tránh phải tự hỏi cho dù đó là an toàn hay không :) –