جدول 7-1 — Classهای Dictionary

در Big-O Notation، زمان Retrieval براساس Key چنین است:

• O(1) برای Hashtable، Dictionary و OrderedDictionary.
• O(log n) برای SortedDictionary و SortedList.
• O(n) برای ListDictionary و Typeهای غیرDictionary مانند List<T>.

n تعداد Elementهای Collection است.

IDictionary<TKey,TValue>

IDictionary<TKey,TValue> Protocol استاندارد را برای تمام Collectionهای مبتنی بر Key/Value تعریف می‌کند. این Interface، ICollection<T> را با افزودن Methodها و Propertyهایی برای دسترسی به Elementها براساس Key از هر Type گسترش می‌دهد:

public interface IDictionary <TKey, TValue> :
  ICollection <KeyValuePair <TKey, TValue>>, IEnumerable
{
   bool ContainsKey (TKey key);
   bool TryGetValue (TKey key, out TValue value);
   void Add         (TKey key, TValue value);
   bool Remove      (TKey key);
   TValue this [TKey key]      { get; set; }  // Main indexer - by key
   ICollection <TKey> Keys     { get; }       // Returns just keys
   ICollection <TValue> Values { get; }       // Returns just values
}

Interface دیگری با نام IReadOnlyDictionary<TKey,TValue> نیز وجود دارد که Subset فقط‌خواندنی Memberهای Dictionary را تعریف می‌کند.

برای افزودن Item به Dictionary، یا Add را فراخوانی می‌کنید یا از Set Accessor مربوط به Indexer استفاده می‌کنید. دومی اگر Key از قبل وجود نداشته باشد Item را اضافه می‌کند و اگر وجود داشته باشد Item را Update می‌کند. Duplicate Key در تمام پیاده‌سازی‌های Dictionary ممنوع است؛ بنابراین فراخوانی دوبارهٔ Add با همان Key Exception پرتاب می‌کند.

برای Retrieval یک Item از Dictionary، از Indexer یا Method با نام TryGetValue استفاده کنید. اگر Key وجود نداشته باشد، Indexer Exception پرتاب می‌کند، درحالی‌که TryGetValue مقدار false برمی‌گرداند. می‌توانید با ContainsKey Membership را صریحاً Test کنید؛ بااین‌حال، اگر بعد از آن Item را Retrieve کنید، هزینهٔ دو Lookup را متحمل می‌شوید.

Enumerate کردن مستقیم روی IDictionary<TKey,TValue> Sequenceای از Structهای KeyValuePair برمی‌گرداند:

public struct KeyValuePair <TKey, TValue>
{
  public TKey Key     { get; }
  public TValue Value { get; }
}

با Propertyهای Keys و Values می‌توانید فقط Keyها یا فقط Valueها را Enumerate کنید.

در بخش بعد، استفاده از این Interface را با Class Generic با نام Dictionary نشان می‌دهیم.

IDictionary

Interface غیرGeneric با نام IDictionary در اصل همان مفهوم IDictionary<TKey,TValue> را دارد، با دو تفاوت Functionality مهم. آگاهی از این تفاوت‌ها مهم است، چون IDictionary در کد Legacy — و حتی در بخش‌هایی از BCL خود .NET — دیده می‌شود:

• Retrieval یک Key ناموجود از طریق Indexer مقدار null برمی‌گرداند، به‌جای اینکه Exception پرتاب کند.
• Contains Membership را Test می‌کند، نه ContainsKey.

Enumerate کردن یک IDictionary غیرGeneric، Sequenceای از Structهای DictionaryEntry برمی‌گرداند:

public struct DictionaryEntry
{
  public object Key   { get; set; }
  public object Value { get; set; }
}

Dictionary<TKey,TValue> و Hashtable

Class Generic با نام Dictionary، همراه با Collection با نام List<T>، یکی از پرکاربردترین Collectionهاست. برای ذخیرهٔ Keyها و Valueها از Data Structure با نام Hashtable استفاده می‌کند و سریع و کارآمد است.

نسخهٔ Nongeneric از Dictionary<TKey,TValue> با نام Hashtable شناخته می‌شود؛ هیچ Class غیرGeneric با نام Dictionary وجود ندارد. هرجا صرفاً از Dictionary صحبت می‌کنیم، منظور Class Generic با نام Dictionary<TKey,TValue> است.

Dictionary هم Interface Generic و هم Nongeneric با نام IDictionary را پیاده‌سازی می‌کند و نسخهٔ Generic به‌شکل Public ارائه می‌شود. در واقع، Dictionary یک پیاده‌سازی «کتاب‌درسی» از IDictionary Generic است.

نمونهٔ استفاده:

var d = new Dictionary<string, int>();
d.Add("One", 1);
d["Two"] = 2;     // adds to dictionary because "two" isn't already present
d["Two"] = 22;    // updates dictionary because "two" is now present
d["Three"] = 3;
Console.WriteLine (d["Two"]);                // Prints "22"
Console.WriteLine (d.ContainsKey ("One"));   // true (fast operation)
Console.WriteLine (d.ContainsValue (3));     // true (slow operation)
int val = 0;
if (!d.TryGetValue ("onE", out val))
  Console.WriteLine ("No val");              // "No val" (case sensitive)
// Three different ways to enumerate the dictionary:
foreach (KeyValuePair<string, int> kv in d)          //  One; 1
  Console.WriteLine (kv.Key + "; " + kv.Value);      //  Two; 22
                                                     //  Three; 3
foreach (string s in d.Keys) Console.Write (s);      // OneTwoThree
Console.WriteLine();
foreach (int i in d.Values) Console.Write (i);       // 1223

Hashtable زیرین با تبدیل Key هر Element به یک Integer Hashcode — یک Value شبه‌یکتا — و سپس اعمال Algorithmی برای تبدیل Hashcode به Hash Key کار می‌کند. این Hash Key در داخل تعیین می‌کند Entry در کدام «Bucket» قرار گیرد. اگر Bucket بیش از یک Value داشته باشد، Linear Search روی آن Bucket انجام می‌شود. Hash Function خوب تلاش نمی‌کند Hashcodeهای کاملاً یکتا بدهد — که معمولاً ناممکن است — بلکه تلاش می‌کند Hashcodeها را در فضای Integer 32-bit به‌طور یکنواخت پخش کند. این کار مانع شکل‌گیری چند Bucket بسیار بزرگ و ناکارآمد می‌شود.

Dictionary می‌تواند با Key از هر Type کار کند، به‌شرط آنکه بتواند Equality بین Keyها را تعیین و Hashcode آن‌ها را به دست آورد. به‌صورت پیش‌فرض، Equality از Method با نام object.Equals مربوط به Key و Hashcode شبه‌یکتا از Method با نام GetHashCode مربوط به Key به دست می‌آید.

می‌توانید این رفتار را با Override کردن این Methodها یا با ارائهٔ Object از نوع IEqualityComparer هنگام ساخت Dictionary تغییر دهید. کاربرد رایج، تعیین Equality Comparer غیرحساس به Case هنگام استفاده از String Keyهاست:

var d = new Dictionary<string, int> (StringComparer.OrdinalIgnoreCase);

این موضوع در بخش «Plugging in Equality and Order» در صفحهٔ 411 بیشتر بررسی می‌شود.

همانند بسیاری از انواع دیگر Collection، می‌توانید Performance مربوط به Dictionary را کمی بهتر کنید؛ کافی است Size مورد انتظار Collection را در Constructor مشخص کنید تا نیاز به Operationهای Resize داخلی حذف یا کمتر شود.

نسخهٔ Nongeneric با نام Hashtable شناخته می‌شود و از نظر Functionality مشابه است، جز تفاوت‌هایی که از ارائهٔ Interface غیرGeneric با نام IDictionary ناشی می‌شود و پیش‌تر توضیح داده شد.

نقطه‌ضعف Dictionary و Hashtable این است که Itemها Sort نیستند. علاوه بر این، Order اولیه‌ای که Itemها با آن اضافه شده‌اند حفظ نمی‌شود. مانند همهٔ Dictionaryها، Duplicate Key مجاز نیست.

وقتی Generic Collectionها در سال 2005 معرفی شدند، تیم CLR نام آن‌ها را براساس چیزی که نمایندگی می‌کنند — Dictionary و List — انتخاب کرد، نه نحوهٔ پیاده‌سازی داخلی — Hashtable و ArrayList. این از یک جهت خوب است، چون آزادی تغییر پیاده‌سازی در آینده را می‌دهد؛ اما از سوی دیگر، Performance Contract که اغلب مهم‌ترین معیار انتخاب نوع Collection است دیگر در Name منعکس نمی‌شود.

OrderedDictionary

OrderedDictionary یک Dictionary غیرGeneric است که Elementها را در همان Orderای نگه می‌دارد که اضافه شده‌اند. با OrderedDictionary می‌توانید Elementها را هم براساس Index و هم Key دسترسی دهید.

OrderedDictionary یک Sorted Dictionary نیست.

OrderedDictionary ترکیبی از Hashtable و ArrayList است. بنابراین تمام Functionality مربوط به Hashtable، به‌علاوهٔ Functionهایی مانند RemoveAt و یک Integer Indexer را دارد. همچنین Propertyهای Keys و Values را ارائه می‌کند که Elementها را در Order اولیهٔ آن‌ها برمی‌گردانند.

این Class در .NET 2.0 معرفی شد؛ بااین‌حال، به‌طور عجیب نسخهٔ Generic ندارد.

¹ نسخهٔ Nongeneric و از نظر Functionality یکسانی نیز وجود دارد که SortedList نام دارد.

ListDictionary و HybridDictionary

ListDictionary از یک Singly Linked List برای ذخیرهٔ Data زیرین استفاده می‌کند. Sorting ارائه نمی‌کند، اما Order اولیهٔ Entryها را حفظ می‌کند.

ListDictionary برای Listهای بزرگ بسیار کند است. تنها «ادعای شهرت» واقعی آن Efficiency برای Listهای بسیار کوچک — کمتر از 10 Item — است.

HybridDictionary یک ListDictionary است که وقتی به Size مشخصی می‌رسد به‌طور خودکار به Hashtable تبدیل می‌شود تا مشکل Performance مربوط به ListDictionary را حل کند. ایده این است که وقتی Dictionary کوچک است Memory Footprint پایین و وقتی بزرگ است Performance خوب داشته باشیم. بااین‌حال، با توجه به Overhead تبدیل از یکی به دیگری و این واقعیت که Dictionary در هیچ‌یک از این دو Scenario بیش از حد سنگین یا کند نیست، اگر از ابتدا Dictionary استفاده کنید هزینهٔ غیرمنطقی نخواهید داشت.

هر دو Class فقط در فرم Nongeneric وجود دارند.

Sorted Dictionaryها

BCL دات‌نت دو Dictionary Class فراهم می‌کند که Structure داخلی آن‌ها طوری است که Content همیشه براساس Key Sort می‌شود:

• SortedDictionary<TKey,TValue>
• SortedList<TKey,TValue>¹

در این بخش، <TKey,TValue> را به‌صورت کوتاه <,> می‌نویسیم.

SortedDictionary<,> از Red/Black Tree استفاده می‌کند؛ Data Structureای که برای Performance پایدار و خوب در هر Scenario مربوط به Insertion یا Retrieval طراحی شده است.

SortedList<,> در داخل با یک جفت Array مرتب‌شده پیاده‌سازی می‌شود و Retrieval سریع — با Binary-chop Search — ولی Performance ضعیف در Insertion دارد، چون Valueهای موجود باید Shift شوند تا برای Entry جدید جا باز شود.

SortedDictionary<,> در Insert کردن Elementها با Sequence تصادفی، به‌ویژه در Listهای بزرگ، بسیار سریع‌تر از SortedList<,> است. بااین‌حال، SortedList<,> قابلیت اضافه‌ای دارد: می‌توان Itemها را علاوه بر Key براساس Index نیز دسترسی داد. با Sorted List می‌توانید از طریق Indexer روی Propertyهای Keys/Values مستقیماً به Element شمارهٔ n در Sorting Sequence بروید. برای انجام همان کار با SortedDictionary<,> باید n Item را دستی Enumerate کنید. راه دیگر این است که Classی بنویسید که Sorted Dictionary را با List Class ترکیب کند.

هیچ‌یک از این سه Collection Duplicate Key را مجاز نمی‌داند؛ همان‌طور که برای همهٔ Dictionaryها صدق می‌کند.

مثال زیر با Reflection تمام Methodهای تعریف‌شده در System.Object را در Sorted Listای Load می‌کند که براساس Name Key شده است و سپس Keyها و Valueها را Enumerate می‌کند:

// MethodInfo is in the System.Reflection namespace
var sorted = new SortedList <string, MethodInfo>();
foreach (MethodInfo m in typeof (object).GetMethods())
  sorted [m.Name] = m;
foreach (string name in sorted.Keys)
  Console.WriteLine (name);
foreach (MethodInfo m in sorted.Values)
  Console.WriteLine (m.Name + " returns a " + m.ReturnType);

Result مربوط به نخستین Enumeration:

Equals
GetHashCode
GetType
ReferenceEquals
ToString

Result مربوط به Enumeration دوم:

Equals returns a System.Boolean
GetHashCode returns a System.Int32
GetType returns a System.Type
ReferenceEquals returns a System.Boolean
ToString returns a System.String

توجه کنید Dictionary را از طریق Indexer پر کردیم. اگر به‌جای آن از Add استفاده می‌کردیم Exception رخ می‌داد، زیرا Class با نام object که روی آن Reflection می‌کنیم Method با نام Equals را Overload کرده است و نمی‌توانید یک Key را دوبار به Dictionary اضافه کنید. با استفاده از Indexer، Entry بعدی Entry قبلی را Overwrite می‌کند و این Error رخ نمی‌دهد.

می‌توانید چند Member با یک Key مشترک ذخیره کنید، اگر هر Value Element را یک List قرار دهید:
SortedList <string, List<MethodInfo>>

در ادامهٔ مثال، کد زیر MethodInfoای را Retrieve می‌کند که Key آن GetHashCode است؛ درست مانند Dictionary معمولی:

Console.WriteLine (sorted ["GetHashCode"]);      // Int32 GetHashCode()

تا اینجا تمام کارهایی که انجام دادیم با SortedDictionary<,> هم کار می‌کرد. اما دو Line زیر که آخرین Key و Value را Retrieve می‌کنند فقط با Sorted List کار می‌کنند:

Console.WriteLine (sorted.Keys  [sorted.Count - 1]);            // ToString
Console.WriteLine (sorted.Values[sorted.Count - 1].IsVirtual);  // True

Collectionهای قابل سفارشی‌سازی و Proxyها

Collection Classهایی که در بخش‌های قبلی توضیح داده شدند از این نظر راحت‌اند که می‌توانید مستقیماً از آن‌ها Instance بسازید، اما اجازه نمی‌دهند کنترل کنید هنگام Add یا Remove شدن Item چه اتفاقی بیفتد. در Applicationهایی با Strongly Typed Collectionها، گاهی به چنین کنترلی نیاز دارید؛ مثلاً:

• Fire کردن Event هنگام Add یا Remove شدن Item.
• Update کردن Propertyها در نتیجهٔ Item اضافه‌شده یا حذف‌شده.
• تشخیص Operation «غیرمجاز» Add/Remove و پرتاب Exception، مثلاً وقتی Operation یک Business Rule را نقض می‌کند.

BCL دات‌نت در Namespace با نام System.Collections.ObjectModel Collection Classهایی دقیقاً برای این هدف فراهم می‌کند. این‌ها اساساً Proxy یا Wrapperهایی هستند که IList<T> یا IDictionary<,> را با Forward کردن Methodها به Collection زیرین پیاده‌سازی می‌کنند. هر Operation از نوع Add، Remove یا Clear از طریق Virtual Methodای Route می‌شود که در صورت Override شدن نقش «Gateway» را دارد.

Customizable Collection Classها معمولاً برای Collectionهایی استفاده می‌شوند که به‌صورت Public در معرض قرار می‌گیرند؛ برای مثال Collection مربوط به Controlهایی که روی Class با نام System.Windows.Form به‌صورت Public ارائه می‌شود.

Collection<T> و CollectionBase

Class با نام Collection<T> یک Wrapper قابل سفارشی‌سازی برای List<T> است.

علاوه بر پیاده‌سازی IList<T> و IList، چهار Virtual Method اضافه و یک Protected Property تعریف می‌کند:

public class Collection<T> :
  IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
{
   // ...
   protected virtual void ClearItems();
   protected virtual void InsertItem (int index, T item);
   protected virtual void RemoveItem (int index);
   protected virtual void SetItem (int index, T item);
   protected IList<T> Items { get; }
}

Virtual Methodها Gatewayی فراهم می‌کنند که می‌توانید از طریق آن به رفتار عادی List «Hook» شوید و آن را تغییر یا توسعه دهید. Protected Property با نام Items اجازه می‌دهد Implementer مستقیماً به «Inner List» دسترسی داشته باشد؛ این قابلیت برای اعمال تغییرات داخلی بدون Fire شدن Virtual Methodها استفاده می‌شود.

لازم نیست Virtual Methodها را Override کنید؛ می‌توان آن‌ها را تا زمانی که نیاز به تغییر رفتار Default List نباشد دست‌نخورده گذاشت. مثال بعدی استفادهٔ «Skeleton» معمول از Collection<T> را نشان می‌دهد:

Zoo zoo = new Zoo();
zoo.Animals.Add (new Animal ("Kangaroo", 10));
zoo.Animals.Add (new Animal ("Mr Sea Lion", 20));
foreach (Animal a in zoo.Animals) Console.WriteLine (a.Name);
public class Animal
{
  public string Name;
  public int Popularity;
  public Animal (string name, int popularity)
  {
    Name = name; Popularity = popularity;
  }
}
public class AnimalCollection : Collection <Animal>
{
  // AnimalCollection is already a fully functioning list of animals.
  // No extra code is required.
}
public class Zoo   // The class that will expose AnimalCollection.
{                  // This would typically have additional members.
  public readonly AnimalCollection Animals = new AnimalCollection();
}

در وضعیت فعلی، AnimalCollection از نظر Functionality چیزی بیش از یک List<Animal> ساده نیست؛ نقش آن فراهم‌کردن Base برای Extensionهای آینده است. برای نشان‌دادن این موضوع، اکنون Property با نام Zoo را به Animal اضافه می‌کنیم تا به Zooای که Animal در آن زندگی می‌کند Reference دهد و سپس هر یک از Virtual Methodهای Collection<Animal> را Override می‌کنیم تا این Property به‌طور خودکار نگهداری شود:

public class Animal
{
  public string Name;
  public int Popularity;
  public Zoo Zoo { get; internal set; }
  public Animal(string name, int popularity)
  {
    Name = name; Popularity = popularity;
  }
}
public class AnimalCollection : Collection <Animal>
{
  Zoo zoo;
  public AnimalCollection (Zoo zoo) { this.zoo = zoo; }
  protected override void InsertItem (int index, Animal item)
  {
    base.InsertItem (index, item);
    item.Zoo = zoo;
  }

  protected override void SetItem (int index, Animal item)
  {
    base.SetItem (index, item);
    item.Zoo = zoo;
  }
  protected override void RemoveItem (int index)
  {
    this [index].Zoo = null;
    base.RemoveItem (index);
  }
  protected override void ClearItems()
  {
    foreach (Animal a in this) a.Zoo = null;
    base.ClearItems();
  }
}
public class Zoo
{
  public readonly AnimalCollection Animals;
  public Zoo() { Animals = new AnimalCollection (this); }
}

Collection<T> همچنین Constructorای دارد که IList<T> موجود را می‌پذیرد. برخلاف سایر Collection Classها، List ارائه‌شده به‌جای Copy شدن Proxy می‌شود؛ یعنی تغییرات بعدی در List زیرین در Wrapper از نوع Collection<T> هم دیده می‌شوند، هرچند Virtual Methodهای Collection<T> Fire نمی‌شوند. برعکس، تغییراتی که از طریق Collection<T> اعمال شوند List زیرین را تغییر می‌دهند.

CollectionBase

CollectionBase نسخهٔ Nongeneric از Collection<T> است. بیشتر همان Featureها را ارائه می‌کند، اما استفاده از آن دست‌وپاگیرتر است. به‌جای Template Methodهای InsertItem، RemoveItem، SetItem و ClearItem، CollectionBase Methodهای «Hook» دارد که تعداد Methodهای لازم را دو برابر می‌کند: OnInsert، OnInsertComplete، OnSet، OnSetComplete، OnRemove، OnRemoveComplete، OnClear و OnClearComplete. چون CollectionBase غیرGeneric است، هنگام Subclass کردن آن باید Typed Methodها را نیز پیاده‌سازی کنید؛ دست‌کم یک Typed Indexer و Method با نام Add.

KeyedCollection<TKey,TItem> و DictionaryBase

KeyedCollection<TKey,TItem> از Collection<TItem> Subclass می‌شود و هم Functionality اضافه می‌کند و هم کم می‌کند. چیزی که اضافه می‌کند، قابلیت دسترسی به Itemها براساس Key است، شبیه Dictionary. چیزی که کم می‌کند، قابلیت Proxy کردن Inner List دلخواه خودتان است.

Keyed Collection تا حدی شبیه OrderedDictionary است، چون Linear List را با Hashtable ترکیب می‌کند. اما برخلاف OrderedDictionary، IDictionary را پیاده‌سازی نمی‌کند و Concept مربوط به Key/Value Pair را ندارد. Keyها در عوض از خود Itemها، از طریق Abstract Method با نام GetKeyForItem، به دست می‌آیند.

این موضوع یعنی Enumerate کردن یک Keyed Collection درست مانند Enumerate کردن یک List معمولی است.

بهترین تصور از KeyedCollection<TKey,TItem> این است: Collection<TItem> به‌علاوهٔ Lookup سریع براساس Key.

چون Keyed Collection از Collection<> Subclass می‌شود، تمام Functionality آن را به ارث می‌برد، جز امکان تعیین یک List موجود در Construction. Memberهای اضافه‌ای که تعریف می‌کند عبارت‌اند از:

public abstract class KeyedCollection <TKey, TItem> : Collection <TItem>
{
  // ...
  protected abstract TKey GetKeyForItem(TItem item);
  protected void ChangeItemKey(TItem item, TKey newKey);
  // Fast lookup by key - this is in addition to lookup by index.
  public TItem this[TKey key] { get; }
  protected IDictionary<TKey, TItem> Dictionary { get; }
}

GetKeyForItem همان Methodی است که Implementer آن را Override می‌کند تا Key یک Item را از Object زیرین به دست آورد. اگر Key Property مربوط به Item تغییر کند، باید ChangeItemKey فراخوانی شود تا Dictionary داخلی Update شود. Property با نام Dictionary Dictionary داخلی مورد استفاده برای Lookup را برمی‌گرداند؛ این Dictionary هنگام افزودن اولین Item ساخته می‌شود. می‌توان این رفتار را با تعیین Creation Threshold در Constructor تغییر داد و ساخت Dictionary داخلی را تا رسیدن به Threshold به تأخیر انداخت؛ در این فاصله، اگر Item براساس Key درخواست شود Linear Search انجام می‌شود. یک دلیل خوب برای تعیین‌نکردن Creation Threshold این است که داشتن Dictionary معتبر برای گرفتن ICollection<> از Keyها از طریق Property با نام Keys در Dictionary مفید است. سپس می‌توان این Collection را به یک Public Property منتقل کرد.

رایج‌ترین کاربرد KeyedCollection<,> فراهم‌کردن Collectionی از Itemهاست که هم براساس Index و هم Name قابل دسترسی باشند. برای نمایش این موضوع دوباره به مثال Zoo برمی‌گردیم و این بار AnimalCollection را به‌صورت KeyedCollection<string, Animal> پیاده‌سازی می‌کنیم:

public class Animal
{
  string name;
  public string Name
  {
    get { return name; }
    set {
      if (Zoo != null) Zoo.Animals.NotifyNameChange (this, value);
      name = value;
    }
  }
  public int Popularity;
  public Zoo Zoo { get; internal set; }