Imagine a grocery-store price book. You know an item’s name, but you need its price. Scanning every entry takes longer as the book grows; sorting it makes binary search possible, but you still have to search. A map lets you associate the name directly with the price. In Python, this kind of map is called a dictionary, or `dict`. section 5.0 section 5.1
Look up a price
Start with `book = {}`. Assign `book["apple"] = 0.67` and `book["avocado"] = 1.49`. Now `book["avocado"]` gives you `1.49`. The item name is the key; its price is the value. You use the same key to store and retrieve the price. section 5.1
How can that lookup be so quick? A hash function consistently turns a key into a location in an underlying array. That location tells the hash table where to store or find the associated value, without scanning the whole array. Python supplies the hash-table implementation; you normally use the dictionary rather than build one yourself. section 5.1 section 5.11
Reach for a dictionary when you need to:
- Look up one thing from another, such as a person’s phone number from their name or a recently visited website’s IP address from its address. section 5.3
- Check whether something has appeared before: store a voter’s name as a key, then test `name in voted` before accepting another vote. section 5.4
- Reuse a result: map a page URL to page data, returning cached data on the next request instead of asking the server to produce it again. section 5.5
A dictionary also helps represent other structures. For a graph, map each node to its out-neighbors. In a weighted graph, a node can map to another dictionary whose keys are neighbors and whose values are edge costs. Separate dictionaries can track current costs and parents while finding a shortest path. section 6.6 section 9.5
Fast does not mean magic—or literally instant. Search, insertion, and deletion average O(1): their time stays roughly the same as the table grows. In the worst case they take O(n). A collision occurs when two keys are assigned the same slot; one way to handle it is a linked list at that slot, which takes longer to search as it grows. A good hash function and a low load factor help avoid that slowdown. Growing a crowded table requires resizing and reinserting its items, but the average performance remains O(1). section 5.7 section 5.8 section 5.9
The trade-off becomes noticeable at enormous scale: storing every crawled web address as a key makes membership checks fast on average, but the dictionary itself can take a lot of space. section 13.6
