Hàm băm từ 64 bit đến 10 bit

Question

Tôi muốn hàm băm có số lượng dài (64 bit) và tạo ra kết quả là 10 bit. Hàm băm tốt nhất cho mục đích đó là gì. Đầu vào về cơ bản là địa chỉ của các biến (Địa chỉ có 64 bit hoặc 8 byte trên Linux), vì vậy hàm băm của tôi nên được tối ưu hóa cho mục đích đó.

Answer 1

tôi sẽ nói somethig như thế này:

uint32_t hash(uint64_t x) 
{ 
    x >>= 3; 
    return (x^(x>>10)^(x>>20)) & 0x3FF; 
} 

Các kẻo đáng kể 3 bit không phải là rất hữu ích, như hầu hết các biến là 4-byte hoặc 8-byte aligned, vì vậy chúng tôi loại bỏ chúng. Sau đó, chúng tôi lấy 30 bit tiếp theo và trộn chúng lại với nhau (XOR) trong khối 10 bit mỗi.

Một cách tự nhiên, bạn cũng có thể lấy số (x>>30)^(x>>40)^(x>>50) nhưng tôi không chắc liệu chúng có thực sự khác biệt trong thực tế hay không.

Answer 2

Tốt nhất cho hầu hết các bản phân phối là mod bằng một số nguyên tố, 1021 là số nguyên tố 10 bit lớn nhất. Không cần phải cắt các bit thấp.

static inline int hashaddress(void *v) 
{ 
     return (uintptr_t)v % 1021; 
} 

Nếu bạn nghĩ rằng hiệu suất có thể là một mối quan tâm, có một vài khuyết trên tay và chủng tộc họ trong chương trình thực tế của bạn. Microbenchmarks là chất thải; một sự khác biệt của một vài chu kỳ là gần như chắc chắn để được đầm lầy bởi hiệu ứng bộ nhớ cache, và kích thước vấn đề.

Answer 3

Tôi đã viết một đồ chơi chương trình-thấy một số địa chỉ thật trên stack, khu vực dữ liệu, và heap. Về cơ bản tôi đã tuyên bố 4 quả cầu, 4 người dân địa phương và đã làm 2 mallocs. Tôi đã bỏ hai bit cuối cùng khi in các địa chỉ. Dưới đây là một đầu ra từ một trong những lần chạy:

20125e8 
20125e6 
20125e7 
20125e4 
3fef2131 
3fef2130 
3fef212f 
3fef212c 
25e4802 
25e4806 

Điều này nói với tôi:

1. Các LSB sản lượng này (bit thứ 3 của địa chỉ) là thường xuyên 'bật' và 'tắt'. Vì vậy, tôi sẽ không thả nó khi tính toán băm. Giảm 2 LSB có vẻ đủ.
2. Chúng tôi cũng thấy rằng có nhiều entropy trong các bit 8-10 thấp hơn. Chúng tôi phải sử dụng khi tính toán giá trị băm.
3. Chúng tôi biết rằng trên máy 64 bit, virtual addresses are never more than 48 bits wide.

Những gì tôi sẽ làm gì tiếp theo:

/* Drop two LSBs. */ 
a >>= 2; 

/* Get rid of the MSBs. Keep 46 bits. */ 
a &= 0x3fffffffffff; 

/* Get the 14 MSBs and fold them in to get a 32 bit integer. 
The MSBs are mostly 0s anyway, so we don't lose much entropy. */ 
msbs = (a >> 32) << 18; 
a ^= msbs; 

Bây giờ chúng ta chuyển thông tin này thông qua một decent 'half avalanche' hash function, thay vì cán của riêng của chúng tôi. 'Một nửa trận tuyết lở' có nghĩa là mỗi bit đầu vào được một cơ hội để ảnh hưởng đến bit tại vị trí tương đương và cao hơn :

uint32_t half_avalanche(uint32_t a) 
{ 
    a = (a+0x479ab41d) + (a<<8); 
    a = (a^0xe4aa10ce)^(a>>5); 
    a = (a+0x9942f0a6) - (a<<14); 
    a = (a^0x5aedd67d)^(a>>3); 
    a = (a+0x17bea992) + (a<<7); 
    return a; 
} 

Đối với một hash 10-bit, sử dụng 10 MSB của uint32_t trả lại.Hàm băm tiếp tục hoạt động tốt nếu bạn chọn N MSB cho hàm băm bit N, tăng gấp đôi số lượng nhóm với mỗi bit bổ sung.

Tôi thấy hơi chán, vì vậy tôi đã viết chuẩn đồ chơi cho việc này. Không có gì lạ mắt, nó phân bổ một nhóm bộ nhớ trên heap và thử băm tôi mô tả ở trên. Nguồn có thể có từ here. Một ví dụ kết quả:

1024 xô, 256 giá trị được tạo ra, 29 collissions
1024 xô, 512 giá trị được tạo ra, 103 collissions
1024 xô, 1024 giá trị được tạo ra, 370 collissions

Next: Tôi đã thử hai băm khác được trả lời ở đây. Cả hai đều có hiệu suất tương tự. Có vẻ như: Chỉ cần chọn nhanh nhất;)