الاستخدام الفعال لـ Hashmap

Question

ما هو النهج الأكثر كفاءة لاستخدام hashmaps؟

أ) استخدم عدة خرائط تصنيف أصغر، أو

ب) تخزين جميع الكائنات في هاشماب عملاق واحد؟

(افترض أن خوارزمية التجزئة للمفاتيح فعالة إلى حد ما، مما يؤدي إلى عدد قليل من الاصطدامات)

إيضاح:يتضمن الخيار (ب) الفصل حسب المفتاح الأساسي - أي.ليس من الضروري إجراء بحث إضافي لتحديد خريطة التجزئة الفعلية التي سيتم استخدامها.(على سبيل المثال، إذا كانت مفاتيح البحث عبارة عن حروف أبجدية رقمية، فإن Hashmap 1 يخزن الحروف A، ويخزن Hashmap 2 الحروف B، وهكذا.)

Answer 1

بالتأكيد ب.تتمثل ميزة جداول التجزئة في أن متوسط ​​عدد المقارنات لكل عملية بحث يكون مستقلاً عن الحجم.

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

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

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

Answer 2

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

وحافظ على hashmap واحد لكل <م> منطقية رسم الخرائط من المفتاح إلى القيمة.

Answer 3

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

إذا كان لديك جداول منفصلة عن تعيينات مختلفة يمكنك 'واضح' كل من تعيينات بشكل مستقل. مثلا من خلال الدعوة "واضحة" أو التخلص من الإشارة إلى الجدول المقابل.

إذا جداول منفصلة عقد تعيينات لإدخالات مؤقتا، يمكنك استخدام الاستراتيجيات المختلفة ل'عمر' الإدخالات منها.

إذا كان الطلب متعددة الخيوط، وذلك باستخدام جداول منفصلة قد يقلل من الخلاف القفل، وربما (لبعض بنيات المعالج) زيادة ذاكرة التخزين المؤقت معالج ضرب النسب.