Scan a barcode, get a price
A shop has 20,000 products. You scan a barcode at the till and the price appears at once.
The till does not read all 20,000 products to find it. It goes straight to the one it needs.
This lesson shows the structure that makes that possible, and why it is so fast.
By the end of this lesson
Note
I can look up a value by its key.
Key words
| Word | What it means | Example |
|---|---|---|
| Map | pairs of keys and values | |
| Dictionary | Python's map | {"MUG-12": 650} |
| Key | the name you look a value up by | "MUG-12" |
| Value | what is stored under a key | 650 |
| Hash | a number worked out from a key that says where it is stored | |
| Set | a group where each value appears once | {"c04", "c17"} |
The cells students fill in are left blank in this preview.
A dictionary pairs keys with values
A dictionary stores pairs. Each pair has a key and a value, written key: value.
You look a value up with its key in square brackets: prices["MUG-12"].
You change a value or add a new pair the same way, with =. in tells you whether a key is there.
Try it: a price list
# A shop's prices in pence, looked up by product code.
prices = {"KET-01": 2499, "LAP-07": 54900, "MUG-12": 650}
print(prices["MUG-12"]) # look up one price
prices["MUG-12"] = 700 # change a price
prices["PEN-03"] = 120 # add a new product
print(prices)
print("LAP-07" in prices) # is this code in the shop?
# Look up the price of "KET-01", then press Run.
A common mistake
Warning
Many people think a dictionary can hold the same key twice. It cannot: each key appears once. Writing to a key that exists replaces its old value. So use something unique as the key, such as a product code, never a first name.
Why a lookup by key is fast
To find a product in a list, the program reads items one by one until it finds a match.
A dictionary works out a hash from the key. The hash is a number that says where the value is kept. So the program goes straight there.
That takes about the same time for 10 products or 10 million.
Worked example: finding the last product
| Products | Steps in a list | Steps in a dictionary |
|---|---|---|
| 10 | up to 10 | about 1 |
| 1,000 | up to 1,000 | about 1 |
| 1,000,000 | up to 1,000,000 | about 1 |
The cells students fill in are left blank in this preview.
A set keeps each value once
A set is like a dictionary with keys and no values. Each value appears once.
Turning a list into a set removes repeats. Checking in on a set is fast, for the same reason as a dictionary.
Use a set to count different customers, or to check a username is not already taken.
Try it: different customers
# Customer ids from today's log. Some came back more than once.
log = ["c17", "c04", "c17", "c22", "c04", "c17"]
visitors = set(log) # each id is kept once
print(visitors)
print(len(log), "visits")
print(len(visitors), "different customers")
print("c22" in visitors)
# Add "c30" to the log, then press Run.