ShamusP's blog

Lets start with the basics. What is a dictionary?  A dictionary provides a mapping of key, value pairs.  They allow a programmer to store a value under a key and look it up later.

A naive implementation could be done with two arrays, one to store the keys, and one to store the values.  For managing a few keys this is fine, but once the number of keys grows large enough, this will begin to suffer because a lookup will have to inspect all elements, resulting in a computation complexity of O(n).