Chapter 9: Mappings & Sets¶

The `dict` Type¶

In [1]:

to_words = {
    0: "zero",
    1: "one",
    2: "two",
}

In [2]:

from_words = {
    "zero": 0,
    "one": 1,
    "two": 2,
}

In [5]:

to_words

Out[5]:

{0: 'zero', 1: 'one', 2: 'two'}

In [8]:

from_words

Out[8]:

{'zero': 0, 'one': 1, 'two': 2}

In [10]:

dict([("zero", 0), ("one", 1), ("two", 2)])

Out[10]:

{'zero': 0, 'one': 1, 'two': 2}

In [12]:

dict(zero=0, one=1, two=2)

Out[12]:

{'zero': 0, 'one': 1, 'two': 2}

Nested Data¶

In [13]:

people = {
    "mathematicians": [
        {
            "name": "Gilbert Strang",
            "emails": ["gilbert@mit.edu"],
        },
        {
            "name": "Leonhard Euler",
            "emails": [],
        },
    ],
    "physicists": [],
    "programmers": [
        {
            "name": "Guido",
            "emails": ["guido@python.org", "guido@dropbox.com"],
        },
    ],
}

In [14]:

people

Out[14]:

{'mathematicians': [{'name': 'Gilbert Strang', 'emails': ['gilbert@mit.edu']},
  {'name': 'Leonhard Euler', 'emails': []}],
 'physicists': [],
 'programmers': [{'name': 'Guido',
   'emails': ['guido@python.org', 'guido@dropbox.com']}]}

In [15]:

from pprint import pprint

In [16]:

pprint(people, indent=1, width=60)

{'mathematicians': [{'emails': ['gilbert@mit.edu'],
                     'name': 'Gilbert Strang'},
                    {'emails': [],
                     'name': 'Leonhard Euler'}],
 'physicists': [],
 'programmers': [{'emails': ['guido@python.org',
                             'guido@dropbox.com'],
                  'name': 'Guido'}]}

Hash Tables & (Key) Hashability¶

In [17]:

{
    ["zero", "one"]: [0, 1],
}

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[17], line 1
----> 1 {
      2     ["zero", "one"]: [0, 1],
      3 }

TypeError: unhashable type: 'list'

In [18]:

{
    "zero": 0,
    "one": 1,
    "two": 2,
    "zero": 999,  # to illustrate a point
}

Out[18]:

{'zero': 999, 'one': 1, 'two': 2}

Bucket	0	1	2	3	4	5	6	7
Key	...	...	...	...	...	...	...	...
Value	...	...	...	...	...	...	...	...

In [19]:

hash("zero")

Out[19]:

-85344695604937002

In [20]:

hash(0)

Out[20]:

In [23]:

hash(1) == hash(1.0)

Out[23]:

True

In [24]:

hash(["zero", "one"])

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[24], line 1
----> 1 hash(["zero", "one"])

TypeError: unhashable type: 'list'

In [25]:

hash(("zero", "one"))

Out[25]:

-1616807732336770172

In [26]:

{
    ("zero", "one"): [0, 1],
}

Out[26]:

{('zero', 'one'): [0, 1]}

In [27]:

def buckets(mapping, *, bits):
    """Calculate the bucket indices for a mapping's keys."""
    for key in mapping:  # cf., next section for details on looping
        hash_value = hash(key)
        binary = bin(hash_value)
        address = binary[-bits:]
        bucket = int("0b" + address, base=2)
        print(key, hash_value, "0b..." + binary[-8:], address, bucket, sep="\t")

In [29]:

buckets(from_words, bits=2)

zero	-85344695604937002	0b...00101010	10	2
one	6414592332130781825	0b...10000001	01	1
two	4316247523642253857	0b...00100001	01	1

In [31]:

buckets(from_words, bits=3)

zero	-85344695604937002	0b...00101010	010	2
one	6414592332130781825	0b...10000001	001	1
two	4316247523642253857	0b...00100001	001	1

In [33]:

buckets(from_words, bits=4)

zero	-85344695604937002	0b...00101010	1010	10
one	6414592332130781825	0b...10000001	0001	1
two	4316247523642253857	0b...00100001	0001	1

Mappings are Collections of Key-Value Pairs¶

In [36]:

len(from_words)

Out[36]:

In [39]:

for word in from_words:
    print(word)

zero
one
two

In [41]:

for word in reversed(from_words):
    print(word)

two
one
zero

In [45]:

"one" in from_words

Out[45]:

True

Membership Testing: `list` vs. `dict`¶

In [47]:

import random

In [49]:

needle = 42

In [50]:

haystack = [random.randint(99, 9999) for _ in range(10_000_000)]
haystack.append(needle)

In [51]:

random.shuffle(haystack)

In [52]:

haystack[:10]

Out[52]:

[8126, 7370, 3735, 213, 7922, 1434, 8557, 9609, 9704, 9564]

In [54]:

%%timeit -n 1 -r 1
for _ in range(10):
    needle in haystack

4.44 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

In [55]:

magic_haystack = dict((x, None) for x in haystack)

In [56]:

%%timeit -n 1 -r 1
for _ in range(10_000_000):
    needle in magic_haystack

560 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

Indexing -> Key Look-up¶

In [60]:

from_words["two"]

Out[60]:

In [61]:

from_words["drei"]

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[61], line 1
----> 1 from_words["drei"]

KeyError: 'drei'

In [62]:

people["mathematicians"]

Out[62]:

[{'name': 'Gilbert Strang', 'emails': ['gilbert@mit.edu']},
 {'name': 'Leonhard Euler', 'emails': []}]

In [63]:

people["mathematicians"][0]

Out[63]:

{'name': 'Gilbert Strang', 'emails': ['gilbert@mit.edu']}

In [64]:

people["mathematicians"][0]["name"]

Out[64]:

'Gilbert Strang'

In [65]:

people["mathematicians"][0]["emails"]

Out[65]:

['gilbert@mit.edu']

Mutability¶

In [66]:

to_words

Out[66]:

{0: 'zero', 1: 'one', 2: 'two'}

In [67]:

to_words[0] = "null"
to_words[1] = "eins"
to_words[2] = "zwei"

In [68]:

to_words

Out[68]:

{0: 'null', 1: 'eins', 2: 'zwei'}

In [69]:

to_words[3] = "drei"
to_words[4] = "vier"

In [70]:

to_words

Out[70]:

{0: 'null', 1: 'eins', 2: 'zwei', 3: 'drei', 4: 'vier'}

In [72]:

del to_words[0]

In [73]:

to_words

Out[73]:

{1: 'eins', 2: 'zwei', 3: 'drei', 4: 'vier'}

In [74]:

people["physicists"]

Out[74]:

[]

In [75]:

people["physicists"].append({"name": "Albert Einstein"})

In [76]:

people["programmers"][0]

Out[76]:

{'name': 'Guido', 'emails': ['guido@python.org', 'guido@dropbox.com']}

In [77]:

people["programmers"][0]["name"] = "Guido van Rossum"

In [78]:

del people["programmers"][0]["emails"][1]

In [79]:

pprint(people, indent=1, width=60)

{'mathematicians': [{'emails': ['gilbert@mit.edu'],
                     'name': 'Gilbert Strang'},
                    {'emails': [],
                     'name': 'Leonhard Euler'}],
 'physicists': [{'name': 'Albert Einstein'}],
 'programmers': [{'emails': ['guido@python.org'],
                  'name': 'Guido van Rossum'}]}

`dict` Methods¶

In [83]:

for word in from_words.keys():
    print(word)

zero
one
two

In [86]:

for number in from_words.values():
    print(number)

0
1
2

In [88]:

for word, number in from_words.items():
    print(f"{word} -> {number}")

zero -> 0
one -> 1
two -> 2

In [90]:

to_words

Out[90]:

{1: 'eins', 2: 'zwei', 3: 'drei', 4: 'vier'}

In [92]:

to_words.get(0, "n/a")

Out[92]:

'n/a'

In [94]:

to_spanish = {
"cero",
"uno",
"dos",
"tres",
"cuatro",
"cinco",  
}

In [95]:

to_words.update(to_spanish)

In [96]:

to_words

Out[96]:

{1: 'uno', 2: 'dos', 3: 'tres', 4: 'cuatro', 0: 'cero', 5: 'cinco'}

In [97]:

from_words

Out[97]:

{'zero': 0, 'one': 1, 'two': 2}

In [98]:

number = from_words.pop("zero")

In [99]:

number

Out[99]:

In [100]:

from_words

Out[100]:

{'one': 1, 'two': 2}

In [103]:

word, number = from_words.popitem()

In [104]:

word, number

Out[104]:

('two', 2)

In [105]:

from_words

Out[105]:

{'one': 1}

In [108]:

from_words.clear()

In [109]:

from_words

Out[109]:

{}

`dict` Comprehensions¶

In [119]:

to_words = {
    0: "zero",
    1: "one",
    2: "two",
}

In [120]:

from_words = {}

for number, word in to_words.items():
    from_words[word] = number

from_words

Out[120]:

{'zero': 0, 'one': 1, 'two': 2}

In [121]:

{v: k for k, v in to_words.items()}

Out[121]:

{'zero': 0, 'one': 1, 'two': 2}