Hàm băm tốt nhất cho số nhận dạng chữ và số hỗn hợp

Question

Vì lý do hiệu suất, tôi cần phải phân tách một tập hợp các đối tượng được nhận dạng bởi một chuỗi thành các nhóm. Đối tượng có thể được xác định bằng cách một số hoặc một chuỗi trong tiền tố hình thức (đủ điều kiện) với dấu chấm tách các bộ phận của định danh:

12 
323 
12343 
2345233 
123123131 
ns1:my.label.one 
ns1:my.label.two 
ns1:my.label.three 
ns1:system.text.one 
ns2:edit.box.grey 
ns2:edit.box.black 
ns2:edit.box.mixed 

định danh Numeric là từ 1 đến vài triệu. Các định danh văn bản có nhiều khả năng có rất nhiều bắt đầu với cùng một tiền tố không gian tên (ns1 :) và với cùng một tiền tố đường dẫn (edit.box.).

Hàm băm tốt nhất cho mục đích này là gì? Sẽ tốt nếu tôi có thể dự đoán bằng cách nào đó kích thước của thùng dựa trên số liệu thống kê định danh đối tượng. Có một số bài viết hay để xây dựng hàm băm tốt dựa trên một số thông tin thống kê?

Có hàng triệu số nhận dạng như vậy, nhưng mục đích là chia chúng thành các nhóm 1-2 nghìn dựa trên hàm băm.

Answer 1

Hai hàm băm tốt có thể được ánh xạ vào cùng một không gian của các giá trị, và nói chung sẽ không gây ra bất kỳ vấn đề mới nào do kết hợp chúng.

Vì vậy, hàm băm của bạn có thể trông như thế này:

if it's an integer value: 
    return int_hash(integer value) 
return string_hash(string value) 

Trừ khi có bất kỳ vón cục của số nguyên của bạn giá trị xung quanh một số modulo N, trong đó N là một số có thể có của xô, sau đó int_hash chỉ có thể trở lại đầu vào của nó.

Chọn băm chuỗi không phải là vấn đề mới. Hãy thử "djb2" (http://www.cse.yorku.ca/~oz/hash.html) hoặc tương tự, trừ khi bạn có yêu cầu về hiệu suất khiêu dâm.

Tôi không nghĩ có nhiều điểm trong việc sửa đổi hàm băm để tính đến tiền tố chung. Nếu hàm băm của bạn là tốt để bắt đầu, thì không chắc rằng các tiền tố phổ biến sẽ tạo ra bất kỳ kết xuất các giá trị băm nào.

Nếu bạn làm điều này và hàm băm không thực hiện bất thường, và bạn đặt vài triệu giá trị băm vào vài nghìn nhóm, thì số lượng nhóm sẽ được phân phối bình thường, với số lượng trung bình (vài triệu/một vài nghìn) và phương sai 1/12 (vài nghìn)^2

Với trung bình 1500 mục trên mỗi nhóm, làm cho độ lệch chuẩn ở khoảng 430. 95% phân bố chuẩn nằm trong phạm vi 2 độ lệch chuẩn , do đó 95% số nhóm của bạn sẽ chứa 640-2360 mục, trừ khi tôi đã hoàn thành sai số tiền của mình. Điều đó có phù hợp không, hoặc bạn có cần các thùng có kích thước tương tự hơn không?

Answer 2

Có thể bạn sẽ an toàn khi đi với sha1 và cắt bớt nó theo bất kỳ kích thước nào bạn muốn.

Nó sẽ không cực kỳ hiệu quả, nhưng có lẽ hàm băm sẽ không phải là một nút cổ chai?

Answer 3

Tôi cho rằng CRC16 sẽ là một hàm băm hợp lý để sử dụng trên các chuỗi này và các nhóm không được lớn hơn 1-2 nghìn.

Điều này sẽ làm cho bảng băm khoảng 1MB + tuy nhiên nhiều mục bạn có trong nó * 4 byte, vì vậy chúng tôi đang nói 50MB, và sau đó bạn cũng có tất cả dữ liệu thực được lưu trữ, mà tốt hơn là rất nhỏ.