在Java中，即使在“电话号码查询代码”中使用HashMap，也会超过时间限制

Question

你会得到一本电话簿，里面有人们的名字和电话号码。之后，你会得到一些人的名字作为查询。对于每个查询，打印该人的电话号码。

输入格式

第一行有一个整数，表示通讯录中的条目数。每个条目由两行组成：姓名和相应的电话号码。

在这些之后，将会有一些查询。每个查询将包含一个人的姓名。读取查询直到文件结束。

限制条件：一个人的姓名仅由小写英文字母组成，可能采用“名字姓氏”格式，也可能采用“名字”格式。每个电话号码正好有8个数字，没有任何前导零。

输出格式

对于每种情况，如果对方在电话簿中没有条目，请打印“未找到”。否则，请打印此人的姓名和电话号码。有关确切格式，请参见示例输出。

为了使问题更简单，我们在编辑器中提供了一部分代码。您可以完成这段代码，也可以完全自己编写。

样本输入

3
uncle sam
99912222
tom
11122222
harry
12299933
uncle sam
uncle tom
harry

样本输出

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

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

使用包含密钥检查映射是否有密钥，并使用get获取值。这两个操作都是O（1）。

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