6.3 Dictionaries

Dictionaries are collections of key-value pairs in Python that preserve insertion order. Each key-value pair in a dictionary is separated by a colon : and enclosed in curly braces {}. Keys are unique within a dictionary, and they can be of any hashable type (such as strings, numbers, or tuples containing only hashable elements). Values can be of any type, including lists, tuples, dictionaries, or other objects. In Table 1, we have examples of dictionaries containing strings, numbers, and a nested dictionary.

Table 1: Examples of dictionaries in Python.

Dictionary Example	Description
`{"name": "Alice", "age": 30}`	A dictionary with string keys, a string value, and an integer value.
`{1: "apple", 2: "banana"}`	A dictionary with integer keys and string values.
`{("x", "y"): 10, ("a", "b"): 20}`	A dictionary with tuple keys and integer values.
`{"name": "Alice", "address": {"city": "New York", "zip": 10001}}`	A dictionary with a nested dictionary as a value.
`{}`	An empty dictionary.

6.3.1 What can a dictionary key be?

A dictionary key in Python must be hashable. Strings and numbers are common examples. A tuple is hashable when all its elements are hashable. In Table 2, we have examples of valid and invalid dictionary keys.

Hashable Types

Dictionary keys in Python must be hashable, which means their hash value must remain unchanged during their lifetime and they must support equality comparisons. Equal keys must have equal hash values; different keys can share a hash value. Python uses hash values to look up dictionary keys efficiently.

Table 2: Examples of valid and invalid dictionary keys in Python.

Dictionary Key Type	Example	Valid?	Reason
String	`"name"`	Yes	Strings are immutable.
Integer	`42`	Yes	Integers are immutable.
Float	`3.14`	Yes	Floats are immutable.
Tuple	`("x", "y")`	Yes	Both elements are hashable. A tuple containing a list would not be a valid key.
List	`["apple", "banana"]`	No	Lists are mutable.
Dictionary	`{"name": "Alice"}`	No	Dictionaries are mutable.
Set	`{1, 2, 3}`	No	Sets are mutable.
Frozen Set	`frozenset({1, 2, 3})`	Yes	Frozen sets are immutable.
Custom Object	`Point(1, 2)`	Depends	The class must provide compatible hashing and equality behavior. Implementing `__hash__` and `__eq__` does not make an object immutable. (advanced topic)

To overcome the limitation of mutable types as dictionary keys, you can convert them to hashable types. For example, you can convert a list of hashable elements to a tuple or a set to a frozen set to use them as dictionary keys. Alternatively, you can use a string representation of the mutable type as the key; this uses the text as the key, so its exact formatting matters. In Listing 1, we have an example of using a tuple as a dictionary key.

Listing 1: Using mutable types as dictionary keys by converting them to immutable types.

6.3.2 Accessing dictionary elements

You can access the value associated with a key in a dictionary using the key within square brackets []. If the key is not present in the dictionary, it raises a KeyError exception. Alternatively, you can use the get method to access the value associated with the key. The get method returns None if the key is not found, or you can specify a default value to return if the key is not present. In Listing 2, we have examples of accessing dictionary elements by key in Python.

Listing 2: Accessing dictionary elements by key in Python. The get method returns a default value if the key is not found. You can also use a try-except block to handle KeyError exceptions.

6.3.3 Updating dictionary elements

You can update the value associated with a key in a dictionary by assigning a new value to the key. If the key is not present in the dictionary, it is added with the new value. In Listing 3, we have examples of updating dictionary elements in Python.

Listing 3: Updating dictionary elements by key in Python. If the key is not present, it is added with the new value.

6.3.4 Dictionary methods

Dictionaries provide a variety of methods to work with key-value pairs. In Table 3, we have a list of common dictionary methods in Python for a dictionary d = {"name": "Alice", "age": 30, "city": "New York"}.

How to Study This?

To study the dictionary methods, create example dictionaries and apply each method to see how it works. When in doubt, code it out!

Table 3: Common dictionary methods in Python considering a dictionary d = {"name": "Alice", "age": 30, "city": "New York"}. Each row starts from this original dictionary.

Dictionary Method	Description	Example	Result
`dict.keys()`	Returns a view of the keys in the dictionary.	`d.keys()`	`dict_keys(["name", "age", "city"])`
`dict.values()`	Returns a view of the values in the dictionary.	`d.values()`	`dict_values(["Alice", 30, "New York"])`
`dict.items()`	Returns a view of the key-value pairs in the dictionary.	`d.items()`	`dict_items([("name", "Alice"), ("age", 30), ("city", "New York")])`
`dict.get(key)`	Returns the value associated with the key, or `None` if the key is not found.	`d.get("name")`	`"Alice"`
`dict.get(key, default)`	Returns the value associated with the key, or the default value if the key is not found.	`d.get("address", "Unknown")`	`"Unknown"`
`dict.pop(key)`	Removes the key and returns the value associated with the key.	`d.pop("age")`	`30`
`dict.popitem()`	Removes and returns the last inserted key-value pair from the dictionary.	`d.popitem()`	`("city", "New York")`
`dict.update(other)`	Updates the dictionary in place with key-value pairs from another dictionary or iterable.	`d.update({"city": "Los Angeles"})`	Returns `None`; `d` becomes `{"name": "Alice", "age": 30, "city": "Los Angeles"}`.
`dict.clear()`	Removes all key-value pairs from the dictionary in place.	`d.clear()`	Returns `None`; `d` becomes `{}`.
`len(dict)`	Returns the number of key-value pairs in the dictionary.	`len(d)`	`3`
`key in dict`	Returns `True` if the key is present in the dictionary, `False` otherwise.	`"name" in d`	`True`
`del dict[key]`	Statement that removes the key and its associated value from the dictionary.	`del d["age"]`	`d` becomes `{"name": "Alice", "city": "New York"}`.

6.3.5 Looping through a dictionary

You can iterate over the key-value pairs of a dictionary using a for loop. In each iteration, the loop variable takes the key of the current key-value pair. In Listing 4, we have an example of looping through a dictionary.

Listing 4: Looping through a dictionary of a person's information and printing the key and value for each key-value pair.

In Listing 5, we have an example of looping through a dictionary using the items method, which returns a view of the key-value pairs as tuples.

Listing 5: Looping through a dictionary of a person's information using the items method and printing the key and value for each key-value pair.

In Listing 6, we have an example of looping through a dictionary using the keys method, which returns a view of the keys in the dictionary.

Listing 6: Looping through a dictionary of a person's information using the keys method and printing the key and value for each key-value pair.

In Listing 7, we have an example of looping through a dictionary using the values method, which returns a view of the values in the dictionary.

Listing 7: Looping through a dictionary of a person's information using the values method and printing the value for each key-value pair.

6.3.6 Dictionary comprehension

Dictionary comprehension is a concise way to create dictionaries in Python. It allows you to create a new dictionary by applying an expression to each key-value pair of an existing dictionary. In Table 4, we have examples of dictionary comprehension.

Table 4: Examples of dictionary comprehension in Python.

Dictionary Comprehension	Description	Example	Result
`{key: value for key, value in dictionary.items()}`	Applies the expression to each key-value pair in the dictionary.	`{k: v*2 for k, v in {"a": 1, "b": 2}.items()}`	`{"a": 2, "b": 4}`
`{key: value for key, value in dictionary.items() if condition}`	Applies the expression to each key-value pair that satisfies the condition.	`{k: v*2 for k, v in {"a": 1, "b": 2}.items() if v > 1}`	`{"b": 4}`
`{key: expression for key in keys}`	Applies the expression to each key in the list of keys.	`{k: k*2 for k in ["a", "b"]}`	`{"a": "aa", "b": "bb"}`
`{key: expression for key in keys if condition}`	Applies the expression to each key that satisfies the condition.	`{k: k*2 for k in ["a", "b"] if k == "b"}`	`{"b": "bb"}`

6.3.7 Merge dictionaries

You can merge two dictionaries in Python using the update method or dictionary unpacking. In Listing 8, we have an example of merging two dictionaries using the update method and in Listing 9, we have an example of merging two dictionaries using dictionary unpacking. The difference between the two methods is that the update method modifies the original dictionary, while dictionary unpacking creates a new dictionary with the merged key-value pairs.

Listing 8: Merging two dictionaries in Python using the update method.

Listing 9: Merging two dictionaries in Python using dictionary unpacking.

6.3.8 Default dictionary

The defaultdict class from the collections module is a subclass of the standard dictionary that provides a default value for missing keys. When you access a missing key using square brackets in a defaultdict, it creates the key and assigns a default value to it. In Listing 10, we have an example of using the defaultdict class to create a dictionary with a default value of 0.

Listing 10: Creating a defaultdict with a default value of 0 and accessing a missing key.

The defaultdict class is useful when you want to avoid KeyError exceptions when accessing missing keys in a dictionary. It simplifies the handling of missing keys by automatically assigning a default value when a missing key is accessed using square brackets.

A useful application is creating a frequency dictionary to count the occurrences of elements in a list. In Listing 11, we have an example of using a defaultdict to create a frequency dictionary.

Listing 11: Creating a frequency dictionary using a defaultdict to count the occurrences of elements in a list.

The default value can also be a list, set, dictionary, or any other data type. In Listing 12, we have an example of using a defaultdict with a default value of an empty list.

Listing 12: Creating a defaultdict with a default value of an empty list and using it to represent a graph. The graph dictionary stores the adjacency list of each vertex in the graph.

Also, you can use a defaultdict with a dictionary as the default value to create a nested dictionary. In Listing 13, we have an example of using a defaultdict with a default value of an empty dictionary. This is useful for creating a nested dictionary where the keys of the outer dictionary correspond to the keys of the inner dictionary.

Listing 13: Creating a defaultdict with a default value of an empty dictionary and using it to represent a weighted graph. The graph dictionary stores the edge weights between vertices in the graph.

6.3.9 Ordered dictionary

The OrderedDict class from the collections module is a subclass of the standard dictionary that maintains insertion order. Regular dictionaries also preserve insertion order, a guarantee since Python 3.7. OrderedDict provides additional ordering operations, such as moving a key to either end with move_to_end(). In Listing 14, we have an example of using the OrderedDict class to create an ordered dictionary.

Listing 14: Creating an OrderedDict and adding key-value pairs to maintain the order of insertion.

The browser displays this result as OrderedDict({'a': 1, 'b': 2, 'c': 3}). The key-value pairs have the same insertion order.

6.3.10 Reading JSON data into a dictionary

JSON (JavaScript Object Notation) is a popular data format for storing and exchanging data. It is human-readable and easy to parse in most programming languages, including Python. You can read JSON data from a file or a string and convert it into a dictionary using the json module.

Suppose data.json contains the JSON object in Listing 15.

Listing 15: JSON object containing a person's name, age, and city.

{
    "name": "Alice",
    "age": 30,
    "city": "New York"
}

You can read the JSON data from the file and convert it into a dictionary using the json.load function. In Listing 16, we have an example of reading JSON data from a file and converting it into a dictionary.

Listing 16: Reading JSON data from a file and converting it into a dictionary using the json.load function.

import json

# Read JSON data from a file and convert it into a dictionary
with open("data.json") as file:
    data = json.load(file)

print(data)  # Output: {"name": "Alice", "age": 30, "city": "New York"}

You can also convert a JSON string into a dictionary using the json.loads function. In Listing 17, we have an example of converting a JSON string into a dictionary.

Listing 17: Converting JSON data from a string into a dictionary using the json.loads function.

6.3.11 Exercises

Route finder

The nearest neighbor (NN) algorithm constructs a route through a set of cities. It is a heuristic, a method for finding a candidate route without guaranteeing the shortest route. The algorithm starts at a random city and then moves to the nearest city that has not been visited yet. The algorithm continues this process until all the cities have been visited.

The algorithm can be implemented using a distance matrix that contains the distances between the cities. The algorithm starts at an origin city (possibly randomly selected) and then iteratively selects the nearest neighbor of the last city in the route until all the cities have been visited.

In this exercise, you will develop a route finder app that finds the best nearest neighbor route and its total distance using the NN algorithm.

Complete the questions in order and implement the functions in Python. The printing and route questions reuse the earlier functions. The dictionary questions repeat those tasks with a different representation.

Use at least two unique city names and a square, symmetric distance matrix with the same number of rows and columns as cities. Distances are nonnegative integer kilometers, and each city's distance to itself is zero. Row and column positions follow the order in cities. In the dictionary representation, each city is an outer key and every destination is an inner key.

Once you have implemented the NN algorithm, see in Figure 1 how to use the folium library to display the routes on a map.

Figure 1: Using folium to display routes on a map.

6.3.Q1 Creating the distance matrix

The first step is to create a distance matrix that contains the distances between the cities. The distance matrix is a list of lists where each element represents the distance between two cities. The distance matrix is symmetric, meaning that the distance between city A and city B is the same as the distance between city B and city A.

Parse the distance matrix of the Dutch cities at Geodatos and use it in the questions. The saved distance table keeps the same eight-city data available for this exercise. Distances are in kilometers. The first row names the destination cities and the first column names the origin cities. Keep that order in cities and use the numeric cells as dist_matrix.

To parse it you can:

Copy the table and format it as a list of lists in Python (use shortcuts to format it faster).
Copy the data into Copilot chat and ask it to format it as a list of lists in Python.

6.3.Q2 Finding the distance between two cities

Create a function that returns the distance between two cities. The function will take two strings origin and destination, a list of lists dist_matrix that represents the distance matrix of the cities, and a list of strings cities. The function should return the distance between the two cities.

Function signature: find_distance_between(origin: str, destination: str, dist_matrix: list[list[int]], cities: list[str]) -> int

Parameters:

origin (str): A string representing the origin city.
destination (str): A string representing the destination city.
dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.
cities (list[str]): A list of strings representing the cities.

Returns:

int: The distance between the two cities.

Constraints:

The origin and destination will be in the list of cities.
The distance matrix will have a minimum size of 2x2.

Example:

Listing 18 shows a call that finds the distance between A and B.

Listing 18: Find the distance between two cities.

cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

origin = 'A'
destination = 'B'

distance = find_distance_between(origin, destination, dist_matrix, cities)
print(distance)  # Output: 1

6.3.Q3 Printing all distances

Create a function that returns all the distances between the cities. The function will take a list of lists dist_matrix that represents the distance matrix of the cities and a list of strings cities. The function should return a string that contains all the distances between the cities as shown in the example below.

Tip: Use the find_distance_between function.

Function signature: print_all_distances(dist_matrix: list[list[int]], cities: list[str]) -> str

Parameters:

dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.
cities (list[str]): A list of strings representing the cities.

Returns:

str: A string that contains all the distances between the cities.

Constraints:

The distance matrix will have a minimum size of 2x2.

Example:

Listing 19 shows the returned string and the required order of the city pairs.

Listing 19: Return the distances between every pair of distinct cities.

cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

distances_str = print_all_distances(dist_matrix, cities)
print(distances_str)  # Output: 'A -> B: 1\nA -> C: 2\nB -> A: 1\nB -> C: 3\nC -> A: 2\nC -> B: 3\n'

6.3.Q4 Finding the nearest neighbor

Create a function that returns the nearest neighbor of the last element in the route. The function will take a tuple of strings route and a list of lists dist_matrix that represents the distance matrix of the cities. The function should return the nearest neighbor of the last element in the route.

Function signature: find_nearest_neighbor(route: tuple[str, ...], dist_matrix: list[list[int]], cities: list[str]) -> str

Parameters:

route (tuple[str, ...]): A tuple of strings representing the route.
dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.
cities (list[str]): A list of strings representing the cities.

Returns:

str: The nearest neighbor of the last element in the route.

Constraints:

The length of the route will be at least 1.
The route contains distinct cities from cities and is shorter than the cities list, so an unvisited city remains.
The nearest neighbor cannot be in the route. If several unvisited cities are equally near, use a consistent tie rule.
The distance matrix will have a minimum size of 2x2.

Example:

Listing 20 shows the nearest neighbor when the route starts at A.

Listing 20: Find an unvisited city nearest to the end of a route.

cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

route = ('A', )


nn = find_nearest_neighbor(route, dist_matrix, cities)
print(nn)  # Output: 'B'

6.3.Q5 Finding the best nearest neighbor route

Create a function that returns the best nearest neighbor route and its total distance. The function will take a list of strings cities and a list of lists dist_matrix that represents the distance matrix of the cities. Try every possible starting city, close each nearest neighbor route by returning to its start, and return a route with the smallest total distance among these candidates. Any tied best route is acceptable.

Tip: Use the find_nearest_neighbor function.

Function signature: find_best_nn_route(cities: list[str], dist_matrix: list[list[int]]) -> tuple[tuple[str, ...], int]

Parameters:

cities (list[str]): A list of strings representing the cities.
dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.

Returns:

tuple[tuple[str, ...], int]: A tuple of the best nearest neighbor route and its total distance.

Constraints:

The length of the cities will be at least 2.
The distance matrix will have a minimum size of 2x2.
The distance matrix will be symmetric.
The route will start and end at the same city.

Example:

Listing 21 shows a closed route and its total distance.

Listing 21: Return a nearest neighbor route and its total distance.

cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

route, total_distance = find_best_nn_route(cities, dist_matrix)

print(route)  # Output: ('A', 'B', 'C', 'A')
print(total_distance)  # Output: 6

6.3.Q6 Alternative distance matrix representation (dictionary of dictionaries)

Re-do the exercises above using a dictionary of dictionaries to represent the distance matrix. The keys of the first-level dictionary will be the origin cities, and the values will be dictionaries with the destination cities as keys and the distances as values. Notice that when using dictionaries, the cities list does not need to be passed as a parameter. The adjusted function signatures are:

find_distance_between(origin: str, destination: str, dist_matrix: dict[str, dict[str, int]]) -> int
print_all_distances(dist_matrix: dict[str, dict[str, int]]) -> str
find_nearest_neighbor(route: tuple[str, ...], dist_matrix: dict[str, dict[str, int]]) -> str
find_best_nn_route(dist_matrix: dict[str, dict[str, int]]) -> tuple[tuple[str, ...], int]

6.3.Q7 Converting the distance matrix representation

Create a function that converts the list of lists representation of the distance matrix to the dictionary of dictionaries representation. The function will take a list of strings cities and a list of lists dist_matrix that represents the distance matrix of the cities. The function should return a dictionary of dictionaries that represents the distance matrix.

Function signature: convert_to_dict_of_dicts(cities: list[str], dist_matrix: list[list[int]]) -> dict[str, dict[str, int]]

Parameters:

cities (list[str]): A list of strings representing the cities.
dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.

Returns:

dict[str, dict[str, int]]: A dictionary of dictionaries that represents the distance matrix.

Constraints:

The length of the cities will be at least 2.
The distance matrix will have a minimum size of 2x2.
The distance matrix will be symmetric.
The cities will be unique.
The rows and columns of the distance matrix will be in the same order as the cities.
The distance matrix will have the same length as the cities.

Example:

Listing 22 shows the dictionary returned for three cities.

Listing 22: Convert a distance matrix to a dictionary of dictionaries.

cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

dist_matrix_dict = convert_to_dict_of_dicts(cities, dist_matrix)

print(dist_matrix_dict)  # Output: {'A': {'A': 0, 'B': 1, 'C': 2}, 'B': {'A': 1, 'B': 0, 'C': 3}, 'C': {'A': 2, 'B': 3, 'C': 0}}

Hint

cities.index(city) returns the zero-based position of the first matching name. The stated inputs guarantee that the name is present; otherwise it raises ValueError. For example, ["A", "B"].index("B") is 1.
len(values) returns its number of elements. range(n) supplies positions from 0 through n - 1. For example, list(range(len(["A", "B"]))) is [0, 1]. route[-1] selects the last item of a nonempty tuple.
route + (city,) returns a tuple with one city added at the end, leaving the original tuple unchanged. For example, ("A",) + ("B",) is ("A", "B").
dist_matrix[origin][destination] retrieves a dictionary's distance value. Iterating over a dictionary visits its keys in insertion order. For example, with {"A": {"A": 0, "B": 1}}, the lookup for "A" and "B" returns 1.