Hàm băm tối thiểu cho C?

Question

Tôi không thể sử dụng tăng: băm vì tôi phải gắn bó với C và không thể sử dụng C++.

Nhưng, tôi cần phải băm một số lượng lớn (10K đến 100k) chuỗi mã (độ dài từ 5 đến 40 byte) để tìm kiếm trong đó nhanh nhất.

MD5, SHA1 hoặc bất kỳ hàm băm dài nào có vẻ quá nặng đối với một tác vụ đơn giản, tôi không làm mật mã. Thêm vào đó là chi phí lưu trữ và tính toán.

Vì vậy câu hỏi của tôi:

1. gì có thể là thuật toán băm đơn giản nhất mà sẽ đảm bảo phòng ngừa va chạm trong trường hợp thực tế nhất.

2. Có bao nhiêu bit để sử dụng cho giá trị băm? Tôi đang phát triển cho các hệ thống 32 bit. Thuật toán băm trong Perl/Python có sử dụng băm 32 bit không? Hay tôi phải nhảy tới 64?

3. Liên quan đến việc triển khai bảng băm trong các ngôn ngữ kịch bản phổ biến: thực hiện kiểm tra xem có bị va chạm hoặc tôi có thể tránh hoàn toàn phần đó không?

Answer 1

Bạn có thể tìm thấy một hàm băm tốt (và nhanh), và một chi thú vị, tại http://www.azillionmonkeys.com/qed/hash.html

Lần duy nhất bạn không nên kiểm tra va chạm, là nếu bạn sử dụng hàm băm hoàn hảo - một bảng tra cứu thời trang cũ tốt, như gperf.

Answer 2

Hàm băm chung cho hash table lookup. Nó chỉ định KHÔNG sử dụng cho các mục đích mã hóa, nhưng vì bạn đã xác định rằng bạn không có ý định cho điều đó thì bạn nên ổn.

Nó bao gồm là Một khảo sát của hàm Hash thử

Answer 3

1. Here là một cái nhìn tổng quan tốt đẹp của các hàm băm đáng chú ý nhất được biết đến.

2. 32 bit chỉ hoạt động tốt.

3. Bạn luôn cần phải kiểm tra va chạm, trừ khi bạn muốn viết một Hashtable hài hước :)

Answer 4

Hãy thử Adler32 cho các chuỗi dài hoặc Murmur2 cho các chuỗi ngắn.

Answer 5

Nếu bạn đang ở trên một hệ thống giống như posix và gắn bó với đồng bằng C, tôi chỉ đơn giản là sẽ sử dụng những gì hệ thống đã cung cấp. man 3 hcreate cung cấp cho bạn tất cả chi tiết hoặc bạn có thể tìm thấy phiên bản trực tuyến tại đây http://linux.die.net/man/3/hcreate

Answer 6

xxhash là tùy chọn khá nhanh và dễ dàng. Một mã đơn giản sẽ sử dụng hàm XXH32:

unsigned int XXH32 (const void* input, int len, unsigned int seed); 

Đó là băm 32 bit.Kể từ len là int, cho dữ liệu lớn hơn 2^31-1 byte sử dụng sau đây:

void*   XXH32_init (unsigned int seed); 
XXH_errorcode XXH32_update (void* state, const void* input, int len); 
unsigned int XXH32_digest (void* state);