Chỉ định duy nhất các URL với một số 64 bit

Question

Đây là vấn đề về toán học, nhưng rất có liên quan đến lập trình: nếu tôi có 1 tỷ chuỗi chứa URL và tôi lấy 64 bit đầu tiên của MD5 băm của mỗi cái, loại tần số va chạm tôi nên mong đợi?

Câu trả lời thay đổi như thế nào nếu tôi chỉ có 100 triệu URL?

Dường như với tôi rằng va chạm sẽ cực kỳ hiếm, nhưng những điều này có xu hướng gây nhầm lẫn.

Tôi có nên sử dụng một cái gì đó khác ngoài MD5 không? Tâm trí bạn, tôi không tìm kiếm bảo mật, chỉ là một hàm băm nhanh. Ngoài ra, hỗ trợ bản địa trong MySQL là tốt đẹp.

EDIT: not quite a duplicate

Answer 1

Nếu 64 bit đầu tiên của MD5 tạo thành một băm với phân phối lý tưởng, nghịch lý sinh nhật sẽ vẫn có nghĩa là bạn sẽ bị va chạm với mỗi 2^32 URL. Nói cách khác, xác suất xảy ra xung đột là số lượng URL chia cho 4,294,967,296. Xem http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem để biết chi tiết.

Tôi sẽ không cảm thấy thoải mái khi bỏ đi một nửa số bit trong MD5; sẽ tốt hơn cho XOR những từ 64 bit cao và thấp để cho họ cơ hội hòa trộn. Sau đó, một lần nữa, MD5 là không có nghĩa là nhanh chóng hoặc an toàn, vì vậy tôi sẽ không bận tâm với nó cả. Nếu bạn muốn tốc độ chói mắt với phân phối tốt, nhưng không giả vờ bảo mật, bạn có thể thử phiên bản 64 bit của MurmurHash. Xem http://en.wikipedia.org/wiki/MurmurHash để biết chi tiết và mã.

Answer 2

Bạn đã gắn thẻ này là "sinh nhật-nghịch lý", tôi nghĩ rằng bạn know the answer already.

P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!) 

trong đó n là 1 tỷ trong trường hợp của bạn.

Bạn sẽ tốt hơn một chút khi sử dụng thứ gì đó khác rồi MD5, vì MD5 có pratical collusion problem.

Answer 3

Từ những gì tôi nhìn thấy, bạn cần một hàm băm với các yêu cầu sau,

1. Hash tùy chuỗi dài đến một giá trị 64-bit
   • Hãy tốt - Tránh va chạm
   • Không nhất thiết phải là một chiều (không yêu cầu bảo mật)
   • Tốt hơn là nhanh - là một đặc tính cần thiết cho một ứng dụng không bảo mật

Điều này hash function survey có thể hữu ích cho việc khoan xuống chức năng phù hợp nhất với bạn.
Tôi sẽ đề xuất thử nhiều chức năng từ đây và mô tả chúng cho tập hợp đầu vào có khả năng của bạn (chọn một vài tỷ URL mà bạn nghĩ bạn sẽ thấy).

Bạn thực sự có thể tạo another column like this test survey cho danh sách URL thử nghiệm của bạn để mô tả và chọn từ hàm băm hiện có hoặc bất kỳ hàm mới nào (có nhiều hàng trong bảng đó) mà bạn có thể muốn kiểm tra. Họ có mã nguồn MSVC++ để bắt đầu với (reference to ZIP link).

Thay đổi hàm băm cho phù hợp với chiều rộng đầu ra (64-bit) sẽ cung cấp cho bạn một đặc tính chính xác hơn cho ứng dụng của bạn.

Answer 4

Chỉ bằng cách sử dụng băm, luôn có khả năng xảy ra xung đột. Và bạn không biết trước các vụ va chạm sẽ xảy ra một hoặc hai lần, hoặc thậm chí hàng trăm hoặc hàng ngàn lần trong danh sách các url của bạn.

Xác suất vẫn chỉ là xác suất. Nó giống như ném một con xúc xắc 10 hoặc 100 lần, cơ hội nhận được tất cả sáu là gì? Xác suất nói nó thấp, nhưng nó vẫn có thể xảy ra. Có thể thậm chí nhiều lần liên tiếp ...

Vì vậy, trong khi birthday paradox chỉ cho bạn cách tính xác suất, bạn vẫn cần phải quyết định xem xung đột có được chấp nhận hay không.

... và va chạm có thể chấp nhận được và băm vẫn là cách phù hợp để đi; tìm một thuật toán băm 64 bit thay vì dựa vào "half-a-MD5" có phân phối tốt. (Mặc dù nó có thể có ...)

Answer 5

Nếu bạn có khả năng băm 2^n, có hơn 50% cơ hội va chạm khi bạn có 2^(n/2) mục.

E.G. nếu băm của bạn là 64 bit, bạn có 2^64 khả năng băm, bạn sẽ có 50% cơ hội va chạm nếu bạn có 2^32 mục trong bộ sưu tập.