Xác suất va chạm khi sử dụng băm 32 bit

Question

Tôi có trường khóa chuỗi ký tự 10 ký tự trong cơ sở dữ liệu. Tôi đã sử dụng CRC32 để băm lĩnh vực này nhưng tôi lo lắng về bản sao. Ai đó có thể cho tôi thấy xác suất va chạm trong tình huống này không?

p.s. trường chuỗi của tôi là duy nhất trong cơ sở dữ liệu. Nếu số lượng các trường chuỗi là 1 triệu, xác suất va chạm là gì?

Answer 1

Duplicate của Expected collisions for perfect 32bit crc

Câu trả lời tham khảo bài viết này: http://arstechnica.com/civis/viewtopic.php?f=20&t=149670

Tìm thấy những hình ảnh dưới đây từ: http://preshing.com/20110504/hash-collision-probabilities

Answer 2

Trong trường hợp bạn trích dẫn, ít nhất một vụ va chạm về cơ bản là được bảo đảm. Xác suất của ít nhất một va chạm là khoảng 1 - 3x10 ^-51. Số lượng trung bình của va chạm bạn mong chờ là khoảng 116.

Nhìn chung, số lượng trung bình các xung đột trong k mẫu, mỗi một sự lựa chọn ngẫu nhiên trong số n giá trị có thể là:

xác suất ít nhất một vụ va chạm là:

Trong trường hợp của bạn, n = 2 và k = 10 .

Xác suất của một vụ va chạm ba trong trường hợp của bạn là khoảng 0,01. Xem Birthday Problem.