A map solves a practical lookup problem: keep contacts locally, find a contact quickly, add new entries, remove old ones, and avoid repeated server or database checks. Unlike a plain array, it is organized around keys rather than positions. section 4.2 section 4.3
A map—also called a dictionary, associative array, or symbol table—is a collection of key-value pairs. Each key appears at most once, and its associated value can be retrieved directly. A minimal interface provides insert(key, value), remove(key), and contains(key), which returns the value associated with a key when present. section 4.3
Choose an implementation according to the key domain, ordering needs, and memory constraints:
- Use a plain array only when the key domain is small enough to map keys directly to positions; otherwise, unused entries can waste substantial memory. section 4.4
- Use a hash table for a large possible key domain when only a limited number of keys are stored. Hashing maps keys to array indices; collisions require chaining or open addressing. section 4.4.3
- Expect hash-table operations to run in amortized O(1) time, on average, while recognizing that a map does not preserve a meaningful insertion order in the abstract model. section 4.2 section 4.4.3
- Consider binary search trees when ordered structure matters, or Bloom filters when lower memory use is worth accepting limited precision. section 6.1.1
Local contact lookup
Load contacts into a map when a session starts. Insert a new contact when the user adds one, remove a deleted contact, and check the map when a recipient is entered. Only an absent contact requires a prompt or later synchronization with the server. section 4.3
Use the abstract API and contract to distinguish a map's required behavior from the hash table or tree implementing it. section 4.3
