Skip to content
Tutorials Center
My learning

Topics

Lesson 55 of 225 ยท Hashing

Dictionaries and Sets in Practice

Use Python dictionaries and sets like a pro: operation costs, get, setdefault, defaultdict, Counter, set algebra, insertion order and the traps that cause bugs.

You now know how a hash table works inside, how it handles collisions and why keys must be hashable. This lesson is about using the finished product: Python's dict and set, which are hash tables you will reach for in most programs and in most interview problems.

The goal is fluency. You will learn what each operation costs, the idioms that replace clumsy if key in d code, the collections helpers (defaultdict, Counter), set algebra, and the handful of surprises that trip up beginners and experienced programmers alike.

Dictionaries: the essentials

A dictionary maps unique keys to values. A set is the same structure with keys only: it stores unique items and answers "is this in here?" quickly.

TEXT
dict:  {"ann": 31, "bo": 25}          set:  {"ann", "bo"}
        key -> value                         key only
Operation Example Average time Worst case
Read / write one key d[k], d[k] = v O(1) O(n)
Membership k in d O(1) O(n)
Delete del d[k], d.pop(k) O(1) O(n)
Length len(d) O(1) O(1)
Iterate for k in d O(n) O(n)
Copy d.copy() O(n) O(n)

The worst case happens only when many keys collide, which a decent hash function and automatic resizing make extremely rare. In practice, treat these operations as O(1). Sets have the same costs.

Python Everyday dictionary operations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Use get when a missing key is normal, and [] when a missing key would be a bug (the KeyError then alerts you).

Counting and grouping idioms

Two jobs account for most dictionary code: counting things and grouping things. Here is counting the letters of a word four ways, from clumsy to clean.

Python Four ways to count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four give the same answer. Counter also supports arithmetic (c1 + c2, c1 - c2) and most_common(k), which you will use in hashing patterns for anagram and top-k problems.

Grouping means building key -> list of items. The naive version has to create the list on first sight of a key. defaultdict(list) and setdefault do it for you:

Python Grouping with defaultdict and setdefault

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Watch out: defaultdict inserts the key as soon as you read it. Checking d["x"] to see whether something exists adds "x" with an empty value. Use "x" in d or d.get("x") for pure lookups.

Sets and set algebra

Use a set whenever you only care about membership or uniqueness. Sets also support mathematical operations, each of which is one line instead of a loop.

TEXT
A = {1, 2, 3, 4}      B = {3, 4, 5}

A | B  union          {1, 2, 3, 4, 5}
A & B  intersection   {3, 4}
A - B  difference     {1, 2}
A ^ B  symmetric diff {1, 2, 5}
Python Set algebra and de-duplication

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only hashable items can go in a set, and elements are stored once. For a set of sets use frozenset. Empty braces {} make an empty dict; write set() for an empty set.

Why membership tests matter: list versus set

Checking x in my_list compares x against items one by one, O(n). Checking x in my_set hashes once and looks in one bucket, O(1) on average. For a loop that checks every item of one collection against another, that is the difference between O(nยทm) and O(n + m).

Python Counting comparisons: list scan versus set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The list version needs 200 ร— 200 = 40,000 comparisons because nothing matches, so every scan runs to the end. The set version needs 200 lookups plus 200 steps to build the set. This "put it in a set first" move is the heart of most hashing patterns.

Ordering rules

  • Dictionaries keep insertion order (guaranteed since Python 3.7). Updating an existing key keeps its position; deleting and re-inserting moves it to the end. Two dicts with the same pairs are equal even when ordered differently.
  • Sets have no order you can rely on. The order depends on hash values, and string hashes change between runs, so always sorted(...) a set before displaying or comparing the output.
Python Order in dicts and sets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Mutating while iterating

Adding or removing keys while looping over a dictionary (or set) raises RuntimeError, because the table may resize under the loop. The fix is to loop over a copy of the keys, or to build a new dictionary.

Python Changing a dict during iteration (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Updating the values of existing keys while iterating is safe; only changing the set of keys is not.

Choosing between dict, set, list and Counter

You need Use
Look up a value by key dict
Only check membership or uniqueness set
Count occurrences Counter
Group items by key defaultdict(list)
Keep order and index by position list
Keep insertion order and remove duplicates dict.fromkeys(items)
An immutable set as a key frozenset

Common mistakes

  • Using a list for repeated membership tests. x in some_list inside a loop is a hidden O(nยฒ).
  • Reading with d[k] when the key may be missing. Use get, in, or a defaultdict.
  • Relying on set order. Sort before you print or compare.
  • Mutating a dict during iteration. Iterate over list(d) or build a new dict.
  • {} for an empty set. It is an empty dict.
  • Mutable default values shared between keys, such as dict.fromkeys(names, []), which gives every key the same list. Use a comprehension: {name: [] for name in names}.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does d.get('x', 0) return when 'x' is not in d?

    get returns the default you supply when the key is missing. It never raises KeyError and never inserts the key.
  2. 2. What is the average time to check x in s when s is a set of n items?

    A set hashes x and inspects one bucket, so membership is O(1) on average. A list would scan up to n items.
  3. 3. What does Counter('banana').most_common(1) return?

    'a' occurs three times, more than any other letter. most_common returns a list of (item, count) pairs.
  4. 4. Why does deleting keys inside for k in d: raise RuntimeError?

    The iterator walks the table directly, so adding or removing keys mid-loop could skip or repeat entries. Python detects the size change and raises RuntimeError.
  5. 5. Which expression removes duplicates from a list while keeping the first-seen order?

    dict keys are unique and keep insertion order, so dict.fromkeys(items) keeps each item once in first-seen order. A plain set loses the order.

Summary

  • dict and set are hash tables: read, write, delete and membership are O(1) on average; iteration is O(n).
  • Use get, setdefault, defaultdict and Counter instead of manual if key in d code for counting and grouping.
  • Set algebra (|, &, -, ^) replaces loops; "put it in a set first" turns O(nยทm) work into O(n + m).
  • Dicts keep insertion order; sets do not, so sort before printing.
  • Never change the keys of a dict while iterating over it; iterate over a copy.

Next: Hashing Patterns