asp.net: هل تعقيد الوقت للبحث عن قيمة عن طريق المفتاح في القاموس وقت ثابت أو Log2 (ن)؟

Question

أحتاج إلى بيانات دراسية في Dotnet حيث يمكنني البحث عن عنصر في وقت ثابت. يعني أن DataSulture يجب أن تنفذ الفهرسة داخليا. قاموس قاموس مفيد لهذا الغرض أو بعضها البعض؟

Answer 1

نعم، استخدم القاموس <> (أو hashtable إذا كنت على إصدار أقدم من .NET). تأكد من أن الكائنات التي تحشوها في القاموس لها قيمة تجزئة جيدة (انظر إلى تجاوز Gethashcode () ومساوي () لكائناتك التي تستخدمها كمفاتيح في القاموس). إذا كانت كائنات البيانات الخاصة بك لها أداء رموز التجزئة السيئة سيبدأ في التدهور. ونعم، للإجابة على سؤالك، يجب أن يكون UPS في القاموس / القاموس قد يكون وقتا ثابتا نسبيا (يقول الكتب عموما إنه س (1)، ولكن هذا قابل للجدل). سيتم تحديد أداء البحث من قبل العديد من العوامل:

1. وظيفة التجزئة (تحديد التوزيع)
2. كيف تعامل الجدول التصادمات؟ التحقيق؟ دلاء؟ (معظم التطبيقات تستخدم الدلاء).
3. هل الجدول قابل للتغيير؟ كيف يتم تغيير حجمها؟ بزيادات صغيرة؟ قوة 2؟ الأعداد الأولية؟
4. إلخ...