HashMaps, Frequency Counting, and Fast Lookups

HashMaps let students stop repeatedly searching and start storing relationships. The key is the lookup value. The value is the information associated with that key. Once students understand that separation, maps become one of the most useful tools in Advanced CS.

Worked example: engagement frequency map

Imagine a safe fictional dataset of course-interest clicks from a student website.

String[] clicks = {
    "AP CSA", "Python", "AP CSA", "USACO",
    "Python", "AI/ML", "AP CSA"
};

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

for (String course : clicks)
{
    if (!counts.containsKey(course))
    {
        counts.put(course, 0);
    }

    counts.put(course, counts.get(course) + 1);
}

After the loop, AP CSA maps to 3, Python maps to 2, and the other labels map to 1. The map replaces a nested loop that would recount every course name from scratch.

Grouping instead of counting

Maps can also store lists. This is a common next step for students who already understand frequency maps.

Map<String, ArrayList<String>> byCourse = new HashMap<>();

for (Signup s : signups)
{
    String course = s.getCourse();

    if (!byCourse.containsKey(course))
    {
        byCourse.put(course, new ArrayList<>());
    }

    byCourse.get(course).add(s.getStudentName());
}

Now the key is a course name and the value is a list of students interested in that course. The important move is this: create the empty list before trying to add into it.

Harder example: first repeated value

A map can remember positions too.

public static int firstRepeatedIndex(String[] values)
{
    Map<String, Integer> firstIndex = new HashMap<>();

    for (int i = 0; i < values.length; i++)
    {
        if (firstIndex.containsKey(values[i]))
            return i;

        firstIndex.put(values[i], i);
    }

    return -1;
}

The map stores the first place each value was seen. When a value appears again, the current index is the first repeated index.

Common traps

• Calling get on a missing key and then trying arithmetic with null.
• Confusing containsKey with containsValue.
• Assuming HashMap iteration order is sorted or insertion order.
• Using a map when duplicate keys need separate records instead of grouped values.