Slides

# Intro to Python
## Week 8
### Dictionaries

---

## While you wait

#### Open these URLs:

- [NLPiA.org/fall26](https://NLPiA.org/fall26)
- [GitLab.com/mesa_python/fall26](https://GitLab.com/mesa_python/fall26)
- [Runestone ch 12: Dictionaries](https://runestone.academy/ns/books/published/mesa_python_fall26/Dictionaries/intro-Dictionaries.html)
- [Runestone Week 8 assignment](https://runestone.academy/assignment/student/doAssignment?assignment_id=296475)

- GitBash terminal ('`~$ prompt`')
- Interactive Python terminal (`>>> ` prompt)

---

## Attendance

- Find your midterm project program on **YOUR** computer.
- Think about what `~` means and how you use it in a path.
- Go to the board and write **ONLY** the full file path of your midterm project

---

## What's left?

| Chapter | Topic | Python |
| ---: | :--- | :--- |
| 11. | Files | `open`, `file`, `with`, `.read()`, `.write()`, `.close()`, `zip` |
| **12.** | **Dictionaries** | **`dict`, `{}`, `.get`, `in`, `.keys`, `.values`, `.items`, `.copy`** |
| 13. | Exceptions | `try`, `except`, `finally`, `raise` |
| 14. | HTML | `flask`, `requests` |
| 15. | GUIs | `tkinter` |

---

## 8 ``types``

1. `NoneType`  
2. `bool`  
3. `int`  
4. `float`  
5. `str`  
6. `list`  
7. `tuple`  
8. `dict` 
8. `dict`

note:
- Remember these other types?
- Today is `dict` day

---

## What's left?

---

## Grouping symbols

- `()` -- `tuple`
- `[]` -- `list`
- `{}` -- `dict`

---

## New skills

<html>
<script>hljs.configure({ 'languages': ['python'] });</script>
<table>
  <tr><th></th><th>Python</th></tr>
  <tr><td>Create a <code class=hljs>dict</code></td><td><code class=hljs>ages = {'ann': 21, 'bob': 30}</code></td></tr>
  <tr><td>Look up a value</td><td><code class=hljs>ages['bob']</code></td></tr>
  <tr><td>Add or change a value</td><td><code class=hljs>ages['cat'] = 19</code></td></tr>
  <tr><td>Count things</td><td><pre><code class=hljs>counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1</code></pre></td></tr>
</table>
</html>

note:
1. A dictionary is like a real dictionary: you look up a word (the **key**) to find its definition (the **value**)
2. You've used lists, where you look things up by position (0, 1, 2...)
3. With a dict you look things up by name
4. The counting pattern at the bottom is the most useful thing you will learn today

---

## A real dictionary

![Multi-volume Latin dictionary](wk8/latin-dictionary.jpg)

- **key**: the word you look up -- **value**: its definition

<small>[Latin dictionary](https://commons.wikimedia.org/wiki/File:Latin_dictionary.jpg), Dr. Marcus Gossler, CC BY-SA 3.0</small>

note:
- Forcellini's Latin lexicon, 1858-87 edition
- you never read a dictionary front to back -- you jump straight to the word
- that jump is what a Python `dict` does for you
- `{'lexicon': 'a book of words and their meanings'}`

---

## A phone book

![1919 Central Ontario telephone directory page](wk8/telephone-directory-1919.jpg)

```python
>>> phones = {'Allan, S.': 8,
...           'Allum, I.': 59,
...           'Arlington Hotel': 16}
>>> phones['Arlington Hotel']
16
```

<small>[1919 telephone directory](https://commons.wikimedia.org/wiki/File:Page_33_of_the_1919_Central_Ontario_telephone_directory,_showing_numbers_for_Deseronto._(5884134337).jpg), Deseronto Archives, no known restrictions</small>

note:
- a phone number from 1919 was just 2 or 3 digits
- key = name, value = phone number
- the book is sorted so humans can find names fast -- Python uses a different trick (coming up)

---

## A library card catalog

![Card catalog drawer labeled LOVER through LUMA](wk8/card-catalog-lover-luma.jpg)

<small>[Card catalog, Indiana State Library](https://commons.wikimedia.org/wiki/File:Card_catalog_at_the_Indiana_State_Library_-_headings_Lover_through_Luma.jpg), TBurmeister (WMF), CC BY-SA 4.0</small>

note:
- every card is a key-value pair: a title (key) and where the book lives on the shelf (value)
- drawer 809 holds every key from LOVER to LUMA
- you go straight to the right drawer instead of searching all of them
- Python does the same thing: it puts each key in a numbered "drawer" called a **bucket**

---

## PO boxes: numbered buckets

![Wall of numbered PO boxes](wk8/po-boxes-chico.jpg)

<small>[PO boxes, Chico Post Office](https://commons.wikimedia.org/wiki/File:PO_boxes_at_the_historic_Chico_Post_Office_(2024)-L1005460.jpg), Frank Schulenburg, CC BY-SA 4.0</small>

note:
- each box has a number and holds your mail
- the postal worker doesn't check every box -- they go straight to box 1234
- but how do you turn a **name** like "Lisa Smith" into a box number?

---

## The slow way: a list of pairs

![Key-value pairs chained one after another](wk8/associative-array-linked-list.svg)

```python
>>> pairs = [('John Smith', '521-1234'), ('Lisa Smith', '521-8976')]
>>> for name, phone in pairs:
...     if name == 'Lisa Smith':
...         print(phone)
521-8976
```

<small>[Associative array as linked list](https://commons.wikimedia.org/wiki/File:Associative_array_as_linked_list.svg), Aleksi Nurmi, public domain</small>

note:
- you could store key-value pairs in a list of tuples
- but to find one you have to check them one at a time
- a million names means up to a million checks
- `dict(pairs)` turns this into a fast dictionary

---

## Hash functions

![Three inputs passed through a hash function produce three different hash sums](wk8/hash-function.svg)

<small>[Hash function](https://commons.wikimedia.org/wiki/File:Hash_function.svg), David Göthberg, public domain</small>

note:
- a hash function turns any key into a number
- the same input always gives the same number
- change one word ("runs" -> "walks") and you get a completely different number
- try `hash('Fox')` in your terminal -- string hashes change every time you restart Python

---

## A hash table

![Names pass through a hash function into numbered buckets holding phone numbers](wk8/hash-table-phonebook.svg)

```python
>>> phonebook = {'John Smith': '521-1234', 'Lisa Smith': '521-8976',
...              'Sandra Dee': '521-9655'}
>>> phonebook['Sandra Dee']
'521-9655'
```

<small>[Hash table](https://commons.wikimedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg), Jorge Stolfi, CC BY-SA 3.0 (non-English labels removed)</small>

note:
- this is what is inside every Python `dict`
- the key is hashed to a bucket number, and the value is stored in that bucket
- looking up a key means 1 hash and 1 jump, no matter how big the dict is

---

## Collisions

![Two names, John Smith and Sandra Dee, hash to the same bucket 02](wk8/hash-table-collision.svg)

<small>[Hash collision](https://commons.wikimedia.org/wiki/File:Hash_table_4_1_1_0_0_1_0_LL.svg), Jorge Stolfi, public domain (non-English labels removed)</small>

note:
- sometimes two keys land in the same bucket -- a collision
- Python handles collisions for you, so you never see them
- that's why keys must be unique: one key, one value
- and why keys must be **immutable** -- if a key changed, its hash would change and Python would look in the wrong bucket

---

## Keys must be hashable

```python
>>> hash(42)
42
>>> hash((0, 3)) == hash((0, 3))
True
>>> {[0, 3]: 1}
Traceback (most recent call last):
  ...
TypeError: unhashable type: 'list'
```

note:
- `int`, `float`, `str`, `tuple` can be keys
- `list` and `dict` can't be keys, because they are mutable
- values can be anything at all

---

## Mostly empty? Use a `dict`

![A large sparse matrix: mostly white (zero) with a few black (nonzero) entries](wk8/sparse-matrix.png)

<small>[Finite element sparse matrix](https://commons.wikimedia.org/wiki/File:Finite_element_sparse_matrix.png), Oleg Alexandrov, public domain</small>

note:
- each black dot is a nonzero number, each white pixel is a zero
- a list of lists would store every zero
- a dict with `(row, col)` tuple keys stores only the black dots
- we'll see the small version from the textbook (section 12.5) later today

---

## Sequences vs mappings

- `str`, `list`, `tuple` are **sequences**  
  - look up by **position**: `'Python'[0]`  
- `dict` is a **mapping**  
  - look up by **key**: `ages['bob']`

note:
- a mapping associates (maps) each key to a value
- keys can be any immutable type: `str`, `int`, `float`, `tuple`
- values can be anything at all, even other dicts or lists

---

## Glossary

- **dictionary** -- a collection of key-value pairs
- **key** -- the thing you look up (must be immutable)
- **value** -- what the key maps to (can be anything)
- **key-value pair** -- one entry: `'bob': 30`
- **mapping type** -- `dict` is Python's only built-in one

---

## Build a `dict` one pair at a time

```python
>>> eng2sp = {}
>>> eng2sp['one'] = 'uno'
>>> eng2sp['two'] = 'dos'
>>> eng2sp['three'] = 'tres'
>>> eng2sp

```

---

## Build a `dict` one pair at a time

```python
>>> eng2sp = {}
>>> eng2sp['one'] = 'uno'
>>> eng2sp['two'] = 'dos'
>>> eng2sp['three'] = 'tres'
>>> eng2sp
{'one': 'uno', 'two': 'dos', 'three': 'tres'}
```

note:
- `{}` is an empty dict (not an empty set!)
- each assignment adds a new key-value pair
- colon `:` separates key from value, comma `,` separates pairs

---

## Or all at once

```python
>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}
>>> eng2sp['two']

```

---

## Or all at once

```python
>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}
>>> eng2sp['two']
'dos'
```

---

## Is a `dict` ordered?

- The textbook says "unordered"  
- Since Python 3.7 a `dict` remembers **insertion order**  
- But you still can't use `eng2sp[0]`  
- And order doesn't matter for `==`

```python
>>> {'b': 1, 'a': 3} == {'a': 3, 'b': 1}
True
```

note:
- The Runestone book was written for older Pythons
- Modern Python keeps keys in the order you added them
- But you should never need to rely on that -- look things up by key

---

## Runestone q01

```python
>>> ages = {'ann': 21, 'bob': 30}
>>> ages['bob']

```

---

## Runestone q01

```python
>>> ages = {'ann': 21, 'bob': 30}
>>> ages['bob']
30
```

---

```python
>>> len(ages)

```

---

```python
>>> len(ages)
2
```

---

```python
>>> 'ann' in ages

```

---

```python
>>> 'ann' in ages
True
```

---

```python
>>> 21 in ages

```

---

```python
>>> 21 in ages
False
```

note:
- `in` checks the **keys**, not the values
- use `21 in ages.values()` to check values

---

```python
>>> ages['cat']

```

---

```python
>>> ages['cat']
Traceback (most recent call last):
  ...
KeyError: 'cat'
```

note:
- Looking up a key that isn't there crashes your program
- Two ways to avoid it: check with `in` first, or use `.get()`

---

## `.get()` never crashes

```python
>>> ages.get('bob')
30
>>> ages.get('cat')

>>> ages.get('cat', 0)

```

---

## `.get()` never crashes

```python
>>> ages.get('bob')
30
>>> print(ages.get('cat'))
None
>>> ages.get('cat', 0)
0
```

note:
- remember `None`? Here's another reason it exists
- the second argument is the default to return when the key is missing

---

## Dictionaries are mutable

```python
>>> inventory = {'apples': 430, 'bananas': 312,
...              'oranges': 525, 'pears': 217}
>>> inventory['bananas'] = inventory['bananas'] + 200
>>> inventory['bananas']

```

---

## Dictionaries are mutable

```python
>>> inventory = {'apples': 430, 'bananas': 312,
...              'oranges': 525, 'pears': 217}
>>> inventory['bananas'] = inventory['bananas'] + 200
>>> inventory['bananas']
512
```

note:
- same as `inventory['bananas'] += 200`

---

## `del` a key

```python
>>> del inventory['pears']
>>> inventory

```

---

## `del` a key

```python
>>> del inventory['pears']
>>> inventory
{'apples': 430, 'bananas': 512, 'oranges': 525}
```

---

## What is printed?

```python
>>> mydict = {"cat": 12, "dog": 6, "elephant": 23}
>>> mydict["mouse"] = mydict["cat"] + mydict["dog"]
>>> print(mydict["mouse"])

```

---

## What is printed?

```python
>>> mydict = {"cat": 12, "dog": 6, "elephant": 23}
>>> mydict["mouse"] = mydict["cat"] + mydict["dog"]
>>> print(mydict["mouse"])
18
```

note:
- a new key on the left side of `=` creates a new pair -- no error

---

## Dictionary methods

note:
- Try `inventory.` then **TAB** in your Python terminal to see them all

---

```python
>>> list(inventory.keys())

```

---

```python
>>> list(inventory.keys())
['apples', 'bananas', 'oranges']
```

---

```python
>>> list(inventory.values())

```

---

```python
>>> list(inventory.values())
[430, 512, 525]
```

---

```python
>>> list(inventory.items())

```

---

```python
>>> list(inventory.items())
[('apples', 430), ('bananas', 512), ('oranges', 525)]
```

note:
- remember tuples `()`? Each item is a `(key, value)` tuple

---

## Loop over a `dict`

```python
for fruit in inventory:
    print(fruit, inventory[fruit])
```

```python
for fruit, count in inventory.items():
    print(fruit, count)
```

note:
- both loops print the same thing
- looping over a dict gives you its keys
- `.items()` hands you key and value together -- tuple unpacking

---

## Accumulate a `list` from a `dict`

```python
>>> low = []
>>> for fruit, count in inventory.items():
...     if count < 500:
...         low.append(fruit)
>>> low

```

---

## Accumulate a `list` from a `dict`

```python
>>> low = []
>>> for fruit, count in inventory.items():
...     if count < 500:
...         low.append(fruit)
>>> low
['apples']
```

note:
- the accumulation pattern from week 5, with a `dict` as the input
- this is very close to the `check_inventory` problem on the assignment
- wrap it in a `def` and replace `500` with a parameter

---

## Count with a `dict`

```python
>>> counts = {}
>>> for w in 'the cat and the hat and the bat'.split():
...     counts[w] = counts.get(w, 0) + 1
>>> counts

```

---

## Count with a `dict`

```python
>>> counts = {}
>>> for w in 'the cat and the hat and the bat'.split():
...     counts[w] = counts.get(w, 0) + 1
>>> counts
{'the': 3, 'cat': 1, 'and': 2, 'hat': 1, 'bat': 1}
```

note:
- `.get(w, 0)` returns 0 the first time we see a word
- this is the heart of the `countALL` problem on the assignment
- for that one, loop over characters instead of words
- and think about what `'B'` vs `'b'` should count as (hint: `.lower()`)

---

## Aliasing

```python
>>> opposites = {'up': 'down', 'right': 'wrong', 'true': 'false'}
>>> alias = opposites
>>> alias['right'] = 'left'
>>> opposites['right']

```

---

## Aliasing

```python
>>> opposites = {'up': 'down', 'right': 'wrong', 'true': 'false'}
>>> alias = opposites
>>> alias['right'] = 'left'
>>> opposites['right']
'left'
>>> alias is opposites
True
```

note:
- same as lists: two names, one object in RAM
- remember `id()` from week 6? `id(alias) == id(opposites)`

---

## `.copy()`

```python
>>> acopy = opposites.copy()
>>> acopy['up'] = 'sideways'
>>> opposites['up']

```

---

## `.copy()`

```python
>>> acopy = opposites.copy()
>>> acopy['up'] = 'sideways'
>>> opposites['up']
'down'
>>> acopy is opposites
False
```

---

## Sparse matrices

```python
matrix = [[0, 0, 0, 1, 0],
          [0, 0, 0, 0, 0],
          [0, 2, 0, 0, 0],
          [0, 0, 0, 0, 0],
          [0, 0, 0, 3, 0]]
```

```python
matrix = {(0, 3): 1, (2, 1): 2, (4, 3): 3}
```

note:
- 25 numbers vs 3 numbers -- only store what isn't zero
- the keys are `(row, column)` tuples -- tuples can be keys because they are immutable
- lists can NOT be keys

---

```python
>>> matrix[(0, 3)]

>>> matrix.get((1, 3), 0)

```

---

```python
>>> matrix[(0, 3)]
1
>>> matrix.get((1, 3), 0)
0
```

---

## Dicts are everywhere: JSON

```python
>>> import json
>>> json.loads('{"name": "Mesa", "open": true, "rooms": null}')

```

---

## Dicts are everywhere: JSON

```python
>>> import json
>>> json.loads('{"name": "Mesa", "open": true, "rooms": null}')
{'name': 'Mesa', 'open': True, 'rooms': None}
```

note:
- JSON is how web apps send data to each other
- `true` becomes `True`, `null` becomes `None`
- the reddit problem on the assignment downloads JSON and hands you a dict
- explore it with `.keys()`

---

## Runestone assignment

- [Week 8 assignment](https://runestone.academy/assignment/student/doAssignment?assignment_id=296475)
- Read ch 12.1 - 12.7
- q01: look up a value
- `countALL(text)` -- count letters
- `check_inventory(inventory, low)` -- list low items
- reddit JSON -- explore a real `dict`

---

## Active practice

- Create `wk8.py` in your GitLab folder
- Write `countALL` and `check_inventory` there first
- Test them in your Python terminal
- Then paste them into Runestone

<br>

#### Have fun!