thuật toán Hash trong C để lập bản đồ 16 byte-giá trị đến 2 byte-giá trị

Question

Tôi đang làm việc trên một dự án điện tử với một vi điều khiển được lập trình trong C.

tôi cần phải lưu trữ một số ID và thông tin liên quan của nó trong bộ nhớ flash (SD). Các ID này dài 16 byte nên có 2^128 giá trị có thể. Mặc dù chúng là 16 byte, chỉ có 50000 (giá trị duy nhất) sẽ được sử dụng. Đó là thể chất không thể lưu trữ tất cả các ID có thể (2^128) trong một SD.

Tôi chỉ có thể lưu trữ 50000 giá trị đã sử dụng nhưng sau đó tôi sẽ phải duyệt qua tất cả (tồi tệ nhất) của chúng để tìm giá trị tôi cần. Bên cạnh đó, nó sẽ phải được tính toán một so sánh giá trị 16-byte cho mỗi người trong số họ mà làm cho nó được khá chậm.

Vì vậy, tôi nghĩ rằng tôi sẽ cần một số loại (băm?) Chức năng bản đồ 2^128 giá trị đến 50000 (bản đồ 16 byte đến 2 byte). Rõ ràng là một số giá trị ban đầu sẽ ánh xạ tới cùng một giá trị/chỉ mục. Ý tưởng là khi tôi nhận được một ID, tôi áp dụng một hàm băm mang lại cho tôi một chỉ số từ 0 đến ~ 50000 (0-65535). Với chỉ mục đó, tôi có thể truy cập trực tiếp (các) sector SD trong đó ID và thông tin liên quan của nó được lưu trữ. Như tôi đã chỉ ra, chỉ mục đó sẽ chỉ đến vị trí bộ nhớ trong đó các ID khác nhau sẽ cùng tồn tại do một số ID khác nhau được ánh xạ tới cùng một giá trị chỉ mục. Tôi sẽ phải tìm ID chính xác nhưng nó sẽ có giá chỉ là một vài so sánh thay vì 50000 bản gốc.

Bất kỳ ý tưởng/ý kiến ​​nào sẽ thực sự được đánh giá cao.

Xin cảm ơn trước.

Answer 1

Assumign các bit trong giá trị 128-bit của bạn đang "phân bố đều", bạn chỉ có thể làm một cái gì đó như thế này:

uint32_t uuid[4]; 

uint16_t hash = 0; 
for(i = 0; i < 4; i++) 
{ 
    hash ^= (uuid[i] & 0xffff)^(uuid[i] >> 16); 
} 

Có lẽ cách thông minh hơn khác, nhưng điều này rất đơn giản, và có thể hoạt động tốt.

Answer 2

Chỉ cần sử dụng 16 MSB của id thực tế. Nó câm nhưng với chi tiết của bạn nó sẽ làm việc.

Answer 3

chắc Mat là tốt, điều này tuy nhiên, bằng cách sử dụng một số nguyên tố nên dẫn đến va chạm ít nơi uuid[x] == uuid[y] (và x!=y)

uint32_t uuid[4]; 

uint16_t hash = 0; 
for(i = 0; i < 4; i++) 
{ 
    // hash *= 31; //next line does this, note 31 is a prime 
    hash = (hash << 5) - hash; 
    hash += (uuid[i] & 0xffff)^(uuid[i] >> 16); 
} 

Hoặc phiên bản này thậm chí còn tốt hơn, vì nó làm giảm xung đột nơi xor của 16 bit đầu tiên và 16 bit thứ hai phù hợp.

uint16_t hash = 0; 
for(i = 0; i < 4; i++) 
{ 
    hash = (hash << 5) - hash; //(*=31) 
    hash += uuid[i] & 0xffff; 
    hash = (hash << 5) - hash; //(*=31) 
    hash += uuid[i] >> 16; 
} 

Answer 4

Vì ID dài 16 byte, tôi cho rằng nó được lưu trữ trong chuỗi ASCII nên ELFhash có thể hoạt động.

int ELFhash(char *key) { 
    unsigned long h = 0; 
    while(*key) { 
     h = (h << 4) + *key++; 
     unsigned long g = h & 0xf0000000L; 
     if (g) h ^= g >> 24; 
     h &= -g; 
    } 
    return h & M; 
} 

đó M là một số nguyên tố nhỏ hơn 65536 hoặc 50000.

Đó là nhiều khả năng rằng các tiền tố của nhiều chuỗi ID là cùng vì họ đại diện cho một meaaing cụ thể, vì vậy bạn nên có cẩn thận hơn để ngăn chặn va chạm, hoặc danh sách liên kết sẽ rất dài.