从集合中查找重复项的最快方法是什么

Question

这是我尝试过的,不知怎的,我觉得这不对,或者这不是性能最好的应用程序,所以有更好的方法来从Map中搜索和获取重复值,或者事实上任何集合.并且可以更好地遍历集合.

public class SearchDuplicates{
    public static void main(String[] args) {
        Map<Integer, String> directory=new HashMap<Integer, String>();
        Map<Integer, String> repeatedEntries=new HashMap<Integer, String>();

        // adding data
        directory.put(1,"john");
        directory.put(2,"michael");
        directory.put(3,"mike");
        directory.put(4,"anna");
        directory.put(5,"julie");
        directory.put(6,"simon");
        directory.put(7,"tim");
        directory.put(8,"ashley");
        directory.put(9,"john");
        directory.put(10,"michael");
        directory.put(11,"mike");
        directory.put(12,"anna");
        directory.put(13,"julie");
        directory.put(14,"simon");
        directory.put(15,"tim");
        directory.put(16,"ashley");

        for(int i=1;i<=directory.size();i++) {
           String result=directory.get(i);
           for(int j=1;j<=directory.size();j++) {
              if(j!=i && result==directory.get(j) &&j<i) {
                 repeatedEntries.put(j, result);
              }
           }
           System.out.println(result);
        }
        for(Entry<Integer, String> entry : repeatedEntries.entrySet()) {
           System.out.println("repeated "+entry.getValue());   
        }
   }
}

任何帮助,将不胜感激.提前致谢

Answer 1

您可以使用a Set来确定条目是否重复.此外,repeatedEntries也可能是一个Set,因为键是没有意义的:

Map<Integer, String> directory=new HashMap<Integer, String>();
Set<String> repeatedEntries=new HashSet<String>();
Set<String> seen = new HashSet<String>();

// ... initialize directory, then:

for(int j=1;j<=directory.size();j++){
    String val = directory.get(j);
    if (!seen.add(val)) {
        // if add failed, then val was already seen
        repeatedEntries.add(val);
    }
}

以额外内存为代价,这可以在线性时间内完成工作(而不是当前算法的二次时间).

编辑:这是一个循环的版本,不依赖于从1开始的连续整数键:

for (String val : directory.values()) {
    if (!seen.add(val)) {
        // if add failed, then val was already seen
        repeatedEntries.add(val);
    }
}

这将检测任何重复值Map,无论密钥如何.