كم عدد دلاء التجزئة

Question

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

لنفترض أن لدي 100 دلو.هل يجب علي إعادة تنظيمه عندما يكون هناك 50 عنصرًا فيه؟500؟5000؟أم يجب أن أبحث عن الدلو الأكثر امتلاءً ومفتاح ذلك؟ثم عندما وصلت إلى هذه النقطة، ما مدى حجم جدول التجزئة الجديد؟

فيما يتعلق بهذا، إذا كنت تعرف مسبقًا تقريبًا عدد العناصر التي سيتم إدخالها، فهل هناك طريقة لحساب عدد المجموعات للحصول على أداء متوسط ​​جيد؟

أعلم أن الإجابة الحقيقية تعتمد على الكثير من الاعتبارات الأخرى مثل مدى أهمية السرعة مقابل السرعة.الحجم في مثال محدد، ولكني أبحث عن خطوط النقابات العامة.

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

Answer 1

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

كم يجب عليك زيادته؟حسنًا، لا توجد أيضًا قيمة مثالية.الحل الأبسط هو مضاعفة السعة عند كل زيادة.لذلك يذهب إلى 200، 400، 800، وهكذا.إذا كنت تعتقد أن هذا كثير جدًا (بعد كل شيء، سيقفز من ذاكرة 8 ميجابايت إلى 16 ميجابايت عندما يصبح جدول التجزئة كبيرًا جدًا وقد لا تملأ أبدًا 16 ميجابايت)، فاختر عامل نمو أصغر.يوصى بـ 1/3 على الأقل (زيادة العدد من 100 إلى 133) أود أن أقول، ربما دعه ينمو بنسبة 50٪ في كل مرة كحل وسط.

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

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

Answer 2

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

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

Answer 3

يوجد عادةً نوعان من جداول التجزئة:مفتوحة ومغلقة.

في جدول التجزئة المفتوح، يمكنك العثور على المجموعة المناسبة بناءً على التجزئة، ثم إنشاء قائمة بالعناصر المعلقة في تلك المجموعة.

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

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

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

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

Answer 4

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

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

Answer 5

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