即使在 "phone number query code" 中使用 HashMap 后，在 Java 中也超出了时间限制

Question

You are given a phone book that consists of people's names and their phone numbers. After that, you will be given some person's name as a query. For each query, print the phone number of that person.

Input Format

The first line will have an integer denoting the number of entries in the phone book. Each entry consists of two lines: a name and the corresponding phone number.

After these, there will be some queries. Each query will contain a person's name. Read the queries until end-of-file.

Constraints: A person's name consists of only lower-case English letters and it may be in the format 'first-name last-name' or in the format 'first name'. Each phone number has exactly 8 digits without any leading zeros.

Output Format

For each case, print "Not found" if the person has no entry in the phone book. Otherwise, print the person's name and phone number. See sample output for the exact format.

To make the problem easier, we provided a portion of the code in the editor. You can either complete that code or write completely on your own.

Sample Input
3
uncle sam
99912222
tom
11122222
harry
12299933
uncle sam
uncle tom
harry
Sample Output
uncle sam=99912222
Not found
harry=12299933

所以，我使用 HashMap 尝试了以下代码：

import java.util.*;
public class Solution
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int q=sc.nextInt();
        sc.nextLine();
        HashMap<String,String> dic=new HashMap<>(q);
        for(int i=0;i<q;i++)
        {
            dic.put(sc.nextLine(),sc.nextLine());
        }
        
        while(sc.hasNext())
        {
           
            String s=sc.nextLine();
            int f=0;
            String ans="";
             for (Map.Entry<String, String> e : dic.entrySet())
            {
                if ((e.getKey()).equals(s))
                {
                    f=1;
                    ans=e.getKey()+"="+e.getValue();
                }    
            }
            if (f==1)
            System.out.println(ans);
            else
            System.out.println("Not found");
           
        }
    }
}

Answer 1

即使在使用 HashMap 时，您仍在迭代映射中的所有条目，这违反了使用哈希映射的目的。

使用containsKey检查地图是否有键并使用get获取值。这两个操作都是O(1).

....
String s = sc.nextLine();
if (dic.containsKey(s)) {
    System.out.println(s + "=" + s.get(s));
} else {
   System.out.println("Not found");
}

即使在 "phone number query code" 中使用 HashMap 后，在 Java 中也超出了时间限制

Getting Time Limit Exceeded in Java even after using HashMap in "phone number query code"

java

arrays

hashmap

data-structures