Introduction to Dictionaries

Dictionaries outperform lists and variables for character counting because they only allocate space for characters that actually appear, not for every possible character.

Programming

The Counting Challenge

Suppose you want to discover which letters appear most frequently in the word brontosaurus. The result should record that r, o, s, and u each appear twice, while b, n, t, and a each appear once. This task is called frequency counting. The collection of counters that records these frequencies is called a histogram.

The difficult part is not adding one to a counter. The important design decision is how to store the counters. You can use separate variables, a list, or a dictionary. All three approaches can solve the same counting problem, but they differ in how much you must know before processing the input and how much unused space they reserve.

How do variables, a list, and a dictionary represent character counts differently, and what trade-offs does each approach have?

Why Dictionaries Adapt

The first two approaches require you to decide in advance which characters might appear. For example, a design using 26 variables or a 26-element list reserves room for every letter of the alphabet, including letters that never occur in the input. A dictionary takes a different approach: it creates an entry only when a character actually appears.

This matters when the possible input is not limited to English letters. A string might include digits, punctuation, or Unicode symbols. A list-based design requires you to know the possible character range and how to map each character to a numeric position. A dictionary can use the arriving character as a key, so the counting pattern does not need a new variable or a preallocated position for every possible character.

What space is represented when the input contains only a few distinct characters?

The Two-Branch Counting Rule

The dictionary algorithm has one decision point. For each character c, check whether c is already a key in the dictionary d. If it is not present, create the key and give it the value 1. If it is already present, increment its existing value. The pattern is commonly written as if c not in d.

Code walkthrough

d = {}
for c in "brontosaurus":
    if c not in d:
        d[c] = 1
    else:
        d[c] = d[c] + 1
print(d)

1
Create an empty dictionary named d to hold the histogram.
2
Process each character c in the word.
3
Use the membership check to distinguish a first encounter from a repeated encounter.
4
Store 1 for a new character or update the existing value for a repeated character.
5
Print the completed histogram.

d starts as an empty dictionary.
The loop reads one character at a time.
A new character receives its first count, 1.
An existing character has its count increased by 1.

Output

{'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}

What do you think happens?

What dictionary will the loop contain after it processes the entire word brontosaurus?

A dictionary with one entry for every character position
A dictionary with one entry for each distinct character and its frequency
A dictionary containing only the last character
An empty dictionary because no keys were known in advance

Reveal answer

Answer:

A dictionary with one entry for each distinct character and its frequency

The dictionary creates a key the first time a character appears and increments that key on later encounters. The completed histogram is {'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}.

Reading the State Changes

The word brontosaurus contains 12 characters but only 8 unique letters. On a first encounter, the dictionary gains a new key with value 1. On a later encounter, no new key is needed; the value belonging to the existing key increases.

How does the dictionary change after each character is read, including first encounters and repeated characters?

Character read	Decision	Dictionary state
b	New key, so initialize b to 1	{'b': 1}
r	New key, so initialize r to 1	{'b': 1, 'r': 1}
o	New key, so initialize o to 1	{'b': 1, 'r': 1, 'o': 1}
r	Existing key, so increase r to 2	{'b': 1, 'r': 2, 'o': 1}
o	Existing key, so increase o to 2	{'b': 1, 'r': 2, 'o': 2}
n	New key, so initialize n to 1	{'b': 1, 'r': 2, 'o': 2, 'n': 1}

The first six processed characters show both branches of the counting rule.

How does each input character become a dictionary key, and how does its corresponding value change?

Choosing the Flexible Structure

Approach	What must be known first	How it stores counts	Main trade-off
Separate variables	The characters to count	A different counter for each planned character	Works for a fixed known set, but does not adapt naturally to unexpected characters
List	The character range and a mapping to positions	A counter at a position for each planned character	Can work for English letters, but reserves positions for letters that may not appear
Dictionary	No complete character set	A key for each character that appears and a value for its frequency	Adapts to letters, digits, punctuation, and Unicode symbols while storing only observed entries

The dictionary approach is especially useful when the possible input is unknown or broad.

A list can be a reasonable choice when you know that the input contains only English letters and you are willing to convert characters to list positions with ord(). However, that approach depends on the known character range. The dictionary pattern keeps the same counting logic when the input later changes to words, multiple languages, digits, punctuation, or other symbols.

Mistakes in Frequency Counting

Common mistake
Treating every character as new
What it looks like
Creating a new entry for r when r appears for the second time
Why it fails
Repeated characters should increase the value of the existing key rather than create another count for the same character.
Do this instead
Check if c not in d. Initialize a new key only when the character is absent; otherwise increment d[c].
Common mistake
Preallocating a fixed set when the input is broader
What it looks like
Using only alphabet positions for text that may contain digits, punctuation, or Unicode symbols
Why it fails
The design requires you to know the full range of possible characters and their positions in advance.
Do this instead
Use the character itself as a dictionary key so the dictionary can create entries as new characters appear.
Common mistake
Confusing a histogram with a graph only
What it looks like
Assuming that frequency data is a histogram only after drawing bars
Why it fails
In computing, a histogram can simply be a collection of counters.
Do this instead
Recognize the dictionary of keys and frequency values as the histogram, even when it is printed as key-value pairs.

Practice the State Trace

EASY

Trace the dictionary while processing the string "level". Write the dictionary after each character is read. Then identify which characters were initialized and which characters were incremented.

Hints

Start with an empty dictionary.
The first l, e, and v are new characters.
The second e and the second l use the existing-key branch.

Your attempt (not saved)

Worked example

Tracing level

Determine the dictionary state after each character in the string level.

1
Read l
l is new, so create the entry l: 1.
2
Read e
e is new, so create the entry e: 1.
3
Read v
v is new, so create the entry v: 1.
4
Read e again
e already exists with value 1, so increase it to 2.
5
Read l again
l already exists with value 1, so increase it to 2.

Result

{'l': 2, 'e': 2, 'v': 1}

Key Takeaways

1
Character frequency counting can use separate variables, a list, or a dictionary.
2
Variables and lists require more advance knowledge about the characters that may appear; a dictionary adapts as characters arrive.
3
The central dictionary pattern is: if a character is new, initialize its count to 1; otherwise increment its existing count.
4
A dictionary histogram stores each observed character as a key and its frequency as the corresponding value.
5
Dictionaries are especially useful when the input may include unexpected characters or when storing entries only for observed characters is preferable.

At a glance

A dictionary represents a frequency table with character keys and count values.
The if c not in d pattern distinguishes first encounters from repeated encounters.
Dictionaries store entries only for characters that actually appear, unlike a fixed collection of variables or positions.
The same approach can adapt to letters, digits, punctuation, Unicode symbols, words, and other frequency-counting tasks.

More concepts starting with I

The Counting Challenge

Why Dictionaries Adapt

The Two-Branch Counting Rule

Reading the State Changes

Choosing the Flexible Structure

Mistakes in Frequency Counting

Practice the State Trace

Key Takeaways

At a glance

Related Topics