If you need a collection of objects accessed by a key, and the key is one of the object’s properties, then you should use the KeyedCollection class instead of Dictionary. For example, you would use a KeyedCollection to store Employee objects accessed by the employee’s ID property.

The KeyedCollection class is a hybrid between an IList and IDictionary. Like the IList, KeyedCollection is an indexed list of items. Like the IDictionary, KeyedCollection has a key associated with each item. But unlike dictionaries, KeyedCollection is not a collection of key/value pairs; rather, the item is the value and the key is embedded within the value. As a result, KeyedCollection provides O(1) indexed retrieval and keyed retrieval that approaches O(1), meaning that item lookup is very fast.

The KeyedCollection class is defined in the in the System.Collections.ObjectModel namespace. KeyedCollection is an abstract base class that you must override and implement the GetKeyForItem method, which extracts the key from the item.

Following is a simple console program that creates a collection of Employee objects accessed by the employee’s integer ID property:





using System;
using System.Collections.ObjectModel;

namespace KeyedCollection
{
    class Program
    {
        static void Main( string[] args )
        {
            EmployeeCollection employees =
                new EmployeeCollection();
            employees.Add( new Employee( 1, "Joe" ) );
            employees.Add( new Employee( 2, "Jim" ) );
            employees.Add( new Employee( 3, "Jane" ) );
            if (employees.Contains( 3 ))
            {
                Employee emp = employees[3];
                Console.WriteLine(
                    "Employee ID={0}, Name={1}",
                    emp.ID, emp.Name );
            }
            Console.ReadLine();
        }
    }
    class Employee
    {
        public Employee( int id, string name )
        {
            this.ID = id;
            this.Name = name;
        }
        public readonly int ID;
        public string Name;
    }
    class EmployeeCollection
        : KeyedCollection<int,Employee>
    {
        protected override int GetKeyForItem( Employee item )
        {
            return item.ID;
        }
    }
}

By default, KeyedCollection includes a lookup dictionary. When an item is added to a KeyedCollection, the item’s key is extracted and saved in the lookup dictionary for faster searches. You can override this behavior by specifying a “dictionary creation threshold” in the KeyedCollection constructor. If you specify a threshold greater than zero, the lookup dictionary is not created until the number of items reaches that threshold. If you specify –1 as the threshold, the lookup dictionary is never created. The default dictionary creation threshold is zero, meaning the dictionary is created when the first item is added. When the lookup dictionary is used, it copies the items into the dictionary, therefore it is better suited for reference types than value types due to boxing/unboxing overhead. For best efficiency, you may want to specify a dictionary creation threshold of 5-10.

Keys in a KeyedCollection must be unique and cannot be null. Notice in the example code above, the Employee’s ID property is marked “readonly,” meaning that it is immutable and cannot be changed. Typically you do not want to modify your keys, otherwise the key in the item will get out of sync with the key in the KeyedCollection. However, if you must modify a key, be sure to call the ChangeItemKey method.

Be careful when using the Contains method. For a KeyedCollection<TKey,TItem>, there is the Contains<TItem> method provided by the base Collection<T> class, and there is the Contains<TKey> method provided by the KeyedCollection class. The latter method is the correct one, meaning you should always check for the key when calling the Contains method. This is apparently by design, as stated in this Microsoft bug report.

Share and Enjoy:
  • Digg
  • Twitter
  • Facebook
  • Reddit
  • StumbleUpon
  • LinkedIn
  • Google Bookmarks
  • Slashdot