java - 如何让算法在 Java 中更有效地查找集合中的重复对象？

Question

我已经声明了一个PersonDetails具有以下三个属性的对象：

long id; 
String residence;

然后我有一个全部填充ArrayList的PersonDetails对象：

List<PersonDetails> personDetailsList = new ArrayList<>();

我需要遍历此列表以PersonDetails通过匹配其residence属性来找出重复项。

Id  |   Residence
 1  |     a       
 2  |     b      
 3  |     a       
 4  |     a       
 5  |     b       
 6  |     c     
 7  |     c      
 8  |     d      

我为完成此任务而创建的代码/算法如下，并使用了一个嵌套的for loop，这真的是低效的：

List<PersonDetails> personDetailsList = new ArrayList<>();
for (int i = 0; i <= personDetailsList.size() - 1; i++) {

    long personId = personDetailsList.get(i)
            .getId();
    String personResidence = personDetailsList.get(i)
            .getResidence();

    for (int j = i + 1; j <= personDetailsList.size() - 1; j++) {
        if (personResidence.equals(personDetailsList.get(j).getResidence())) {
            count++;
        }
    }
}

任何人都可以提出一种更省时的方法来解决这个问题吗？我正在尝试想出一种更好的方法来优化这一点，但非常感谢第二双眼睛。对于更大的数据集，嵌套的 for 循环将是地狱。

标签： javaperformancearraylistcollectionsduplicates

Answer 1

您可以对列表进行一次迭代PersonDetails，记住您residence第一次使用 a时遇到的情况Map<String, PersonDetails>：

List<PersonDetails> personDetails = new ArrayList<>();
personDetails.add(new PersonDetails(1, "a"));
personDetails.add(new PersonDetails(2, "b"));
personDetails.add(new PersonDetails(3, "a"));
personDetails.add(new PersonDetails(4, "a"));

Map<String, PersonDetails> encountered = new HashMap<>();
for (PersonDetails pd : personDetails) {
  PersonDetails first = encountered.putIfAbsent(pd.residence, pd);
  if (first != null) {
    pd.isDuplicate = first.id;
    first.isDuplicate = first.id; // mark the first encountered as duplicate
  }
}