Exercise 2.5: Improving Performance with HashMap

Refactoring for Efficiency

Author

Chuck Nelson

Published

October 18, 2025

execute: echo: false —

1 Purpose

Welcome to your first major refactoring exercise. A key part of a software developer’s job isn’t just writing code that works, but writing code that works efficiently. In this exercise, you will learn how choosing the right data structure can dramatically improve your application’s performance. You will be introduced to the HashMap and use it to optimize task lookups.

2 What You’ll Accomplish

By the end of this exercise, you will have:

  • Understood the performance difference between searching an ArrayList versus a HashMap.
  • Refactored an existing class to use a HashMap for fast data retrieval.
  • Modified existing methods to keep multiple data structures in sync.
  • Explained the concept of a space-time trade-off in software design.
  • Program Learning Outcomes (PLOs):
    • 3. Apply concepts: You will apply advanced data structure concepts to a practical problem.
    • 5. Implement solutions: You will implement a more performant version of an existing feature.
  • Course Learning Outcomes (CLOs):
    • 1. Develop algorithmic solution: You will analyze and improve the efficiency of an algorithm.
    • 3. Create and use data types: You will use the HashMap generic type.
Learning Objective O*NET KSAs Technologies Used
Refactor code to use a HashMap for efficient lookups. Knowledge: Computers and Electronics
Skills: Programming, Critical Thinking
Abilities: Speed of Closure		 Object or component oriented development software: Java (HashMap)
Explain the concept of algorithmic complexity. Skills: Systems Analysis N/A

3 The Need for Speed

Think about a TaskManager.getTask(Long id) method. It needs to loop through the taskStore ArrayList from the beginning until it finds a matching ID. This is fine for 10 tasks, but what about 10,000? Or a million? The time it takes to find a task would grow linearly with the number of tasks. This is known as O(n) complexity, or “linear time.”

We can do better. A HashMap is a data structure that stores key-value pairs. It uses the key (in our case, the task ID) to calculate a hash code, which tells it almost exactly where to find the corresponding value (the Task object). This means that finding a task, whether there are 10 or 10 million, takes roughly the same, near-instant amount of time. This is O(1) complexity, or “constant time.”

To achieve this speed, a HashMap uses more memory than an ArrayList. This is a classic space-time trade-off: we use a bit more memory to gain a lot more speed.

3.1 1. Add a HashMap to TaskManager

Let’s refactor TaskManager.java. First, import the Map and HashMap classes. Then, add a new instance variable to hold our HashMap. The key will be the Integer task ID, and the value will be the Task object itself.

// Add these imports at the top
import java.util.Map;
import java.util.HashMap;

// Inside the TaskManager class
public class TaskManager {
    private List<Task> taskStore = new ArrayList<>();
    private Map<Integer, Task> taskMap = new HashMap<>(); // Our new lookup map
    private int nextTaskId = 1;
    // ... rest of the class
}

3.2 2. Keep the Data Structures in Sync

Now, whenever we add or remove a task, we need to update both our ArrayList and our HashMap.

Modify your addTask method:

// In TaskManager.java
public void addTask(Task task) {
    // ... (validation logic from previous exercises)
    task.setId(nextTaskId);

    taskStore.add(task); // Add to the list
    taskMap.put(task.getId(), task); // Add to the map

    nextTaskId++;
    System.out.println("Task added: " + task.getTitle());
}

3.3 Your Turn: Modify the Delete Method

Now, modify your deleteTask() method. When you remove a task from the taskStore list, you must also remove it from the taskMap.

Hint: To remove from the map, you’ll need the task’s ID. If you are deleting by index from the ArrayList, you can get the Task object before you delete it to find out its ID.

3.4 3. Optimize getTask

This is the payoff. We can now write a getTask() method with a single, elegant line of code to retrieve a Task by the HashMap key that matches the Task.id property.

Write your getTask method like this. Instead of throwing an exception, we will adopt a common pattern: return null if the resource isn’t found. This happens automatically since the HashMap.get() method returns a NULL when a key is not found.

// In TaskManager.java
public Task getTask(Long taskId) {
    // The .get() method of a HashMap returns null if the key doesn't exist.
    return taskMap.get(taskId);
}

Look how much cleaner and faster that is! We’ve replaced a whole loop with a single, elegant line of code. The caller of this method will now need to check for a null return value to know if the task was found.

4 Reflect and Review

ImportantReflection: 3-2-1

In your Microsoft Teams Student Notebook, answer the following:

  • 3 differences between an ArrayList and a HashMap.
  • 2 reasons why you might choose one data structure over another.
  • 1 question you still have about algorithmic complexity or refactoring.
TipCheck on Learning

Answer the following questions in your Microsoft Teams Student Notebook.

  1. In your own words, what is a “space-time trade-off”?
  2. What does O(n) complexity mean? Why is it less desirable than O(1) for lookups?
  3. In a HashMap<Integer, Task>, what is the “key” and what is the “value”?
  4. Why did we need to modify both addTask and your delete method after adding the HashMap?
Back to top