In which scenario is it recommended to use Keyedcollection instead of a Dictionary?

Question

I didn’t know about the existence of KeyedCollection until you see this reply gypsy.

I wondered how and when to use a KeyedCollection, since there is the Dictionary which apparently has the same goal.

Answer 1

In fact the KeyedCollection is a Dictionary where you choose how to build the index.

Notice that in the example of the mentioned answer I use something like this:

public class MortoCollection : KeyedCollection<String, Morto>
{
    protected override string GetKeyForItem(Morto item)
    {
        return item.NrCpf.ToString();
    }
}

The use is practically equal to a Dictionary:

var morto = minhaCollection['12345678901'];

Using so, I return in morto the object whose property Cpf be equal to 12345678901.

When to Use?

When you want to assemble a dictionary of objects indexed by some object property. Unlike a List, where you need to use extensions to get objects by value (hence slower, since you need to iterate the items one by one to get the value), the KeyedCollection makes obtaining an element much simpler.

Answer 2

You should use in the situation you need to access the elements of this collection in O(1) (finds what you want essentially at the same time, no matter the size of the collection) either by the position of the element, or by the key. Or if you need the collection enumerated so much in order that it has been added or find an element inside it quickly.

List

In a List it is easy to maintain the data entry order and access them according to your position. A list is like a array. Just the index and you arrive at the element very quickly only with a quick calculation of the memory position. In a way we can say that the index is the key to this collection. If you try to find a value in this list will have an O(n) complexity, that is, you will have to potentially scroll through the list to find what you want.

Dictionary

In a Dictionary storage is done through functions of hash, that is, the key is calculated and gets a number that will be used to position the element in an internal structure that will store the collection. So it’s very fast to find an element by its key in almost every case. Just do the key calculation to find your "magic number" (hashcode) and there you position where the element is, do not need to go through the other elements (there are cases that need to go through some elements because there may be collision but this is another subject and I will not go into detail, in functions hash good this almost does not happen). The problem is that if you want to enumerate these elements sequentially, nothing guarantees how it comes, there is no order. And because you don’t have defined order, you can’t take an element by the added position. You cannot catch the first or last element added to the collection.

Best of worlds

To KeydCollection solve this, you can do both.

But how can he do that?

In computing everything is tradeoff. You have to choose the one that will give up to have an advantage. In this case will give up the memory. This collection holds, roughly, a List and a Dictionary internally. So it can have both characteristics. Of course it consumes more space.

One way to achieve this is to have a list that is added in order and have a table hash which has as its key what was defined in KeydCollection and its value (remember that a dictionary uses a key pair and value) is the position in the list where this element is. So you don’t have to duplicate the content in the two structures.

Of course I’m talking about a hypothetical implementation, that’s implementation detail (if you want to see how it’s actually implemented, the source is available). In an ideal situation there should be a higher optimization, especially in case the value size is smaller than the index size of the list. But I doubt this will be done.

Using the class

As can be seen in documentation of this collection, it is abstract, you cannot actually use it. One must create a derivative and overwrite a abstract method to find a key in the middle of a defined value. Being abstract, it needs a concrete implementation.

A example of concrete implementation of the class allowing it to be used in a generic way, i.e., the key is defined by an anonymous function and avoids having to derive the class whenever it needs a different criterion, which should be quite common to be different in each case when using the KeyedCollection.

Note that in this class you do not specify the key and value, as occurs in Dictionary. You specify the value of the element. The key will be obtained by any calculation defined within the class in the method GetKeyForItem(). This calculation can take the value as a whole, can take a member of the value, or can make a complex composition of what is found in the value.