Fundamentals of data structures: Dictionaries

A dictionary is a general-purpose data structure for storing a group of objects. A dictionary has a set of keys and each key has a single associated value. When presented with a key, the dictionary will return the associated value.

For example, the results of a classroom test could be represented as a dictionary with pupil's names as keys and their scores as the values:

results = 'Detra' : 17, 'Nova' : 84, 'Charlie' : 22, 'Henry' : 75, 'Roxanne' : 92, 'Elsa' : 29> 

Instead of using the numerical index of the data, we can use the dictionary names to return values:

>>> results['Nova'] 84 >>> results['Elsa'] 29

A dictionary is also called a hash, a map, a hashmap in different programming languages (and an Object in JavaScript). They're all the same thing: a key-value store.

The concept of a key-value store is widely used in various computing systems, such as caches and high-performance databases.

Typically, the keys in a dictionary must be simple types (such as integers or strings) while the values can be of any type. Different languages enforce different type restrictions on keys and values in a dictionary. Dictionaries are often implemented as hash tables.

Keys in a dictionary must be unique; an attempt to create a duplicate key will typically overwrite the existing value for that key.

Note that there is a difference (which may be important) between a key not existing in a dictionary, and the key existing but with its corresponding value being null.

Differences from similar data structures

Arrays arrays and dictionaries both store collections of data, but differ by how they are accessed. Items in an array are accessed by position (often a number) and hence have an order. Items in a dictionary are accessed by key and are unordered. Sets Sets are groups of items, unordered with duplicates removed. The keys of a dictionary form a set, but each key has an associated value; these values could be duplicated within a dictionary.

Main operations on dictionaries

Dictionaries typically support different operations:

• retrieve a value (depending on language, attempting to retrieve a missing key may give a default value or throw an exception)
• insert or update a value (typically, if the key does not exist in the dictionary, the key-value pair is inserted; if the key already exists, its corresponding value is overwritten with the new one)
• remove a key-value pair
• test for existence of a key

Most programming languages with dictionaries will also support iteration over the keys or values in a dictionary. Note that items in a dictionary are unordered, so loops over dictionaries will return items in an arbitrary order.

Given a dictionary results containing the class result above, these are examples of these operations:

results("Nova") 

results['Nova'] 

results.Add("Nova", 99)