The Map

This chapter is about maps. A map is a collection of key–value pairs with distinct keys and no order, and it looks up the value stored under a given key.

After reading this chapter, you should be able to:

• Specify the Map ADT’s contract: what put returns when the key is already present, what get returns for an absent key, and why null values are rejected
• Implement a map as a linked list (LinkedMap) and as an unsorted array of entries (ArrayMap)
• Trace a sequence of map operations on LinkedMap and ArrayMap, telling a put that inserts a new key from one that overwrites a value
• Compare the two implementations in time and memory, including why linear search keeps get, put, and remove at $O(n)$ in both
• Explain why a key must not change after it is stored, which makes immutable keys such as String the safe choice
• Make a map iterable over its keys by having Map extend Iterable<K> and writing the key iterator for each implementation
• Implement an entries() traversal that visits every key–value pair in $O(n)$, instead of the $O(n^2)$ of calling get inside a key loop
• Design a read-only Map.Entry interface that lets a caller read a stored key and value but not change the map’s internals

You can download the accompanying code for this chapter: starter and solution.

Sections

1. Storing a Password
2. The Map ADT
3. Map ADT Specification
4. Using a Linked List to Implement a Map
5. The LinkedMap Class
6. Implementing get, containsKey, put, and remove
7. Tracing the LinkedMap
8. Using an Array to Implement a Map
9. The ArrayMap Class
10. Implementing get, containsKey, put, and remove
11. Tracing the ArrayMap
12. Keys Must Not Change
13. Iterating a Map
14. Returning the Stored Entries
15. Why Not Return the Stored Object
16. The Map.Entry Interface
17. Iterating the Entries