جدول التجزئة: هل يجب علي زيادة عدد العناصر على الاصطدامات؟

Question

في الوقت الحالي ، تحسب جداول التجزئة عدد كل عنصر تم إدخاله في جدول التجزئة. أستخدم هذا العد ، مع حجم جدول التجزئة الكلي ، لحساب عامل التحميل وعندما يصل إلى 70 ٪ ، أعيد صياغة ذلك.

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

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

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

Answer 1

تهدف إعادة التحويل إلى تقليل احتمال الاصطدام ، لذلك تجاهل التصادم بشكل منهجي لتحديد متى يتم إعادة صياغة يبدو هزيمة الذات.

قد يكون الأفضل إذا كنت قد احتفظت مع كل إدخال قيمة التجزئة الكاملة الأصلية (يتم تحديد تصادم بالطبع بدلاً من ذلك من خلال Modulo Modulo بحجمك الحالي) وحساب التصادمات فقط بسبب عملية Modulo - مع الاعتراف ضمنيًا أنه يرجع إلى قيم التجزئة الكاملة المتطابقة للعناصر المختلفة ، لا يوجد أي شيء يمكن أن يفعله للمساعدة (ما لم "إعادة صياغة" ، فأنت تدل أيضًا على التحول إلى وظيفة تجزئة مختلفة ، لكن هذا لا يبدو أن هذا ما تعنيه هنا ؛-).

إن الحفاظ على قيم التجزئة الكاملة يعني أيضًا إعادة صياغة أرخص لأنك لا تحتاج إلى تشغيل وظيفة التجزئة مرة أخرى (ما مدى أهمية ذلك يعتمد على مدى تكلفة وظيفة التجزئة ، بالطبع).