Fundamentals of data structures: Dictionaries

From Wikibooks, open books for an open world
Jump to navigation Jump to search

PAPER 1 - ⇑ Fundamentals of data structures ⇑

← Hash tables and hashing Dictionaries Vectors →


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,
           'Charley' : 22,
           'Hwa' : 75,
           'Roxann' : 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[edit]

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[edit]

Dictionaries typically support several 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:

Operation VB.net Python 3
Retrieve
results("Nova")
results['Nova']
Insert
results.Add("Nova", 99)
results['Nova'] = 99
Delete
results.Remove("Nova")
del results['Nova']
Key existence
results.ContainsKey("Nova")
'Nova' in results
Iterate over dictionary
For Each kvp As KeyValuePair(Of String, Integer) In results
    Console.WriteLine(kvp.Key, kvp.Value)
for pupil in results:
    print(pupil, results[pupil])