تصادمات التجزئة المتوقعة
وزّع 100 مفتاح على 128 حاوية، وفي المتوسط ينتهي أكثر من نصف المفاتيح بمشاركة حاوية مع غيرها، بمعامل تحميل قدره 0.78125. وتحصل أيضًا على المفاتيح المنفردة والحاويات الفارغة والمشغولة والمفاتيح الفائضة. مجاني في متصفحك.
- مجاني
- يعمل في متصفحك
- دون تسجيل
- بياناتك لا تغادر جهازك
شغّل الأداة مجانًا
مثال محلول
- N
- 100
- M
- 128
- عامل التحميل
- 0.78125
- المفاتيح المتصادمة المتوقعة
- 53.9975057729
- المفاتيح المنفردة المتوقعة
- 46.0024942271
- السلال المشغولة المتوقعة
- 69.5768323316
عندما تُوزَّع n مفاتيح متميزة توزيعًا منتظمًا على m حاويات، تتشارك بعضها فتحة واحدة حتى مع معامل تحميل متواضع. ويقلل الحدس من تقدير الإشغال: يتذكر الناس احتمال مفارقة أعياد الميلاد بأن زوجًا واحدًا على الأقل يتصادم، ثم يعاملون ذلك الاحتمال كما لو كان عددًا. تجيب حاسبة تصادمات التجزئة المتوقعة عن سؤال تخطيط مختلف. فهي تستخدم نموذج الكرات والصناديق الكلاسيكي — يختار كل عنصر واحدة من m حاويات استقلالًا وبانتظام — وتعيد العدد المتوقع للمفاتيح المتصادمة، أي المفاتيح التي ليست وحدها في حاويتها. وإلى جانب ذلك الرقم الرئيسي تُبلِغ عن المفاتيح المنفردة، والحاويات المشغولة والفارغة، ومفاتيح الفيضان بعد أول شاغل، والتصادمات الزوجية، ومعامل التحميل n مقسومًا على m. والحساب هوية مغلقة تُقيَّم في الفضاء اللوغاريتمي، حتمية تمامًا، بلا أخذ عينات Monte Carlo وبلا نموذج لغوي. استخدمها لتحديد حجم جدول تجزئة، أو ضبط معامل تحميل، أو مقارنة فضاء تجزئة ذي 32 بت بفضاء أضيق، أو التحقق من زعم إشغال في كتاب قبل أن تخصص ذاكرة.
ما الذي تقيسه المفاتيح المتصادمة المتوقعة في نموذج الكرات والصناديق
ألقِ n كرات استقلالًا وبانتظام في m صناديق فتحصل على النموذج القياسي لتجزئة منتظمة. المفتاح المتصادم كرة تشارك صندوقها كرة أخرى على الأقل. وليست هذه الكمية ذاتها احتمال مفارقة أعياد الميلاد بأن كرتين على الأقل تشتركان في صندوق، ولا عدد التطابقات الزوجية.
ولتخطيط السعة تريد عادة عددًا: كم مفتاحًا في المتوسط يخفق في نيل فتحة خاصة، وكم حاوية تبقى فارغة بينما تفيض أخريات، وكم مفتاحًا زائدًا يتراكم فوق أول شاغل. وتعطي خطية التوقع إجابات نقية بلا محاكاة. ثبّت أي مفتاح واحد.
تفوت المفاتيح الأخرى وعددها n ناقص واحد حاوية ذلك المفتاح باحتمال واحد ناقص واحد على m، فيكون احتمال أن يكون المفتاح المختار منفردًا هو (1 − 1/m) مرفوعًا إلى n ناقص واحد. اضرب في n فتحصل على العدد المتوقع للمفاتيح المنفردة. اطرح من n فتحصل على العدد المتوقع للمفاتيح المتصادمة: n مضروبًا في واحد ناقص (1 − 1/m) إلى n ناقص واحد.
ويُنتج برهان الإشغال نفسه العدد المتوقع للحاويات الفارغة، وهو m مضروبًا في (1 − 1/m) إلى n، ومن ثم عدد الحاويات المشغولة. ومفاتيح الفيضان هي العناصر بعد الأول في كل حاوية مشغولة، وتساوي n ناقص المشغولة. والتصادمات الزوجية تساوي توافيق n اثنين اثنين مقسومة على m، لأن أي زوج محدد يسقط معًا باحتمال واحد على m.
ومعامل التحميل هو ببساطة n على m. ومعًا تخبرك هذه الأرقام إن كان الجدول المقترح يعاني نقص الحاويات، أو هو مشغول فحسب، أو يدفع أصلًا ضريبة طول السلسلة يزيلها m أكبر.
تخطيط السعة والحدود والتسعير وأين تكسب الأرقام قيمتها
استخدم أداة المتصفح عندما تختار حجم جدول، أو تقارن معاملات التحميل، أو تشرح لفريق لماذا يترك معامل تحميل يساوي واحدًا حصة كبيرة من المفاتيح تتشارك حاوية. ارفع m حتى تهبط المفاتيح المتصادمة المتوقعة أو مفاتيح الفيضان دون ميزانية مستوى الخدمة، ثم أبقِ هامشًا للنمو. قابل النتيجة باحتمال مفارقة أعياد الميلاد إن احتجت أيضًا فرصة وجود أي تصادم؛ فذلك الاحتمال يشبع قرب الواحد قبل أن يكبر عدد المفاتيح المتصادمة المتوقع بزمن طويل، ولهذا يجيب الأداتان عن تذاكر مختلفة.
والنتائج حتمية تمامًا: فالقيمتان n وm نفساهما تعطيان دائمًا متجه الإشغال نفسه، لذا يمكنك تثبيت الأمثلة في الاختبارات والمواد التعليمية. ولا يوجد نموذج لغوي ولا خدمة إحصاء خارجية ولا عشوائية.
حالات الاستخدام
تحديد حجم جداول التجزئة والخرائط
اجعل n مساويًا لعدد مفاتيح مجموعة العمل وامسح m (مواضع الجدول) حتى تهبط المفاتيح المتصادمة المتوقعة ومفاتيح الفيضان دون ميزانية زمن الاستجابة.
إشغال شظايا الذاكرة المؤقتة والأقسام
عامل الشظايا بوصفها حاويات والمفاتيح الواردة بوصفها كرات لتقدير كم مفتاحًا يتشارك قسمًا ساخنًا قبل أن تضيف سعة أو تعيد التجزئة.
أواكل حتمية للدروس والاختبارات
تستدعي المقررات ومنصات المقابلات وأجنحة CI أوراكل إشغال مستقرًا يرفض n أو m الأدنى من واحد ويعيد الحقول ذاتها للمدخلات ذاتها.
الأسئلة الشائعة
ما المفتاح المتصادم في هذه الحاسبة؟
مفتاح ليس وحده في حاويته. العدد المتوقع هو n ناقص العدد المتوقع للمنفردات. إنه عدد متوقع، لا احتمال أن يتصادم زوج واحد على الأقل.
بماذا يختلف هذا عن مفارقة أعياد الميلاد؟
تعيد مفارقة أعياد الميلاد P(يوم مشترك واحد على الأقل). وتعيد هذه الأداة أعداد إشغال متوقعة لضبط التجزئة: مفاتيح متصادمة، وفيضان، وحاويات فارغة، وتصادمات زوجية وفق الكرات والصناديق.
ماذا يحدث إذا كان n أو m أدنى من 1؟
يلزم عنصر واحد على الأقل وحاوية واحدة على الأقل؛ ويُرفض الصفر والقيم السالبة ولا تُحتسب رسومًا.
كم حاوية تبقى فارغة في المتوسط؟
القيمة المتوقعة هي عدد الحاويات مضروبًا في احتمال ألا يقع أي مفتاح في حاوية بعينها. ومع 100 مفتاح في 128 حاوية يبقى قرابة نصف الحاويات فارغًا، مع أن أكثر من نصف المفاتيح يتشارك مكانه.
ما المفاتيح الفائضة؟
هي المفاتيح التي تأتي بعد المفتاح الأول في كل حاوية مشغولة، وعددها يساوي عدد المفاتيح ناقص الحاويات المشغولة. وهي توضح كم مفتاحًا يتكدس فوق مكان له صاحب بالفعل.
أدوات ذات صلة
للمطوّرين — الوصول عبر API
كل ما في هذه الصفحة متاح برمجيًا. هذا القسم موجّه للفرق التقنية التي تريد ربط الأداة بأنظمتها الخاصة؛ بقية المستخدمين يمكنهم استخدام الأداة أعلاه مباشرة دون الحاجة لقراءة ما يلي.
الـEndpoint
صادِق على طلبك بترويسة Bearer، وأرسل طلب POST واحدًا لتدخل مهمتك قائمة التنفيذ فورًا؛ ثم تستلم النتيجة عبر webhook أو رابط موقّع.
استدعِ الخدمة من بيئتك
curl -X POST https://api.kit.forhosting.com/dev/hash-expected-collisions \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":100,"m":128}'const res = await fetch("https://api.kit.forhosting.com/dev/hash-expected-collisions", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 100,
"m": 128
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/hash-expected-collisions",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 100,
"m": 128
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/hash-expected-collisions", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":100,"m":128}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":100,"m":128}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/hash-expected-collisions", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)مثال على الطلب
{
"n": 100,
"m": 128
}مثال على الاستجابة
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.hash_expected_collisions",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}الواجهة غير متزامنة: تستلم task_id فور الإرسال، ويمكنك الاستعلام عن الحالة بمعدل طلب واحد في الثانية.
الأسعار
السعر معلن كما تراه: لا tokens ولا نظام نقاط؛ وإن فشلت المهمة فلن تُحاسَب عليها.
الحدود
max_n | 1000000000000 |
max_m | 1000000000000 |
الأخطاء
| HTTP | الرمز | المعنى |
|---|---|---|
401 | unauthorized | مفتاح الوصول مفقود أو غير صالح؛ تحقق من ترويسة Bearer في طلبك. |
402 | insufficient_balance | رصيدك لا يكفي لتنفيذ هذه المهمة؛ أعد شحن الرصيد ثم أعد المحاولة. |
404 | unknown_type | نوع المهمة المطلوب غير موجود في الكتالوج — راجع الاسم المرسل في الطلب. |
429 | rate_limited | تجاوزت الحد المسموح من الطلبات؛ انتظر قليلًا ثم أعد المحاولة. |
ملاحظات تقنية
عقد الإدخال والصيغ والاستقرار العددي والأخطاء
أرسل عددين صحيحين إلزاميين: n وهو عدد العناصر، وm وهو عدد الحاويات. ويجب أن تكون القيمتان عددين صحيحين منتهيين ضمن الحدود المنشورة: n من واحد إلى تريليون، وm من واحد إلى تريليون، وهذا يغطي أمثلة القاعات، والخرائط في الذاكرة، وفضاء تجزئة كاملًا ذا 32 بت يضم أربعة مليارات ومئتين وأربعة وتسعين مليونًا وتسعمئة وسبعة وستين ألفًا ومئتين وستة وتسعين موضعًا. وبعد التحقق يقيّم المحرك قوى واحد ناقص واحد على m في الفضاء اللوغاريتمي بوصفها أسية الأس مضروبًا في log1p لسالب واحد على m، حتى لا ينهار n وm الكبيران إلى صفر صامت كما تفعل حلقة ضرب ساذجة. وتبقى الحالات الخاصة دقيقة: عنصر واحد لا يتصادم أبدًا؛ وحاوية واحدة فيها عنصران أو أكثر تجعل كل مفتاح يتصادم؛ ويُعامل الأس الصفري واحدًا حتى لا يصبح (1 − 1/m) إلى القوة صفر صفرًا إلى الصفر غير محدد. وتُقبل الأسماء البديلة items أو keys أو balls بدل n، وbuckets أو bins بدل m. أما الحقول المفقودة وغير الصحيحة وn أو m الأدنى من واحد والقيم فوق الحدود القصوى فتفشل مع invalid_input ولا تُحتسب رسومًا. ويكرر جسم JSON قيمتي n وm، ثم يعيد load_factor وexpected_colliding_keys وexpected_singleton_keys وexpected_occupied_buckets وexpected_empty_buckets وexpected_collision_buckets وexpected_overflow_keys وexpected_pairwise_collisions وسلسلة formula تعيد صياغة الهويتين الرئيسيتين.
تخطيط السعة والحدود والتسعير وأين تكسب الأرقام قيمتها
واستخدم API عندما يحتاج نص برمجي أو بيئة مقابلة أو دفتر ضبط قواعد بيانات أو فحص تكامل مستمر إلى JSON مستقر لأزواج كثيرة من (n, m) بموجب عقد واحد. كل طلب ناجح بند قابل للفوترة بسعر $0.002، والتحقق الفاشل لا يستهلك الرصيد. وتحافظ النطاقات المنشورة على بقاء التقييم المغلق داخل أعداد IEEE-754 المزدوجة العادية مع تغطية كل جدول تجزئة عملي كنت ستحدد حجمه يدويًا. صِل نقطة النهاية بدروس جداول التجزئة، أو بمخططي شظايا الذاكرة المؤقتة، أو بفحوص إشغال قريبة من Bloom، أو بأواكل مقابلات البرمجة حيث تفضل هويات الكرات والصناديق الدقيقة على مدرجات أخذ العينات التقريبية التي لا تستقر أبدًا تمامًا.
أسئلة تقنية
كيف أقدّر تصادمات التجزئة المتوقعة لـ n مفاتيح وm حاويات؟
أرسل العددين الصحيحين n (عناصر) وm (حاويات) إلى dev.hash_expected_collisions. تتضمن الاستجابة expected_colliding_keys = n*(1-(1-1/m)^(n-1)) إضافة إلى المشغول والفارغ والفيضان والزوجي وload_factor.
هل حاسبة تصادمات التجزئة المتوقعة مجانية؟
تعمل أداة المتصفح مجانًا على جهازك. وتستخدم استدعاءات API رصيد KIT المدفوع مقدمًا بسعر $0.002 لكل بند ناجح؛ ولا تُحتسب إخفاقات التحقق.