Using KeyedCollection<> instead of a Dictionary<>

October 23, 2013

one comment

The System.Collections.Generic.Dictionary<TKey, TValue> class is one of the most useful of all .NET collections. It maps a key to a value, and allows for fast retrieval based on the key, as it’s implemented as a hash table, calling GetHashCode on the key object to get to a specific “bucket”, and then looks up the actual value (with Object.Equals or a specific IEqualityComparer<Tkey>.Equals).

One feature that Dictionary<> doesn’t support is the ability to access items by integer index. That is, insertion order is not maintained. For most cases, this may be ok, but some cases require fast search and index based access.

Some values contain the keys themselves. Here’s a simple Customer class:

  1. class Customer {
  2.     public int Id { get; set; }
  3.     public string Name { get; set; }
  4.     public string Address { get; set; }
  5. }

Let’s suppose that the Id of a Customer is unique, and so can serve as a key. Here’s a dictionary of such customers:

  1. var customers = new Dictionary<int, Customer>();
  2. customers.Add(1, new Customer { Id = 1, Name = "Bart Simpson" });
  3. customers.Add(20, new Customer { Id = 20, Name = "Homer Simpson" });

This seems harmless enough, but notice that the key (Id) is supplied twice. This may not seem like a big deal, but the key could be a more complex entity. It’s also not as elegant as we would like. I’d rather just use code like the following:

  1. customers.Add(new Customer { Id = 1, Name = "Bart Simpson" });

And get the same result, that is, the Id is still a key to search by. Dictionary<> cannot take that syntax. Enter KeyedCollection<>.

KeyedCollection<TKey, TValue> is an abstract base class that inherits from Collection<TValue>, thus giving it index-based access. A requirement is that the key is somewhere inside the value, or connected to the value, as is the case with our Customer class. The only question remains is how to return a key based on a value?

This is why we need a new class, extending KeyedCollection<> and overriding a single abstract method, GetKeyForItem:

  1. class CustomerCollection : KeyedCollection<int, Customer> {
  2.     protected override int GetKeyForItem(Customer item) {
  3.         return item.Id;
  4.     }
  5. }

This says that given a Customer, its key is its Id. Now we can use this class as follows:

  1. var customers = new CustomerCollection();
  2. customers.Add(new Customer { Id = 1, Name = "Bart Simpson" });
  3. customers.Add(new Customer { Id = 20, Name = "Homer Simpson" });

We just add Customer objects, and internally they are keyed by Id. The Add method used is the one from Collection<TValue>. This means, we can also access customers by index, or search using the Contains method.

As an extra bonus, the KeyedCollection<> can be configured to not create an internal Dictionary<>, depending on the number of items. For a small number of items, Dictionary<> is an overkill, and a linear search is faster. By default, a Dictionary is created upon first insertion, but this can be configured by using one of KeyedCollection<>’s constructors.

The idea of mapping a value to a key as was done in GetKeyForItem can be generalized, so that we don’t have to create new classes for new types. Here’s a generalized class that uses a delegate to execute the required code in GetKeyForItem:

  1. [Serializable]
  2. public sealed class GenericKeyedCollection<TKey, TValue> : KeyedCollection<TKey, TValue> {
  3.     Func<TValue, TKey> _itemKey;
  4.  
  5.     public GenericKeyedCollection(Func<TValue, TKey> itemKey, IEqualityComparer<TKey> comparer = null, int threshold = 0)
  6.         : base(comparer, threshold) {
  7.         if(itemKey == null)
  8.             throw new ArgumentNullException("itemKey");
  9.         _itemKey = itemKey;
  10.  
  11.     }
  12.  
  13.     protected override TKey GetKeyForItem(TValue item) {
  14.         return _itemKey(item);
  15.     }
  16. }

With this class in hand, we can create a Customer collection like so:

  1. var customers = new GenericKeyedCollection<int, Customer>(c => c.Id);

Pretty neat.

Add comment
facebook linkedin twitter email

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

one comment

  1. AlexApril 20, 2017 ב 14:26

    This is pragmatic !

    Reply