使用预定义规则查找唯一实例的有效方法 (Java)

Question

我正在尝试查找给定实例列表的所有唯一元素。

我有一个匹配算法来确定两个项目是否应该被视为相同

boolean isIdentical(MyItem a, MyItem b) {
//matching algorithm goes here
//return true if a and b are identical with some rules; false otherwise
}

查找所有唯一项的最有效方法是什么？

List<MyItem> findUniqueItems(List<MyItem> allItems) {
}

由于向后兼容，我不能使用 java 8，但必须找到一种更迭代的方法来实现它。

Answer 1

tl;博士

鉴于您被限制在 Java 8 之前的 Java 版本…

在您的 class 上覆盖 equals 和 hashCode，在两者上使用相同的逻辑。

实例化一个Set such as HashSet。

一次添加一个对象，但首先询问集合是否已经包含该对象。如果是这样，你手头有一个副本。

例子

这是一些示例代码。我认为这将在 Java 7 中运行，尽管我今天使用的是 Java 17。

这里我们定义了一个classEmployee，包含三个字段：id(UUID)、name(String)、whenHired(LocalDate)。

当覆盖 equals 和 hashCode 时，我们仅使用 id 字段及其 UUID 值。研究此示例代码中的这两种方法。

package work.basil.comp;

import java.time.LocalDate;
import java.util.UUID;

public final class Employee
{
    private final UUID id;
    private final String name;
    private final LocalDate whenHired;

    public Employee ( UUID id , String name , LocalDate whenHired )
    {
        this.id = id;
        this.name = name;
        this.whenHired = whenHired;
    }

    public UUID id () { return id; }

    public String name () { return name; }

    public LocalDate whenHired () { return whenHired; }

    @Override
    public boolean equals ( Object obj )
    {
        // Match on `id` (UUID) field alone.
        if ( obj == this ) return true;
        if ( obj == null || obj.getClass() != this.getClass() ) return false;
        Employee that = ( Employee ) obj;
        return this.id.equals( that.id );
    }

    @Override
    public int hashCode ()
    {
        // Hash `id` (UUID) field alone.
        return this.id.hashCode();
    }

    @Override
    public String toString ()
    {
        return "Employee[" +
                "id=" + id + ", " +
                "name=" + name + ", " +
                "whenHired=" + whenHired + ']';
    }

}

制作一些示例数据。

Employee alice = new Employee( UUID.fromString( "5228256a-69c5-44d7-8ff5-40703f1b6491" ) , "Alice" , LocalDate.of( 2010 , Month.MARCH , 15 ) );
Employee bob = new Employee( UUID.fromString( "0ee605a2-24bf-4e35-ab68-54007c472717" ) , "Bob" , LocalDate.of( 2021 , Month.JANUARY , 23 ) );
Employee bobby = new Employee( UUID.fromString( "0ee605a2-24bf-4e35-ab68-54007c472717" ) , "Bobby" , LocalDate.of( 2021 , Month.JANUARY , 23 ) );
Employee carol = new Employee( UUID.fromString( "4b63c9ef-4921-46ff-a43a-60741bedf9a3" ) , "Carol" , LocalDate.of( 2019 , Month.DECEMBER , 1 ) );
List < Employee > inputs = new ArrayList <>();
inputs.add( alice );
inputs.add( bob );
inputs.add( bobby );
inputs.add( carol );

创建一个空的 Set 来放置我们的 Employee 对象。一组定义禁止重复。我们可以询问集合是否包含特定对象。将调用对象的 equals 方法来确定“包含”查询的答案。在 HashSet 中，对象的 hashCode 方法将作为集合上存储和检索操作的一部分被调用。

Set < Employee > employees = new HashSet <>();

循环我们的输入（Employee 个对象）。对于每一个，询问它是否已经包含在我们的集合中。如果是这样，我们有一个副本。如果没有，请添加。

for ( Employee input : inputs )
{
    if ( employees.contains( input ) )
    {
        System.out.println( "duplicate = " + input );
    } else
    {
        employees.add( input );
    }
}

当运行.

duplicate = Employee[id=0ee605a2-24bf-4e35-ab68-54007c472717, name=Bobby, whenHired=2021-01-23]

如果您不关心哪些项目是重复的，只想丢弃它们，请将 for 循环替换为一行，调用 Set#addAll:

Set < Employee > employees = new HashSet <>();
employees.addAll( inputs );  // Any duplicates are ignored. A `Set` is distinct by definition.

Answer 2

这个：

List<MyItem> findUniqueItems(List<MyItem> allItems) {
  List<MyItem> list = new ArrayList<>();
  LinkedHashSet<MyItem> hashSet = new LinkedHashSet<>();
  for(MyItem m: allItems){
      if (hashSet.add(m)) list.add(m);
  }
  return list;
}

或者将 hashSet 包装在 LinkedHashList 中。当然你必须实现equals和hashCode。

使用预定义规则查找唯一实例的有效方法 (Java)

Efficient way to find unique instances with pre-defined rules (Java)

java

algorithm

unique

tl;博士

例子