Dictionaries

Overview

Recall questions on key-value pairs, how a dictionary differs from an array, why it is usually built on a hash table, and the word-count algorithm.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a dictionary?

   Model answer

   A dictionary is an abstract data type built from pairs, each pairing a key with a value. Retrieval works by quoting the key rather than a numeric index or a position in the structure, so a lookup does not depend on where an item happens to sit. No key may occur twice, which is what makes a key an unambiguous handle on its value: a dictionary of exam entries keyed by candidate number returns exactly one record for 4021.

2. 2

   How does a dictionary differ from an array?

   Model answer

   An array is indexed by integers running over a fixed range and holds elements all of the same type in a definite order. A dictionary is indexed by keys, which can be of any suitable type such as strings, and there is no requirement that the keys form a continuous numeric range. Access to a dictionary is by meaningful key rather than by position.

3. 3

   How is a dictionary usually implemented, and why?

   Model answer

   Using a hash table. The key is passed through a hashing algorithm to give the position at which the value is stored, so a value can be retrieved directly from its key rather than by searching every pair. That gives lookup in constant time on average, provided collisions are rare.

4. 4

   Give five simple applications of a dictionary.

   Model answer

   Information retrieval, such as counting the occurrences of each word in a document. A translation dictionary, mapping a word in one language to a word in another. Storing configuration settings, where a setting name maps to its value. A telephone directory mapping a name to a number, and caching results of a slow calculation under the input that produced them.

5. 5

   The document 'The green, green grass grows' is to be represented as a dictionary counting how often each word occurs, ignoring letter case. Give the dictionary.

   Model answer

   {'grass': 1, 'green': 2, 'grows': 1, 'the': 1}. Each distinct word is a key and its count is the value. 'green' appears twice, so its value is 2; the other three words appear once each. 'The' and 'the' count as the same word because letter case is ignored.

6. 6

   Describe the algorithm for building a word-count dictionary from a document.

   Model answer

   Start with an empty dictionary. Read the document and split it into words, removing punctuation and converting every word to lower case so that differences of case and punctuation do not create separate keys. For each word, test whether it is already a key in the dictionary: if it is, increase its value by one; if it is not, add it as a new key with the value 1. When all the words have been processed the dictionary holds each distinct word with its number of occurrences.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.