Dictionary Efficiency

We could simulate the effect of a Dictionary pretty easily by keeping a List keys and a List values, in the same order. We could find the entry with a specified key with:

int i = keys.IndexOf(key);
return values[i];

Searching though a List, however, take time proportional to the length of the List in general, linear order. Through a clever implementation covered in data structures classes, a Dictionary uses a hash table to make the average lookup time of constant order. A hash table depends on the keys being immutable.