Cải thiện việc phân phối các giá trị hàm băm

Question

Giả sử tôi có một số lượng rất lớn các chuỗi (giả sử 10 tỷ chuỗi ~ 50 ký tự mỗi chuỗi). Tôi muốn phân phối các chuỗi thành chính xác 10 nhóm. Mỗi nhóm nên chứa khoảng 10% các chuỗi. Với hàm băm() Tôi có thể làm:

int bucket_for_s = h(s) % 10 

Tuy nhiên điều này không đảm bảo về tính đồng đều của phân phối. Giả sử tôi làm điều trên cho tất cả các chuỗi và thấy rằng 30% chuyển đến nhóm 1, 5% chuyển đến nhóm 2 và cứ tiếp tục như vậy. Câu hỏi của tôi là:

Với phân phối h(), có cách nào để tạo hàm băm mới h2() sẽ phân phối các chuỗi đồng đều hơn không? Ngoài ra, có một quy trình có thể tạo ra một loạt hàm băm h2(), h3() ... sao cho 1: mỗi hàm băm tốt hơn so với hàm trước và 2: Tôi chỉ phải tạo ra một hàm băm. số hàm băm hợp lý?

Tôi cũng nên đề cập đến điều đó thật không may, tôi không thể chỉ đơn giản chia đầu vào thành 10 phần vì đầu vào của tôi được trải rộng trên một số máy. Tôi đang tìm một giải pháp xác định tôi có thể áp dụng cho từng máy riêng biệt và nhận được kết quả tương tự (vì vậy cuối cùng "hello" sẽ chuyển sang nhóm x, bất kể máy nào được lưu trữ).

Answer 1

Hàm băm mật mã hóa chắc chắn phải có phân phối rất đồng đều trên tất cả các bit của đầu ra băm.

Nếu bạn đang sử dụng một cái gì đó giống như Java hashCode() mà tôi tin rằng trông giống như

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

bạn cũng có thể thấy phân phối băm nhỏ hơn lý tưởng.

Thử sử dụng hàm băm mật mã như SHA-256 làm cơ sở.

Google City Hash ít được phân phối hơn SHA-256, nhưng nhanh hơn nhiều. Điều đó có thể cung cấp đủ phân phối với chi phí tính toán ít hơn.

Answer 2

Một hướng về cách giải quyết nó đơn giản đến 2 xô thay vì 10 hoặc N.

Giả sử bạn nhận được một bản phân phối h() với phân bổ p cho xô 1 và q cho xô 2, và tất nhiên p + q = 1.

Bây giờ, mục tiêu là để tìm phân phối như h2() với các thông số p1, q1, p2, q2 rằng: trao xô 1 nó sử dụng cơ hội p1, q1 (p1+q1=1) và trao xô 2 nó sử dụng cơ hội p2, q2 (p2+q2=1):

  h()   h2() 

       /bucket1 p*p1 
     bucket1 p - 
    /   \ bucket2 p*q1 
x - 
    \   /bucket1 q*p2 
     bucket2 q - 
       \ bucket2 q*q2 

nơi mục tiêu của chúng tôi là để thậm chí cơ hội cho tất cả 2 xô:

p*q1 + q*p2 = 1/2 (total chances for bucket 1 after h2()) 
p*q2 + q*q2 = 1/2 (total chances for bucket 2 after h2()) 

và như trước:

p1 + q1 = 1 
p2 + q2 = 1 

Đây là hệ thống tuyến tính của 4 phương trình có 4 biến (tham số p1,q1,p2,q2 của phân phối h2()).

Lưu ý: Với 10 nhóm, chúng tôi sẽ có h() với p1, p2, ..., p10 trong đó p1 + p2 + ... + p10 = 1. Trong trường hợp số lượng nhóm> 2 có ít phương trình hơn số không xác định: đối với mỗi phân bổ như p1 bạn nhận được một thành phần của h2() với p11+p12+...+p1_10=1). Do đó trong 10 nhóm có 100 tham số không xác định của h2() và chỉ 20 phương trình. Điều này có nghĩa là một số giá trị tùy ý (nhưng khả thi) có thể được trao cho 80 tham số của h2() trước khi giải phương trình cho các tham số còn lại. Không đẹp nhưng vẫn là một giải pháp.

Answer 3

Chức năng băm chuỗi hoặc tạo một chuỗi hàm băm sẽ tốn kém tính toán không cần thiết. Bạn nên sử dụng hàm băm đã có các thuộc tính bắt buộc ngoài hộp.

có thể ứng cử viên

Từ những gì bạn mô tả, các hàm băm nên xác định ("hello" của bạn chẳng hạn) - đây là đúng đối với tất cả các hàm băm - và cần tạo ra một phân phối chẵn.

Mã băm mật mã như SHA-256 phải đáp ứng các yêu cầu của bạn vì nó xuất ra các băm hoàn toàn khác nhau ngay cả đối với các đầu vào hơi khác nhau như "hello" và "hallo". Bằng cách sử dụng phép toán modulo (%) trên băm, bạn có thể có nhiều nhóm như bạn muốn (không nhiều hơn số lượng băm).

Tuy nhiên, các hàm băm mật mã được xây dựng để bảo mật và kiểm tra và liên quan đến một số tính toán phức tạp. Trong trường hợp của bạn, rất có khả năng bạn sẽ không cần các thuộc tính liên quan đến bảo mật mạnh mà họ cung cấp.

Bạn có thể muốn tìm cái gọi là "hàm băm mật mã không" có thuộc tính thoải mái và được thiết kế để tra cứu - do đó chúng được tối ưu hóa cho tốc độ. hashCode() của Java, MurmurHash và CityHash đã đề cập (Google announcement) có thể là một khởi đầu tốt.

tính chất xác định của hàm băm vs thậm chí phân phối băm

Điều đó nói rằng, như hàm băm là xác định liên quan đến đầu vào, băm cho một đầu vào nhất định như "hello" sẽ luôn là như nhau, thậm chí nếu bạn gọi hàm băm nhiều lần. Nếu tập dữ liệu của bạn chứa một số phần tử có nhiều trùng lặp chính xác (ví dụ: "a" và "the" là các nghi phạm thông thường cho văn bản được mã hóa), điều này có thể dễ dàng dẫn đến các nhóm không đồng đều, bất kể hàm băm nào bạn sử dụng.

Giả sử bạn muốn sử dụng phân phối đồng đều các băm để phân phối đồng đều khối lượng công việc, điều này có thể được khắc phục bằng cách sử dụng chiến lược sau. Hãy nghĩ về từng thùng như một gói công việc hoặc công việc có thể được xử lý bởi bất kỳ máy nào có sẵn. Nếu bạn có nhiều gói công việc hơn máy (giả sử 20 hoặc 30 gói cho 10 máy), bạn có thể phân phối đồng đều khối lượng công việc miễn là bạn cho phép lập lịch linh hoạt. Khi máy A nhận được một trong các gói quá khổ và mất một thời gian để xử lý nó, máy B có thể xử lý hai gói nhỏ hoặc vừa trong cùng một thời gian, do đó tác động hiệu suất tổng thể của gói quá khổ bị giảm.

Answer 4

Hàm băm được thiết kế để phân phối đồng đều. Nếu đây không phải là trường hợp với dữ liệu của bạn, thì dữ liệu của bạn bằng cách nào đó "nghịch đảo" một phần của hàm băm cụ thể đó và vấn đề sẽ biến mất khi bạn chọn một dữ liệu khác.

Do đây là một câu hỏi lý thuyết, một cách tiếp cận sẽ là:

trắng màu tiếng ồn

Bạn có thể chơi với int bucket_for_s

int bucket_for_s = put_in_bucket(s) 

put_in_bucket: 
    x = h(s) % 10 + 10*((h(s)/10)%10) 
    if(0<=x<=2) return 0 
    if(3<=x<=5) return 1 
    if(6<=x<=9) return 2 
    #The previous bucket_1 (30%) is now split into 3 buckets 
    if(10<=x<=27) return 0 
    #The previous bucket_2 (5%) is now enlarged 
    #to incorporate more of the small old buckets (or parts of buckets) 
    #This bucket is now bucket_4 
    #... more of the same 
    if(83<=x<=99) return 9 

Bạn có thể mở rộng ý tưởng này bằng chữ số khác cho đến khi bạn hài lòng với "độ phân giải" của bạn

Bạn có thể lấy logic ra khỏi put_in_bucket và đặt nó vào h2(s) sử dụng h1(s).

Cách tiếp cận này được sử dụng để tô màu tiếng ồn trắng (hoặc nhiễu màu làm trắng, như trong trường hợp này), do đó tên.