Dictionaries

- Before the days of the internet, when you wanted to look up the meaning of a word, you could look it up in a dictionary like this one. This dictionary holds thousands of definitions in it, and I can find the definition I'm looking for very quickly, because I can index it using the associated word. In the programming world, dictionary is a term that's used to describe a data structure that stores a collection of key and value pairs. You might also hear words like map, simple table, or hash table, which also accomplish the same thing. Just like with a real life dictionary, I can look up values quickly by using the associated keys.

Fortunately, programming dictionaries aren't limited to just storing words and definitions. Time to invite my friends over. Now, some people might call me old fashioned, but I like to keep track of my friends' phone numbers, in my trusty old, pen and paper Rolodex. My Rolodex is just like a dictionary. Each card in my Rolodex contains a single name and the corresponding number for that person. This name and number pair is the key and value pairs that make up each entry in the dictionary. I can look up a person's phone number very quickly, because all of the cards are sorted alphabetically.

If I want to look up Olivia's phone number, I don't have to search the entire Rolodex to find her card. I flip straight to the O's, where I know her card will be, and I can find it right away. A programming dictionary uses a similar concept, so you can rapidly look up the value that corresponds to a given key. But dictionary entries are not always organized alphabetically, like my Rolodex. Instead, many languages use a method called hashing to store and retrieve dictionary values. When I want to store a key value pair in the dictionary, Python uses a hash function on the key, which is a special routine that takes the key object, and maps it to a single, mathematically calculated number.

That number is used as the index into a table to determine where the corresponding value should be stored. Later, when you want to retrieve a value you give the dictionary the key that you want to look up, and it uses the same hash function on the key to calculate the index. And then it retrieves the corresponding value from the table. When I organize the entries in my Rolodex alphabetically, I'm actually using a very simple form of hashing. For my hash function, I take the name of each entry, I extract the first letter of that name, and I use that single value as the index into my Rolodex.

Depending on the language you're working with, dictionaries might be called hashes, maps, or collections. I have the script start_08_01_rolodex open, which contains the code to create my rolodex. The rolodex is a Python dictionary, which I created by using these curly braces. Each entry in the dictionary has a key object on the left, which is the name of a person, and the corresponding value on the right, which is their phone number. When I run the script, Python will build the dictionary, using the hash function on each of those keys to determine where to store the phone numbers.

Now, I can use the interactive shell to quickly look up phone numbers for my friends. To look up Verne's phone number, I would simply access the rolodex using square brackets, and pass in Verne's name as the key. The dictionary finds the value attached to that key, and returns Verne's phone number, 5555309. As I mentioned earlier, the dictionary uses a hash function on each key to determine its index in the dictionary. If I call the Python hash function on the string Verne, we can see that it maps to this value.

When I first created the entry for Verne in my dictionary, it got stored at an index corresponding to that number. Then later, when I wanted to look up Verne's number, I passed his name as the key, the dictionary used the hash function on it, and knew right where to look to find his number. Now, time for a few phone calls.