chức năng tính toán một số băm, chính xác nó làm gì và tại sao?

Question

Tôi biết chức năng này đang làm điều gì đó với số băm, nhưng không hiểu chính xác mục đích của hàm này? lý do tại sao "res * 31 + * key"? lý do tại sao 31?

unsigned int HashAlg(char* key) 
{ 
    unsigned int res = 0; 

    while (*key != 0) 
    { 
     res = res * 31 + *key; 
     ++key; 
    } 

    return res; 
} 

Answer 1

tại sao "res * 31 + phím *"

Giả sử những gì sẽ xảy ra nếu nó chỉ là res = res + *key; sau đó băm sẽ chỉ thêm tất cả các giá trị trong khóa. Điều đó sẽ mang lại giá trị băm giống nhau cho các chuỗi được hoán đổi như hello, elloh, olleh, loleh, vv Nhân với một giá trị> 1 làm cho điều này ít có khả năng hơn.

lý do tại sao 31?

Có lẽ để tránh sức mạnh của 2, chỉ đơn giản là chuyển sang trái một giá trị và mất nó sau một vài thay đổi. Một phi quyền lực của 2 tránh được vấn đề này.

Answer 2

Triển khai thực hiện là một biến thể của hàm băm chuỗi nhân với D.J. Bernstein:

unsigned djb_hash (void *key, int len) 
{ 
    unsigned char *p = key; 
    unsigned h = 0; 
    int i; 

    for (i = 0; i < len; i++) 
    h = 33 * h + p[i]; 

    return h; 
} 

Mục đích của hàm băm như thế này là để ánh xạ một phím tìm kiếm, như chuỗi "item1", một chỉ số mà sau đó có thể được sử dụng trong một bảng băm, một bộ nhớ cache, vv .; đơn giản, giá trị băm cung cấp cho chúng ta vị trí trong bảng mà bản ghi tương ứng cho "item1" phải được lưu trữ. Các bảng băm, lần lượt, được sử dụng để thực hiện các mảng kết hợp và các bộ động. Để biết thêm chi tiết, tôi khuyên bạn nên bắt đầu tại Wikipedia page.

Bạn có thể thấy rằng trong quá trình triển khai, hằng số 33 đã được chuyển cho 31. Không có nhiều công việc toán học thực sự mà có thể chứng minh dứt khoát mối quan hệ giữa số nguyên tố và hàm băm. Khái niệm cơ bản về việc sử dụng các số nguyên tố trong hàm băm xoay quanh khái niệm biến đổi trạng thái hiện tại của hàm băm (áp dụng một số dạng toán tử như phép nhân hoặc phép cộng vào giá trị băm). Kết quả bị ràng buộc là một giá trị băm mới nên có giá trị entropic cao hơn về mặt thống kê hoặc nói cách khác là độ lệch bit rất thấp đối với bất kỳ bit nào trong giá trị băm mới. Nói một cách đơn giản, khi bạn nhân một tập hợp các số ngẫu nhiên với số nguyên tố, các số kết quả (khi được phân tích ở mức bit) sẽ không có xu hướng trở thành trạng thái này hay trạng thái khác, tức là P(Bi = 1) ~= 0.5. Không có bằng chứng cụ thể rằng đây là trường hợp hoặc nó chỉ xảy ra với số nguyên tố, nó chỉ có vẻ là một trực giác tự tuyên bố đang diễn ra mà chúng tôi có vẻ bắt buộc phải tuân theo. Các thuộc tính này được đánh giá là một phần sau, có nghĩa là chúng tôi cố gắng phân tích các thuộc tính hàm băm (hoặc PRNG) với các hằng số được chọn và phát triển trực giác, nó hoạt động tốt, tức là tạo ra các bản phân phối cụ thể hoặc thể hiện hiệu ứng tuyết lở. bộ đầu vào cụ thể, v.v.