Chức năng băm cho bốn số nguyên không dấu (C++)

Question

Tôi đang viết một chương trình ngay bây giờ để tạo bốn số nguyên 32 bit không dấu như đầu ra từ một hàm nhất định. Tôi muốn băm bốn số nguyên này, vì vậy tôi có thể so sánh đầu ra của hàm này với các đầu ra trong tương lai.

Tôi đang gặp sự cố khi viết chức năng băm phong nha. Khi tôi viết mã này ban đầu, tôi đã ném vào một bổ sung đơn giản của mỗi trong bốn số nguyên, mà tôi biết sẽ không đủ. Tôi đã thử một số kỹ thuật khác, chẳng hạn như dịch chuyển và thêm, không có kết quả. Tôi nhận được một băm, nhưng nó có chất lượng kém, và chức năng tạo ra một tấn va chạm.

Đầu ra băm có thể là số nguyên 32 bit hoặc 64 bit. Hàm trong câu hỏi tạo ra hàng tỷ băm, do đó va chạm là một vấn đề thực sự ở đây, và tôi sẵn sàng sử dụng một biến lớn hơn để đảm bảo rằng có ít va chạm nhất có thể.

Có ai giúp tôi tìm ra cách viết hàm băm chất lượng không?

Answer 1

Tại sao bạn không lưu trữ bốn số nguyên trong cấu trúc dữ liệu phù hợp và so sánh tất cả? Lợi ích của việc băm chúng trong trường hợp này dường như không rõ ràng với tôi, trừ khi lưu trữ là một vấn đề.

Nếu lưu trữ là vấn đề, bạn có thể sử dụng một trong các hàm băm được phân tích here.

Answer 2

Vì băm có thể tạo ra xung đột, bạn phải giữ các khóa trong bộ nhớ để khám phá những va chạm này. Hashmaps và các cơ sở dữ liệu tiêu chuẩn khác làm điều này trong sổ sách kế toán nội bộ của họ.

Vì khóa quá nhỏ, chỉ cần sử dụng khóa trực tiếp thay vì băm. Điều này sẽ nhanh hơn và sẽ đảm bảo không có va chạm.

Answer 3

Tại sao băm? Nó có vẻ như một std :: set hoặc std :: multi set sẽ phù hợp hơn để lưu trữ loại đầu ra này. Tất cả những gì bạn cần làm là bọc bốn số nguyên vào một cấu trúc và viết một hàm so sánh đơn giản.

Answer 4

Thử sử dụng CRC hoặc FNV. FNV là tốt đẹp vì nó là nhanh chóng và có một phương pháp được xác định của bit gấp để có được "nhỏ hơn" giá trị băm (tức là 12-bit/24-bit/etc). Ngoài ra lợi ích của việc tạo ra một băm 64 bit từ một số 128-bit (4 X 32-bit) là một chút có vấn đề bởi vì như những người khác đã gợi ý, bạn chỉ có thể sử dụng giá trị ban đầu như một chìa khóa trong một bộ. Bạn thực sự muốn số bit trong hàm băm đại diện cho số lượng giá trị ban đầu của bạn. Ví dụ: nếu tập dữ liệu của bạn có giá trị 100.000 4X32 bit, bạn có thể muốn giá trị băm 17 bit hoặc 18 bit, chứ không phải giá trị băm 64 bit.

Answer 5

Có thể hơi quá mức cần thiết, nhưng hãy xem xét Boost.Hash. Tạo ra mã rất đơn giản và các giá trị tốt.

Answer 6

Tôi hoàn toàn đồng ý với Vinko - chỉ cần so sánh tất cả. Nếu bạn vẫn muốn có một hàm băm tốt, bạn cần phải phân tích sự phân bố của 4 số nguyên chưa được đánh dấu của bạn. Sau đó, bạn phải tạo chức năng băm của mình theo cách, kết quả sẽ được phân phối trên toàn bộ phạm vi giá trị băm 32 bit.

Ví dụ đơn giản - giả sử hầu hết thời gian, kết quả từ mỗi hàm nằm trong khoảng từ 0 đến 255. Sau đó, bạn có thể dễ dàng trộn 8 bit thấp hơn từ mỗi hàm vào băm của bạn. Hầu hết thời gian, bạn sẽ tìm thấy kết quả trực tiếp, chỉ đôi khi (khi một hàm trả về kết quả lớn hơn), bạn sẽ có một xung đột.

Để tổng hợp - không có thông tin về cách kết quả của 4 hàm được phân phối, chúng tôi không thể giúp bạn với hàm băm tốt.

Answer 7

Dưới đây là một hàm băm khá hợp lý từ 4 số nguyên tới 1 số nguyên:

unsigned int hash = in[0]; 
hash *= 37; 
hash += in[1]; 
hash *= 37; 
hash += in[2]; 
hash *= 37; 
hash += in[3]; 

Với đầu vào thống nhất phân phối nó mang lại cho sản lượng thống nhất phân phối. Tất cả các bit của đầu vào tham gia vào đầu ra, và mọi giá trị đầu vào (mặc dù không phải mọi bit đầu vào) đều có thể ảnh hưởng đến mọi bit đầu ra. Rất có thể nó nhanh hơn chức năng tạo ra đầu ra, trong trường hợp đó không có mối quan tâm về hiệu suất.

Có các băm khác với các đặc điểm khác, nhưng tích lũy-với-nhân-by-prime là một khởi đầu tốt cho đến khi được chứng minh bằng cách khác. Bạn có thể thử tích lũy với xor thay vì bổ sung nếu bạn muốn. Dù bằng cách nào, thật dễ dàng để tạo ra va chạm (ví dụ {1, 0, a, b} va chạm với {0, 37, a, b} cho tất cả a, b), vì vậy bạn có thể muốn chọn một số nguyên tố mà bạn nghĩ không liên quan gì đến bất kỳ lỗi triển khai chính đáng nào trong chức năng của bạn. Vì vậy, nếu hàm của bạn có rất nhiều modulo-37 số học trong đó, có thể sử dụng 1000003 để thay thế.