0.13.1.1. What is a Map?¶

A Map (often referred to in computer science as a dictionary, associative array, or symbol table) is a collection that establishes relationships between keys and values. Instead of using numeric slot numbers to access data, a map uses arbitrary domain objects—frequently strings or custom identifiers—to index into the collection.

A map consists of a collection of key-value associations (often called entries or mappings):

Key (Lookup Identifier)        Value (Associated Data)
-----------------------        ------------------------
"CS 1114"              ===>    "Intro to Software Design"
"MATH 1225"            ===>    "Calculus of a Single Variable"
"ENGL 1105"            ===>    "First-Year Writing"

Every association in a map obeys two fundamental rules:

1. Keys Must Be Unique: A map cannot contain duplicate keys. Each key identifies at most one associated value. If you attempt to insert a new pair using a key that already exists in the map, the new value overwrites the previous value.

2. Values Need Not Be Unique: Multiple distinct keys may be associated with identical values. For example, two different courses (“MATH 1225” and “MATH 1226”) might both have 4 credit hours associated with them.

0.13.1.2. The Generic Map<K, V> Interface¶

The Map<K, V> interface in the java.util package utilizes two generic type parameters:

• K specifies the data type of the keys used for lookup.

• V specifies the data type of the values stored in the collection.

For example:

• Map<String, String>: maps a person’s name to their phone number.

• Map<String, Integer>: maps a student username to their exam score.

• Map<Integer, Student>: maps an integer student ID to a Student object.

• Map<String, Command>: maps a command verb string (like "temp") to an executable Command object.

Because Java collections only operate on reference types, primitive types must be specified using their corresponding wrapper classes (such as Integer, Double, or Boolean). Java’s autoboxing mechanisms automatically handle converting between primitives and wrapper objects when adding or reading data.

0.13.1.3. Concrete Implementations: HashMap vs. TreeMap¶

Just as List<E> is an interface implemented by concrete classes like ArrayList<E> and LinkedList<E>, Map<K, V> is an interface that cannot be instantiated directly. The Java Collections Framework provides several concrete classes implementing Map<K, V>, the two most common being:

1. java.util.HashMap<K, V>: Implements the map using an internal data structure known as a hash table. A hash table uses a mathematical hashing function to convert any key object into an internal bucket index, allowing insertions, lookups, and removals to complete in $O(1)$ constant time on average, regardless of how many thousands of entries the map holds. However, HashMap does not preserve any predictable ordering of its keys.

2. java.util.TreeMap<K, V>: Implements the map using a balanced binary search tree structure (a Red-Black Tree). It guarantees that when iterating through keys, they will always appear in sorted natural order (such as alphabetical order for strings). However, this sorted organization requires $O(log N)$ time for lookups, insertions, and removals, making it slightly slower than HashMap for large datasets.

In CS 1114, HashMap<K, V> is our standard default choice for mapping tasks, just as ArrayList<E> is our default choice for lists. We instantiate maps using interface polymorphism:

// Declaring with the interface type, instantiating with concrete HashMap
Map<String, Integer> inventory = new HashMap<String, Integer>();

Using the diamond operator (<>), the generic type parameters on the right side can be inferred by the compiler:

Map<String, Integer> inventory = new HashMap<>();

0.13.2.1. Storing Associations: put(key, value)¶

To insert a new association into a map, you call the put() method, passing the key as the first argument and the value as the second:

Map<String, Book> catalog = new HashMap<>();

Book book1 = new Book("Intro to Java", "Shaffer", 450);
Book book2 = new Book("Data Structures", "Weiss", 620);

catalog.put("978-0134685991", book1);
catalog.put("978-0135166307", book2);

When put() is called:

• If the key does not yet exist in the map, a brand-new association is created, the size of the map increases by one, and put() returns null.

• If the key already exists in the map, the map replaces the old value with the new value, leaves the map’s size unchanged, and returns the previous value that was displaced.

This overwriting behavior is fundamental:

Book book3 = new Book("Intro to Java (2nd Edition)", "Shaffer", 480);

// Replaces book1 under the identical ISBN key:
Book previous = catalog.put("978-0134685991", book3);

// previous now references book1; catalog now associates the key with book3

0.13.2.2. Retrieving Values: get(key)¶

To retrieve the value associated with a specific key, call get():

Book found = catalog.get("978-0135166307");
System.out.println("Title: " + found.getTitle());

String targetISBN = "978-0000000000"; // Nonexistent ISBN
Book result = catalog.get(targetISBN);

if (result != null)
{
    System.out.println("Found book: " + result.getTitle());
}
else
{
    System.out.println("No book found matching ISBN: " + targetISBN);
}

0.13.2.3. Defensive Membership Checking: containsKey(key)¶

If you merely want to determine whether a key exists in a map without necessarily retrieving its value, or if you want to verify presence before accessing, use containsKey():

if (catalog.containsKey("978-0135166307"))
{
    System.out.println("The catalog contains this book.");
}

The containsKey() method returns true if the key is stored in the map and false otherwise, executing in constant $O(1)$ time.

0.13.2.4. Removing Associations: remove(key)¶

To remove an association, call remove() with the key:

Book removedBook = catalog.remove("978-0135166307");

// removedBook holds the removed Book object
// catalog.containsKey("978-0135166307") now returns false
// catalog.size() is decremented by 1

If the specified key does not exist in the map, remove() leaves the map unchanged and safely returns null.

0.13.2.5. Looping Over Map Keys with keySet()¶

Unlike a list or an array, a map does not provide numeric indices, and Map<K, V> does not implement Iterable. You cannot directly write for (Book b : catalog).

Instead, because the keys of a map are unique, Java provides the keySet() method. The keySet() method returns a java.util.Set<K> containing all the unique keys stored in the map.

Because sets implement Iterable, you can traverse the keys using a standard enhanced for-each loop, looking up each corresponding value with get():

for (String isbn : catalog.keySet())
{
    Book currentBook = catalog.get(isbn);
    System.out.println("ISBN: " + isbn + " -> Title: " + currentBook.getTitle());
}

This pattern is clean, intuitive, and the standard way to inspect all entries in a map. If you only need to iterate over the values without caring about their keys, you can similarly use catalog.values():

for (Book currentBook : catalog.values())
{
    System.out.println("Book title: " + currentBook.getTitle());
}

0.13.3.1. Properties of a Set¶

A set differs from a list in three essential ways:

1. Strict Element Uniqueness: A set cannot contain duplicate elements. If you attempt to add an element that is already in the set, the addition is ignored.

2. No Positional Indexing: Sets have no concept of “first element”, “second element”, or “index 4”. You cannot call set.get(0).

3. High-Speed Membership Testing: While determining whether an element exists in a List<E> requires scanning up to all $N$ elements via linear search ($O(N)$), a HashSet<E> checks membership via hashing in $O(1)$ constant time.

0.13.3.2. Concrete Implementations: HashSet vs. TreeSet¶

Like Map, Set<E> is an interface implemented by concrete classes:

• java.util.HashSet<E>: Stores elements using a hash table. Provides $O(1)$ insertions, deletions, and membership checks. Does not maintain any predictable iteration order. This is our standard choice.

• java.util.TreeSet<E>: Stores elements in a balanced binary search tree. Maintains elements in sorted natural order (e.g., ascending alphabetical or numerical order) with $O(log N)$ performance.

0.13.3.3. Core Set Operations¶

The Set<E> interface provides an intuitive collection API:

public boolean add(E element);      // Adds element; returns true if added, false if duplicate
public boolean contains(Object o);  // Returns true if element is present in O(1) time
public boolean remove(Object o);    // Removes element; returns true if present
public int size();                  // Returns count of unique elements
public boolean isEmpty();           // Returns true if size() == 0
public void clear();                // Removes all elements

0.13.3.4. Using a HashSet¶

Consider managing unique tags on library books or tracking active student usernames:

Set<String> activeUsers = new HashSet<>();

// Adding elements
activeUsers.add("edwards");
activeUsers.add("alovelace");
activeUsers.add("aturing");

// Attempting to add a duplicate element
boolean wasAdded = activeUsers.add("edwards");
System.out.println("Was duplicate added? " + wasAdded); // prints false
System.out.println("Active user count: " + activeUsers.size()); // prints 3

// Testing membership in O(1) time
if (activeUsers.contains("alovelace"))
{
    System.out.println("Ada Lovelace is currently active.");
}

// Iterating with enhanced for-each
for (String user : activeUsers)
{
    System.out.println("User: " + user);
}

0.13.3.5. Practical Application: Tracking Visited Nodes¶

One of the most vital uses of a Set in computer science is cycle detection and path tracking. When traversing interconnected networks—such as web crawlers visiting hyperlinks, GPS routing algorithms navigating road maps, or autonomous agents wandering through connected spaces—it is easy to get trapped in infinite loops if you revisit a location you have already explored.

By storing visited location identifiers in a Set<String>, an algorithm can check visited.contains(locationId) in $O(1)$ time to avoid cyclic traps:

Set<String> visitedLocations = new HashSet<>();

public void visit(String locationId)
{
    if (visitedLocations.contains(locationId))
    {
        System.out.println("You have already visited " + locationId);
    }
    else
    {
        System.out.println("Exploring new area: " + locationId);
        visitedLocations.add(locationId);
    }
}

0.13.4.1. The Map-Based Command Registry¶

Now that you understand associative collections, we can deliver the elegant, professional solution foreshadowed in Chapter 11: replacing conditional ladders with a Map-driven command registry.

Instead of hardcoding command decisions into an if/else-if chain, the interpreter maintains a:

Map<String, Command> commands = new HashMap<>();

In this structure:

• The key is the command word string (e.g., "status", "temp", "light").

• The value is an object implementing the Command interface that encapsulates the behavior to execute.

0.13.4.2. Registering Commands Dynamically¶

During initialization, the interpreter populates the registry by registering command instances:

public class CommandInterpreter
{
    private Map<String, Command> commands;

    public CommandInterpreter(Thermostat thermostat, SmartLight light)
    {
        commands = new HashMap<>();

        // Register command words mapping directly to Command objects
        commands.put("status", new StatusCommand(thermostat, light));
        commands.put("temp", new TemperatureCommand(thermostat));
        commands.put("light", new LightCommand(light));
    }

    public void registerCommand(String verb, Command command)
    {
        commands.put(verb.toLowerCase(), command);
    }
    ...
}

0.13.4.3. Executing via Map Lookup¶

With the map in place, the entire multi-page conditional ladder collapses into just three lines of code:

public void interpretSingleCommand(String verb)
{
    Command cmd = commands.get(verb.toLowerCase());

    if (cmd != null)
    {
        cmd.execute();
    }
    else
    {
        System.out.println("Unrecognized command: " + verb);
    }
}

Look closely at how this works:

1. commands.get(verb.toLowerCase()) performs an immediate $O(1)$ hash table lookup.

2. If the command word is registered, get() returns the corresponding Command object, and cmd.execute() polymorphically triggers the action.

3. If the command word is unrecognized, get() returns null, and the else branch cleanly notifies the user.

0.13.4.4. Architectural Comparison¶

0.13.5.1. Representing Spatial Connections with Map<String, CampusLocation>¶

How do we model an arbitrary spatial graph in object-oriented Java?

Consider an interactive digital campus tour guide. We can design a CampusLocation class where each location encapsulates its own pathway map:

public class CampusLocation
{
    private String name;
    private String description;
    private Map<String, CampusLocation> pathways;

    public CampusLocation(String name, String description)
    {
        this.name = name;
        this.description = description;
        this.pathways = new HashMap<>();
    }

    public String getName()
    {
        return name;
    }

    public String getDescription()
    {
        return description;
    }

    public void connectLocation(String pathwayName, CampusLocation destination)
    {
        pathways.put(pathwayName.toLowerCase(), destination);
    }

    public CampusLocation getDestination(String pathwayName)
    {
        return pathways.get(pathwayName.toLowerCase());
    }
}

In this design:

• The key is the pathway name or directional label entered by the user (e.g., "bridge", "tunnel", "quad", "north").

• The value is a reference to the neighboring CampusLocation reached by following that path.

0.13.5.2. Connecting Locations into a Spatial Topology¶

Creating a virtual campus world simply requires instantiating the locations and linking their pathways:

// 1. Create the campus locations
CampusLocation library = new CampusLocation(
    "Newman Library", "a six-story hub of study spaces and media labs");
CampusLocation studentCenter = new CampusLocation(
    "Squires Center", "a lively student union with dining and music venues");
CampusLocation drillfield = new CampusLocation(
    "The Drillfield", "a vast open oval lawn crisscrossed with walking paths");

// 2. Link pathways between locations
library.connectLocation("plaza", studentCenter);
studentCenter.connectLocation("plaza", library);

library.connectLocation("walkway", drillfield);
drillfield.connectLocation("walkway", library);

studentCenter.connectLocation("bridge", drillfield);
drillfield.connectLocation("bridge", studentCenter);

Notice the flexibility of this model:

• If a visitor is at Newman Library and chooses "plaza", library.getDestination("plaza") returns the Squires Center.

• If a visitor asks for "tunnel" while at the library, library.getDestination("tunnel") safely returns null because no tunnel connection was registered.

• Adding an underground pedestrian tunnel or a new academic building requires calling connectLocation()—no existing location code needs modification!

0.13.5.3. Dynamically Formatting Available Pathways¶

Because the pathways are stored in a map, a location can inspect its own keySet() to dynamically display all available travel options to the user:

public String listAvailablePathways()
{
    StringBuilder sb = new StringBuilder("Available pathways:");
    for (String pathway : pathways.keySet())
    {
        sb.append(" ").append(pathway);
    }
    return sb.toString();
}

If the library connects via the plaza and the walkway, listAvailablePathways() outputs: "Available pathways: plaza walkway". If you later add a "skybridge", the method automatically includes it without any code modifications.

0.13.6.1. The Normalization Rule: “Normalize on Entry, Normalize on Lookup”¶

To guarantee robust, defect-free retrieval, professional software systems follow the Key Normalization Rule:

Java’s String class provides two essential methods for this purpose:

1. .toLowerCase(): Converts all uppercase characters to lowercase.

2. .trim(): Strips all leading and trailing whitespace.

We implement this rule defensively inside our domain classes:

public class CampusLocation
{
    private Map<String, CampusLocation> pathways = new HashMap<>();

    public void connectLocation(String pathwayName, CampusLocation destination)
    {
        if (pathwayName != null && destination != null)
        {
            // Normalize on entry:
            pathways.put(pathwayName.trim().toLowerCase(), destination);
        }
    }

    public CampusLocation getDestination(String pathwayName)
    {
        if (pathwayName == null)
        {
            return null;
        }
        // Normalize on lookup:
        return pathways.get(pathwayName.trim().toLowerCase());
    }
}

With these defensive normalization guards in place:

location.connectLocation("BRIDGE", studentCenter); // Stored internally as "bridge"

location.getDestination("bridge");          // returns studentCenter
location.getDestination("Bridge");          // returns studentCenter
location.getDestination("  BRIDGE  ");      // returns studentCenter

Every variant reliably resolves to the identical destination, creating a smooth, forgiving user experience.

0.13.7.1. Testing Campus Navigation Pathways¶

A robust test class for CampusLocation must verify:

1. Setting and retrieving connections with standard lowercase pathway names.

2. Case-insensitivity and whitespace trimming (verifying uppercase, mixed-case, and padded lookups).

3. Querying nonexistent pathways safely returning null.

4. Guarding against null lookup arguments without throwing exceptions.

5. Overwriting a pathway with a new destination.

6. Pathway listing via listAvailablePathways().

public class CampusLocationTest extends TestCase
{
    private CampusLocation library;
    private CampusLocation studentCenter;
    private CampusLocation drillfield;

    /**
     * Sets up the test fixture before each test method runs.
     */
    public void setUp()
    {
        library = new CampusLocation("Library", "study spaces");
        studentCenter = new CampusLocation("Student Center", "dining halls");
        drillfield = new CampusLocation("Drillfield", "open lawn");

        library.connectLocation("plaza", studentCenter);
        library.connectLocation("walkway", drillfield);
    }

    /**
     * Verifies successful destination retrieval with standard lowercase keys.
     */
    public void testGetDestinationStandard()
    {
        assertEquals(studentCenter, library.getDestination("plaza"));
        assertEquals(drillfield, library.getDestination("walkway"));
    }

    /**
     * Verifies that getDestination is case-insensitive and trims whitespace.
     */
    public void testGetDestinationCaseInsensitive()
    {
        assertEquals(studentCenter, library.getDestination("PLAZA"));
        assertEquals(studentCenter, library.getDestination("Plaza"));
        assertEquals(drillfield, library.getDestination("  WALKWAY  "));
    }

    /**
     * Verifies that querying a nonexistent pathway returns null.
     */
    public void testGetDestinationNonexistent()
    {
        assertNull(library.getDestination("tunnel"));
        assertNull(library.getDestination("skybridge"));
    }

    /**
     * Verifies that null queries safely return null without throwing an exception.
     */
    public void testGetDestinationNullKey()
    {
        assertNull(library.getDestination(null));
    }

    /**
     * Verifies that re-connecting a pathway overwrites the previous destination.
     */
    public void testConnectLocationOverwrite()
    {
        CampusLocation bookstore = new CampusLocation("Bookstore", "merchandise");
        library.connectLocation("plaza", bookstore);

        assertEquals(bookstore, library.getDestination("plaza"));
    }

    /**
     * Verifies that listAvailablePathways outputs all registered pathway labels.
     */
    public void testListAvailablePathways()
    {
        String pathways = library.listAvailablePathways();

        assertTrue(pathways.contains("plaza"));
        assertTrue(pathways.contains("walkway"));
        assertFalse(pathways.contains("tunnel"));
    }
}

0.13.7.2. Testing Map-Driven Command Interpreters¶

When testing a command interpreter powered by Map<String, Command>, you verify that valid command words invoke receiver actions while unknown command words trigger default fallbacks:

public class CommandInterpreterTest extends TestCase
{
    private Thermostat thermostat;
    private SmartLight light;
    private CommandInterpreter interpreter;

    public void setUp()
    {
        thermostat = new Thermostat(70);
        light = new SmartLight();
        interpreter = new CommandInterpreter(thermostat, light);
    }

    /**
     * Tests executing a registered command via the map dispatcher.
     */
    public void testValidCommandExecution()
    {
        assertFalse(light.isOn());

        interpreter.interpretSingleCommand("light on");
        assertTrue(light.isOn());

        interpreter.interpretSingleCommand("light off");
        assertFalse(light.isOn());
    }

    /**
     * Tests case-insensitive command verb dispatch.
     */
    public void testCommandVerbCasing()
    {
        interpreter.interpretSingleCommand("TEMP 74");
        assertEquals(74, thermostat.getTargetTemperature());

        interpreter.interpretSingleCommand("Temp 68");
        assertEquals(68, thermostat.getTargetTemperature());
    }

    /**
     * Tests unrecognized command words gracefully fall back without crashing.
     */
    public void testUnrecognizedCommand()
    {
        // Should output error message without throwing exception:
        interpreter.interpretSingleCommand("jump");
        assertEquals(70, thermostat.getTargetTemperature());
        assertFalse(light.isOn());
    }
}

Notice how clean, fast, and deterministic these unit tests are. Because our classes rely on encapsulated maps and clean interfaces, every execution path can be verified with high-speed assertions in BlueJ and Web-CAT.