Map / Dictionary (Associative Array ADT) — Junior Level¶

Table of Contents¶

1. Introduction
2. Prerequisites
3. Glossary
4. What Is a Map?
5. The Map ADT — Operations
6. Real-World Analogies
7. Implementations of the Map ADT
8. Big-O Summary
9. Built-In Map Types in Go, Java, Python
10. Code Examples
11. Iteration and Ordering
12. Default Value Patterns
13. The Key Contract
14. Pros and Cons
15. Edge Cases and Pitfalls
16. Common Mistakes
17. Cheat Sheet
18. Visual Animation
19. Summary
20. Further Reading

Introduction¶

Focus: "What is a Map ADT?" and "How is it different from a Hash Table?"

A Map (also called Dictionary, Associative Array, or just table) is one of the most useful data structures in everyday programming. It stores key-value pairs and lets you look up a value by its key.

This topic is about the Map ADT — the contract, not any single implementation. A Map can be backed by a hash table, a balanced binary search tree, a skip list, or even a sorted array. Each backing has different trade-offs, but the interface stays the same.

The hash-table topic (05-hash-tables) teaches one implementation. This topic teaches the interface and how to choose between implementations.

Prerequisites¶

• Required: Basic programming — variables, loops, functions, conditionals
• Required: Familiarity with arrays and lists
• Helpful: Read 05-hash-tables/junior.md first — it covers the most common backing
• Helpful: Big-O notation basics (06-algorithmic-complexity)

Glossary¶

What Is a Map?¶

A Map is a partial function from keys to values. "Partial" means not every possible key has a value — only keys that have been inserted do.

m: Key -> Value | absent

m("alice") = 95
m("bob")   = 82
m("carol") = absent   <-- never inserted

Three properties define a Map:

1. Keys are unique. Inserting ("alice", 100) after ("alice", 95) replaces the old value.
2. Lookup is by key, not by position. Unlike an array, you do not access m[0] — you access m["alice"].
3. No defined order (in the basic ADT). Some implementations add ordering as an extra guarantee.

A Map is the right tool whenever you think "given X, what is Y?": - Given a username, what is the user record? - Given a word, what is its frequency? - Given a product SKU, what is the price? - Given an HTTP status code, what is the status message?

The Map ADT — Operations¶

The Map ADT defines a set of operations. Different languages name them differently, but the contract is the same.

"Absent" vs "null value"¶

There is a subtle but important distinction:

• Key not present — containsKey(k) returns false
• Key present, value is null/None/nil — containsKey(k) returns true

Languages handle this differently:

This matters when null is a valid value:

m["alice"] = null   <-- present, value is null
m["bob"]   = absent <-- never inserted

get(m, "alice") -> null (Java: ambiguous!)
get(m, "bob")   -> null

Real-World Analogies¶

1. Phone Book¶

A phone book maps names to phone numbers. You look up by name. Some phone books are sorted (ordered map); a digital contact list might be insertion-ordered.

2. English Dictionary¶

A dictionary maps words to definitions. Real dictionaries are sorted alphabetically — an example of an ordered map. You scan by word, not by page number.

3. Library Catalog¶

A catalog maps call numbers to books. Given the call number you can locate the book. The catalog itself does not store books in call-number order — it just records the mapping.

4. Environment Variables¶

os.environ maps variable names to string values. The OS gives you PATH, HOME, USER. You query by name.

5. Restaurant Menu¶

A menu maps dish names to prices and descriptions. You order by name; the kitchen looks up what to prepare. Menus often have an order (appetizers, mains, desserts) — an insertion-ordered map.

Where the analogy breaks: real-world objects (a book, a dish) are physical; a Map entry is just a binding. Deleting a Map entry does not destroy the value — other references may still hold it.

Implementations of the Map ADT¶

The same Map interface can be implemented several ways. The choice affects performance and ordering.

1. Hash-Backed (Unordered Map)¶

• Backing: Hash table (see 05-hash-tables)
• Examples: Go's map, Java's HashMap, Python's dict, C++ unordered_map
• Big-O: O(1) average for get/put/remove; O(n) worst case
• Iteration order: Undefined (or insertion-ordered as an implementation detail in Python 3.7+)

2. Tree-Backed (Ordered Map)¶

• Backing: Balanced BST (red-black tree usually)
• Examples: Java's TreeMap, C++ std::map, Python's sortedcontainers.SortedDict
• Big-O: O(log n) for get/put/remove
• Iteration order: Sorted by key
• Extras: Range queries, firstKey, lastKey, floorKey, ceilingKey

3. Insertion-Ordered Map¶

• Backing: Hash table + doubly-linked list of entries
• Examples: Java's LinkedHashMap, Python's dict (3.7+ guarantees this), PHP's array
• Big-O: O(1) average for get/put/remove
• Iteration order: Insertion order

4. Access-Ordered Map (LRU Pattern)¶

• Backing: Hash table + doubly-linked list, reordered on access
• Examples: Java's LinkedHashMap with accessOrder=true, Python's OrderedDict.move_to_end
• Use: Building blocks for LRU caches (see 21-advanced-structures/lru-cache)

Big-O Summary¶

k = number of entries returned by the range query.

Built-In Map Types in Go, Java, Python¶

Code Examples¶

Example 1: Word Frequency Counter¶

We count how many times each word appears in a sentence. Classic Map use case.

Go¶

package main

import (
    "fmt"
    "strings"
)

func wordFreq(text string) map[string]int {
    freq := make(map[string]int)
    for _, w := range strings.Fields(text) {
        freq[w]++ // zero value of int is 0; increment works on absent key
    }
    return freq
}

func main() {
    text := "the quick brown fox the lazy dog the fox"
    for w, n := range wordFreq(text) {
        fmt.Printf("%s: %d\n", w, n)
    }
}

Java¶

import java.util.HashMap;
import java.util.Map;

public class WordFreq {
    public static Map<String, Integer> wordFreq(String text) {
        Map<String, Integer> freq = new HashMap<>();
        for (String w : text.split("\\s+")) {
            freq.merge(w, 1, Integer::sum); // 'merge' is idiomatic for counters
        }
        return freq;
    }

    public static void main(String[] args) {
        String text = "the quick brown fox the lazy dog the fox";
        wordFreq(text).forEach((w, n) -> System.out.println(w + ": " + n));
    }
}

Python¶

from collections import Counter

def word_freq(text: str) -> dict[str, int]:
    return dict(Counter(text.split()))

if __name__ == "__main__":
    text = "the quick brown fox the lazy dog the fox"
    for w, n in word_freq(text).items():
        print(f"{w}: {n}")

What it does: Builds a Map from word to count. Uses each language's idiom for "increment-or-insert." Run: go run main.go | javac WordFreq.java && java WordFreq | python wordfreq.py

Example 2: Phone Book — Add, Lookup, Delete¶

A small phone book showing the basic CRUD operations of a Map.

Go¶

package main

import "fmt"

func main() {
    phones := map[string]string{}

    // put
    phones["alice"] = "555-1234"
    phones["bob"] = "555-5678"

    // get with comma-ok: distinguishes absent from empty string
    if num, ok := phones["alice"]; ok {
        fmt.Println("alice:", num)
    }
    if _, ok := phones["carol"]; !ok {
        fmt.Println("carol not found")
    }

    // remove
    delete(phones, "bob")

    // size
    fmt.Println("entries:", len(phones))
}

Java¶

import java.util.HashMap;
import java.util.Map;

public class PhoneBook {
    public static void main(String[] args) {
        Map<String, String> phones = new HashMap<>();

        phones.put("alice", "555-1234");
        phones.put("bob", "555-5678");

        // Distinguish absent vs null-valued with containsKey
        if (phones.containsKey("alice")) {
            System.out.println("alice: " + phones.get("alice"));
        }
        if (!phones.containsKey("carol")) {
            System.out.println("carol not found");
        }

        phones.remove("bob");
        System.out.println("entries: " + phones.size());
    }
}

Python¶

phones: dict[str, str] = {}
phones["alice"] = "555-1234"
phones["bob"] = "555-5678"

# Use 'in' to test membership, get(k, default) to avoid KeyError
if "alice" in phones:
    print("alice:", phones["alice"])
if "carol" not in phones:
    print("carol not found")

del phones["bob"]
print("entries:", len(phones))

Example 3: Ordered Map — Sorted Iteration¶

Iterate keys in sorted order. Hash-backed maps cannot do this; tree-backed can.

Go¶

package main

import (
    "fmt"
    "sort"
)

func main() {
    scores := map[string]int{"bob": 82, "alice": 95, "carol": 91}

    // Go's map iteration order is randomized. To iterate sorted,
    // extract keys, sort, then look up values.
    keys := make([]string, 0, len(scores))
    for k := range scores {
        keys = append(keys, k)
    }
    sort.Strings(keys)
    for _, k := range keys {
        fmt.Printf("%s: %d\n", k, scores[k])
    }
}

Java¶

import java.util.TreeMap;

public class SortedScores {
    public static void main(String[] args) {
        // TreeMap iterates keys in natural sorted order.
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("bob", 82);
        scores.put("alice", 95);
        scores.put("carol", 91);

        scores.forEach((k, v) -> System.out.println(k + ": " + v));
        // alice: 95, bob: 82, carol: 91
    }
}

Python¶

scores = {"bob": 82, "alice": 95, "carol": 91}

# Plain dict preserves insertion order; sort keys for sorted iteration.
for k in sorted(scores):
    print(f"{k}: {scores[k]}")

Iteration and Ordering¶

Iteration order is the most surprising aspect of Maps for new programmers.

Rule: never rely on iteration order unless the implementation documents one. Code that "accidentally works" because keys happen to print alphabetically will break in production.

Default Value Patterns¶

A common need: "get the value for key K, or some default if K is absent."

Go¶

// Go does not have a built-in getOrDefault, but the comma-ok idiom is clean.
freq := map[string]int{}
count, ok := freq["apple"]
if !ok {
    count = 0
}
freq["apple"] = count + 1

// Shorter: zero value of int is 0, so for counters:
freq["apple"]++

Java¶

// getOrDefault
int count = freq.getOrDefault("apple", 0);
freq.put("apple", count + 1);

// computeIfAbsent — for List<V> values
map.computeIfAbsent("apple", k -> new ArrayList<>()).add("red");

// merge — for counters
freq.merge("apple", 1, Integer::sum);

Python¶

# .get() with default
count = freq.get("apple", 0)
freq["apple"] = count + 1

# collections.defaultdict — creates the default on missing access
from collections import defaultdict
freq = defaultdict(int)
freq["apple"] += 1   # int() returns 0

groups = defaultdict(list)
groups["fruit"].append("apple")

The Key Contract¶

For a Map to work, the key type must satisfy certain rules.

Rule of thumb across all three: Use immutable keys. Strings, integers, and tuples of immutables are safe. Mutable keys (lists, mutable objects) cause bugs if changed after insertion.

Pros and Cons¶

When to use: Lookups by an identifier. Counting. Caching. Indexing. Configuration. When NOT to use: Sequential numeric access (use array). When you need both ordering AND O(1) (use LinkedHashMap or accept the tree's log n).

Edge Cases and Pitfalls¶

• Mutating keys after insertion: Changes hash/equality; entry becomes unreachable
• Iterating while modifying: ConcurrentModificationException in Java; undefined in Go
• Null keys/values: HashMap allows one null key and null values; TreeMap does not allow null keys; Go's map does not allow nil for non-pointer types as keys; Python forbids unhashable keys
• Hash collisions degrading performance: Bad hash function or adversarial input flips O(1) to O(n)
• Assuming iteration order: Tests that pass locally but fail in CI due to different order

Common Mistakes¶

• Using a Map when an array would do (e.g., map[int]string for indices 0..n-1)
• Using HashMap when you need sorted iteration — pick TreeMap
• Calling get() and containsKey() twice instead of one comma-ok / getOrDefault
• Using a mutable object as a key
• Relying on Python 3.7+ dict ordering for cross-version code (older Pythons may not preserve it)
• Returning null from get() and not handling it
• Mutating a Map during iteration

Cheat Sheet¶

Visual Animation¶

See animation.html for an interactive Map visualization. The animation shows put / get / remove against three ordering variants (unordered, sorted, insertion-ordered) so you can compare iteration behavior side-by-side.

Summary¶

The Map ADT is a contract: store key-value pairs, look up values by key. The hash-table topic teaches one implementation; this topic teaches that there are many. Pick by ordering needs and complexity budget:

• Unordered + fast: HashMap / map / dict
• Sorted: TreeMap / std::map
• Insertion-ordered: LinkedHashMap / Python dict
• Access-ordered: LinkedHashMap with accessOrder=true / OrderedDict

Master the key contract, the absent-vs-null distinction, and the default-value patterns — they show up in every codebase.

Further Reading¶

• Introduction to Algorithms (CLRS) — Chapter 11: Hash Tables
• Java Map interface JavaDoc
• Python: collections module, PEP 468 (insertion-ordered dict)
• Go: language spec on map types and iteration
• 05-hash-tables (this section) — the most common backing
• 21-advanced-structures/lru-cache — building eviction on top of a Map