هل من المنطقي تغيير حجم جدول التجزئة؟ وعندما؟

Question

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

هل من المنطقي أنه يجب علي تغيير حجم جدول التجزئة في أي وقت أم يجب أن أتركه كما هو؟ خلاف ذلك ، إذا قمت بزيادة الحجم (بمقدار ضعف ما يقرب من ضعف ، في الواقع أتابع هذا: http://planetmath.org/encyclopedia/goodhashtablepremes.html) عندما يكون الحمل 70 ٪ ، هل يجب أن أقوم بتغيير حجمه عندما يحصل الحمل بنسبة 30 ٪ أو أقل؟

Answer 1

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

Answer 2

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

لماذا هذا ذو صلة بالسؤال؟ لأنه عندما تقلص علامة تجزئة في طراز اثنين ، يمكنك ترك جميع الإدخالات في النصف السفلي حيث تكون وببساطة إلحاق القائمة المرتبطة في الفتحة i (من النصف العلوي) إلى القائمة المرتبطة في الفتحة i - n/2.

Answer 3

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

Answer 4

الفكرة الأولى: السبب الوحيد لتنمية علامة التصنيف هو أن الأداء القابل للهاوية يتناقص إذا كان هناك الكثير من الاصطدامات. إن زراعة الطاولة عندما يتجاوز تحميله 70 ٪ هو قاعدة جيدة للإبهام لمنع حدوث ذلك ولكنها مجرد قاعدة للإبهام. من الأفضل بكثير تتبع عدد الاصطدامات وتنمية فقط التصنيف إذا تجاوزت حدًا معينًا أو بمجرد ضرب نسبة تصادم معينة. بعد كل شيء ، لماذا تريد أن تنمو علامة تصنيف تم تحميلها بنسبة 90 ٪ ، ولكن ليس لديها تصادم واحد؟ لن يكون لها ميزة.

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

الفكرة الثالثة: عند النمو أو الانكماش ، تنمو دائمًا/تتقلص بطريقة ما بعد العملية ، يتم ضمان عامل تحميل معين. على سبيل المثال ، عند النمو ، تنمو دائمًا بحيث يكون عامل التحميل بعد ذلك 50 ٪ وعند تقلصه ، يتقلص دائمًا بطريقة ما بعد ذلك عامل التحميل هو 70 ٪. بطبيعة الحال ، لا يقول هذا شيئًا عن عدد التصادمات ، لذا فإن إضافة عنصر فور النمو/تقلص قد يتسبب في نمو علامة التصنيف مرة أخرى ، لكن هذا أمر لا مفر منه لأن محاكاة تأثير النمو/الانكماش غالي الثمن عادة. غالبًا ما يتم استدعاء تقليص مرة واحدة مرة واحدة لا يتم تخطيط أي تعديلات أخرى ، وبالتالي يجب أن ينقذ الذاكرة بدلاً من تجنب الاضطرار إلى النمو مرة أخرى في المستقبل.

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