لماذا يتم ترتيب الإدخالات بالإضافة إلى ذلك في قاموس .Net؟

Question

لقد رأيت هذا السلوك للتو وأذهلتني قليلاً ...

إذا أضفت 3 أو 4 عناصر إلى قاموس، ثم قمت بإجراء "لكل" للحصول على جميع المفاتيح، فإنها تظهر بنفس الترتيب الذي أضفتها إليه.

السبب الذي أدهشني هو أنه من المفترض أن يكون القاموس عبارة عن HashTable داخليًا، لذلك توقعت أن تظهر الأشياء بأي ترتيب (مرتبة حسب تجزئة المفتاح، أليس كذلك؟)

ما الذي أفتقده هنا؟هل هذا سلوك يمكنني الاعتماد عليه؟

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

Answer 1

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

add 1
add 2
add 3
add 4
remove 2
add 5

ستعود 1 5 3 4 لأنها تعيد استخدام الفتحات الفارغة.

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

Answer 2

يقوم القاموس باسترداد العناصر بترتيب مجزأ.حقيقة أنهم خرجوا بترتيب الإدراج كانت محض صدفة.

تقول وثائق MSDN:

ترتيب المفاتيح في KeyCollection غير محدد، ولكنه نفس ترتيب القيم المرتبطة في ValueCollection التي يتم إرجاعها بواسطة خاصية القيم.

Answer 3

لا يمكنك الاعتماد على هذا السلوك، لكنه ليس مفاجئا.

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

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

Answer 4

أعتقد أن هذا يأتي من .NET 1.1 القديم حيث كان لديك نوعان من القواميس "ListDictionary" و"HybridDictionary". ListDictionary كان قاموسًا تم تنفيذه داخليًا كقائمة مرتبة وتمت التوصية به لـ "مجموعات صغيرة من الإدخالات".ثم كان لديك قاموس هجين, ، تم تنظيمها في البداية داخليًا كقائمة، ولكن إذا أصبحت أكبر من الحد القابل للتكوين فإنها ستصبح جدول تجزئة.وقد تم ذلك لأن القواميس القائمة على التجزئة المناسبة تاريخياً كانت تعتبر باهظة الثمن.في هذه الأيام، لا يبدو هذا منطقيًا، ولكن أعتقد أن .NET يعتمد فقط على فئة القاموس العامة الجديدة الخاصة به على HybridDictionary القديم.

ملحوظة:على أية حال، كما أشار شخص آخر بالفعل، يجب عليك ذلك أبداً الاعتماد على ترتيب القاموس لأي شيء

Answer 5

إقتباس من MSDN :

ترتيب المفاتيح في القاموس <(من <(tkey ، tvalue>)>). KeyCollection غير محدد ، ولكنه نفس ترتيب القيم المرتبطة في القاموس <(من <(tkeke ، tvalue>)>) .valueCollection التي تم إرجاعها بواسطة القاموس <(من <(tkey ، tvalue>)>).

Answer 6

ما هي المفاتيح التي أضفتها في الاختبار، وبأي ترتيب؟

Answer 7

قد تكون جميع إدخالاتك موجودة في نفس مجموعة التجزئة في القاموس.من المحتمل أن تكون كل مجموعة عبارة عن قائمة بالإدخالات الموجودة في المجموعة.هذا من شأنه أن يفسر عودة الإدخالات بالترتيب.

Answer 8

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

Answer 9

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

أضف 100 أو 1000 عنصر ومعرفة ما إذا كانت لا تزال بنفس الترتيب.

Answer 10

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

يحرر:يبدو أن الحل هو استخدام SortedDictionary، الذي يتصرف بشكل مشابه لـ std::map.

Answer 11

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

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

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