如何优化基于HashMap的电话簿查询程序以降低运行时间？

Hey there! Let's get that phonebook program running within the time limits. The main issue here is how you're looking up entries in your HashMap—you're doing a full linear scan through every entry when HashMap is built to give you near-instant lookups. That's why your code is timing out on large test cases!

What's Wrong with the Current Approach? #

Your loop method iterates through every single entry in the HashMap to find a matching name. For each query, this is an O(n) operation. If you have 10,000 entries, that's 10,000 operations per query—multiply that by 10,000 queries, and you're looking at 100 million operations total. No wonder it's taking over 5 seconds!

HashMap's core superpower is its O(1) average lookup time using get(key). You don't need to loop through anything—just ask the HashMap directly for the value associated with a name.

Optimized Code #

Here's the revised version of your code with key fixes:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class HM2a {
    public static void main(String[] args) throws IOException {
        HashMap<String, String> phonebook = new HashMap<>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        try {
            int entries = Integer.parseInt(bufferedReader.readLine());

            // Populate the phonebook
            for (int i = 0; i < entries; i++) {
                String name = bufferedReader.readLine().toLowerCase();
                String phonenum = bufferedReader.readLine();
                phonebook.put(name, phonenum);
            }

            // Process queries and output results immediately
            for (int i = 0; i < entries; i++) {
                String query = bufferedReader.readLine().toLowerCase();
                String number = phonebook.get(query);
                if (number != null) {
                    System.out.println(query + "=" + number);
                } else {
                    System.out.println("Not found");
                }
            }
        } catch (Exception e) {
            System.err.println("Error: " + e.getMessage());
        } finally {
            // Clean up resources to avoid leaks
            if (bufferedReader != null) {
                bufferedReader.close();
            }
        }
    }
}

Key Optimizations #

• Replaced linear scan with HashMap.get(): Each query now takes O(1) time instead of O(n), which drastically reduces total runtime for large datasets.
• Removed the unnecessary listQuery: We output results immediately after each query, eliminating the memory overhead of storing all results and the extra loop to print them later.
• Added reader cleanup: Using a finally block to close the BufferedReader is good practice to prevent resource leaks (though this might not affect runtime directly).
• Simplified code: Got rid of the redundant loop method to make the code more readable and efficient.

Why This Works #

HashMap uses a hash table under the hood, so when you call get(query), it calculates the hash of the query string, jumps directly to the correct bucket, and finds the entry (if it exists) in constant time. This is night and day compared to looping through every entry for each query.

Give this version a try—those timeout test cases should pass now!

内容的提问来源于stack exchange，提问作者Dionisius Pratama