在忽略字段的列表中查找重复项

Question

我有 List 个人，我想查找重复的条目，考虑除 id 之外的所有字段。所以使用 equals() 方法（结果是 List.contains()），因为他们考虑了 id。

public class Person {
    private String firstname, lastname;
    private int age;
    private long id;
}

修改 equals() 和 hashCode() 方法以忽略 id 字段不是一个选项，因为代码的其他部分依赖于此。

如果我想忽略 id 字段，在 Java 中整理重复项的最有效方法是什么？

Answer 1

您可以使用 Java HashMap 和 <K,V> 对。 Map<K,V> map = new HashMap<K,V>()。此外，还可以使用某种形式的 Comparator 实现。如果您检查 containsKey 或 containsValue 方法并发现您已经有了一些东西（即您正在尝试添加重复项，请将它们保留在原始列表中。否则，将它们弹出。这样，您最终会得到一个列表在您的原始列表中重复的元素。TreeSet<,> 将是另一种选择，但我还没有使用它，因此无法提供建议。

Answer 2

正如 @LuiggiMendoza 在评论中建议的那样：

您可以创建自定义 Comparator class 比较两个 Person 对象是否相等，忽略它们的 ID。

class PersonComparator implements Comparator<Person> {

    // wraps the compareTo method to compare two Strings but also accounts for NPE
    int compareStrings(String a, String b) {
        if(a == b) {           // both strings are the same string or are null
          return 0;
        } else if(a == null) { // first string is null, result is negative
            return -1;
        } else if(b == null){  // second string is null, result is positive
            return 1;
        } else {               // no strings are null, return the result of compareTo
            return a.compareTo(b);
        }
    }

    @Override
    public int compare(Person p1, Person p2) {

        // comparisons on Person objects themselves
        if(p1 == p2) {                 // Person 1 and Person 2 are the same Person object
            return 0;
        }
        if(p1 == null && p2 != null) { // Person 1 is null and Person 2 is not, result is negative
            return -1;
        }
        if(p1 != null && p2 == null) { // Person 1 is not null and Person 2 is, result is positive
            return 1;
        }

        int result = 0;

        // comparisons on the attributes of the Persons objects
        result = compareStrings(p1.firstname, p2.firstname);
        if(result != 0) {   // Persons differ in first names, we can return the result
            return result;
        }
        result = compareStrings(p1.lastname, p2.lastname);
        if(result != 0) {  // Persons differ in last names, we can return the result
            return result;
        }

        return Integer.compare(p1.age, p2.age); // if both first name and last names are equal, the comparison difference is in their age
    }
}

现在您可以将 TreeSet 结构与此自定义 Comparator 一起使用，例如，制作一个消除重复值的简单方法。

List<Person> getListWithoutDups(List<Person> list) {
    List<Person> newList = new ArrayList<Person>();
    TreeSet<Person> set = new TreeSet<Person>(new PersonComparator()); // use custom Comparator here

    // foreach Person in the list
    for(Person person : list) {
        // if the person isn't already in the set (meaning it's not a duplicate)
        // add it to the set and the new list
        if(!set.contains(person)) {
            set.add(person);
            newList.add(person);
        }
        // otherwise it's a duplicate so we don't do anything
    }

    return newList;
}

contains操作在TreeSet,as the documentation says,"provides guaranteed log(n) time cost".

我上面建议的方法需要 O(n*log(n)) 时间，因为我们对每个列表元素执行 contains 操作，但它还使用 O(n) space 来创建新的列表和 TreeSet。

如果您的列表非常大（space 非常重要）但您的处理速度不是问题，那么您可以删除每个重复项而不是将每个非重复项添加到列表中发现：

 List<Person> getListWithoutDups(List<Person> list) {
    TreeSet<Person> set = new TreeSet<Person>(new PersonComparator()); // use custom Comparator here
    Person person;
    // for every Person in the list
    for(int i = 0; i < list.size(); i++) {
        person = list.get(i);
        // if the person is already in the set (meaning it is a duplicate)
        // remove it from the list
        if(set.contains(person) { 
            list.remove(i);
            i--; // make sure to accommodate for the list shifting after removal
        } 
        // otherwise add it to the set of non-duplicates
        else {
            set.add(person);
        }
    }
    return list;
}

由于列表上的每个 remove 操作需要 O(n) 时间（因为每次删除元素时列表都会移动），并且每个 contains 操作需要 log(n) 时间，这种方法将是 O(n^2 log(n)) 时间。

但是，space 复杂度会减半，因为我们只创建 TreeSet 而不是第二个列表。

Answer 3

我建议不要使用 Comparator 来执行此操作。很难根据其他字段写出合法的compare()方法

我认为更好的解决方案是像这样创建 class PersonWithoutId：

public PersonWithoutId {
  private String firstname, lastname;
  private int age;
  // no id field
  public PersonWithoutId(Person original) { /* copy fields from Person */ }
  @Overrides public boolean equals() { /* compare these 3 fields */ }
  @Overrides public int hashCode() { /* hash these 3 fields */ }
}

然后，给定一个名为 people 的 List<Person>，您可以这样做：

Set<PersonWithoutId> set = new HashSet<>();
for (Iterator<Person> i = people.iterator(); i.hasNext();) 
    if (!set.add(new PersonWithoutId(i.next())))
        i.remove();

编辑

正如其他人在评论中指出的那样，此解决方案并不理想，因为它会创建大量对象供垃圾收集器处理。但是这个解决方案比使用 Comparator 和 TreeSet 的解决方案快多。保持 Set 的顺序需要时间，与原问题无关。我在使用

构造的 Person 的 1,000,000 个实例的 List 上测试了这个

new Person(
    "" + rand.nextInt(500),  // firstname 
    "" + rand.nextInt(500),  // lastname
    rand.nextInt(100),       // age
    rand.nextLong())         // id

并发现此解决方案的速度大约是使用 TreeSet 的解决方案的两倍。（诚然，我使用了 System.nanoTime() 而不是适当的基准测试）。

那么如何在不产生大量不必要对象的情况下有效地做到这一点呢？ Java 并不容易。一种方法是在 Person

中编写两个新方法

boolean equalsIgnoringId(Person other) { ... }

int hashCodeIgnoringId() { ... }

然后编写 Set<Person> 的自定义实现，您基本上可以在其中剪切和粘贴 HashSet 的代码，除了将 equals() 和 hashCode() 替换为 equalsIgnoringId() 和 hashCodeIgnoringId() .

以我的拙见，您可以创建使用 Comparator 的 TreeSet，但不能创建使用自定义版本 equals/ 的 HashSet hashCode 是语言中的一个严重缺陷。

Answer 4

构建 Comparator<Person> to implement your natural-key ordering and then use a binary-search based deduplication. TreeSet 将为您提供开箱即用的能力。

注意 Comparator<T>.compare(a, b) must fulfil 通常的反对称性、传递性、一致性和自反性要求或二分搜索排序将失败。您还应该使其具有空值意识（例如，如果一个、另一个或两者的名字字段为空）。

Person class 的简单自然键比较器如下（它是一个静态成员 class，因为如果每个字段都有访问器，您还没有显示）。

public class Person {
    public static class NkComparator implements Comparator<Person>
    {
        public int compare(Person p1, Person p2)
        {
            if (p1 == null || p2 == null) throw new NullPointerException();
            if (p1 == p2) return 0;
            int i = nullSafeCompareTo(p1.firstname, p2.firstname);
            if (i != 0) return i;
            i = nullSafeCompareTo(p1.lastname, p2.lastname);
            if (i != 0) return i;
            return p1.age - p2.age;
        }
        private static int nullSafeCompareTo(String s1, String s2)
        {
            return (s1 == null)
                    ? (s2 == null) ? 0 : -1
                    : (s2 == null) ? 1 : s1.compareTo(s2);
        }
    }
    private String firstname, lastname;
    private int age;
    private long id;
}

然后您可以使用它来生成唯一列表。使用 add 方法 returns true 当且仅当元素不存在于集合中时：

List<Person> newList = new ArrayList<Person>();
TreeSet<Person> nkIndex = new TreeSet<Person>(new Person.NkComparator());
for (Person p : originalList)
    if (nkIndex.add(p)) newList.add(p); // to generate a unique list

或者交换此行的最后一行以输出重复项

    if (nkIndex.add(p)) newList.add(p);

无论您做什么，在枚举原始列表时都不要使用 remove，这就是这些方法将您的独特元素添加到新列表的原因。

如果您只对独特的列表感兴趣，并希望使用尽可能少的行：

TreeSet<Person> set = new TreeSet<Person>(new Person.NkComparator());
set.addAll(originalList);
List<Person> newList = new ArrayList<Person>(set);

在忽略字段的列表中查找重复项

Finding duplicates in a List ignoring a field

java

list

duplicate-removal