تحديد عناوين URL بشكل فريد مع رقم واحد 64 بت

Question

هذه هي مشكلة الرياضيات في الأساس، ولكن البرمجة ذات الصلة للغاية: إذا كان لدي 1 مليار سلاسل تحتوي على عناوين URL، وأخذ أول 64 بت من تجزئة MD5 من كل منها، أي نوع من تردد الاصطدام يجب أن أتوقع؟

كيف تتغير الإجابة إذا كان لدي سوى 100 مليون عناوين URL؟

يبدو لي أن الاصطدامات ستكون نادرة للغاية، لكن هذه الأشياء تميل إلى أن تكون مربكة.

هل سأكون أفضل حالا باستخدام شيء آخر غير MD5؟ مانع لك، أنا لا أبحث عن الأمن، مجرد وظيفة تجزئة سريعة جيدة. أيضا، الدعم الأصلي في MySQL هو لطيف.

تعديل: ليس تماما مكررة

Answer 1

إذا كانت أول 64 بت من MD5 شكلت تجزئة توزيعا مثاليا، فسيظل مفارقة عيد الميلاد تعني أنك تحصل على تصادم لكل 2 ^ 32 URL. وبعبارة أخرى، فإن احتمال الاصطدام هو عدد URL مقسوما على 4،294،967،296 4. يرى http://en.wikipedia.org/wiki/birthday_paradox#cast_as_a_colleision_problem. للتفاصيل.

لن أشعر بالراحة فقط رمي نصف البتات في MD5؛ سيكون من الأفضل ل XOR الكلمات العالية والمنخفضة 64 بت لمنحهم فرصة للخلط. ثم مرة أخرى، MD5 ليس بسرعة أو آمنة، لذلك لن أزعجها على الإطلاق. إذا كنت تريد سرعة العمياء بتوزيع جيد، ولكن لا يوجد أي ذريعة للأمان، فيمكنك تجربة إصدارات 64 بت من Murmurhash. يرى http://en.wikipedia.org/wiki/murmurhash. للحصول على التفاصيل والرمز.

Answer 2

لقد وصفت بهذا "بارادوكس عيد ميلاد"، وأعتقد أنك تعرف الجواب بالفعل.

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

حيث ن هو 1 مليار في قضيتك.

ستكون أفضل قليلا باستخدام شيء آخر ثم MD5، لأن MD5 لديها مشكلة التواطؤ pratical..

Answer 3

من ما أراه، تحتاج إلى وظيفة تجزئة مع المتطلبات التالية،

1. حروف طول التجزئة التعسفي إلى قيمة 64 بت
   • كن جيدا - تجنب الاصطدامات
   • ليس بالضرورة في اتجاه واحد (الأمن غير مطلوب)
   • ويفضل أن يكون سريعا - وهو مميزة ضرورية للتطبيق غير الأمني

هذه مسح وظيفة التجزئة قد تكون مفيدة للحفر إلى الوظيفة الأكثر ملاءمة لك.
سأقترح تجربة مهام متعددة من هنا وتمييزها عن مجموعة الإدخال المحتملة (اختر بضعة مليارات عنوان URL تعتقد أنك سترى).

يمكنك فعلا توليد عمود آخر مثل هذا المسح الاختبار للحصول على قائمة عنوان URL الخاص بك لتمييز واختيار من وظائف التجزئة الحالية أو أي جديدة (المزيد من الصفوف في هذا الجدول) قد ترغب في التحقق منها. لديهم رمز مصدر MSVC ++ للبدء مع (مرجع إلى الرمز البريدي).

إن تغيير وظائف التجزئة لتناسب عرض الإخراج الخاص بك (64 بت) سوف يمنحك توصيف أكثر دقة للتطبيق الخاص بك.

Answer 4

إذا كان لديك 2 ^ n احتمالات التجزئة، فهناك أكثر من فرصة الاصطدام بنسبة 50٪ عندما يكون لديك عناصر 2 ^ (n / 2).

على سبيل المثال إذا كان لديك Hash 64 بت، لديك 2 ^ 64 من إمكانيات التجزئة، سيكون لديك فرصة بنسبة 50٪ من الاصطدام إذا كان لديك 2 ^ 32 عناصر في مجموعة.

Answer 5

فقط باستخدام التجزئة، هناك دائما فرصة الاصطدامات. وأنت لا تعرف ذلك مسبقا، ستحدث التصادمات مرة واحدة أو مرتين، أو حتى مئات أو آلاف المرات في قائمة عناوين URL الخاصة بك.

الاحتمال لا يزال مجرد احتمال. انها مثل رمي النرد 10 أو 100 مرة، ما هي فرص الحصول على جميع الست؟ يقول الاحتمال إنه منخفض، ولكن لا يزال يمكن أن يحدث. ربما حتى عدة مرات على التوالي ...

لذلك في حين مفارقة عيد ميلاد يوضح لك كيفية حساب الاحتمالات، ما زلت بحاجة إلى تحديد ما إذا كانت الاصطدامات مقبولة أم لا.

... والاصطدامات مقبولة، ولا تزال التجزئة هي الطريقة الصحيحة للذهاب؛ ابحث عن خوارزمية تتجاوز 64 بت بدلا من الاعتماد على "Half-A-MD5" وجود توزيع جيد. (على الرغم من أنه ربما يكون ...)