Map

We know that a List is an ordered collection. If you have a List that stores instances of Student and you want to find the score of a specific Student based on the name, what should you do?

The simplest method is to iterate through the List, check if the name is equal, and then return the specified element:

java

List<Student> list = ...
Student target = null;
for (Student s : list) {
    if ("Xiao Ming".equals(s.name)) {
        target = s;
        break;
    }
}
System.out.println(target.score);

This requirement is actually very common: querying a value based on a key. Using a List to achieve this results in very low efficiency because, on average, you need to scan half of the elements to determine the result. The Map data structure, which is a key-value mapping table, is designed to efficiently look up values based on keys.

Here is how you can use a Map to query a Student by name:

java

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

public class Main {
    public static void main(String[] args) {
        Student s = new Student("Xiao Ming", 99);
        Map<String, Student> map = new HashMap<>();
        map.put("Xiao Ming", s); // Map "Xiao Ming" to the Student instance
        Student target = map.get("Xiao Ming"); // Retrieve the Student instance by key
        System.out.println(target == s); // true, same instance
        System.out.println(target.score); // 99
        Student another = map.get("Bob"); // Attempt to retrieve another key
        System.out.println(another); // Returns null if not found
    }
}

class Student {
    public String name;
    public int score;
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
}

From the above code, we can see that Map<K, V> is a key-value mapping table. When we call the put(K key, V value) method, it maps the key to the value and stores it in the Map. When we call V get(K key), we can retrieve the corresponding value using the key. If the key does not exist, it returns null. Similar to List, Map is also an interface, and the most commonly used implementation is HashMap.

If you only want to check whether a key exists, you can call the boolean containsKey(K key) method.

What happens if you call the put() method twice with the same key but different values when storing mappings in a Map? For example:

java

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 123);
        map.put("pear", 456);
        System.out.println(map.get("apple")); // 123
        map.put("apple", 789); // Put "apple" key again with a new value 789
        System.out.println(map.get("apple")); // 789
    }
}

Putting the same key-value pair multiple times does not cause any issues, but a key can only be associated with one value. In the above code, initially, the key "apple" is mapped to the Integer value 123. When the put() method is called again with the key "apple" and a new value 789, the original value 123 is replaced. In fact, the signature of the put() method is V put(K key, V value). If the key already exists, the put() method returns the old value that was replaced; otherwise, it returns null.

Always Remember

There are no duplicate keys in a Map because inserting the same key will only replace the existing key-value pair's value.

Additionally, while keys in a Map cannot be duplicated, values can be duplicated:

java

Map<String, Integer> map = new HashMap<>();
map.put("apple", 123);
map.put("pear", 123); // OK

Iterating Over a Map

To iterate over the keys of a Map, you can use a for-each loop to traverse the Set returned by the keySet() method of the Map instance. This Set contains all the unique keys:

java

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 123);
        map.put("pear", 456);
        map.put("banana", 789);
        for (String key : map.keySet()) {
            Integer value = map.get(key);
            System.out.println(key + " = " + value);
        }
    }
}

To iterate over both keys and values, you can use a for-each loop to traverse the entrySet() of the Map object, which contains each key-value mapping:

java

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 123);
        map.put("pear", 456);
        map.put("banana", 789);
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + " = " + value);
        }
    }
}

Unlike List, Map stores key-value mappings and does not guarantee order. When iterating, the order of traversal is neither necessarily the order in which keys were inserted using put(), nor the sorted order of keys. For example, with a HashMap, if you insert the keys "A", "B", "C", the traversal order of these keys is not guaranteed and may even differ across different JDK versions. However, each key will be traversed exactly once.

Note

When iterating over a Map, do not assume that the output keys are ordered!

Practice

Please write a program that searches for a score based on the name and uses a Map as a cache to improve lookup efficiency:

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Student> list = List.of(
            new Student("Bob", 78),
            new Student("Alice", 85),
            new Student("Brush", 66),
            new Student("Newton", 99));
        var holder = new Students(list);
        System.out.println(holder.getScore("Bob") == 78 ? "Test Passed!" : "Test Failed!");
        System.out.println(holder.getScore("Alice") == 85 ? "Test Passed!" : "Test Failed!");
        System.out.println(holder.getScore("Tom") == -1 ? "Test Passed!" : "Test Failed!");
    }
}

class Students {
    List<Student> list;
    Map<String, Integer> cache;

    Students(List<Student> list) {
        this.list = list;
        cache = new HashMap<>();
    }

    /**
     * Find the score based on name. Returns the score if found, otherwise returns -1.
     */
    int getScore(String name) {
        // First, search in the Map:
        Integer score = this.cache.get(name);
        if (score == null) {
            // TODO:
        }
        return score == null ? -1 : score.intValue();
    }

    Integer findInList(String name) {
        for (var ss : this.list) {
            if (ss.name.equals(name)) {
                return ss.score;
            }
        }
        return null;
    }
}

class Student {
    String name;
    int score;

    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
}

Summary

A Map is a mapping table that allows for quick lookup of values based on keys.
You can iterate over keys using keySet() or iterate over key-value pairs using entrySet() with a for-each loop.
The most commonly used implementation of Map is HashMap.

Map ​

Always Remember ​

Iterating Over a Map ​

Note ​

Practice ​

Summary ​

Map

Always Remember

Iterating Over a Map

Note

Practice

Summary