كيف يتم الحفاظ على القاموس داخليًا؟

Question

عندما أقول

Dictionary<int,string>

هل يعادل صفيفتين مختلفتين مثل:

int[] keys =new int[] { 1, 2, 3 };
string[] values=new string[]{"val1","val2","val3"};

Answer 1

هذا ليس بعيدًا جدًا. بالنظر إلى الكود المصدر في Reflector ، يبدو أن ثلاث مجموعات داخلية تستخدم:

private Entry<TKey, TValue>[] entries;
private KeyCollection<TKey, TValue> keys;
private ValueCollection<TKey, TValue> values;

لاحظ أن هناك أيضًا ملف int[] buckets متغير لتتبع دلاء مطلوب في حالة تصادمات ترميز التجزئة.

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

Answer 2

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

التعقيد الخوارزمي للقاموس (علامة التصنيف) هو O (1) وفي أسوأ الحالات O (السجل (N)) (أسوأ حالة يعني أننا نتعامل فقط مع التصادمات) ، حيث N هو عدد من العناصر في القاموس.

Answer 3

كل شيء مكتوب بوضوح MSDN:

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

Answer 4

لا ، إنه جدول التجزئة. حسنًا ، إنه ليس بالضبط جدول التجزئة ، لكنه يرتبط ارتباطًا وثيقًا.

http://en.wikipedia.org/wiki/hash_table.

http://www.kirupa.com/net/dictionary_hashtable.htm