Hàm băm thích hợp để băm chuỗi nhị phân ngẫu nhiên

Question

tôi có hai mảng: char data1 [length] trong đó độ dài là bội số của 8 chiều dài tức là 8, 16,24 ... Mảng chứa dữ liệu nhị phân được đọc từ một tệp đang mở ở chế độ nhị phân. Tôi sẽ tiếp tục đọc từ các tập tin và mọi i đọc i sẽ lưu trữ giá trị đọc trong một bảng băm. Việc phân tách dữ liệu nhị phân này có phân phối ngẫu nhiên. Tôi muốn băm từng mảng và lưu trữ chúng trong một bảng băm để có thể tìm kiếm các char với các dữ liệu cụ thể một lần nữa. Điều gì sẽ là một hàm băm tốt để đạt được nhiệm vụ này. Cảm ơn

Xin lưu ý rằng tôi đang viết điều này bằng ngôn ngữ C++ và c để bất kỳ ngôn ngữ nào bạn chọn cung cấp giải pháp sẽ tuyệt vời.

Answer 1

Nếu dữ liệu mà bạn đọc là 8 byte dài và thực sự phân phối ngẫu nhiên, và hashcode của bạn cần phải được 32 bit, những gì về vấn đề này:

uint32_t hashcode(const unsigned char *data) { 
    uint32_t hash = 0; 
    hash ^= get_uint32_le(data + 0); 
    hash ^= get_uint32_le(data + 4); 
    return hash; 
} 

uint32_t get_uint32_le(const unsigned char *data) { 
    uint32_t value = 0; 
    value |= data[0] << 0; 
    value |= data[1] << 8; 
    value |= data[2] << 16; 
    value |= data[3] << 24; 
    return value; 
} 

Nếu bạn cần tốc độ hơn, mã này có lẽ có thể làm nhanh hơn rất nhiều nếu bạn có thể đảm bảo rằng data luôn được căn chỉnh chính xác để được hiểu là const uint32_t *.

Answer 2

Tôi đã sử dụng thành công MurmurHash3 trong một trong các dự án của tôi.

Ưu điểm:

• Đó là nhanh. Rất nhanh.
• Nó được cho là có tỷ lệ va chạm thấp.

Nhược điểm:

• Nó không phù hợp cho các ứng dụng mật mã.
• Nó không được tiêu chuẩn hóa ở bất kỳ hình dạng hoặc hình thức nào.
• Không thể di chuyển sang nền tảng không phải x86. Tuy nhiên, nó đủ nhỏ để bạn có thể chuyển nó nếu bạn thực sự cần - tôi có thể chuyển nó sang Java, mặc dù điều đó gần như không giống nhau.

Đó là một khả năng tốt để sử dụng trong ví dụ: triển khai bảng băm nhanh ...