Imagine scanning a baseball card and needing to know immediately whether you own it. A map, also called a dictionary, stores information under a key: the player’s name could lead to a card’s details or the number of copies you own. Unlike an array lookup by position, a map lets you ask for a value by key. section 12.1 section 12.0
A map’s core operations are:
- Insert a value under a key. section 12.3
- Search for a key and retrieve its associated value, if one exists. section 12.3
- Delete an entry by key or value, depending on the interface. section 12.3
Count repeated items
A Python dictionary can keep a running count of each item in a collection: `counters = {}; for c in C: counters[c] = counters.get(c, 0) + 1`. The lookup supplies the current count—or zero for a new key—before adding one. A related use is removing duplicates: keep an item only when its key has not been seen before. section 12.2
A map describes *what* you can do, not *how* entries are stored. Arrays and linked lists can implement one, but finding a key may require scanning entries. A balanced binary search tree provides logarithmic time for insertion, search, and deletion. A hash table offers constant average time for those operations, though search or deletion can take linear time in the worst case. Choose an implementation for the operations you need; predecessor and successor lookup, for example, are not guaranteed by the basic map interface. section 12.4 section 12.8 section 12.22 section 12.3
Table 12.1 Running time for various implementations of the dictionary (view table figure)
| Insert |
Delete |
Search |
Init with n elements |
|
|---|---|---|---|---|
| Unsorted array |
O(1) |
O(n) |
O(n) |
O(n) |
| Sorted array |
O(n) |
O(n) |
O(log(n)) |
O(n*log(n)) |
| Unsorted doubly linked list |
O(1) |
O(n) |
O(n) |
O(n) |
| Sorted doubly linked list |
O(n) |
O(n) |
O(n) |
O(n2) |
| Balanced binary search tree |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n*log(n)) |
Compare insertion, deletion, search, and construction costs for array, linked-list, and balanced-tree implementations. The listed insertion costs assume no duplicate-key check. section 12.8
